CHAPTER 2

Quantum Circuit Model

This chapter introduces the quantum circuit model for quantum computing,

emphasizing universality, and quantum algorithms for simulating quantum physics.

Informatics is the study of storing, processing and communicating informa-

tion. The mathematical treatment of information starts with bit strings {0, 1}∗ =

n≥0

Z2 n. Pythagoreas once said “everything is a number.” Every number has a

binary expansion in terms of 0’s and 1’s, so we can encode everything if infinite bit

strings are allowed. But in this book we will consider only finite bit strings, i.e.,

vectors in the Z2-vector space Z2

n

for some n, unless stated otherwise.

A key informatical notion is complexity, a measure of resource-dependent dif-

ficulty. Complexity classes of computational problems are defined relative to re-

sources such as time, space, and accuracy. As bit strings x ∈ Z2

n

encode information,

families of Boolean maps from bit strings to bit strings

f(x) = fn(x) : Z2

n

−→

Z2m

encode computing problems. Computability theory selects a class of problems which

are algorithmically computable. Any computing model X determines a class of

problems XP eﬃciently solvable within X. Computational complexity theory stud-

ies these classes and their relationships.

In its most liberal form, information processing can be thought of as a black

box:

• The initial input x is encoded onto some physical system.

• The evolution of the physical system processes x.

• The computational result f(x) is read out through some measurement of

the system.

The physical system used to process x can be classical or quantum, which deter-

mines whether we are doing classical or quantum information theory. It is in-

teresting to ponder whether other physical theories could be employed to process

information. As alluded to in the introduction, the computational power of quan-

tum field theory is presumably the same as that of quantum mechanics. Also,

the logical issue of computability does not concern us because quantum computers

and classical computers solve the same class of computing problems. Rather, our

interest is to process classical information more eﬃciently.

How do we compute quantum mechanically? For simplicity, suppose we are

given a map f : Z2

n

→ Z2

n

that we need to compute. Choose a quantum system

with state space

(C2)⊗n

= C[Z2

n].

For each input x ∈ Z2

n,

represent x as a basis

state |x ∈

(C2)⊗n.

Then ideally we would like to implement a unitary matrix Ux

in

(C2)⊗n

so that Ux|x = |f(x) (Fig. 2.1).

But we don’t know which Ux would eﬃciently send |x to |f(x) or even just

close to |f(x) explicitly (this is the quantum algorithm issue), and if Ux exists,

25

http://dx.doi.org/10.1090/cbms/112/02