# How to build a CNOT out of universal CCNOT gates?

By the classic theory of computation, every classic gate can be build with NAND operation, for example XOR ("the classic CNOT") is build by net of NANDs, I saw that the quantum analogue for NAND can be build with CCNOT gate (Toffoli gate) and that is indeed a universal gate.

My question\request is can you please draw me a quantum circuit that express CNOT using universal CCNOT gate?

• Why not set one of the control bits to $\vert 1\rangle$ and never touch it again? Nov 3 '19 at 12:34
• Note: The Toffoli is universal for reversible classical computation; it is not universal by itself for quantum computation. There are individual two-qubit gates that are universal, but ultimately you have to understand the dense approximation concept as part of what "universal" means in the quantum case. Nov 3 '19 at 20:48

CNOT is a Boolean function $$f:\{0,1\}^2\to\{0,1\}^2$$ that eats two input bits and spits two output bits. As Wikipedia explains, Toffoli gates require some ancillary (extra) qubits to do emulate any Boolean function. In this case, just one extra qubit will do the job. As MarkS mentioned in the comments, set one of the control qubits of the Toffoli gate to $$|1\rangle$$ (that is now your ancilla qubit), and you're done.

The circuit will be no different than any ordinary circuit diagram of a Toffoli. You can play with it yourself on Quirk (the top qubit is the ancilla).

If you're wondering why this method works, have a look at the truth table of the Toffoli. Note that if the first bit is set at 1, the reduced truth table for the other two bits will basically match the CNOT's table.

CNOT is more simple gate than Toffoli (CCNOT). Actually, CCNOT is realized with six CNOT gates (see Wikipedia link above for a CCNOT circuit). Additionally, CNOT is relized physically on a quantum computer. To sum up, direct usage of CNOT is better because it enable the quantum circuit to be more simple.

• Hi Martin! Take note that in order to realize a CCNOT gate with 6 CNOT gates, you will also need a number of single qubit gates Nov 6 '19 at 0:53
• Thanks for pointing that out. I wanted mainly emphasize that there is no point in implementing single CNOT with six CNOTs. And of course, you need some T and its hermitian conjugate gates as well. Nov 6 '19 at 5:46