Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
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?
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.
