Introduction 5

A third example is a search for a needed entry in an unsorted database.

Here the gain is not so significant: to locate one entry in N we need about

√

N steps on a quantum computer, compared to N steps on a classical one.

As of this writing, these are all known examples — not because quantum

computers are useless for other problems, but because their theory has not

been worked out yet. We can hope that there will soon appear new mathe-

matical ideas that will lead to new quantum algorithms.

The physical realization of a quantum computer is an exceed-

ingly interesting, but diﬃcult problem. Only a few years ago doubts were

expressed about its solvability in principle. The trouble is that an arbitrary

unitary transformation can be realized only with certain accuracy. Apart

from that, a system of spins or a similar quantum system cannot be fully pro-

tected from the disturbances of the surrounding environment. All this leads

to errors that accumulate in the computational process. In L ∼

δ−1

steps

(where δ is the precision of each unitary transformation) the probability of

an error will be of the order of 1, which renders the computation useless. In

part this diﬃculty can be overcome using quantum error-correcting codes. In

1996 P. Shor [65] proposed a scheme of error correction in the quantum com-

puting process (fault-tolerant quantum computation). The original method

was not optimal but it was soon improved by a number of authors. The

end result amounts to the following. There exists some threshold value δ0

such that for any precision δ δ0 arbitrarily long quantum computation is

possible. However, for δ δ0 errors accumulate faster than we can succeed

in correcting them. By various estimates, δ0 lies in the interval from

10−6

to

10−2

(the exact value depends on the character of the disturbances and

the circuit that is used for error correction).

So, there are no obstacles in principle for the realization of a quantum

computer. However, the problem is so diﬃcult that it can be compared to

the problem of controlled thermonuclear synthesis. In fact, it is essential to

simultaneously satisfy several almost contradictory demands:

1. The elements of a quantum computer — quantum bits (spins or some-

thing similar) — must be isolated from one another and from the envi-

ronment.

2. It is essential to have the possibility to act selectively on each pair of

quantum bits (at least, on each neighboring pair). Generally, one needs

to implement several types of elementary operations (called quantum

gates) described by different unitary operators.

3. Each of the gates must be realized with precision δ δ0 (see above).

4. The quantum gates must be suﬃciently nontrivial, so that any other

operator is, in a certain sense, expressible in terms of them.