This is one in a series of posts working through the exercises in the Quantum Country online introduction to quantum computing and related topics. The exercises in the original document are not numbered; I have added my own numbers for convenience in referring to them.

Exercise 14. Describe a quantum circuit that can compute the NAND gate, where the NAND of two bits and is the NOT of .

Answer: The Toffoli gate with inputs , , and produces the outputs , , and . It thus functions as an AND gate.

One way to produce a NAND gate is thus to put the target output through the X gate, which will NOT the value.

A second, and simpler, way is to use the input value as the target qubit to the Toffoli gate. This will produce the target output . When then we have , and when we have . Thus is equivalent to .

Therefore a Toffoli gate with inputs , , and acts as a NAND gate producing the target output .