Next: Example: A One-Bit Up: Quantum Search Methods Previous: Quantum Search Methods

## An Overview of Quantum Computers

The basic distinguishing feature of a quantum computer [2, 4, 11, 12, 18, 19, 29, 31, 35, 48, 51] is its ability to operate simultaneously on a collection of classical states, thus potentially performing many operations in the time a classical computer would do just one. Alternatively, this quantum parallelism can be viewed as a large parallel computer requiring no more hardware than that needed for a single processor. On the other hand, the range of allowable operations is rather limited.

To describe this more concretely, we adopt the conventional ket notation from quantum mechanics [13, section 6,] to denote various states. That is, we use to denote the state of a computer described by . At a low level of description, the state of a classical computer is described by values of its bits. So for instance if it has n bits, then there are possible states for the machine, which can be associated with the numbers . We then say the computer is in state when the values of its bits correspond to the number . More commonly, a computer is described in terms of higher level constructs formed from groups of bits, such as integers, character strings, sets and addresses of variables in a program. For example, a state that could arise during a search is corresponding to a set of assignments for variables in a CSP and a value of false for the program variable soln, e.g., used to represent whether a solution has been found. In these higher level descriptions, there will often be aspects of the computer's state, e.g., stack pointers or values for various iteration counters, that are not explicitly mentioned.

The states presented so far, where each bit or higher-level construct has a definite value, apply both to classical and quantum computers. However, quantum computers have a far richer set of possible states. Specifically, if are the possible states for a classical computer, the possible states of the corresponding quantum computer are all linear superpositions of these states, i.e., states of the form where is a complex number called the amplitude associated with the state . The physical interpretation of the amplitudes comes from the measurement process. When a measurement is made on the quantum computer in state , e.g., to determine the result of the computation represented by a particular configuration of the bits in a register, one of the possible classical states is obtained. Specifically, the classical state is obtained with probability . Furthermore, the measurement process changes the state of the computer to exactly match the result. That is, the measurement is said to collapse the original superposition to the new superposition consisting of the single classical state (i.e., the amplitude of the returned state is 1 and all other amplitudes are zero). This means repeated measurements will always return the same result.

An important consequence of this interpretation results from the fact that probabilities must sum to one. Thus the amplitudes of any superposition of states must satisfy the normalization condition

Another consequence is that the full state of a quantum computer, i.e., the superposition, is not itself an observable quantity. Nevertheless, by changing the amplitude associated with different classical states, operations on the superposition can affect the probability with which various states are observed. This possibility is crucial for exploiting quantum computation, and makes it potentially more powerful than probabilistic classical machines, in which some choices in the program are made randomly.

These superpositions can also be viewed as vectors in a space whose basis is the individual classical states and is the component of the vector along the i basis element of the space. Such a state vector can also be specified by its components as when the basis is understood from context. The inner product of two such vectors is where denotes the complex conjugate of . In matrix notation, this can also be written as where is treated as a column vector and is a row vector given by the transpose of with all entries changed to their complex conjugate values. For these vectors, the normalization condition amounts to requiring that .

To complete this overview of quantum computers, it remains to describe how superpositions can be used within a program. In addition to the measurement process described above, there are two types of operations that can be performed on a superposition of states. The first type is to run classical programs on the machine, and the second allows for creating and manipulating the amplitudes of a superposition. In both these cases, the key property of the superposition is its linearity: an operation on a superposition of states gives the superposition of that operation acting on each of those states individually. As described below, this property, combined with the normalization condition, greatly limits the range of physically realizable operations.

In the first case, a quantum computer can perform a classical program provided it is reversible, i.e., the final state contains enough information to recover the initial state. One way to achieve this is to retain the initial input as part of the output. To illustrate the linearity of operations, consider some reversible classical computation on these states, e.g., which produces a new state from a given input one. When applied to a superposition of states, the result is . Why is reversibility required? Suppose the procedure f is not reversible, i.e., it maps at least two distinct states to the same result. For example, suppose . Then for the superposition linearity requires that giving , a superposition that violates the normalization condition. Thus this irreversible classical operation is not physically realizable on a superposition, i.e., it cannot be used with quantum parallelism.

In contrast to this use of computations on individual states, the second type of operation modifies the amplitude of various states within a superposition. That is, starting from the operation, denoted by U, creates a new superposition . Because the operations are linear with respect to superpositions, the new amplitudes can be expressed in terms of the original ones by , or in matrix notation by . That is, linearity means that an operation changing the amplitudes can be represented as a matrix. To satisfy the normalization condition, Eq. 2, this matrix must be such that . In terms of the matrix U this condition becomes

which must hold for any initial state vector with . To see what this implies about the matrix , suppose is the j unit vector, corresponding to the superposition where all amplitudes are zero except for . In this case which must equal one by Eq. 3. That is, the diagonal elements of must all be equal to one. For with ,

This must equal one by Eq. 3, and we already know that the diagonal terms equal one. Thus we conclude . A similar argument using , a superposition with an imaginary value for the second amplitude, gives . Together these conditions mean that A is the identity matrix, so , i.e., the matrix U must be unitary to operate on superpositions. Moreover, this condition is sufficient to make any initial state satisfy Eq. 3. This shows how the restriction to linear unitary operations arises directly from the linearity of quantum mechanics and Eq. 2, the normalization condition for probabilities. The class of unitary matrices includes permutations, rotations and arbitrary phase changes (i.e., diagonal matrices where each element on the diagonal is a complex number with magnitude equal to one).

Reversible classical programs, unitary operations on the superpositions and the measurement process are the basic ingredients used to construct a program for a quantum computer. As used in the search algorithm described below, such a program consists of first preparing an initial superposition of states, operating on those states with a series of unitary matrices in conjunction with a classical program to evaluate the consistency of various states with respect to the search requirements, and then making a measurement to obtain a definite final answer. The amplitudes of the superposition just before the measurement is made determine the probability of obtaining a solution. The overall structure is a probabilistic Monte Carlo computation [41] in which at each trial there is some probability to get a solution, but no guarantee. This means the search method is incomplete: it can find a solution if one exists but can never guarantee a solution doesn't exist.

An alternate conceptual view of these quantum programs is provided by the path integral approach to quantum mechanics [20]. In this view, the final amplitude of a given state is obtained by a weighted sum over all possible paths that produce that state. In this way, the various possibilities involved in a computation can interfere with each other, either constructively or destructively. This differs from the classical combination of probabilities of different ways to reach the same outcome (e.g., as used in probabilistic algorithms): the probabilities are simply added, giving no possibility for interference. Interference is also seen in classical waves, such as with sound or ripples on the surface of water. But these systems lack the capability of quantum parallelism. The various formulations of quantum mechanics, involving operators, matrices or sums over paths are equivalent but suggest different intuitions about constructing possible quantum algorithms.

Next: Example: A One-Bit Up: Quantum Search Methods Previous: Quantum Search Methods