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

computation?2

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

executed.

Let us try to use a quantum circuit for calculating a function F :

Bn

→

Bm,

where B = {0, 1} is the set of values of a classical

bit.3

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) =

y1,...,yN

cy1,...,yN (x1,...,xn) |y1,...,yN ,

2The

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

cLk

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).