Though this article does not describe a full-blown nand2tetris project, it is inspired by the course. In it, you learn how to build all possible logic gates exclusively out of NAND gates. And while you are encouraged to use your growing library of logic gates to in turn build more and more complex logic gates, even the most complex logic gates are fundamentally nothing more than large collections of NAND gates.
The point of this article is that you can build quantum logic gates in a similar manner. There may definitely be better ways — the AND gate is a perfect example — but you can still build your algorithms even if you don’t know those better ways. For example, if you don’t know the best way to implement a quantum OR gate — there definitely is one — you can still build the OR gate functionality that you need.
This article assumes that that you, the reader, are familiar with logic gates.
The Hadamard gates allow for all possible input combinations: 00, 01, 10, and 11. The NAND gate is simply an AND gate (Toffoli gate) with it’s output negated (reversed).
The resultant histogram is a truth table for a NAND logic gate: if both inputs are 1, the output is 0; for all other input combinations, the output is 1.
The NOT gate takes only one input, but a NAND gate takes two inputs. Therefore, both NAND inputs must be the same. The CNOT gate solves this be causing the second input to be the same as the first input.
If the input is 1, the output is 0. If the input is 0, the output is 1.
This is obviously horribly inefficient considering you could simply use one Toffoli gate, but I’m nonetheless continuing with the theme of constructing logic gates exclusively out of NAND gates.
If both inputs are 1, the output is 1; for all other input combinations, the output is 0.
Though not as simply as the AND gate, the OR gate can nonetheless also be greatly simplified. However, if you don’t know how to build the simpler version of the OR gate, you can still construct one exclusively out of NAND gates.
This is an unusual histogram, because you only see the inputs as either 00 or 11, even though the truth table for the OR gate shows you the 01 and 10 combinations, as well. However, the output probabilities are correct: 75% of the input combinations result in an output of 1 and 25% of the input combinations result in an output of 0.
The eXclusive-OR is as far as I’ll go in this article, because you can see these logic gates increasing in complexity. It is easy to see that I should quickly run out of qubits if I continued much further.
If the inputs are either both 0 or both 1, the output is 0. If the inputs are a 0 and a 1, in either order, the output is a 1.
In the nand2tetris course, you build far more complex logic gates. However, as I stated at the very beginning of this article, they are all fundamentally built out of nothing more than NAND gates. Therefore, given enough qubits, you should be able to perform any logic operation on a quantum processor that you might otherwise do with classical logic gates.
And, though there may be better ways to construct those quantum logic gates, that shouldn’t stop you from at least building the functionality you need. Between your NAND-based circuit and a quantum processor’s transpiled circuit, hopefully you can find a way to optimize the total number of qubits and gates required.