The Square Root of NOT
Quantum Logic Gates
Both the ordinary Boolean NOT gate and the probabilistic versions of it are still constructions of classical physics. A quantum-mechanical gate is far stranger. The strangeness goes to the very root of the quantum-computational process, to the bits themselves, which to emphasize their unconventional nature are sometimes called qubits. Whereas classical bits have the value 0 or 1 at all moments, qubits can occupy a "superposition" of the 0 and 1 states during certain stages of a computation. This is not to say that the qubit has some intermediate value between 0 and 1. Rather, the qubit is in both the 0 state and the 1 state at the same time, to varying extents. When the state of the qubit is eventually observed or measured, it is invariably either 0 or 1.
Quantum states and their superpositions are represented by means of a notational device called a ket, written "|." The state of a qubit is given as a|0 + ß|1, where the coefficients a and ß are the "amplitudes" of each state. In general the amplitudes are complex numbers (with both a real and an imaginary part), but the examples considered here will be confined to positive and negative real numbers. The amplitude associated with a state determines the probability that the qubit will be found in that state; specifically, the probability is equal to the square of the absolute value of the corresponding amplitude.
The relation between amplitude and probability can be made clearer with an example. A quantum gate that Brassard designates QCF (for "quantum coin flip") has the following matrix of amplitudes:
To find the probability of each of these transitions, take the absolute value of the corresponding amplitude and square it: |1/v2|2 is equal to 1/2, and so is |-1/v2|2. Thus all the entries in the probability matrix are 1/2, and the quantum-mechanical QCF gate appears on first examination to be identical to the classical CF gate. Either a 0 or a 1 signal passing through the QCF gate has an equal chance of coming out a 0 or a 1.
Under the surface, however, the CF and QCF gates are not at all alike. A way to see the difference is to link two gates in series. As noted above, two NOT gates in sequence compose the identity function. Two CF gates are also easy to analyze. Whatever the value of the initial input, the first CF gate produces a 0 or a 1 at random, and the second gate randomizes this value again. Hence any number of CF gates in sequence are equivalent in function to a single CF gate.
Two QCF gates in series work very differently. In a quantum-mechanical system it is not possible to assign a definite value to the unobserved intermediate signal between the two gates. The output of the first QCF gate is not a 0 or a 1 but a superposition of |0 and |1 states. Specifically, if the input to the first gate is a 1, the output of that gate is the superposition 1/v2|0 + 1/v2|1, as indicated by the matrix of amplitudes. Now this superposition of states becomes the input to the second QCF gate, which acts on it according to the same amplitude matrix. The 0 part of the superposition gets transformed into 1/v2(1/v2|0 - 1/v2|1), while the 1 part becomes 1/v2(1/v2|0 + 1/v2|1). Thus the entire state of the system becomes
1/v2(1/v2|0 - 1/v2|1) + 1/v2(1/v2|0 + 1/v2|1)
Multiplying out the various factors of 1/v2 yields 1/2(|0 - |1 + |0 + |1); now the +|1 and -|1 components cancel, leaving 1/2(|0 + |0), or simply |0. A similar analysis shows that when the input to the first gate is a 0, the output observed at the second gate is a 1. The two gates implement the NOT function: (QCF)2 = NOT. Accordingly, a single QCF gate is said to calculate "the square root of NOT."
There is something decidedly counterintuitive about these results. Passing a signal through one QCF gate randomizes it, yet putting two QCF gates in a row yields a deterministic result. It is as if we had invented a machine that first scrambles eggs and then unscrambles them. There is no analogue of this machine in the more familiar world of classical physics.
The source of these odd effects is the phenomenon of quantum interference. The superposition of states can be thought of as a superposition of waves, which either reinforce or cancel depending on their amplitude and phase. Just as two coherent light sources combine to produce a pattern of light and dark "fringes," two quantum states interfere either constructively or destructively according to the sign of their amplitudes.
Consider again what happens when two CF gates or two QCF gates are wired in series. In the classical case, there are four possible sequences of events, which can be imagined as paths through the branches of a tree. Suppose the initial state, at the root of the tree, is a 1, and the first CF gate happens to produce a 0; the probability of this event is 1/2. Now if the second CF gate also emits a 0, again with probability 1/2, the overall probability of the entire 1 0 0 path is 1/2 X 1/2, or 1/4. The other three paths, 1 0 1, 1 1 0 and 1 1 1, have the same probability of 1/4. Since two paths yield a 0 as the final state and two paths end in a 1, each of these outcomes has probability 1/2.
For QCF gates the analysis is framed in terms of amplitudes instead of probabilities. The first QCF gate transforms the initial |1 state into a |0 state with an amplitude of 1/v2, then the second QCF gate produces a final |0 state with a further amplitude of 1/v2. Multiplying these component amplitudes (just as one would multiply probabilities) yields an overall amplitude of 1/2 for the computational path |1 |0 |0. The amplitude is the same for the paths |1 |1 |0 and |1 |1 |1. In the case of the path |1 |0 |1, however, the result is different; because the transition from |0 to |1 has an amplitude of -1/v2, the total amplitude for this path is -1/2. In the absence of interference, this change of sign would still have no effect on the outcome of an experiment: Squaring the absolute value of each amplitude would yield four path probabilities of 1/4, which would sum to a probability of 1/2 for the |0 final state and 1/2 for the |1 final state. Because of interference, however, the two paths leading to the |1 state, with amplitudes of 1/2 and -1/2, cancel each other out, whereas the |0 paths, both with amplitudes of 1/2, sum to yield a total amplitude (and also a total probability) of 1.