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 , 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 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 being the probability to obtain the
state *s*. Thus amplitudes satisfy the normalization condition . 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 can only
change to a new vector related to the original one by a
unitary transformation, i.e., where *U* is a
unitary matrix of dimension . 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 . 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 , 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 with . This *quantum parallelism* allows
a machine with *n* bits to operate simultaneously with different
classical states.

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

This converts , which could correspond to an atom prepared in its ground state, to , 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.

Feb. 1999