4 Introduction

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)

2

. 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 [62] found a quantum

algorithm4

which factors an n-digit integer in about

n3

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.