Quantum NAND gate

Question

Wondering how a quantum NAND gate would be implemented, and if it would be considered universal. I saw for quantum computing the Hadamard, phase, CNOT and π/8 gates are universal, but didn't see NAND in there. Wondering why it's not universal in quantum computing, and if/how you can construct a quantum NAND gate.

Answer 1

The trick is, unlike classical gates, quantum gates have to be reversible (aka invertible). In other words, for every possible output, there must be one and only one possible input producing that output.

This means the classical NAND gate can't possibly work in quantum computing: there are more inputs than outputs, so by the pigeonhole principle there must be some inputs that map to the same output. In particular, the inputs $(1,0)$, $(0,1)$, and $(0,0)$ all produce the output $1$.

So first, let's focus on reversible classical computing: we force all gates to be reversible, but don't worry about qubits yet. By the pigeonhole principle, we see that each gate must have at least as many output bits as it has input bits.

For one input bit and one output bit, there are only two reversible gates: ID (return the input unchanged) and NOT (return the opposite of the input). Neither of these are universal, as we can't build a NAND out of them.

For two input bits and two output bits, there are a few different trivial gates (such as "return both inputs unchanged", "return the first one unchanged and flip the second one", etc). But the most interesting one is CNOT, defined something like this:

$$CNOT(x, y) = (x, x \oplus y)$$

In other words, it flips $y$ if $x$ is true, and also outputs $x$ unchanged. Now we have an equivalent to XOR! But unfortunately, this still isn't universal: you can't build NAND out of CNOT, just like you can't build NAND out of XOR. (The proof works the same way, too.)

Well, what about three inputs and three outputs? Once we've got three bits to work with, we can build CCNOT, which works like this:

$$CCNOT(x, y, z) = (x, y, (x \wedge y) \oplus z)$$

And using this, you can build a reversible NAND!

$$NAND(x, y) = CCNOT(x, y, 1)$$

So it turns out that CCNOT is indeed universal, for reversible classical computation. It's better-known as the Toffoli gate, after its discoverer. But you could certainly think of it as "reversible NAND".

But once we bring in quantum computing, things get more complicated. CCNOT can implement all classical computations, but it can never create superpositions: you need something like a Hadamard gate for that. It turns out no single gate can ever be universal for quantum computing. So while "reversible NAND" is an important part of quantum computing, it can't stand alone: you need other operators too.

Answer 2

The NAND gate is not reversible, you can't recover its inputs using its outputs, so it's not a well defined quantum gate. Or, at the very least, it must contain some sort of internal measurement mechanism that would cause decoherence. This would prevent it from being universal for quantum computation.

A simple way to fix the reversibility problem is to have the gate work like a Toffoli. Instead of having two inputs a, b and producing one output a nand b, have three inputs a, b, c and toggle c based on a nand b thus producing the output a, b, c xor (a nand c). This gate is just a minor variation on the Toffoli gate, so it has the same universality properties as the Toffoli. It is universal for classical reversible computation, but not universal for quantum computation unless you add some sort of superposing gate such as the Hadamard.