Any two level flip in $n$ qubit system

Question

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...

Answer 1

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).