## Quantum Country exercise 14

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 $x$ and $y$ is the NOT of $x \wedge y$.

Answer: The Toffoli gate with inputs $\vert x \rangle$, $\vert y \rangle$, and $\vert 0 \rangle$ produces the outputs $\vert x \rangle$, $\vert y \rangle$, and $\vert 0 \oplus \left( x \wedge y \right) \rangle = \vert x \wedge y \rangle$. It thus functions as an AND gate.

One way to produce a NAND gate is thus to put the target output $\vert x \wedge y \rangle$ through the X gate, which will NOT the value.

A second, and simpler, way is to use the input value $\vert 1 \rangle$ as the target qubit $\vert z \rangle$ to the Toffoli gate. This will produce the target output $\vert 1 \oplus \left( x \wedge y \right) \rangle$. When $x \wedge y = 0$ then we have $1 \oplus 0 = 1$, and when $x \wedge y = 1$ we have $1 \oplus 1 = 0$. Thus $1 \oplus \left( x \wedge y \right)$ is equivalent to $\neg \left( x \wedge y \right)$.

Therefore a Toffoli gate with inputs $\vert x \rangle$, $\vert y \rangle$, and $\vert 1 \rangle$ acts as a NAND gate producing the target output $\vert \neg \left( x \wedge y \right) \rangle$.

This entry was posted in quantum country. Bookmark the permalink.