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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s