Introduction 3
a different point of view: quantum mechanics being hard means it is power-
ful. Indeed, a quantum system effectively “solves” a complex computational
problem it models its very self.
Can we use quantum systems for solving other computational prob-
lems? What would be a mathematical model of a quantum computer that
is just as independent of physical realization as are models of classical
It seems that these questions were first posed in 1980 in
the book by Yu. I. Manin [49]. They were also discussed in the works of
R. Feynman [23, 24] and other authors. In 1985 D. Deutsch [20] proposed a
concrete mathematical model the quantum Turing machine, and in 1989
an equivalent but more convenient model the quantum circuit [21] (the
latter was largely based on Feynman’s ideas).
What exactly is a quantum circuit? Suppose that we have N spins,
each located in a separate numbered compartment and completely isolated
from the surrounding world. At each moment of time (as a computer clock
ticks) we choose, at our discretion, any two spins and act on them with an
arbitrary 4 × 4 unitary matrix. A sequence of such operations is called a
quantum circuit. Each operation is determined by a pair of integers, indexing
the spins, and sixteen complex numbers (the matrix entries). So a quantum
circuit is a kind of computer program, which can be represented as text and
written on paper. The word “quantum” refers to the way this program is
Let us try to use a quantum circuit for calculating a function F :

where B = {0, 1} is the set of values of a classical
It is necessary to
be able to enter the initial data, perform the computations, and read out the
result. Input into a quantum computer is a sequence (x1,...,xn) of zeros
and ones meaning that we prepare an initial state |x1,...,xn, 0,..., 0 .
(The amount of initial data, n, is usually smaller than the overall number
of “memory cells,” i.e., of spins, N. The remaining cells are filled with
zeros.) The initial data are fed into a quantum circuit, which depends on
the problem being solved, but not on the specific initial data. The circuit
turns the initial state into a new quantum state,
|ψ(x1,...,xn) =
cy1,...,yN (x1,...,xn) |y1,...,yN ,
standard mathematical model of an ordinary computer is the Turing machine. Most
other models in use are polynomially equivalent to this one and to each other, i.e., a problem,
that is solvable in L steps in one model, will be solvable in
steps in another model, where c
and k are constants.
3Any computational problem can be posed in this way. For example, if we wish to solve the
problem of factoring an integer into primes, then (x1, . . . , xn) = x (in binary notation) and F (x)
is a list of prime factors (in some binary code).
Previous Page Next Page