next up previous
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 statesgif. That is, we use tex2html_wrap2416 to denote the state of a computer described by tex2html_wrap_inline2518 . 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 tex2html_wrap2417 possible states for the machine, which can be associated with the numbers tex2html_wrap2418 . We then say the computer is in state tex2html_wrap2419 when the values of its bits correspond to the number tex2html_wrap2420 . 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 tex2html_wrap2421 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 tex2html_wrap2422 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 tex2html_wrap2423 where tex2html_wrap2424 is a complex number called the amplitude associated with the state tex2html_wrap2419 . The physical interpretation of the amplitudes comes from the measurement process. When a measurement is made on the quantum computer in state tex2html_wrap2426 , 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 tex2html_wrap2419 is obtained with probability tex2html_wrap2428 . 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 tex2html_wrap2419 and tex2html_wrap2424 is the component of the vector along the i tex2html_wrap_inline2522 basis element of the space. Such a state vector can also be specified by its components as tex2html_wrap2431 when the basis is understood from context. The inner product of two such vectors is tex2html_wrap2432 where tex2html_wrap2433 denotes the complex conjugate of tex2html_wrap2434 . In matrix notation, this can also be written as tex2html_wrap2435 where tex2html_wrap2436 is treated as a column vector and tex2html_wrap2437 is a row vector given by the transpose of tex2html_wrap2438 with all entries changed to their complex conjugate values. For these vectors, the normalization condition amounts to requiring that tex2html_wrap2439 .

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., tex2html_wrap2440 which produces a new state from a given input one. When applied to a superposition of states, the result is tex2html_wrap2441 . 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 tex2html_wrap2442 . Then for the superposition tex2html_wrap2443 linearity requires that tex2html_wrap2444 giving tex2html_wrap2445 , 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 tex2html_wrap2446 the operation, denoted by U, creates a new superposition tex2html_wrap2447 . Because the operations are linear with respect to superpositions, the new amplitudes can be expressed in terms of the original ones by tex2html_wrap2448 , or in matrix notation by tex2html_wrap2449 . 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 tex2html_wrap2450 . In terms of the matrix U this condition becomesgif


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


This must equal one by Eq. 3, and we already know that the diagonal terms equal one. Thus we conclude tex2html_wrap2463 . A similar argument using tex2html_wrap2464 , a superposition with an imaginary value for the second amplitude, gives tex2html_wrap2465 . Together these conditions mean that A is the identity matrix, so tex2html_wrap2466 , 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 up previous
Next: Example: A One-Bit Up: Quantum Search Methods Previous: Quantum Search Methods

Tad Hogg
Wed Mar 20 16:29:17 PST 1996