2 Introduction
This assertion may seem extremely obvious: in nature there exists a multi-
tude of processes that are unlike operations with zeros and ones. We might
attempt to use those processes for the creation of an analog computer. For
example, interference of light can be used to compute the Fourier transform.
However, in most cases the gain in speed is not major, i.e., it depends weakly
on the size of the device. The reason lies in the fact that the equations of
classical physics (for example, Maxwell’s equations) can be effectively solved
on an ordinary digital computer. What does “effectively” mean? The cal-
culation of an interference pattern may require more time than the real
experiment by a factor of a million, because the speed of light is great and
the wave length is small. However, as the size of the modelled physical sys-
tem gets bigger, the required number of computational operations grows at
a moderate rate as the size raised to some power or, as is customarily said
in complexity theory, polynomially. (As a rule, the number of operations is
proportional to the quantity V t, where V is the volume and t is the time.)
Thus we see that classical physics is too “simple” from the computational
point of view.
Quantum mechanics is more interesting from this perspective. Let us
consider, for example, a system of n spins. Each spin has two so-called basis
states (0 = “spin up” and 1 = “spin down”), and the whole system has
basis states |x1,...,xn (each of the variables x1,...,xn takes values 0 or 1).
By a general principle of quantum mechanics,

cx1,...,xn |x1,...,xn
is also a possible state of the system; here cx1,...,xn are complex numbers
called amplitudes. The summation sign must be understood as a pure for-
mality. In fact, the “sum” (also called a superposition) represents a new
mathematical object a vector in a
complex vector space.
Physically, |cx1,...,xn
is the probability to find the system in the basis state
|x1,...,xn by a measurement of the values of the variables xj. (We note
that such a measurement destroys the superposition.) For this to make sense,
the formula

= 1 must hold. Therefore, the general state
of the system (i.e., a superposition) is a unit vector in the
complex space. A state change over a specified time interval is described by
a unitary matrix of size
If the time interval is very small ( /J,
where J is the energy of spin-spin interaction and is Planck’s constant),
then this matrix is rather easily constructed; each of its elements is easily
calculated knowing the interaction between the spins. If, however, we want
to compute the change of the state over a large time interval, then it is nec-
essary to multiply such matrices. For this purpose an exponentially large
number of operations is needed. Despite much effort, no method has been
found to simplify this computation (except for some special cases). Most
plausibly, simulation of quantum mechanics is indeed an exponentially hard
computational problem. One may think this is unfortunate, but let us take
Previous Page Next Page