Any two level flip in $n$ qubit system

Let start with a multi controlled Toffoli gate. Looking at the matrix representation (in the binary base), you easily see $$\pmatrix{ 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0& 0& 1& 0\\ }$$ that it only switches two states: $$|111\rangle$$ and $$|110\rangle$$. Conjugating with some $$X$$ gates on qubit 1 and 2 gives three more pair switches. Similar for the Fredkin gate which switches $$|110\rangle$$ and $$|101\rangle$$.

1. How to generate any of the $$8\cdot 7$$ possible two level switches for three qubits out of elementary gates?

2. And how for general $$n$$?

For the three qubit case, I tried to e.g. construct a switch of $$|000\rangle \leftrightarrow |111\rangle$$ by mapping $$|110\rangle \mapsto |000\rangle$$. To achieve that I conjugated the Toffoli with the following sub circuit: two CNOTs conjugated by some $$X$$.

It worked! I could even construct a switch of $$|000\rangle \leftrightarrow |011\rangle$$ by extending the above subcircuit (with another Toffoli) the maps $$|111\rangle \mapsto |011\rangle$$.

But I'm not sure whether this approach is valid or if I had just a lucky punch...

Conjugate by CNOTs to reduce to a case where the two states differ by exactly one bit, and conjugate by NOTs to make all the controls look for 1s instead of 0s.

1. Find a bit position t where the two states disagree about a bit. Let s be the state where the bit at t is 0.

2. For each bit position p other than t where the bit is 0 in s, apply a NOT to qubit p.

3. For each bit position p other than t where the two states disagree about a bit, apply a CNOT from qubit t to qubit p.

4. Apply a CCC...CNOT targeting qubit t controlled by all other qubits.

5. Do the same thing as in step (3).

6. Do the same thing as in step (2).

• +1 thanks...  – draks ... Apr 10 at 17:32
• How would that approach extend if a replace the $X=\pmatrix{0&1\\1&0}$ in the lower right (a two level swap) by a three cycle, e.g. $\pmatrix{1_n&0&0&0\\0&0&0&1\\0&1&0&0\\0&0&1&0}$..? The question would then be to create a generic three level swap... – draks ... Apr 16 at 11:00