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 ∼
(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  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
(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-
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.