next up previous
Next: 3 The Satisfiability Problem Up: Solving Highly Constrained Search Previous: 1 Introduction

2 Quantum Computers 

The state of a classical computer can be described by a string of bits, each of which is implemented by some two-state device. Quantum computers use physical devices whose full quantum state can be controlled. For example [19], an atom in its ground state could represent a bit set to 0, and an excited state for 1. The atom can be switched between these states and also be placed in a uniquely quantum mechanical superposition of these values, which can be denoted as a vector tex2html_wrap_inline1624 , with a component (called an amplitude) for each of the corresponding classical states for the system. These amplitudes are complex numbers. A superposition should not be confused with a probabilistic representation of ignorance about whether a classical bit is really 0 or 1. Nor is a superposition simply in between a 0 or 1, as could be the case with a 3 volt value for classical bits implemented as 0 and 5 volts. Instead, a superposition has no complete classical analog.

In contrast to a classical machine which, at any given step of its program, has a definite value for each bit, a quantum machine with n quantum bits exists in a general superposition of the tex2html_wrap_inline1628 classical states for n bits, described by the vector


The amplitudes have a physical interpretation: when the computer's state is measured, the superposition randomly changes to one of the classical states with tex2html_wrap_inline1632 being the probability to obtain the state s. Thus amplitudes satisfy the normalization condition tex2html_wrap_inline1636 . This measurement operation is used to obtain definite results from a quantum computation.

Using this rich set of states requires operations that can rapidly manipulate the amplitudes in a superposition. Because quantum mechanics is linear and the normalization condition must always be satisfied, these operations are limited to unitary linear operators [29]. That is, a state vector tex2html_wrap_inline1638 can only change to a new vector tex2html_wrap_inline1640 related to the original one by a unitary transformation, i.e., tex2html_wrap_inline1642 where U is a unitary matrixgif of dimension tex2html_wrap_inline1654 . In particular, this requires that the operations be reversible: each output is the result of a single input. In spite of the exponential size of the matrix, in many cases the operation can be performed in a time that grows only as a polynomial in n by quantum computers [7, 35]. Importantly, the quantum computer does not explicitly form, or store, the matrix U. Rather it performs a series of elementary operations whose net effect is to produce the new state vector tex2html_wrap_inline1660 . On the other hand, the components of the new vector are not directly accessible: rather they determine the probabilities of obtaining various results when the state is measured.

Important examples of such operations are reversible classical programs [3, 22]. Let P be such a program. Then for each classical state s, i.e., a string of bit values, it produces an output tex2html_wrap_inline1666 , and each output is produced by only a single input. A simple example is a program operating with two bits that replaces the first value with the exclusive-or of both bits and leaves the second value unchanged, i.e., P[00]=00, P[01]=11, P[10]=10 and P[11]=01. When used with a quantum superposition, such classical programs operate independently and simultaneously on each component to give a new superposition. That is, a program operating with n bits gives


where tex2html_wrap_inline1678 with tex2html_wrap_inline1666 . This quantum parallelism allows a machine with n bits to operate simultaneously with tex2html_wrap_inline1628 different classical states.

Unitary operations can also mix the amplitudes in a state vector. An example for n=1 is


This converts tex2html_wrap_inline1688 , which could correspond to an atom prepared in its ground state, to tex2html_wrap_inline1690 , i.e., an equal superposition of the two states. Since amplitudes are complex numbers, such mixing can combine amplitudes to leave no amplitude in some of the states. This capability for interference [4, 21] distinguishes quantum computers from probabilistic classical machines.

next up previous
Next: 3 The Satisfiability Problem Up: Solving Highly Constrained Search Previous: 1 Introduction

Tad Hogg
Feb. 1999