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.
