In classical digital computers, we know that
it is possible to implement any logic operation by using a combination of NOT gates on a single
bit and negative-AND gates on pairs of bits. A similar situation exists in quantum computing
but with a very important difference. Not all the classical logic gates are allowed in the quantum world. This is because quantum mechanics imposes very stringent requirements. A quantum system can never lose information over time and it must always be possible to reconstruct the past. Let’s take the example of the AND logic operation. It takes two inputs and gives one output with the value one if and only if both inputs are one. Obviously, I have no way to tell what the two input bits were just by looking at the one bit output. So let’s say that I let one of the inputs propagate and change to the output. Even with these two bits of information at the output there is still an ambiguity that prevents me from reconstructing the past. The output 00 could arise from inputs 00 or 01. In the quantum world, this would not be allowed. So let me show you a logic gate that is allowed in the quantum world. We call it CNOT gate which stands for Controlled-Not. It applies a NOT operation to qubit B when qubit A is in state one. If qubit A is 0, qubit B is left unchanged.
If qubit A is 1, qubit B gets flipped. Now you see that there is no ambiguity. There are four different possible outputs, each corresponding to four different inputs which I can reconstruct knowing the outputs. No information is lost. If the qubits are physically implemented with spins, creating a CNOT gate is very simple. The frequency at which Spin B responds to an electromagnetic field depends on the state of Spin A in its vicinity because Spin A produces a magnetic field that depends on its orientation. Therefore, Spin A controls whether I can flip Spin B. The CNOT gate can be used to produce an entangled state of A and B. We just have to prepare A in the super position of 0 and 1 and then apply a CNOT to B, together with arbitrary single qubit rotations, the CNOT gate can implement any logic function on a quantum computer. So we are starting to see what it takes to build a quantum computer. We need individual qubits that we can rotate in arbitrary directions and we need interactions between pairs of qubits that implement CNOT gates.