How do you implement the Toffoli gate using only single-qubit and CNOT gates?

Question

I've been reading through "Quantum Computing: A Gentle Introduction", and I've been struggling with this particular problem. How would you create the circuit diagram, and what kind of reasoning would lead you to it?

Answer 1

is the decomposition (I took this from google images, originally on this website.)

In order to understand how to decompose it, we can look at it's base structure. The idea is that we combine gates that cancel out, but put CNOT gates in between such that if the specific NOT is executed, the gates don't cancel. This is how generic controlled-U gates are implemented for arbitrary U. as explained in Quantum Computation and Quantum Information by Nielsen and Chuang.

For a simpler example, imagine you have a gate U and you want to make a controlled-U from it, with just one control. To do so you find single qubit gates A, B, C such that CBA = I, but CXBXA = U. By putting a CNOT where every X gate must be applied, you have created a control-U gate. Similar logic applies in the CC-U case, except you need EDCBA = EXDCXBA = EDXCBXA = I up to a phase, and EXDXCXBXA = U. Where the first and third X corresponds to a CNOT from one control, and the second and fourth are from the other.

Essentially the intuition for this structure is that you want the have the bottom line cancel out if either control is zero, and to be your desired unitary if they both apply the not gates.

For additional reading check out pages 181-183 in Nielsen and Chuang. [EDIT: The link @Norbert Schuch posted also contains the same info, and you don't need to track down a textbook.]

Answer 2

You also have this one with V the square root of NOT gate:

If you have as control qubits :

(0,0) : do nothing; (0,1) : apply V and its conjugate which is identity; (1,0) : same but inversed; (1,1) : apply V twice which correspond to your NOT gate.