9.3 Building blocks and universality
In section 2.4, we discussed classical gates, and I illustrated how to create an or gate from nand gates. nand is universal because we can make all the other classical logic gates from it. For example, nand`gate-style gate$nand`gate-style
We could construct any software we code for classical computers from millions of nand gates, but it would be horribly inefficient. There are higher-level gates and circuits in modern processors that are tremendously faster.
The basic CNOT acts like a xor on the standard kets. xor`gate-style gate$xor`gate-style
This maps the basis kets in this way:
The xor result is the final qubit state of q1. More than simply a logic operation, this implements addition mod 2. That is, this standard gate does a basic arithmetic operation “⊕”. For example, |1⟩ ⊕ |1⟩ = |0⟩ and |1⟩ ⊕ |0⟩ = |1⟩...
