which depends on (x1,...,xn). It is now necessary to read out the result. If
the circuit were classical (and correctly designed to compute F), we would
expect to find the answer in the first m bits of the sequence (y1,...,yN ), i.e.,
we seek (y1,...,ym) = F(x1,...,xn). To determine the actual result in the
quantum case, the values of all spins should be measured. The measurement
may produce any sequence of zeros and ones (y1,...,yN ), the probability of
obtaining such a sequence being equal to cy1,...,yN (x1,...,xn)
. A quantum
circuit is “correct” for a given function F if the correct answer (y1,...,ym) =
F(x1,...,xn) is obtained with probability that is suﬃciently close to 1. By
repeating the computation several times and choosing the answer that is
encountered most frequently, we can reduce the probability of an error to
be as small as we want.
We have just formulated (omitting some details) a mathematical model
of quantum computation. Now, two questions arise naturally.
1. For which problems does quantum computation have an advantage in
comparison with classical?
2. What system can be used for the physical realization of a quantum
computer? (This does not necessarily have to be a system of spins.)
With regard to the first question we now know the following. First, on
a quantum computer it is possible to model an arbitrary quantum system
in polynomially many steps. This will allow us (when quantum computers
become available) to predict the properties of molecules and crystals and to
design microscopic electronic devices, say, 100 atoms in size. Presently such
devices lie at the edge of technological possibility, but in the future they will
likely be common elements of ordinary computers. So, a quantum computer
will not be a thing to have in every home or oﬃce, but it will be used to
make such things.
A second example is factoring integers into primes and analogous num-
ber-theoretic problems. In 1994 P. Shor  found a quantum
which factors an n-digit integer in about
steps. This beautiful result
could have an outcome that is more harmful than useful: factoring allows
one to break the most commonly used cryptosystem (RSA), to forge elec-
tronic signatures, etc. (But anyway, building a quantum computer is such
a diﬃcult task that cryptography users may have good sleep — at least, for
the next 10 years.) The method at the core of Shor’s algorithms deals with
Abelian groups. Some non-Abelian generalizations have been found, but it
remains to be seen if they can be applied to any practical problem.
4Without going into detail, a quantum algorithm is much the same thing as a quantum circuit.
The difference lies in the fact that a circuit is defined for problems of fixed size (n = const), whereas
an algorithm applies to any n.