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.
