1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ +1 thanks... $ $ $\endgroup$ – draks ... Apr 10 at 17:32
  • $\begingroup$ 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... $\endgroup$ – draks ... Apr 16 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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