how quantum computing will change the world and how does quantum computing work | pdf free download
JackBrown,Georgia,Professional
Published Date:11-07-2017
Your Website URL(Optional)
Comment
Quantum Computing:
Lecture Notes
Ronald de WolfContents
1 Quantum Computing 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Quantum mechanics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Superposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.3 Unitary evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Quantum memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Elementary gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Example: quantum teleportation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 The Circuit Model and Deutsch-Jozsa 9
2.1 Quantum computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.1 Classical circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.2 Quantum circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Universality of various sets of elementary gates . . . . . . . . . . . . . . . . . . . . . 11
2.3 Quantum parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 The early algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4.1 Deutsch-Jozsa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4.2 Bernstein-Vazirani . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 Simon’s Algorithm 16
3.1 The problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 The quantum algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3 Classical algorithms for Simon’s problem . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3.1 Upper bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3.2 Lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4 The Fourier Transform 21
4.1 The classical discrete Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2 The Fast Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.3 Application: multiplying two polynomials . . . . . . . . . . . . . . . . . . . . . . . . 22
4.4 The quantum Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.5 An efficient quantum circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.6 Application: phase estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
ii5 Shor’s Factoring Algorithm 28
5.1 Factoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5.2 Reduction from factoring to period-finding. . . . . . . . . . . . . . . . . . . . . . . . 28
5.3 Shor’s period-finding algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.4 Continued fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
6 Grover’s Search Algorithm 35
6.1 The problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6.2 Grover’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6.3 Amplitude amplification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6.4 Application: satisfiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
7 Quantum Walk Algorithms 41
7.1 Classical random walks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
7.2 Quantum walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
7.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
7.3.1 Grover search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
7.3.2 Collision problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
7.3.3 Finding a triangle in a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
8 Quantum Query Lower Bounds 49
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
8.2 The polynomial method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
8.3 The quantum adversary method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
9 Quantum Complexity Theory 56
9.1 Most functions need exponentially many gates . . . . . . . . . . . . . . . . . . . . . . 56
9.2 Classical and quantum complexity classes . . . . . . . . . . . . . . . . . . . . . . . . 57
9.3 Classically simulating quantum computers in polynomial space . . . . . . . . . . . . 58
10 Quantum Encodings, with a Non-Quantum Application 61
10.1 Mixed states and general measurements . . . . . . . . . . . . . . . . . . . . . . . . . 61
10.2 Quantum encodings and their limits . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
10.3 Lower bounds on locally decodable codes . . . . . . . . . . . . . . . . . . . . . . . . 64
11 Quantum Communication Complexity 67
11.1 Classical communication complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
11.2 The quantum question . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
11.3 Example 1: Distributed Deutsch-Jozsa . . . . . . . . . . . . . . . . . . . . . . . . . . 69
11.4 Example 2: The Intersection problem . . . . . . . . . . . . . . . . . . . . . . . . . . 70
11.5 Example 3: The vector-in-subspace problem . . . . . . . . . . . . . . . . . . . . . . . 71
11.6 Example 4: Quantum fingerprinting . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
12 Entanglement and Non-locality 75
12.1 Quantum non-locality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
12.2 CHSH: Clauser-Horne-Shimony-Holt . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
12.3 Magic square game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
iiiChapter 1
Quantum Computing
1.1 Introduction
Today’s computers—both in theory (Turing machines) and practice (PCs)—are based on classical
physics. However, modern quantum physics tells us that the world behaves quite differently. A
quantumsystemcanbeinasuperposition ofmanydifferentstatesatthesametime,andcanexhibit
interference effects during the course of its evolution. Moreover, spatially separated quantum
systems may be entangled with each other and operations may have “non-local” effects because of
this.
Quantum computation is the field that investigates the computational power and other prop-
erties of computers based on quantum-mechanical principles. An important objective is to find
quantum algorithms that are significantly faster than any classical algorithm solving the same
problem. The field started in the early 1980s with suggestions for analog quantum computers by
Yuri Manin 65 (and appendix of 66), Richard Feynman 41, 42, and Paul Benioff 14, and
reached more digital ground when in 1985 David Deutsch defined the universal quantum Turing
machine 33. The following years saw only sparse activity, notably the development of the first al-
gorithmsbyDeutschandJozsa35andbySimon82,andthedevelopmentofquantumcomplexity
theory by Bernstein and Vazirani 18. However, interest in the field increased tremendously after
Peter Shor’s very surprising discovery of efficient quantum algorithms for the problems of integer
factorization and discrete logarithms in 1994 81. Since most of current classical cryptography is
based on the assumption that these two problems are computationally hard, the ability to actually
build and use a quantum computer would allow us to break most current classical cryptographic
systems, notably the RSA system 76, 77. (In contrast, a quantum form of cryptography due to
Bennett and Brassard 17 is unbreakable even for quantum computers.)
Let us mention three different motivations for studying quantum computers, from practical to
more philosophical:
1. The process of miniaturization that has made current classical computers so powerful and
cheap, has already reached micro-levels where quantum effects occur. Chip-makers tend to
go to great lengths to suppressthose quantum effects, butinstead one might also try to make
good use of them.
2. Making use of quantum effects allows one to speed-up certain computations enormously
(sometimes exponentially), and even enables some things that are impossible for classical
1computers The main purpose of this course is to explain these things (algorithms, crypto,
etc.) in detail.
3. Finally, one might state the main goal of theoretical computer science as “study the power
and limitations of the strongest-possible computational devices that nature allows us.” Since
our current understanding of nature is quantum mechanical, theoretical computer science
should be studying the power of quantum computers, not classical ones.
Before limiting ourselves to theory, let us say a few words about practice: to what extent will
quantum computers ever be built? At this point in time, it is just too early to tell. The first
small 2-qubit quantum computer was built in 1997 and 2001 a 5-qubit quantum computer was
used to successfully factor the number 15 85. Since then, experimental progress on a number of
different technologies has beensteady but slow. Thepractical problems facing physical realizations
of quantum computers seem formidable. The problems of noise and decoherence have to some
extent been solved in theory by the discovery of quantum error-correcting codes and fault-tolerant
computing (see, e.g., Chapter 14 in these notes or 72, Chapter 10), but these problems are by no
means solved in practice. On the other hand, we shouldrealize that the field of physical realization
of quantum computing is still in its infancy and that classical computing had to face and solve
many formidable technical problems as well—interestingly, often these problems were even of the
samenatureasthose nowfacedbyquantumcomputing(e.g., noise-reduction anderror-correction).
Moreover, thedifficultiesfacingtheimplementationofafullquantumcomputermayseemdaunting,
but more limited things involving quantum communication have already been implemented with
some success, for example teleportation (which is the process of sending qubits using entanglement
andclassical communication),andquantumcryptographyisnowadaysevencommerciallyavailable.
Even if the theory of quantum computing never materializes to a real physical computer,
quantum-mechanical computers are still anextremely interesting ideawhich will bearfruitin other
areas than practical fast computing. On the physics side, it may improve our understanding of
quantum mechanics. The emerging theory of entanglement has already done this to some extent.
Onthecomputerscienceside, thetheoryofquantumcomputationgeneralizes andenrichesclassical
complexity theory and may help resolve some of its problems.
1.2 Quantum mechanics
Here we give a brief and abstract introduction to quantum mechanics. In short: a quantum state
is a superposition of classical states, to which we can apply either a measurement or a unitary
operation. For the required linear algebra and Dirac notation we refer to Appendix A.
1.2.1 Superposition
Consider some physical system that can be inN different, mutually exclusive classical states. Call
these states 1i,2i,...,Ni. Roughly, by a “classical” state we mean a state in which the system
can befoundifwe observe it. A pure quantum state (usually justcalled state)φi isa superposition
of classical states, written
φi =α 1i+α 2i+···+α Ni.
1 2 N
Here α is a complex number that is called the amplitude of ii in φi (see Appendix B for a brief
i
explanation of complex numbers). Intuitively, a system in quantum state φi is in all classical
2states at the same time It is in state1i with amplitudeα , in state2i with amplitudeα , and so
1 2
on. Mathematically, the states1i,...,Ni form an orthonormal basis of anN-dimensional Hilbert
space (i.e., anN-dimensional vector space equipped with an inner product) of dimensionN, and a
quantum state φi is a vector in this space.
1.2.2 Measurement
There are two things we can do with a quantum state: measure it or let it evolve unitarily without
measuring it. We will deal with measurement first.
Measurement in the computational basis
Suppose we measure state φi. We cannot “see” a superposition itself, but only classical states.
Accordingly, if we measure stateφi we will see one and only one classical stateji. Which specific
ji will we see? This is not determined in advance; the only thing we can say is that we will
2
see state ji with probability α , which is the squared norm of the corresponding amplitude α
j j
√
2 2
(a+ib = a +b ). Thus observing a quantum state induces a probability distribution on the
P
N
2
classical states, given by the squared norms of the amplitudes. This implies α =1, so the
j
j=1
vectorofamplitudeshas(Euclidean)norm1. Ifwemeasureφiandseeclassicalstatejiasaresult,
thenφi itselfhas“disappeared,”andall thatisleftisji. Inotherwords, observingφi “collapses”
the quantum superposition φi to the classical state ji that we saw, and all “information” that
might have been contained in the amplitudes α is gone.
i
Projective measurement
Asomewhatmoregeneralkindofmeasurementthantheabove“measurementinthecomputational
(or standard) basis” is possible. This will be used only sparsely in the course, so it may be skipped
on a first reading. Such a projective measurement is described by projectors P ,...,P (m≤N)
1 m
which sum to identity. These projectors are then pairwise orthogonal, meaning that PP = 0 if
i j
i = 6 j. The projectorP projects on some subspaceV of the total Hilbert spaceV, and every state
j j
P
m
φi∈V canbedecomposedinauniquewayasφi = φ i,withφ i=P φi∈V . Becausethe
j j j j
j=1
projectors are orthogonal, the subspacesV are orthogonal as well, as are the statesφ i. When we
j j
2
applythismeasurementtothepurestateφi, thenwewillgetoutcomej withprobabilitykφ ik =
j
Tr(P φihφ) and the state will then “collapse” to the new state φ i/kφ ik=P φi/kP φik.
j j j j j
For example, a measurement in the standardbasis is the specific projective measurement where
m=N andP =jihj. Thatis,P projectsontothestandardbasisstatejiandthecorresponding
j j
P
N
subspace V is the space spanned by ji. Consider the state φi = α ji. Note that P φi =
j j j
j=1
2
2
α ji, so applying our measurement to φi will give outcome j with probability kα jik = α ,
j j j
α α
j j
and in that case the state collapses to α ji/kα jik = ji. The norm-1 factor may be
j j
α α
j j
disregarded because it has no physical significance, so we end up with the state ji as we saw
before.
As another example, a measurement that distinguishes between ji with j ≤ N/2 and ji
P P
with j N/2 corresponds to the two projectors P = jihj and P = jihj.
1 2
j≤N/2 jN/2
q
1 2
√
Applying this measurement to the stateφi = 1i+ Ni will give outcome 1 with probability
3
3
32
kP φik = 1/3, in which case the state collapses to 1i, and will give outcome 2 with probability
1
2
kP φik =2/3, in which case the state collapses toNi.
2
1.2.3 Unitary evolution
Instead of measuringφi, we can also apply some operation to it, i.e., change the state to some
ψi =β 1i+β 2i+···+β Ni.
1 2 N
Quantum mechanics only allows linear operations to be applied to quantum states. What this
T
means is: if we view a state like φi as an N-dimensional vector (α ,...,α ) , then applying an
1 N
operation that changes φi to ψi corresponds to multiplying φi with an N ×N complex-valued
matrix U:
α β
1 1
. .
. .
U = .
. .
α β
N N
P P
Note that by linearity we have ψi =Uφi =U ( αii) = αUii.
i i
i i
Because measuring ψi should also give a probability distribution, we have the constraint
P
N
2
β = 1. This implies that the operation U must preserve the norm of vectors, and hence
j
j=1
−1
must be a unitary transformation. A matrix U is unitary if its inverse U equals its conjugate
∗
transpose U . This is equivalent to saying that U always maps a vector of norm 1 to a vector of
norm1. Becauseaunitarytransformationalwayshasaninverse,itfollowsthatany(non-measuring)
−1
operation on quantumstates mustbe reversible: byapplyingU we can always “undo”the action
ofU,andnothingislostintheprocess. Ontheotherhand,ameasurementisclearlynon-reversible,
because we cannot reconstruct φi from the observed classical state ji.
1.3 Quantum memory
In classical computation, the unit of information is a bit, which can be 0 or 1. In quantum compu-
tation, this unit is a quantum bit (qubit), which is a superposition of 0 and 1. Consider a system
1
with 2 basis states, call them 0i and 1i. We identify these basis states with the vectors
0
0
and , respectively. A single qubit can be in any superposition
1
2 2
α 0i+α 1i, α +α =1.
0 1 0 1
2
Accordingly, a single qubit “lives” in the vector spaceC . Similarly we can think of systems of
more than 1 qubit, which “live” in the tensor product space of several qubit systems. For instance,
a 2-qubit system has 4 basis states: 0i⊗0i,0i⊗1i,1i⊗0i,1i⊗1i. Here for instance1i⊗0i
means that the first qubit is in its basis state 1i and the second qubit is in its basis state 0i. We
will often abbreviate this to1i0i, 1,0i, or even 10i.
n
More generally, a register ofn qubits has 2 basis states, each of the formb i⊗b i⊗...⊗b i,
1 2 n
n
with b ∈ 0,1. We can abbreviate this to b b ...b i. We will often abbreviate 0...0 to 0 .
i 1 2 n
n
Since bitstrings of length n can be viewed as numbers between 0 and 2 −1, we can also write
4n
the basis states as numbers0i,1i,2i,...,2 −1i. A quantum register of n qubits can be in any
superposition
n
2 −1
X
n 2
α 0i+α 1i+···+α n 2 −1i, α =1.
0 1 2 −1 j
j=0
2
If we measure this in the standard basis, we obtain the n-bit state state ji with probabilityα .
j
Measuring just the first qubit of a state would correspond to the projective measurement that
has the two projectors P = 0ih0⊗I n−1 and P = 1ih1⊗I n−1. For example, applying this
0 2 1 2
q
1 2
√
measurement to the state 0iφi+ 1iψi will give outcome 0 with probability 1/3 (the state
3
3
thenbecomes0iφi)andoutcome1withprobability2/3(thestatethenbecomes1iψi). Similarly,
measuring the first n qubits of an (n+m)-qubit state in the standard basis corresponds to the
n n
m
projective measurement that has 2 projectors P =iihi⊗I for i∈0,1 .
i 2
Animportant propertythat deserves tobementioned is entanglement, whichreferstoquantum
correlations between different qubits. For instance, consider a 2-qubit register that is in the state
1 1
√ 00i+√ 11i.
2 2
Such2-qubit states are sometimes called EPR-pairs inhonor ofEinstein, Podolsky, andRosen39,
who first examined such states and their seemingly paradoxical properties. Initially neither of the
two qubits has a classical value0i or1i. However, if we measure the first qubit and observe, say,
a 0i, then the whole state collapses to 00i. Thus observing the first qubit immediately fixes also
the second, unobserved qubit to a classical value. Since the two qubits that make up the register
may be far apart, this example illustrates some of the non-local effects that quantum systems can
exhibit. In general, a bipartite state φi is called entangled if it cannot be written as a tensor
productφ i⊗φ i whereφ i lives in the first space andφ i lives in the second.
A B A B
At this point, a comparison with classical probability distributions may be helpful. Suppose
n m
we have two probability spaces, A and B, the first with 2 possible outcomes, the second with 2
n
possible outcomes. A distribution on the first space can be described by 2 numbers (non-negative
n
reals summing to 1; actually there are only 2 − 1 degrees of freedom here) and a distribution
m
on the second by 2 numbers. Accordingly, a product distribution on the joint space can be
n m
described by 2 + 2 numbers. However, an arbitrary (non-product) distribution on the joint
n+m n+m
space takes 2 real numbers, since there are 2 possible outcomes in total. Analogously, an
n
n-qubit state φ i can be described by 2 numbers (complex numbers whose squared moduli sum
A
m n m
to 1), an m-qubit state φ i by 2 numbers, and their tensor product φ i⊗φ i by 2 +2
B A B
n+m
numbers. However, an arbitrary (possibly entangled) state in the joint space takes 2 numbers,
n+m
since it lives in a 2 -dimensional space. We see that the number of parameters required to
describe quantum states is the same as the number of parameters needed to describe probability
1
distributions. Also note the analogy between statistical independence of two random variables A
and B and non-entanglement of the product state φ i⊗φ i. However, despite the similarities
A B
between probabilities and amplitudes, quantum states are much more powerful than distributions,
because amplitudes may have negative parts which can lead to interference effects. Amplitudes
only become probabilities when we square them. The art of quantum computing is to use these
special properties for interesting computational purposes.
1
Two random variablesA andB are independent if their joint probability distribution can be written as a product
of individual distributions for A and for B: PrA =a∧B =b= PrA =a·PrB =b for all possible values a,b.
51.4 Elementary gates
A unitary that acts on a small number of qubits (say, at most 3) is often called a gate, in analogy
to classical logic gates like AND, OR, and NOT; more about that in the next chapter. Two simple
but important 1-qubit gates are the bitflip gate X (which negates the bit, i.e., swaps 0i and 1i)
and the phaseflip gate Z (which puts a − in front of 1i). Represented as 2×2 unitary matrices,
these are
0 1 1 0
X = , Z = .
1 0 0 −1
Anotherimportant1-qubitgateisthephase gate R ,whichmerelyrotatesthephaseofthe1i-state
φ
by an angle φ:
R 0i =0i
φ
iφ
R 1i =e 1i
φ
This corresponds to the unitary matrix
1 0
R = .
φ
iφ
0 e
iπ
Note that Z is a special case of this: Z =R , because e =−1.
π
Possibly the most important 1-qubit gate is the Hadamard transform, specified by:
1 1
H0i = √ 0i+√ 1i
2 2
1 1
√ √
H1i = 0i− 1i
2 2
As a unitary matrix, this is represented as
1
1 1
√
H = .
1 −1
2
If we apply H to initial state 0i and then measure, we have equal probability of observing 0i
or 1i. Similarly, applying H to 1i and observing gives equal probability of 0i or 1i. However,
1 1
√ √
if we apply H to the superposition 0i + 1i then we obtain 0i: the positive and negative
2 2
amplitudes for 1i cancel out (note that this also means that H is its own inverse) This effect is
called interference, and is analogous to interference patterns between light or sound waves.
An example of a two-qubit gate is the controlled-not gate CNOT. It negates the second bit of
its input if the first bit is 1, and does nothing if it’s 0:
CNOT0ibi =0ibi
CNOT1ibi =1i1−bi
In matrix form, this is
1 0 0 0
0 1 0 0
CNOT= .
0 0 0 1
0 0 1 0
61.5 Example: quantum teleportation
In the next chapter we will look in more detail at how we can use and combine such elementary
gates, but as an example we will here already explain teleportation 15. Suppose there are two
parties, Alice and Bob. Alice hasa qubitα 0i+α 1i that she wants to sendto Bob via a classical
0 1
channel. Without further resources this would be impossible, but Alice also shares an EPR-pair
1
√
(00i+11i)
2
with Bob (say Alice holds the first qubit and Bob the second). Initially, their joint state is
1
(α 0i+α 1i)⊗√ (00i+11i).
0 1
2
The first two qubits belong to Alice, the third to Bob. Alice performs a CNOT on her two qubits
and then a Hadamard transform on her first qubit. Their joint state can now be written as
1
00i(α 0i+α 1i) +
0 1
2
1
01i(α 1i+α 0i) +
0 1
2
1
10i(α 0i−α 1i) +
0 1
2
1
11i(α 1i−α 0i).
0 1
2
z z
Alice Bob
Alice then measures her two qubits in the computational basis and sends the result (2 random
classical bits) to Bob over a classical channel. Bob now knows which transformation he must do
on his qubit in order to regain the qubit α 0i +α 1i. For instance, if Alice sent 11 then Bob
0 1
knows that his qubit isα 1i−α 0i. A bitflip (X) followed by a phaseflip(Z) will give himAlice’s
0 1
original qubit α 0i+α 1i. In fact, if Alice’s qubit had been entangled with other qubits, then
0 1
teleportation preserves this entanglement: Bob then receives a qubit that is entangled in the same
way as Alice’s original qubit was.
Note that the qubit on Alice’s side has been destroyed: teleporting moves a qubit from A to B,
rather than copying it. In fact, copying an unknown qubit is impossible 88, see Exercise 1.
Exercises
1. Prove the quantum no-cloning theorem: there does not exist a 2-qubit unitary U that maps
φi0i7→φiφi
for every qubit φi. Hint: consider what U has to do when φi = 0i, when φi = 1i, and when φi is a
superposition of these two.
2. Show that unitaries cannot “delete” information: there is no one-qubit unitary U that maps
φi7→0i for every one-qubit state φi.
3. Compute the result of applying a Hadamard transform to both qubits of0i⊗1i in two ways
(the first way using tensor product of vectors, the second using tensor product of matrices),
and show that the two results are equal:
H0i⊗H1i =(H⊗H)(0i⊗1i).
74. Show that a bit-flip operation, preceded and followed by Hadamard transforms, equals a
phase-flip operation: HXH =Z.
1
√
5. Prove that an EPR-pair (00i+11i) is an entangled state, i.e., that it cannot be written
2
as the tensor product of two separate qubits.
6. A matrix A is inner product-preserving if the inner product hAvAwi between Av and Aw
equalstheinnerproducthvwi, forallvectorsv,w. Ais norm-preserving ifkAvk=kvkforall
∗ ∗
vectorsv, i.e.,ApreservestheEuclideanlengthofthevector. Aisunitary ifA A =AA =I.
In the following, you may assume for simplicity that the entries of the vectors and matrices
are real, not complex.
(a) Prove that A is norm-preserving if, and only if, A is inner product-preserving.
∗ ∗
(b) Prove that A is inner product-preserving iff A A=AA =I.
(c) Conclude that A is norm-preserving iff A is unitary.
Bonus: prove the same for complex instead of real vector spaces.
7. Suppose Alice and Bob are not entangled. If Alice sends a qubit to Bob, then this can give
2
Bob at most one bit of information about Alice. However, if they share an EPR-pair, they
cantransmit two classical bitsbysendingonequbitover thechannel; thisiscalled superdense
coding 16. This exercise will show how this works.
1
√
(a) They start with a shared EPR-pair, (00i +11i). Alice has classical bits a and b.
2
Suppose she does an X-operation on her half of the EPR-pair if a = 1, and then a Z-
operation ifb =1 (she does both ifab=11, and neither ifab=00). Write the resulting
2-qubit state.
(b) Suppose Alice sends her half of the state to Bob, who now has two qubits. Show that
Bob can determine both a and b from his state. Write Bob’s operation as a quantum
circuit with Hadamard and CNOT gates.
2
Thisisactuallyadeepstatement,aspecialcaseofHolevo’s theorem. MoreaboutthismaybefoundinChapter10.
8Chapter 2
The Circuit Model and Deutsch-Jozsa
2.1 Quantum computation
Below we explain how a quantum computer can apply computational steps to its register of qubits.
Twomodelsexistforthis: thequantumTuringmachine33,18andthequantumcircuitmodel34,
89. These models are equivalent, in the sense that they can simulate each other in polynomial
time, assuming the circuits are appropriately “uniform.” We only explain the circuit model here,
which is more popular among researchers.
2.1.1 Classical circuits
In classical complexity theory, a Boolean circuit is a finite directed acyclic graph with AND, OR,
and NOT gates. It has n input nodes, which contain the n input bits (n ≥ 0). The internal
nodes are AND, OR, and NOT gates, and there are one or more designated output nodes. The
initial input bits are fed into AND, OR, and NOT gates according to the circuit, and eventually
the output nodes assume some value. We say that a circuit computes some Boolean function
n m n
f :0,1 →0,1 if the output nodes get the right value f(x) for every inputx∈0,1 .
A circuit family is a set C =C of circuits, one for each input size n. Each circuit has one
n
∗ n
output bit. Such a family recognizes or decides a language L⊆0,1 =∪ 0,1 if, for every
n≥0
n
n and every input x∈0,1 , the circuit C outputs 1 if x∈L and outputs 0 otherwise. Such a
n
circuit family is uniformly polynomial if there is a deterministic Turing machine that outputs C
n
given n as input, using space logarithmic in n (this implies time polynomial in n, because such
a machine will have only poly(n) different internal states, so it either halts after poly(n) steps or
cycles forever). Note that the size (number of gates) of the circuits C can then grow at most
n
polynomially with n. It is known that uniformly polynomial circuit families are equal in power
to polynomial-time deterministic Turing machines: a language L can be decided by a uniformly
polynomial circuit family iffL∈P 73, Theorem 11.5, whereP is the class of languages decidable
by polynomial-time Turing machines.
Similarly we can consider randomized circuits. These receive, in addition to the n input bits,
also some random bits (“coin flips”) as input. A randomized circuit computes a function f if it
successfullyoutputstherightanswerf(x)withprobabilityatleast2/3foreveryx(probabilitytaken
over the values of the random bits; the 2/3 may be replaced by any 1/2+ε). Randomized circuits
are equal in power to randomized Turing machines: a language L can be decided by a uniformly
9polynomial randomized circuit family iff L ∈ BPP, where BPP (“Bounded-error Probabilistic
Polynomial time”) is the class of languages that can efficiently berecognized byrandomized Turing
machines with success probability at least 2/3.
2.1.2 Quantum circuits
A quantum circuit (also called quantum network or quantum gate array) generalizes the idea of
classical circuit families, replacing the AND, OR, and NOT gates by elementary quantum gates.
A quantum gate is a unitary transformation on a small (usually 1, 2, or 3) number of qubits. We
saw a number of examples already in the last chapter: the bitflip gate X, the phaseflip gate Z,
the Hadamard gate H. The main 2-qubit gate we have seen is the controlled-NOT (CNOT) gate.
Adding another control register, we get the 3-qubit Toffoli gate, also called controlled-controlled-
not (CCNOT) gate. This negates the third bit of its input if both of the first two bits are 1. The
Toffoli gate is important because it is complete for classical reversible computation: any classical
computation can be implemented by a circuit of Toffoli gates. This is easy to see: using auxiliary
wireswithfixedvalues, Toffoli canimplementAND(fixthe3rdingoingwireto0)andNOT(fixthe
1st and2ndingoingwireto1). ItisknownthatAND andNOT-gates together sufficetoimplement
any classical Boolean circuit, so if we can apply (or simulate) Toffoli gates, we can implement any
classical computation in a reversible manner.
Mathematically, such elementary gates can be composed by taking tensor products (if gates
are applied in parallel to different parts of the register, and ordinary products (if gates are applied
sequentially). We have already seen a simple example of such a circuit of elementary gates, namely
to implement teleportation in the previous chapter.
For example, if we apply the Hadamard gate H to each bit in a register of n zeroes, we obtain
P
1 ⊗n
√
ji, which is a superposition of all n-bit strings. More generally, if we applyH to
n
n
j∈0,1
2
n
an initial state ii, with i∈0,1 , we obtain
X
1
⊗n i·j
H ii = √ (−1) ji, (2.1)
n
2
n
j∈0,1
P
n
n
where i·j = i j denotes the inner product of the n-bit strings i,j ∈0,1 . For example:
k k
k=1
X
1 1 1
⊗2 01·j
H 01i = √ (0i+1i)⊗√ (0i−1i) = (−1) ji.
2
2 2
2
j∈0,1
Then-fold Hadamard transform will be very useful for all the quantum algorithms explained later.
As in the classical case, a quantum circuit is a finite directed acyclic graph of input nodes,
gates, and output nodes. There are n nodes that contain the input (as classical bits); in addition
we may have some more input nodes that are initially 0i (“workspace”). The internal nodes of
the quantum circuit are quantum gates that each operate on at most 2 qubits of the state. The
gates in the circuit transform the initial state vector into a final state, which will generally be
a superposition. We measure some dedicated output bits of this final state to (probabilistically)
obtain an answer.
In analogy to the classical class BPP, we will define BQP (“Bounded-error Quantum Poly-
nomial time”) as the class of languages that can efficiently be computed with success probability
at least 2/3 by (a family of) quantum circuits whose size grows at most polynomially with the
input length. We will study this quantum complexity class and its relation with various classical
complexity classes in more detail in Chapter 9.
102.2 Universality of various sets of elementary gates
Which set of elementary gates should we allow? There are several reasonable choices.
(1) The set of all 1-qubit operations together with the 2-qubit CNOT gate is universal,
meaning that any other unitary transformation can be built from these gates.
Allowing all 1-qubit gates is not very realistic from an implementational point of view, as there are
uncountably many of them. However, the model is usually restricted, only allowing a small finite
set of 1-qubit gates from which all other 1-qubit gates can be efficiently approximated.
(2) The set consisting of CNOT, Hadamard, and the phase-gate R is universal in
π/4
the sense of approximation, meaning that any other unitary can be arbitrarily well
approximated using circuits of only these gates. The Solovay-Kitaev theorem says that
thisapproximationisquiteefficient: wecanapproximateanygateon1or2qubitsupto
error ε using polylog(1/ε) gates from our small set; in particular, simulating arbitrary
gates up to exponentially small error costs only a polynomial overhead.
It is often convenient to restrict to real numbers and use an even smaller set of gates:
(3) The set of Hadamard and Toffoli (CCNOT) is universal for all unitaries with real
entries in the sense of approximation, meaning that any unitary with only real entries
canbearbitrarilywellapproximatedusingcircuitsofonlythesegates(againtheSolovay-
Kitaev theorem says that this simulation can be done efficiently).
2.3 Quantum parallelism
One uniquely quantum-mechanical effect that we can use for buildingquantum algorithms is quan-
n
tum parallelism. Suppose we have a classical algorithm that computes some functionf :0,1 →
m
0,1 . Then we can build a quantum circuit U (consisting only of Toffoli gates) that maps
n
xi0i→xif(x)i foreveryx∈0,1 . Now supposeweapplyU toasuperpositionof all inputsx
(which is easy to build usingn Hadamard transforms):
X X
1 1
√ √
U xi0i = xif(x)i.
n n
2 2
n n
x∈0,1 x∈0,1
n
WeappliedU justonce,butthefinalsuperpositioncontainsf(x)forall 2 inputvaluesx However,
byitself thisisnot veryusefulanddoesnotgive morethanclassical randomization, since observing
the final superposition will give just one random xif(x)i and all other information will be lost.
As we will see below, quantum parallelism needs to be combined with the effects of interference
and entanglement in order to get something that is better than classical.
2.4 The early algorithms
The two main successes of quantum algorithms so far are Shor’s factoring algorithm from 1994 81
and Grover’s search algorithm from 1996 47, which will be explained in later chapters. In this
section we describe some of the earlier quantum algorithms that preceded Shor’s and Grover’s.
11Virtually all quantum algorithms work with queries in some form or other. We will explain
this model here. It may look contrived at first, but eventually will lead smoothly to Shor’s and
Grover’s algorithm. We should, however, emphasize that the query complexity model differs from
the standard model described above, because the input is now given as a “black-box.” This means
that the exponential quantum-classical separations that we describe below (like Simon’s) donot by
themselves give exponential quantum-classical separations in the standard model.
N
To explain the query setting, consider an N-bit input x = (x ,...,x )∈0,1 . Usually we
1 N
n
will have N =2 , so that we can address bitx using ann-bit indexi. One can think of the input
i
as an N-bit memory which we can access at any point of our choice (a Random Access Memory).
A memory access is via a so-called “black-box,” which is equipped to output the bit x on inputi.
i
As a quantum operation, this would be the following unitary mapping on n+1 qubits:
O :i,0i→i,xi.
x i
The first n qubits of the state are called the address bits (or address register), while the (n+1)st
qubit is called the target bit. Since this operation must be unitary, we also have to specify what
happens if the initial value of the target bit is 1. Therefore we actually let O be the following
x
unitary transformation:
O :i,bi→i,b⊕xi,
x i
n
here i∈0,1 , b∈0,1, and⊕ denotes exclusive-or (addition modulo 2). In matrix representa-
tion, O is now a permutation matrix and hence unitary. Note also that a quantum computer can
x
apply O on a superposition of various i, something a classical computer cannot do. One applica-
x
tion of this black-box is called a query, and counting the required number of queries to compute
this or that function of x is something we will do a lot in the first half of these notes.
Given the ability to make a query of the above type, we can also make a query of the form
1
x
i
√
ii→(−1) ii by setting the target bit to the state −i= (0i−1i) =H1i:
2
1
x
i
O (ii−i) =ii√ (xi−1−xi) =(−1) ii−i.
x i i
2
This±-kindofqueryputstheoutputvariableinthephaseofthestate: ifx is1thenwegeta−1in
i
the phase of basis stateii; ifx =0 then nothing happenstoii. This “phase-oracle” is sometimes
i
more convenient than the standard type of query. We sometimes denote the correspondingn-qubit
unitary transformation by O .
x,±
2.4.1 Deutsch-Jozsa
Deutsch-Jozsa problem 35:
n N
For N =2 , we are given x∈0,1 such that either
(1) all x have the same value (“constant”), or
i
(2) N/2 of the x are 0 and N/2 are 1 (“balanced”).
i
The goal is to find out whetherx is constant or balanced.
n
The algorithm of Deutsch and Jozsa is as follows. We start in then-qubit zero state0 i, apply
a Hadamard transform to each qubit, apply a query (in its ±-form), apply another Hadamard to
each qubit, and then measure the final state. As a unitary transformation, the algorithm would
120i
H H
O measure
0i
H x,± H
0i
H H
Figure 2.1: The Deutsch-Jozsa algorithm for n=3
⊗n ⊗n
be H O H . We have drawn the corresponding quantum circuit in Figure 2.1 (where time
±
progresses from left to right).
n
Let us follow the state through these operations. Initially we have the state 0 i. By Equa-
tion2.1onpage10,afterthefirstHadamardtransformswehaveobtainedtheuniformsuperposition
of all i:
X
1
√
ii.
n
2
n
i∈0,1
The O -query turns this into
±
X
1
x
i
√
(−1) ii.
n
2
n
i∈0,1
Applying the second batch of Hadamards gives (again by Equation 2.1) the final superposition
X X
1
x i·j
i
(−1) (−1) ji,
n
2
n n
i∈0,1 j∈0,1
P
n
n n
where i·j = i j as before. Since i·0 = 0 for all i∈0,1 , we see that the amplitude of
k k
k=1
n
the 0 i-state in the final superposition is
1 if x =0 for all i,
i
X
1
x
i
(−1) = −1 if x =1 for all i,
i
n
2
n
0 if x is balanced.
i∈0,1
n
Hence the final observation will yield 0 i if x is constant and will yield some other state if x
is balanced. Accordingly, the Deutsch-Jozsa problem can be solved with certainty using only 1
quantum query and O(n) other operations (the original solution of Deutsch and Jozsa used 2
queries, the 1-query solution is from 31).
In contrast, it is easy to see that any classical deterministic algorithm needs at least N/2+1
queries: if it has made onlyN/2 queries and seen only 0s, the correct output is still undetermined.
However, aclassicalalgorithmcansolvethisproblemefficientlyifweallowasmallerrorprobability:
just queryx at two random positions, output “constant” if those bits are the same and “balanced”
if they are different. This algorithm outputs the correct answer with probability 1 if x is constant
and outputs the correct answer with probability 1/2 if x is balanced. Thus the quantum-classical
separation of this problem only holds if we consider algorithms without error probability.
132.4.2 Bernstein-Vazirani
Bernstein-Vazirani problem 18:
n N n
For N = 2 , we are given x∈0,1 with the property that there is some unknown a ∈0,1
such that x =(i·a) mod 2. The goal is to finda.
i
The Bernstein-Vazirani algorithm is exactly the same as the Deutsch-Jozsa algorithm, but now
x (i·a) mod 2 i·a
i
the final observation miraculously yields a. Since (−1) = (−1) = (−1) , we can write
the state obtained after the query as:
X X
1 1
x i·a
i
√ (−1) ii = √ (−1) ii.
n n
2 2
n n
i∈0,1 i∈0,1
Applying a Hadamard to each qubit will turn this into the classical state ai and hence solves
the problem with 1 query and O(n) other operations. In contrast, any classical algorithm (even
a randomized one with small error probability) needs to ask n queries for information-theoretic
reasons: thefinalanswerconsistsofnbitsandoneclassical querygivesatmost1bitofinformation.
Bernstein and Vazirani also defined a recursive version of this problem, which can be solved
exactly by a quantum algorithm inpoly(n) steps, but for which any classical randomized algorithm
Ω(logn)
needs n steps.
Exercises
−1
1. Is the controlled-NOT operation C Hermitian? Determine C .
2. Show that every unitary one-qubit gate with real entries can be written as a rotation matrix,
possibly preceded and followed by Z-gates. In other words, show that for every 2×2 real
unitary U, there exist signs s ,s ,s ∈1,−1 and angle θ∈0,2π) such that
1 2 3
1 0 cos(θ) −sin(θ) 1 0
U =s
1
0 s sin(θ) cos(θ) 0 s
2 3
3. Construct a CNOT from two Hadamard gates and one controlled-Z (the controlled-Z gate
maps11i7→−11i and acts like the identity on the other basis states).
4. A SWAP-gate interchanges two qubits: it maps basis state a,bi to b,ai. Implement a
SWAP-gate using a few CNOTs.
5. Let U be a 1-qubit unitary that we would like to implement in a controlled way, i.e., we
c
want to implement a map cibi 7→ciU bi for all c,b ∈0,1. Suppose there exist 1-qubit
unitaries A, B, and C, such that ABC = I and AXBXC = U (remember that X is the
NOT-gate). Give a circuit that acts on two qubits and implements a controlled-U gate, using
CNOTs and (uncontrolled) A, B, and C gates.
6. It is possible to avoid doing any intermediate measurements in a quantum circuit, using one
auxiliary qubit to delay a measurement till the end of the computation. Show how.
Hint: instead of measuring the qubit, apply a CNOT that “copies” it to a new 0i-qubit, which is then left
alone until the end of the computation. Analyze what happens.
14n n
7. (a) Give a circuit that maps 0 ,bi 7→ 0 ,1−bi for b ∈ 0,1, and that maps i,bi 7→
n n
i,bi whenever i ∈0,1 \0 . You are allowed to use every type of elementary gate
mentioned in the lecture notes (incl. Toffoli gates), as well as auxiliary qubits that are
initially 0i and that should be put back to0i at the end of the computation.
You can draw a Toffoli gate similar to a CNOT gate: a bold dot on each of the two
control wires, and a ‘⊕’ on the target wire.
N
(b) Suppose we can make queries of the type i,bi 7→ i,b⊕xi to input x∈0,1 , with
i
n ′ ′
N =2 . Letx be the inputxwith its firstbit flipped(e.g., ifx=0110 thenx =1110).
′
Give a circuit that implements a query to x. Your circuit may use one query to x.
′′
(c) Give a circuit that implements a query to an input x that is obtained from x (analo-
gously to (b)) by setting its first bit to 0. Your circuit may use one query to x.
8. In Section 2.4 we showed that a query of the typei,bi7→i,b⊕xi (wherei∈0,...,N−1
i
x
i
andb∈0,1) can be used to implement a phase-query, i.e., one of the typeii7→(−1) ii.
Is the converse possible: can a query of the first type be implemented using phase-queries,
and possibly some ancilla qubits and other gates? If yes, show how. If no, explain why not.
9. Give a randomized classical algorithm (i.e., one that can flip coins during its operation) that
makes only two queries tox, and decides the Deutsch-Jozsa problem with success probability
at least 2/3 on every possible input. A high-level description is enough, no need to write out
the classical circuit.
10. Suppose our N-bit input x satisfies the following promise:
either (1) the firstN/2 bits ofx are all 0 andthe secondN/2 bits are all 1; or (2) the number
of 1s in the first half of x plus the number of 0s in the second half, equals N/2. Modify the
Deutsch-Jozsa algorithm to efficiently distinguish these two cases (1) and (2).
N
11. Aparity query toinputx∈0,1 correspondstothe(N+1)-qubitunitarymapQ :y,bi7→
x
P
N−1
N
y,b⊕(x·y)i, where x·y = xy mod 2. For any fixed function f :0,1 →0,1,
i i
i=0
give aquantumalgorithm that computesf(x)usingonlyone suchquery(i.e., one application
of Q ), and as many elementary gates as you want. You don’t need to give the circuit in full
x
detail, an informal description of the algorithm is good enough.
15Chapter 3
Simon’s Algorithm
The Deutsch-Jozsa problem showed an exponential quantum improvement over the best determin-
istic classical algorithms; the Bernstein-Vazirani problem shows a polynomial improvement over
the best randomized classical algorithms that have error probability≤1/3. In this chapter we will
combine these two features: we will see a problem where quantum computers are exponentially
more efficient than bounded-error randomized algorithms.
3.1 The problem
n n
LetN =2 , andN =1,...,N, which we can identify with0,1 . Letj⊕sbethen-bit string
obtained by bitwise adding the n-bit strings j and s mod 2.
Simon’s problem 82:
n n
ForN =2 , we are given x=(x ,...,x ), withx ∈0,1 , with the property that there is some
1 N i
n
unknown non-zero s∈0,1 such that x =x iff i=j⊕s. The goal is to finds.
i j
Note that x, viewed as a function from N to N is a 2-to-1 function, where the 2-to-1-ness
is determined by the unknown mask s. The queries to the input here are slightly different from
before: the inputx =(x ,...,x ) now has variables x that themselves are n-bit strings, and one
1 N i
n
query gives such a string completely (i,0 i7→i,xi). However, we can also view this problem as
i
n
having n2 binary variables that we can query individually. Since we can simulate one x -query
i
using only n binary queries (just query all n bits of x ), this alternative view will not affect the
i
number of queries very much.
3.2 The quantum algorithm
Simon’s algorithm starts out very similar to Deutsch-Jozsa: start in a state of 2n zero qubits
n n
0 i0 i and apply Hadamard transforms to the firstn qubits, giving
X
1
n
√
ii0 i.
n
2
n
i∈0,1
16At this point, the second n-qubit register still holds only zeroes. A query turns this into
X
1
√
iixi.
i
n
2
n
i∈0,1
Now the algorithm measures the secondn-bit register (this measurement is actually not necessary,
but it facilitates analysis). The measurement outcome will be some value x and the first register
i
will collapse to the superposition of the two indices having that x -value:
i
1
√ (ii+i⊕si)xi.
i
2
We will now ignore the second register and applyHadamard transformsto the firstnqubits. Using
Equation 2.1 and the fact that (i⊕s)·j =(i·j)⊕(s·j), we can write the resulting state as
X X
1
i·j (i⊕s)·j
√
(−1) ji+ (−1) ji =
n+1
2
n n
j∈0,1 j∈0,1
X
1
i·j s·j
√
(−1) 1+(−1) ji .
n+1
2
n
j∈0,1
Note that ji has non-zero amplitude iff s·j = 0 mod 2. Measuring the state gives a uniformly
randomelement fromthesetj s·j =0 mod 2. Accordingly, weget alinear equation that gives
information about s. We repeat this algorithm until we have obtained n−1 independent linear
n
equations involving s. The solutions to these equations will be 0 and the correct s, which we can
compute efficiently by a classical algorithm (Gaussian elimination modulo 2). This can be done by
3
means of a classical circuit of size roughly O(n ).
k
Note thatifthej’syouhave generated at somepointspanaspace ofsize2 , forsomekn−1,
then the probability that your next run of the algorithm produces aj that is linearly independent
n−1 k n−1
of the earlier ones, is (2 − 2 )/2 ≥ 1/2. Hence an expected number of O(n) runs of the
algorithm suffices to find n−1 linearly independent j’s. Simon’s algorithm thus finds s using an
expected number of O(n) x -queries and polynomially many other operations.
i
3.3 Classical algorithms for Simon’s problem
3.3.1 Upper bound
√
n
Let us first sketch a classical randomized algorithm that solves Simon’s problem using O( 2 )
queries, based on the so-called “birthday paradox.” Our algorithm will make T randomly chosen
distinct queries i ,...,i , for some T to be determined later. If there is a collision among those
1 T
queries (i.e., x = x for some k 6= ℓ), then we are done, because then we know i = i ⊕s,
i i k ℓ
k ℓ
equivalently s = i ⊕i . How large should T be such that we are likely to see a collision in case
k ℓ
T
n n 1 2
s = 6 0 ? (there won’t be any collisions if s = 0 .) There are = T(T −1)≈T /2 pairs in our
2 2
sequence that could be a collision, and since the indices are chosen randomly, the probability for a
n
fixed pair to form a collision is 1/(2 −1). Hence by linearity of expectation, the expected number
√
2 n+1
n+1
of collisions in our sequence will be roughly T /2 . If we choose T = 2 , we expect to have
17
Advise:Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.
