The Square Root of NOT
Conventional computers are built out of Boolean logic gates, notably those that implement the logic functions AND, OR and NOT. What are the corresponding primitive elements of a quantum computer? These building blocks too can be conceived as logic gates, but they operate on a very different kind of logic, in which probabilities play a crucial role. What follows is a sketch of the ideas underlying the construction of quantum logic gates. It is based on a lucid expository article by Gilles Brassard of the Université de Montreal (9) and on a talk that Shor delivered in March at the University of Maryland Baltimore County.
The simplest classical Boolean device is the NOT gate, which accepts a single bit of input and produces a single bit of output; the action of the gate is to negate or invert the input. In other words, if the input is a 0, the output is a 1; if the input is a 1, the output is a 0. Two NOT gates connected in series restore the input to its original state: An initial 0 is changed to a 1 by the first gate and then changed back to a 0 by the second gate. Thus a double negative is equivalent to the identity function.
The NOT gate is wholly deterministic: Once the input is known, the output is determined with absolute certainty. Suppose we relax this standard of determinism somewhat, creating a probabilistic logic gate that usually inverts its input—say 90 percent of the time—but occasionally passes the input through unchanged. This transformation can be represented by a probability matrix, as follows:
Here the numbers along the left edge, labeling the rows of the matrix, are the inputs to the gate, and the column labels at the top are the outputs. To find the probability that an input of 0 produces an output of 1, you read along the 0 row to where it intersects the 1 column. Note that even though the entries in the matrix are fractional values, this "probably NOT" gate is still a binary device whose inputs and outputs are always either 0 or 1. Also note that the probabilities in each column and each row sum to 1, indicating that every possible combination of input and output has been accounted for.
The operation of the simple deterministic NOT gate can be represented in the same matrix notation. Here is the transformation matrix:
In this case the probability of getting a 0 output from a 0 input is 0 (it will never happen) whereas the probability of transforming a 0 into a 1 is 1 (certainty).
At the opposite pole from a completely deterministic logic gate is one that completely randomizes its input, producing a 0 or 1 output with equal probability. The transformation matrix for this function is:
In effect, the gate models a fair coin flip, and so it is designated CF. (A gate of this kind may seem totally useless, but in fact randomness is an important resource in certain algorithms.)