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 efficiently 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 efficiently.
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 efficiently 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
Previous Page Next Page