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

2n

basis states |x1,...,xn (each of the variables x1,...,xn takes values 0 or 1).

By a general principle of quantum mechanics,

∑

x1,...,xn

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

2n-dimensional

complex vector space.

Physically, |cx1,...,xn

|2

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

∑

x1,...,xn

|cx1,...,xn

|2

= 1 must hold. Therefore, the general state

of the system (i.e., a superposition) is a unit vector in the

2n-dimensional

complex space. A state change over a specified time interval is described by

a unitary matrix of size

2n

×

2n.

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