How to construct common classical gates with CNOT circuit?

Question

How can I construct AND, OR, NAND, NOR with CNOT gates.

First off, this other question describes how to make them with matrices.

Theoretically I can construct all those gates already. I know how to construct all of them from the TOFFOLI gate, which itself I can construct based on CNOT gates.

However, the TOFFOLI gate requires 6 CNOT gates, which seems like more than I should need for those simple gates. Do I really need that many gates?

Also, what thought process could I use to come up with those gates, without requiring the TOFFOLI construction?

Answer 1

Note that all these gates are not reversible. As such, it is not possible to implement these "in place". However, you can using the well-known scheme: $$|x\rangle|y\rangle\to|x\rangle|y\oplus f(x)\rangle$$

AND Gate

By definition, the Toffoli gate is exactly the one you're looking for. So, you can't use less than 6 CNOT to implement it exactly. Note that there are some decomposition which use only 3 CNOT at the cost of a relative phase. Thus, if you plan on uncomputing this gate at some point, you can afford only using 3 CNOTs.

NAND Gate

It is quite easy to implement an AND Gate from a NAND one: simply apply an $X$ gate on the output. Since the optimal decomposition of the AND Gate is known (it's simply a Toffoli), it's not possible to do better for implementing the NAND Gate.

OR Gate

Once again, it's quite easy to implement an AND Gate from an OR one: simply apply $X$ gates on the controls qubits before and after the OR Gate. As such, this not only shows that you can't implement an OR gate using less than 6 CNOTs, it also gives you the optimal decomposition.

NOR Gate

Finally, you ca implement an OR gate from a NOR one by applying an $X$ gate on the target qubit. This also implies that this gate cannot be implemented using less than 6 CNOTs.

Conclusion

Since all these gates can be built from one to another without using additional CNOTs, their optimal decomposition in terms of CNOTs gates is the same. Since we happen to know that the optimal decomposition for the Toffoli gate uses 6 CNOTs, you cannot find an implementation that uses less than 6 CNOTs, as long as you want to implement them perfectly. You can use as less as 3 CNOTs if you allow relative phases though, which is still a 2x improvement.

Answer 2

Lets first have a look how CNOT works. It changes computational basis states in the following way:

• $|00\rangle \rightarrow |00\rangle$
• $|01\rangle \rightarrow |01\rangle$
• $|10\rangle \rightarrow |11\rangle$
• $|11\rangle \rightarrow |10\rangle$

As you can see, the first qubit (control) is left unchnaged. The second qubit is in state $|1\rangle$ provided control and target qubits are in different states, otherwise it is in state $|0\rangle$. This means that if input states are the basis ones, CNOT gate's second output is effectively XOR of control and target qubits.

Since XOR is not universal gate for classcial computing, it cannot be used for realization of AND, OR and NOT gates which conversely form a set of universal classical gates. To implement these logical functions, you have to use Toffoli gate which returns result of NAND applied on both control qubits provided that the target qubit is in state $|1\rangle$ before application of the Toffoli. Since NAND is universal for classical computing, this construction allows you to implement AND, OR and NOT, and any other Boolean function, on a quantum computer.