I'm struggling to find an analytic way to solve this problem.

There are $4! = 24$ possible classical operations on the four 2-Cbit basis states. How many of these are achievable via the classical operations $S_{ij}, C_{ij}, X_j$ and compositions thereof.

I've thought about this in terms of permutation groups and counting the members of each class of these operations, but I am not getting anywhere.

Edit: C-Bits refer to classical bits (binary states) $S_{ij}$ is the swap operation between bits $0$ and $1$. $C_{ij}$ is the control not operation with control $i$ and target $j$. $X_j$ is the not operation with target $j$.

  • $\begingroup$ What are Cbits, $S_{ij}$, $C_{ij}$ and $X_j$? $\endgroup$
    – Rammus
    Commented Sep 15, 2020 at 15:03

1 Answer 1


Why is 4! valid?

We can imagine the desired operation to implement as a truth table / permutation matrix. Recognize that we may do this because none of the operations actually modify the amplitudes - they solely switch the amplitudes among basis states. Plus, because the operations provided are unitary, we know that a permutation table is valid. Let's call this permutation function $f(x)$.

So, given the inputs of 00, 01, 10, 11, there are 4! potential outputs, depending on which output corresponds to which input (e.g plugging 00 into our operation could yield 00/01/10/11, $f(01)$ could yield all except $f(00)$.)


Now, which of these operations are actually implementable given the desired gate set? Recognize that each of the operations is also a permutation table:

  • Swap: interchanges the amplitudes of 01, 10
  • CNOT: interchanges the amplitudes of 10, 11 or 01, 11
  • X: interchanges the amplitudes of 00, 10 and 11, 01 or 00, 01 and 10, 11

So, let's first find sub operations that allow us to selectively swap any two amplitudes. Note that we are seeking $4C2 = 6$ such operations, and we already have 3 of them ($SWAP$, $CNOT01$, $CNOT10$). This leaves us with 3 two amplitude swaps: $(00, 01)$, $(00, 10)$, and $(00, 11)$.

  • $(00, 01)$: $X_0 CNOT_{0, 1} X_0$.
  • $(00, 10)$: $X_1 CNOT_{1, 0} X_1$
  • $(00, 11)$: Because every other 2-amplitude swap is implementable, we know that $(00, 11)$ is also implementable.

So, we know that all 2-amplitude swaps are possible with the given gates. Furthermore, we can split the permutation tables into four classes based on derangement (how many of the inputs are preserved):

  • 4 inputs invariant ($1$)
  • 2 inputs invariant ($4C2 * !2 = 6$)
  • 1 input invariant ($4C1 * !3 = 8$)
  • 0 inputs invariant ($!4 = 9$)

(Note that three invariant inputs is not possible; we always need at least one amplitude to swap with).

  • The first case is trivial, and satisfiable with an identity function.
  • We just proved the second case.
  • The third/fourth cases are provable by way of the second case.

I'm not as familiar with the combinatorics references here, so feel free to add more vernacular. The core idea is still the same: because we can tune our gate set to selectively affect only two amplitudes, we are able to produce any permutation matrix.

  • 1
    $\begingroup$ What is meant by the notation $!n$. I've never seen that before $\endgroup$
    – camble
    Commented Sep 15, 2020 at 17:28
  • $\begingroup$ Ah, no worries! I learned it too today. That's the notation for a derangement - a permutation where no elements share their original spot (e.g. 1, 2, 3, 4 -> 2, 3, 4, 1, but not 1, 3, 2, 4) $\endgroup$
    – C. Kang
    Commented Sep 15, 2020 at 19:11
  • $\begingroup$ Interesting! Thanks for this, I never thought I'd be learning about permutation groups through quantum computing. $\endgroup$
    – camble
    Commented Sep 15, 2020 at 19:36
  • $\begingroup$ It's a fascinating question, and I think there must be a component of functional completeness in this. If someone can find a cleaner proof, I would love to see it :D $\endgroup$
    – C. Kang
    Commented Sep 15, 2020 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.