Lecture notes for the 28th
McGill Invitational Workshop on
Computational Complexity
Bellairs Institute
Holetown, Barbados

The Complexity of Quantum States and Transformations:
From Quantum Money to Black Holes

Primary Lecturer :Scott Aaronson
Guest Lecturers:
Adam Bouland
Luke SchaefferContents

1 Quantum Information Basics
1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2 Basics of Quantum Mechanics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Quantum States, Unitary Transformations, and Measurements . . . . . . . . 2
1.2.2 Multipartite Systems, Entanglement, and Density Matrices . . . . . . . . . . 5
1.2.3 More General Operations and Measurements . . . . . . . . . . . . . . . . . . 8
1.2.4 Measuring Distances Between Quantum States . . . . . . . . . . . . . . . . . 9
1.3 “Almost As Good As New” Lemma and Quantum Union Bound . . . . . . . . . . . 10
1.4 The No-Cloning Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5 Monogamy of Entanglement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Quantum Circuits, Gates, and Complexity
2.1 Quantum Circuits and Universal Gate Sets . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 The Solovay-Kitaev Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Relations to Complexity Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Classical Simulation of Quantum Computation . . . . . . . . . . . . . . . . .
2.2.2 Quantum Oracle Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14
14
16
16
17
18

3 Hidden Subgroup and Complexity of States and Unitaries
3.1 Hidden Subgroup Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Circuit Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Quantum State Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 State Versus Unitary Complexity . . . . . . . . . . . . . . . . . . . . . . . . .

22
22
25
26
28

4 QSampling States and QMA
4.1 QSampling States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Quantum Witness States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 QMA-Complete Promise Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4 Group Non-Membership . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30
30
34
35
36

5 QCMA, PostBQP, and BQP/qpoly
5.1 QCMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Bestiary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Grover’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4 QMA versus QCMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5 Complexity of Preparing Witness States . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.1 Quantum Advice States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39
39
39
40
41
44
44

i

5.6

Upper-Bounding BQP/qpoly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

6 Black Holes, Firewalls and Complexity
6.1 Thermodynamics and Reversibility . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 The Xeroxing Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3 The Firewall Paradox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.4 The HH Decoding Task . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.5 The Harlow-Hayden Argument . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.5.1 Improvements to Harlow-Hayden . . . . . . . . . . . . . . . . . . . . . . . . .
6.5.2 The “Generic Case” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.5.3 Preskill’s Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50
50
52
52
55
56
58
60
61

7 Complexity, AdS/CFT, and Wormholes
7.0.4 Susskind’s Puzzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1 The Proposal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.1 Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

62
63
64
66

8 Private-Key Quantum Money
8.1 The Wiesner and BBBW Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.2 Formal Underpinnings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.3 Security/Storage Tradeoff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.3.1 Open Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.4 Interactive Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.4.1 The Elitzur-Vaidman Bomb Attack . . . . . . . . . . . . . . . . . . . . . . . .
8.5 Quantum Money and Black Holes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

70
70
72
73
76
77
77
80

9 Public-Key Quantum Money
9.1 Public-Key Mini-Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.2 Candidates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.3 Public-Key Quantum Money Relative to Oracles . . . . . . . . . . . . . . . . . . . .
9.4 The Hidden Subspace Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.5 Instantiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.6 Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.7 Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

81
81
83
83
84
86
87
88

10 Classification of Gate Sets
10.1 Physical Universality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.2 Difficulty of Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.3 Classification of Quantum Gates and Hamiltonians . . . . . . . . . . . . . . . . . . .
10.3.1 Two-Level Unitaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.3.2 Hamiltonians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.4 Classification of Reversible Classical Gates . . . . . . . . . . . . . . . . . . . . . . . .
10.4.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.4.2 Classification of Reversible Gates . . . . . . . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

90
90
91
92
92
93
95
95
96
98

ii

Foreword

These notes reflect a series of lectures given by Scott Aaronson and a lecture given by Adam Boulandand Luke Schaeffer at the 28th McGill Invitational Workshop on Computational Complexity. The
workshop was held at the Bellairs Research Institute in Holetown, Barbados in February, 2016.

iii

Abstract

This mini-course will introduce participants to an exciting frontier for quantum computing theory:
namely, questions involving the computational complexity of preparing a certain quantum state
or applying a certain unitary transformation. Traditionally, such questions were considered in thecontext of the Nonabelian Hidden Subgroup Problem and quantum interactive proof systems, butthey are much broader than that. One important application is the problem of “public-key quantum
money” – that is, quantum states that can be authenticated by anyone, but only created or copied
by a central bank – as well as related problems such as copy-protected quantum software. A second,very recent application involves the black-hole information paradox, where physicists realized thatfor certain conceptual puzzles in quantum gravity, they needed to know whether certain states andoperations had exponential quantum circuit complexity. These two applications (quantum money
and quantum gravity) even turn out to have connections to each other! A recurring theme of thecourse will be the quest to relate these novel problems to more traditional computational problems,so that one can say, for example, “this quantum money is hard to counterfeit if that cryptosystem issecure,” or “this state is hard to prepare if PSPACE is not in PP/poly.” Numerous open problems
and research directions will be suggested, many requiring only minimal quantum background. Some
previous exposure to quantum computing and information will be assumed, but a brief review will
be provided.

iv

Lecture 1
Quantum Information Basics
Lecturer: Scott Aaronson

1.1

Scribe: Anil Ada and Omar Fawzi

Introduction

This is a mini-course on quantum complexity theory, focusing in particular on the complexity ofquantum states and unitary transformations. To be a bit more specific, we’ll be interested in thefollowing sorts of questions:• Complexity of quantum states: Given a quantum state, how many operations do we needto prepare it?
• Complexity of unitary transformations: Given a unitary transformation, how many
operations do we need to apply it?
One way to present quantum computing is to talk about which languages or decision problems
we can solve in quantum polynomial time. Instead of that, we’ll just talk directly about how hard it
is to solve quantum problems, e.g., how hard is it to create a given quantum state or to apply agiven transformation of states?
This is not a new idea; people have looked at such questions since the beginning of quantum
computing theory in the 1990s. For example, even if you want classical information out of yourcomputation at the end, the subroutines will still involve transforming quantum states. What’s
new, in this course, is that(1) we’re going to be a little more systematic about it, pausing to ask whichever questions needasking, and(2) we’re going to use the complexity of states and unitaries as a connecting thread tying together
a huge number of interesting topics in quantum computing theory, both “ancient” (i.e., morethan 10 years old) and “modern.”
The impetus for the course is that the same underlying questions, e.g. about the difficulty ofapplying a given unitary transformation, have recently been showing up in contexts as varied as
quantum proofs and advice, the security of quantum money schemes, the black-hole information
problem, and the AdS/CFT correspondence (!). One example of such a question is the so-called“Unitary Synthesis Problem,” which we’ll state in Lecture 3. So, that provides a good excuse to
discuss all these topics (each of which is fascinating in its own right) under a single umbrella!
Here’s a rough outline of the topics we’ll cover in this course:1• Lecture 1: Crash course on quantum mechanics itself.
• Lecture 2: Crash course on quantum computation.
• Lecture 3: Complexity of states and unitaries, using the famous Hidden Subgroup Problem(HSP) as a case study.
• Lecture 4: Quantum sampling and quantum witness states.
• Lecture 5: Quantum versus classical proofs and advice (featuring Grover’s algorithm).
• Lecture 6: The black-hole information problem, the firewall paradox, and the complexity ofunitaries.
• Lecture 7: Wormholes, AdS/CFT, and the complexity of quantum states.
• Lecture 8: Building a secure private-key quantum money scheme.
• Lecture 9: Public-key quantum money.
• Lecture 10: Special guest lecture on the classification of quantum gate sets.
Since the audience for these lectures includes both classical computational complexity theorists
with no background in physics, and string theorists with no background in computer science (!), we’ll
try hard to remain accessible to both audiences, while still getting as quickly as we can into current
research topics. Readers who find some particular lecture too difficult or esoteric (or conversely, whoalready know the material) are invited to skip around. Roughly speaking, Lectures 1 and 2 haveessential quantum-information prerequisites that the rest of the course builds on, while Lecture 3
has less familiar material that nevertheless plays a role in several other lectures. After that, Lecture
5 builds on Lecture 4, and Lecture 9 builds on Lecture 8, and we’ll highlight other connecting
links—but a reader who only cared (for example) about quantum gravity could safely skip many of
the other lectures, and vice versa.

1.2

Basics of Quantum Mechanics

1.2.1

Quantum States, Unitary Transformations, and Measurements

In this section we’ll introduce the basics of quantum mechanics that we’ll be using for the rest of
the course. Quantum mechanics is simply a mathematical generalization of the rules of probability
theory. In this generalization, probabilities are replaced with amplitudes, which are complex numbers.
The central claim of quantum physics is that the state of a perfectly isolated physical system is
described by a unit vector of complex numbers.
An N -dimensional quantum state is defined to be a unit vector in CN . (The space, CN , where
quantum states live is also called Hilbert space, although the mathematical fact that it’s a Hilbert
space is only important in infinite dimensions. In finite dimensions, you can just regard it as CN .)The notation that the physicists use to denote quantum states is called the ket notation, which
consists of an angle bracket and a vertical bar: |·i. Suppose there are N distinguishable states. We’ll
denote these states by |1i, |2i, . . . , |N i. A quantum state |ψi is a superposition of these N states:|ψi = α1 |1i + α2 |2i + · · · + αN |N i.
2

Here,
for all i, αi ∈ C is the amplitude corresponding to state i, and these amplitudes must satisfyP2Ni |αi | = 1. We think of |1i, |2i, . . . , |N i as an orthonormal basis spanning C and we can thinkof |ψi as the unit vector
 α1
 α2  
 ..  .
 . αNThe conjugate transpose of |ψi is denoted using the bra notation: h·|. So hψ| represents the row
vector ∗∗ ,α1 α2∗ · · · αN
where αi∗ denotes the complex conjugate of αi . Given two states |ψi = α1 |1i + · · · + αN |N i and|ϕi = β1 |1i + · · · + βN |N i, their inner product is∗hψ|ϕi = α1∗ β1 + · · · + αNβN .

So the bra and the ket come together to form the bra-ket notation.1 The outer product |ψihϕ|corresponds to the product α1
 α2  

  ∗
∗ ,
 ..  β1 β2∗ · · · βN . αNwhich results in the N × N matrix of rank 1 in which the (i, j)’th entry is αi βj∗ . The outer product|ψihψ| is called a projection to |ψi.
Quantum mechanics has two kinds of operations that you can apply to quantum states. The
first is unitary transformations and the second is measurements.
1. Unitary transformations. A unitary transformation U is simply a linear map U : CN → CNthat preserves inner products between pairs of vectors. That is, if |ψ 0 i = U |ψi and |ϕ0 i = U |ϕi, thenhψ 0 |ϕ0 i = hψ|U † U |ϕi = hψ|ϕi, where U † denotes the conjugate transpose of U . This implies that aunitary transformation preserves the norm of a state. So as you’d expect, a unitary transformation
maps a quantum state into another quantum state. There are various equivalent ways of defining aunitary transformation. We could’ve defined it as a linear transformation U that satisfies U † U = I,
where I is the identity (in other words, the inverse of U equals its conjugate transpose). A third
definition of a unitary transformation is that the rows of U (when U is viewed as a matrix) form an
orthonormal set of vectors, or equivalently that the columns do so.
Let’s now consider an example. Suppose N = 2 (which is the case√ for a single qubit). Let’s√
denote by |0i and |1i the two orthogonal states. Define |+i = (|0i+|1i)/ 2 and |−i = (|0i−|1i)/ 2.
Observe that |+i and |−i form another orthonormal basis.
1

This notation was introduced by Paul Dirac.

3

We can apply unitary transformations to rotate states. For example, consider the following
unitary transformation:cos Θ − sin ΘUΘ =sin Θ cos ΘThis transformation takes any state and rotates it by Θ counterclockwise. Fix Θ = π/4. Then it’s
clear from the picture that if we were to apply UΘ to |0i, we’d get |+i. If we were to apply UΘ one
more time, then we’d get |1i. This small example illustrates what’s called interference: the central
phenomenon of quantum mechanics that doesn’t appear in classical probability theory. Interference
refers to the fact that amplitudes can cancel each other out (whereas probabilities can’t).
To see this, let’s write out explicitly how the state is changing. First, UΘ changes |0i and |1i asfollows:
1
1UΘ
|0i −→|+i = √ |0i + √ |1i,
2
2
1
1
UΘ
|1i −→−|−i = − √ |0i + √ |1i.
2
2
If we then start with |0i and apply UΘ twice, we get
11UΘ√ |0i + √ |1i|0i −→
2
2




1
1
1
1
1
1
UΘ
√ |0i + √ |1i + √− √ |0i + √ |1i
−→ √
2
2
2
2
2
2
1
1
1
1
=
|0i + |1i − |0i + |1i
2
2
2
2= |1i.
Note that we arrive at the |1i state because the positive 1/2 and the negative 1/2 contributions to
the amplitude of the |0i state cancel each other out, i.e., they interfere with each other destructively.
One can describe the double-slit experiment in this manner. A photon can be in a superposition ofgoing through two slits, and the two paths that it can take can interfere destructively and cancel
each other out. This is why you don’t see the photon appear at a certain location on the screen
4even though if you were to close one of the slits, the photon would have some nonzero probability
to appear at that location.
2. Measurements. Quantum states can’t exist forever in the abstract realm. At some point
we have to measure them. The most basic type of measurement we can do is with respect to theorthonormal basis {|1i, |2i, . . . , |N i}. If |ψi = α1 |1i + · · · + αN |N i, and we measure |ψi, we’ll get
the outcome i with probability |αi |2 . Measurement is a destructive operation. This means thatonce |ψi is measured and outcome i is observed, the state collapses to |ii, and all other information
about the original state is vanished (or exists in parallel universes depending on your interpretationof quantum mechanics).
A more general version of the measurement rule allows us to measure a given state |ψi in any
orthonormal basis {|v1 i, |v2 i, . . . , |vN i}. In this case, the probability that we get the outcome i is|hψ|vi i|2 . And once the measurement is done, the state collapses to |vi i.
Note that the only way one can access information about the amplitudes of a quantum stateis through measurements. This is extremely important. Many of the misconceptions people haveabout quantum mechanics come from imagining that you have some kind of access to a quantum
state other than measurements.
Once consequence of our not having such access is that the global phase of a quantum state isunobservable. For example, −|0i and |0i are physically the same state, since the −1 multiplier in−|0i disappears whenever we calculate the probability of a measurement outcome by taking theabsolute squares of amplitudes. In contrast, relative phase is physically observable: for example,
α|0i + β|1i and α|0i − β|1i are different whenever α and β are both nonzero, even though |1i and−|1i are the same when considered in isolation.
Two states are more distinguishable the closer they are to being orthogonal (in fact, two states
are perfectly distinguishable if and only if they’re orthogonal). For example, |+i and |−i are
orthogonal, and indeed they can be perfectly distinguished by measuring them with respect to thebasis {|+i, |−i}.

1.2.2

Multipartite Systems, Entanglement, and Density Matrices

Next we’ll talk about how to represent the combination of more than one quantum state. In general,
to combine states, we use the tensor product. Suppose we have a qubit α|0i + β|1i and another
qubit γ|0i + δ|1i. The joint state of these two qubits is(α|0i + β|1i) ⊗ (γ|0i + δ|1i) = αγ(|0i ⊗ |0i) + αδ(|0i ⊗ |1i) + βγ(|1i ⊗ |0i) + βδ(|1i ⊗ |1i).
We often omit the tensor product sign and write the state as:αγ|0i|0i + αδ|0i|1i + βγ|1i|0i + βδ|1i|1i.
Going even further, we use the shorthand |00i to denote |0i|0i (and so forth), so we can rewrite theabove state as:αγ|00i + αδ|01i + βγ|10i + βδ|11i.
This is a vector in the 4-dimensional space spanned by the basis vectors {|00i, |01i, |10i, |11i}.
A bipartite state is called separable if it can be written as the tensor product of two states.
Clearly, by construction, the above state is separable. However, there are states that aren’t separable.
5The most famous example is called the Bell pair (or singlet, or EPR pair):|00i + |11i√.
2
(Exercise for the reader to prove its non-separability.) If a state is not separable, we call it entangled,
which can be thought of as the quantum analogue of correlation between two random variables.
Two qubits being entangled with each other doesn’t prevent them from being separated byarbitrary distances (they could even be in two different galaxies).
Now suppose Alice and Bob are physically separated. Alice has one qubit, Bob has another
qubit, and the joint state of the two qubits is
a|00i + b|01i + c|10i + d|11i.
What happens if Alice measures her qubit?
Here we need a rule for partial measurements. The rule simply says that Alice observes theoutcome 0 with probability |a|2 + |b|2 , and observes the outcome 1 with probability |c|2 + |d|2 . Also,
after the measurement is done, the state undergoes a partial collapse. If Alice observes a 0, we’d
expect the collapsed state to be described by a|00i + b|01i. However, we need to normalize
thisp
2 + |b|2 ,vector so that it’s a unit vector. Therefore the state actually collapses to (a|00i+
b|01i)/|a|p
which means Bob’s qubit after Alice’s measurement would bep(a|0i + b|1i)/ |a|2 + |b|2 . Similarly,
if Alice observes a 1, then Bob’s state becomes (c|0i + d|1i)/ |c|2 + |d|2 .
Now suppose Alice and Bob share a Bell pair. We’d like a description of the qubit that Alicehas. We know that the joint state is entangled, but can we get a description of Alice’s qubit that’s
local to Alice?
One attempt would be to describe Alice’s state as |+i. But this would be flat-out wrong: you cancheck for yourself that, if we were to measure Alice’s qubit in the {|+i, |−i} basis, then we’d observe|+i and |−i with equal probability. More generally, if you measure Alice’s qubit in any orthonormal
basis, you’ll get the two outcomes with equal probability. So Alice’s qubit is not behaving like thequantum states that we’ve talked about so far. In fact, it’s behaving much more like a classicalrandom bit.
We need a formalism to represent such states. A mixed state is defined as a probability
distribution over quantum states: {(pi , |ψi i)}, where pi is the probability of state |ψi i. The kindof quantum states we talked about before, the individual vectors |ψi i, are often called pure statesin order to distinguish them from mixed states. With this formalism, Alice’s qubit in the above
scenario can be represented as the mixed state {(1/2, |0i), (1/2, |1i)}.
Now, an important and counterintuitive property of mixed states is that different decompositions
can physically represent the same state. For example, the mixed states {(1/2, |0i), (1/2, |1i)} and{(1/2, |+i), (1/2, |−i)} are actually physically indistinguishable (just like |0i and −|0i are physicallyindistinguishable). That is, we can measure both mixtures in any basis we want, and the probabilitiesof all measurement outcomes will the same in both cases (as you can check for yourself).
This means that this encoding of a mixed state as a probability distribution over pure states isa redundant encoding. Conveniently, though, there’s a different way to represent a mixed state,called a density matrix, that has no redundancy.
The density matrix, usually denoted by ρ, corresponding to the mixed state {(pi , |ψi i)} is the
N × N matrixXρ=pi |ψi ihψi |.
i

6

We leave it as an exercise to verify that two mixed states have the same density matrix if and only
if they’re indistinguishable by any measurement.
P
Suppose Alice and Bob jointly have a bipartite state
αji |ji|ii. This state can be rewritten
P
as
for
some
β
and
|ψ
i.
Then
the
densitymatrixthat describes Alice’s state is
β
|ψ
i|ii,
i i
i
i
P
2
|βi | |ψi ihψi |. The example below nicely illustrates this.
Example: Let the joint state of Alice and Bob be|00i + |01i − |10i√,3
which we can rewrite asrr 
2 |0i − |1i
1
√
|0i +
|0i|1i.
3
32Then the density matrix describing Alice’s state is



 

2 1/2 −1/2
1 1 0
2/3 −1/3+=.
−1/3 1/3
3 −1/2 1/2
3 0 0
In general, any matrix that’s Hermitian, positive semidefinite, and whose eigenvalues sum to
1 is a density matrix. We can state the rules of quantum mechanics directly in terms of density
matrices. A quantum state is a mixed state represented by a density matrix ρ. When we apply aunitary matrix U to ρ, we get the state U ρU † . It’s also easy to verify that if we do a measurementin the basis {|1i, |2i, . . . , |N i}, we’ll observe outcome i with probability ρii . In other words, theprobabilities of the different outcomes are just the diagonal entries of ρ.
Let’s now revisit the idea that in a bipartite system, one party’s local measurement can affectthe other party’s state even though the two states can be arbitrarily far apart. A popular version ofentanglement is that the particles in the universe are spookily connected; you measure one qubit
and it must instantaneously send a signal to another qubit that it’s entangled with.
But this is a misunderstanding of entanglement! Quantum mechanics actually upholds Einstein’s
principle that you can’t send a signal instantaneously (and in particular, faster than the speed oflight). The quantum-mechanical version of that principle can be proven and is known as the No
Communication Theorem.
Theorem 1.2.1 (No Communication Theorem). Suppose Alice and Bob share a bipartite state. Thennothing that Alice chooses to do (i.e. any combination of measurements and unitary transformations)can change Bob’s local state, i.e., his density matrix ρBob .
The proof is left as an exercise for the reader.
As an example, consider the Bell state √12 (|00i + |11i). Then the density matrix describing
Bob’s state is the following maximally mixed state:


1/2 0
ρBob =.
0 1/2
If Alice measures her qubit, with 1/2 probability she’ll observe a 0, in which case Bob’s state willbe |0i, and with 1/2 probability she’ll observe a 1, in which case Bob’s state will be |1i. So Bob’s
density matrix does not change; he still has a maximally mixed state. (Of course, if we condition on
7

Alice’s outcome, that does change Bob’s density matrix. And this would also be true in the classicalprobability world.) As an exercise, one can also check that whatever unitary transformation Aliceapplies to her qubit won’t change Bob’s density matrix.
In 1935, Einstein, Podolsky, and Rosen (EPR) published a famous paper which asked, in modern
terms, whether quantum entanglement can be understood purely in terms of classical correlation.
They thought this was necessary to uphold the ‘no faster than light communication’ principle.
Indeed, the experiment described above, in which we measure the Bell pair in the {|0i, |1i} basis,
doesn’t distinguish quantum entanglement from classical correlation.
John Bell, in the 1960s, clarified the situation significantly. He described experiments (in which
Alice and Bob both randomly choose a basis to do their measurements in rather than just selectingthe {|0i, |1i} basis) that provably distinguish quantum entanglement from classical correlation.
More concretely, he proved that, if such experiments have the outcomes that quantum mechanics
predicts (and later experimental work would show that they do), then the correlations obtained byquantum entanglement can’t be achieved by any theory of shared classical randomness (i.e., classicalcorrelations).
Entanglement is thus “intermediate” between classical correlation and faster-than-light communication: it doesn’t allow faster-than-light communication, and yet any simulation of entanglement
in a classical universe would require faster-than-light communication.2

1.2.3

More General Operations and Measurements

The type of measurement we’ve discussed so far is called a projective measurement: you pick anorthonormal basis to measure in and you ask your state to collapse to one of the basis vectors. But
we can also make measurements that involve an additional ancilla system.
For example, suppose we have a state |ψi that we want to measure, but we introduce anadditional qubit in the |0i state. So the joint state is |ψi ⊗ |0i, and we can apply a projective
measurement to this state. This is not the same as a projective measurement on just |ψi, since it
lives in a higher-dimensional vector space. This more general kind of measurement goes by thecatchy name positive-operator valued measurement (POVM).
More precisely, a POVM can be described as follows. Suppose ρ is an N -dimensional density
matrix. A POVM is simply a set of Hermitian positive semidefinite NP
by N matrices {E1 , E2 , . . . , Ek }(where k can be chosen to be any number), with the property that i Ei equals the identity matrix
I. When such a POVM is applied to ρ, we observe the outcome i with probability Tr(Ei ρ). Let’s
underline the fact that if k > N , then the POVM allows for more than N outcomes. Also note that
the POVM formalism doesn’t specify what happens to the post-measurement state. It’s left as an
exercise to show that any POVM (as just defined) can be described as a projective measurement
applied to the original state together with an ancilla state. Conversely, any projective measurement
done on the original state together with an ancilla state can be described as a POVM.
There’s yet another formalism for quantum operations that in some sense, is more general thanboth unitaries and POVMs. It’s appropriately called the superoperator formalism. This formalism
captures any combination of unitaries, measurements, and ancillary systems in a single mathematicalpackage.
2

From a theoretical computer scientist’s standpoint, Bell’s result can be restated as saying that there exists a
two-prover game that can be won with greater probability in nature than it could be if the provers were separated andhad only classical shared randomness.

8Formally, a superoperator is specified by a set of matrices {E1 , E2 , . . . , Ek } satisfying
I. Given a density matrix ρ, the superoperator maps it to another density matrix
S(ρ) =k
X†
i Ei Ei =P

Ei ρEi† .

iNote that S(ρ) can have a different dimension than ρ. (Exercise: show that S(ρ) is indeed a density
matrix.) Superoperators can also be used to do a measurement: outcome i ∈ {1, 2, . . . , k} is observedwith probability Tr(Ei ρEi† ) and ρ collapses to Ei ρEi† / Tr(Ei ρEi† ).
Another concept that we’ll use is purification of a mixed state. It’s easy to prove that any mixed
state ρ in N dimensions can be obtained by tracing out a higher dimensional pure state |ψi (in fact,
N 2 dimensions suffices for this). That is, given ρ which acts on a Hilbert space HA , there exists
a pure state |ψi, which lives in a Hilbert space HA ⊗ HB , such that TrB (|ψihψ|) = ρ. This |ψi iscalled a purification of ρ.

1.2.4

Measuring Distances Between Quantum States

There are several ways to measure distances between quantum states. For example, if we had
two pure states, we could try to measure the distance between them using the Euclidean distance.
However, note that even though the Euclidean distance between |0i and −|0i is 2, they’re really thesame state. Thus, a better choice would be to look at the inner product of the states. In particular,
if |ψi and |ϕi are two pure states, their distance can be measured using |hψ|ϕi|, which is always
between 0 and 1. We can generalize the inner product to allow mixed states, which gives us ameasure known
p as fidelity. If ρ is a mixed state and |ψi is a pure state, then the fidelity between ρand |ψi is hψ|ρ|ψi. If ρ and σ are two mixed states, then the fidelity between them is defined as
F (ρ, σ) = max |hψ|ϕi|,|ψi,|ϕiwhere the maximum is over all purifications |ψi of ρ and all purifications |ϕi of σ. The fidelity
between ρ and σ can also be computed as

q
√ √
√ √
F (ρ, σ) = Trρσ ρ = k ρ σktr ,where the trace norm k · ktr is equal to the sum of the singular values.
The second distance measure we’ll look at is the trace distance, which is a generalization ofvariation distance between probability distributions. If D1 and D2 are two probability distributions,the variation distance between them is
1X|D1 (x) − D2 (x)|.
kD1 − D2 k =2 xInformally, this is a measure of how well we can distinguish a sample from the first distribution
from a sample from the second distribution. If the distance is 1, we can tell them apart perfectly,
and if it’s 0, we can’t distinguish them at all. Any experiment that accepts a sample from the first
distribution with probability p will accept a sample from the second distribution with probability in9p − kD1 − D2 k, p + kD1 − D2 k . The generalization of this to quantum states is the trace distance.
Given two mixed states ρ and σ, their trace distance is defined as
 1X
1 p
(ρ − σ)2 =kρ − σktr = Tr
|λi | ,22iwhere λi are the eigenvalues of ρ − σ. It’s easy to check that the trace distance is invariant underunitary transformations (same is true for fidelity):kρ − σktr = kU ρU † − U σU † ktr .
Being a distance measure, trace distance indeed satisfies the triangle inequality:
kA − Cktr ≤ kA − Bktr + kB − Cktr .
Furthermore, if you trace out parts of ρ and σ, that can only decrease the trace distance kρ − σktr
(exercise).
Similar to the variation distance, if we have two mixed states ρ and σ with kρ − σktr ≤ ε, andwe have a 2-outcome POVM that accepts ρ with probability p, then the same POVM accepts σ withprobability in [p − ε, p + ε]. This is a very important property that we’ll use many times throughout
the course.
The trace distance and fidelity are related as follows:p
1 − F (ρ, σ) ≤ kρ − σktr ≤ 1 − F (ρ, σ)2 .
In the upper bound, equality is achieved if ρ and σ are both pure states. This means that if ρ and σ
are pure states, then there’s a simple expression for the trace distance in terms of the inner product.

1.3“Almost As Good As New” Lemma and Quantum Union
Bound

We’ll now see an application of trace distance. We know that measurement in quantum mechanics is
an inherently destructive process. Yet we shouldn’t interpret this as saying that every measurement
is always maximally destructive. In reality, how destructive a measurement is depends on whether
there are any basis vectors (in the basis in which we’re measuring) that are close to the state being
measured. If the state being measured is close to a basis vector, then with high probability it will
“snap” to that basis vector—and since those vectors were close to begin with, the loss of information
about our original vector will be minimal.
Lemma 1.3.1 (“Almost As Good As New Lemma” [Aar05a], closely related to “Gentle Measurement
Lemma” [Win99]). Let ρ be a mixed state acting on Cd . Let U be a unitary and (Π0 , Π1 = 1 − Π0 )0
be projectors all acting on Cd ⊗ Cd . We interpret (U, Π0 , Π1 ) as a measurement performed byappending an ancillary system of dimension d0 in the state |0ih0|, applying U and then performing
the projective measurement {Π0 , Π1 } on the large system. Assuming that the outcome corresponding
to Π0 has probability 1 − ε, i.e., Tr[Π0 (U ρ ⊗ |0ih0|U † )] = 1 − ε, we have√kρ − ρ̃ktr ≤ ε ,where ρ̃ is state after performing the measurement and then undoing the unitaryU and tracing out
the ancillary system: ρ̃ = Trd0 U † Π0 U (ρ ⊗ |0ih0|)U † Π0 + Π1 U (ρ ⊗ |0ih0|)U † Π1 U .
10Proof. We start with the case where ρ is a pure state that we write |ψihψ|. Defining the two
orthogonal unit vectors |φ0 i and |φ1 i as
Π0 U (|ψi ⊗ |0i)
|φ0 i = pTr[Π0 (U ρ ⊗ |0ih0|U † )]

Π1 U (|ψi ⊗ |0i)
and |φ1 i = p,
Tr[Π1 (U ρ ⊗ |0ih0|U † )]and using the defining expression for ε, we have√√
U (|ψi ⊗ |0i) = 1 − ε|φ0 i + ε|φ1 i .
With this notation, we havehiρ̃ = Trd0 U † ((1 − ε)|φ0 ihφ0 | + ε|φ1 ihφ1 |) U † .
We can now computeppkU (|ψihψ| ⊗ |0ih0|)U † − ((1 − ε)|φ0 ihφ0 | + ε|φ1 ihφ1 |) ktr = k ε(1 − ε)|φ0 ihφ1 | + ε(1 − ε)|φ1 ihφ0 |ktrp
= ε(1 − ε) .
Topsee the last equality, we observe that |φ0 i ± |φ1 i are the two eigenvectors with eigenvalues± ε(1 − ε). Using the fact that the trace distance cannot increase if we apply U † followed by the0partial trace on the system Cd , we obtain
p
√
(1.1)
kρ − ρ̃ktr ≤ ε(1 − ε) ≤ ε .
PFor the general case, we take an eigendecomposition of ρ = i pi |ψi ihψi |. We define
εi = Tr[Π1 (U |ψi ihψi | ⊗ |0ih0|U † )] ,  ψ̃i = Trd0 U † Π0 U (|ψi ihψi | ⊗ |0ih0|)U † Π0 + Π1 U (|ψi ihψi | ⊗ |0ih0|)U † Π1 U .
Note that
we havePi pi εi = ε andPi pi ψ̃i = ρ̃. Using the triangle inequality and the pure state case (1.1),kρ − ρ̃ktr ≤
≤
≤

X
i

pi k|ψi ihψi | − ψ̃i ktr

X √p i εii√ε,where we used the concavity of the square-root function in the last inequality.
(Note: the proof above fixes an error in the proof given in [Aar05a].)
The above is also known as the gentle measurement lemma in the information theory literature(see e.g., [Wil13, Section 9.4] for more discussion). Its standard formulation is as follows.
Lemma 1.3.2 (“Gentle Measurement” [Win99]). Let ρ be a mixed state and {Λ, 1 − Λ} be a
two-outcome POVM with Tr[Λρ] = 1 − ε, then√where ρ̃ =√Λρ ΛTr[Λρ] .

kρ̃ − ρktr ≤ ε ,11

To compare to Lemma 1.3.1, we can set Λ = h0|U † Π0 U |0i. Note that here, the state conditionedon the measurement outcome is used, whereas Lemma 1.3.1 uses the unconditioned state.
It’s useful to generalize these results to multiple measurements performed in sequence.
Lemma 1.3.3 (“Quantum Union Bound” (e.g. [Aar06])). Let ρ be a mixed state acting on Cd .
Suppose we have k measurements described by (Ui , Πi0 , Πi1 ) for every i ∈ {1, . . . , k}. Assume thatfor all i ∈ {1, . . . , k}, Tr[Πi0 (Ui ρ ⊗ |0ih0|Ui† )] ≥ 1 − ε. Define the superoperator Mi taking operators
on Cd to operators on Cd by  
Mi (ρ) = Trd0i Ui† Πi0 Ui (ρ ⊗ |0ih0|)Ui† Πi0 + Πi1 Ui (ρ ⊗ |0ih0|)Ui† Πi1 Ui .
Then,√kρ − (Mk ◦ · · · ◦ M1 )(ρ)ktr ≤ k ε .
Proof. Using the triangle inequality, we havekρ − (Mk ◦ · · · ◦ M1 )(ρ)ktr ≤ kρ − Mk (ρ)ktr + · · · + k(Mk ◦ · · · ◦ M2 )(ρ) − (Mk ◦ · · · ◦ M1 )(ρ)ktr≤ kρ − Mk (ρ)ktr + · · · + kρ − M1 (ρ)ktr ,where we used in the last inequality that applying a superoperator cannot increase the trace distance.
√
To conclude, we observe that Lemma 1.3.1 precisely states that kρ − Mi (ρ)ktr ≤ ε for all i.
We note that, in the special√ case of projective measurements, the bound of Lemma 1.3.3 can be√
improved from O(k ε) to O( kε) [Sen12]—and indeed, even better than that, to O(kε) [Gao15].
Meanwhile,for arbitrary POVMs, Wilde [Wil13b] showed that the bound can be improved to√O( kε), but whether it can be improved further to O(kε) remains open.

1.4

The No-Cloning Theorem

Let’s now prove an extremely basic fact about quantum mechanics that will be invoked throughout
the course.
Theorem 1.4.1 (The No-Cloning Theorem). There is no quantum-mechanical procedure that maps
an arbitrary state |ψi (even of a single qubit) to |ψi⊗2 = |ψi ⊗ |ψi.
Proof. Consider a unitary transformation that maps (α|0i + β|1i)|0i to (α|0i + β|1i)(α|0i + β|1i).
But the latter expression is equal to α2 |00i + αβ|01i + αβ|10i + β 2 |11i, and thus this is a manifestly
nonlinear transformation, and thus can’t be unitary.
Technically, the above assumes that the cloning procedure is unitary; one needs to say slightly
more to extend the theorem to arbitrary superoperators.
Thus, for a more general proof, consider a superoperator S such that S(|ψi) = |ψi⊗2 . Consider
two state vectors |φi and |ψi, and the associated density matrices ρ = |φihφ| and σ = |ψihψ|. Letρ⊗2 and σ ⊗2 likewise be the density matrices of the cloned states S(ρ) and S(σ), respectively.
Let C = Tr(ρ · σ) and note that 0√≤ C ≤ 1. The trace distance of ρ and σ, ||ρ − σ||√tr , for density
matrices of this form, is equal to 2 1 − C. Similarly, ||ρ⊗2 − σ ⊗2 ||tr is equal to 2 1 − C 2 . (Forthese
√ consult equations (5) and (6) in [Maz15] and the references cited therein.) Note that√ equalities,
2 1 − C < 2 1 − C 2 . Thus the trace distance increases after applying the cloning superoperator
S. This contradicts the fact that applying a superoperator can never increase the trace distance
between two states.
12

1.5

Monogamy of Entanglement

We now discuss another important property of quantum states. Consider a 3-qubit system with
qubits held by Alice, Bob, and Charlie. Monogamy of entanglement is the principle that, if Alice’sand Bob’s qubits are fully entangled, then there can be no entanglement—or for that matter, evenclassical correlation—between Alice’s and Charlie’s qubits. To illustrate, consider the pure state1√ (|0iA |0iB |0iC + |1iA |1iB |1iC ).
2
The probability that Alice sees 0 is 1/2, and thus the density matrix for the reduced system BC
is |00iBC with probability 1/2, and |11iBC with probability 1/2. Thus Bob and Charlie’s density
matrix is
1/2 0 0 0
 0 0 0 0 ρBC =  0 0 0 0 .
0 0 0 1/2
This is an unentangled mixed state.
This should be contrasted with the Bell pair between Alice and Bob, which is1√ (|0iA |0iB + |1iA |1iB ),
2
or


1/2
 0
ρAB = 
 0
1/2

0
0
0
0


0 1/2
0 0 
.
0 0 
0 1/2

This is an entangled pure state.
Monogamy of Entanglement says that, if ρAB is the density matrix of the maximally entangledstate, then ρABC = ρAB ⊗ ρC . I.e., if Alice and Bob are totally entangled, then there can be noentanglement at all between Alice and Charlie—or even classical correlation. There are quantitative
versions of this theorem, as well as generalizations to larger numbers of qubits.
Before moving on to quantum circuits, we should also say something about the different ways tomeasure entanglement. Distillable Entanglement is defined as the number of EPR pairs that one
can obtain from a state, using only local operations and classical communication. Entanglement ofFormation is defined as the number of EPR pairs that are needed in order to create the state, again
using local operations and classical communication. These notions coincide for pure states, but for
mixed states, distillable entanglement can be strictly less than entanglement of formation.

13

Lecture 2
Quantum Circuits, Gates, and Complexity
Lecturer: Scott Aaronson

2.1

Scribe: Eric Allender and Michael Saks

Quantum Circuits and Universal Gate Sets

A quantum circuit—one of the central concepts of quantum computing, and of this course inparticular—just means a procedure to implement a complicated unitary transformation on n qubits,
by decomposing it into a product of simple unitary transformations on a few qubits at a time.
Let’s now introduce some conventions for representing quantum circuits that act on n qubits,
implementing a transformationXαx |xi = |ψi 7→ U (|ψi)
x∈{0,1}nwhere U is a 2n × 2n unitary matrix. Below, we see an example on n = 4 qubits, where the gate G
is applied to the two low-order bits. This circuit implements the 2n × 2n matrix I ⊗ I · · · ⊗ I ⊗ G,
which has copies of the 4-by-4 unitary matrix G along the main diagonal.
|x1 i
|x2 i
|x3 i

G

|x4 i
Define C(U ) to be the minimum number of gates required in order to implement U (exactly) using
any sequence of 1- and 2-qubit gates. For almost all U , we have C(U ) ≥ 4n by a dimension-counting
argument, and this is approximately tight by an explicit construction.
However, our focus is mainly on what can be done using a fixed, finite collection of gates. Hereare some important examples.
• The Hadamard Gate

1
H=√
2



1 1
1 −1

mapping |0i to |+i and |1i to |−i (and vice versa).

14• The Controlled-NOT (CNOT) gate, mapping |x, yi to |x, x ⊕ yi (where ⊕ represents XOR).

1 0 0 0
 0 1 0 0 
CNOT =  0 0 0 1 
0 0 1 0As an example, the following circuit diagram represents a Hadamard gate on the first qubit
providing the “control” for a CNOT applied to the second qubit.
|x1 i

H

•

|x2 i

Composition of gates corresponds to multiplying the relevant unitary matrices. Continuingwith this example, applying this circuit to the input |xi = |00i yields√ √   √ 
1/ 2
0√ 1/ 20√
1 0 0 01/ 2
1
 0 1 0 0  0
 0   0 
1/
2
0
−1/
2

 √
  = √ 0 0 0 1   1/ 2
0√ 1/ 20√   0   0√ 
0
0 0 1 0
1/ 2
0
1/ 2
0
−1/ 2
• The Toffoli gate, mapping |x, y, zi to |x, y, z ⊕ xyi.
• The Phase gate


P =

1 0
0 i



Let G be a finite set of gates. G is universal if we can use gates from G to approximate any
unitary U on any number of qubits to any desired precision. To give some examples:• {Toffoli,H,Phase} is universal.
• {CNOT, G} is universal for almost any 1-qubit gate G—i.e., with probability 1 over the set of
2-by-2 unitary matrices G.
• In particular, {CNOT, G} is universal, for
3/5 4i/5G=
4/5 −3i/5• {Toffoli,H} is not universal, since these are both matrices over R. However, this set isnonetheless sometimes called “universal for quantum computing” since it densely
P generates
therealorthogonalgroup.
Thisisreasonable,
since
one
can
“simulate”
the
state
x αx |xi by
P
Re(α
)|0xi
+
Im(α
)|1xi.
xxx• {CNOT,H,Phase} is not universal, since it turns out to generate only a discrete subgroup.
Furthermore, the celebrated Gottesman-Knill Theorem states that circuits over this set ofgates can be simulated in classical polynomial time (and in fact they can be simulated in thecomplexity class ⊕L [AG04]).
See Lecture 10 for more about universality of gate sets.
15

2.1.1The Solovay-Kitaev Theorem

We now state one of the most important results about quantum gates.
Theorem 2.1.1 (Solovay-Kitaev (see [DN05])). Given any physically universal gate set G and atarget unitary U , the number of G gates that are needed in order to approximate U to accuracy (entrywise) is logO(1) (1/), omitting dependence on the number of qubits n.
It is known that if G has certain special properties, then the number of gates drops down toO(log 1/), which is optimal (see [HRC02]).

2.2

Relations to Complexity Classes

We assume that the reader is familiar with the complexity class P (deterministic polynomial time).
The analogous probabilistic class BPP consists of all languages L ⊆ {0, 1}∗ for which there’s aTuring machine running in polynomial time, which takes as input a pair (x, y), where the length of
y is bounded by a polynomial in the length of x, such that
• if x ∈ L then Py [M (x, y) = 1] > 2/3, and• if x 6∈ L then Py [M (x, y) = 1] < 1/3(So in particular, for every x, the probability that M accepts x is bounded away from 1/2.) Languages
in BPP are considered easy to compute; indeed, it’s widely conjectured today that P = BPP. (See[IW97].)
By analogy, Bernstein and Vazirani [BV97] defined BQP, or Bounded-Error Quantum PolynomialTime, as the class of all languages efficiently decidable by quantum computers.
Definition 2.2.1. BQP is the class of languages L ⊆ {0, 1}∗ for which there exists a P-uniform
family of polynomial-size quantum circuits {Cn }n≥1 acting on p(n) qubits (for some polynomial p)
over some finite universal gate set G such that, for all n and for all x ∈ {0, 1}n ,x ∈ A =⇒ P[Cn accepts |xi ⊗ |0i⊗p(n)−n ] ≥ 2/3.

x 6∈ A =⇒ P[Cn accepts |xi ⊗ |0i⊗p(n)−n ] ≤ 1/3.

(The original definition given by Bernstein and Vazirani was in terms of “quantum Turingmachines.” But this definition, in terms of quantum circuits, is easier to work with and known tobe equivalent.)
As a first observation, the Toffoli gate can be used to implement universal classical computation(for example, by simulating a NAND gate). Hence, we can do error amplification like usual, by
repeating an algorithm several times and then outputting the majority vote. For this reason, theconstants 2/3 and 1/3 in the definition of BQP are arbitrary, and can be replaced by other constants(or even by, say, 1 − 2−n and 2−n ), exactly like for the classical probabilistic complexity class BPP.
Proposition 2.2.2. P ⊆ BQP
Proof. Again, we use {Toffoli} as our gate set. For every polynomial-time computable function f ,there’s a circuit using only Toffoli gates implementing the transformation |x, 0, 0m i 7→ |x, f (x), 0m i,
for some m bounded by a polynomial in the length of x.
16

Proposition 2.2.3. BPP ⊆ BQP.
Proof. On input x, using Hadamard gates, a quantum circuit can generate a sequence of random
bits y, which can then be fed into a circuit that simulates the (deterministic) operation of a BPP
machine M on input (x, y).

2.2.1

Classical Simulation of Quantum Computation

The complexity class GapP consists of all functions f : {0, 1}∗ −→ Z for which there’s a nondeterministic polynomial-time Turing machine M such that f (x) = AM (x) − RM (x), where AM (x) andRM (x) are the number of accepting and rejecting paths respectively of M on input x. Anotherdefinition of GapP is
GapP = {f − g : f, g ∈ #P.
Here #P is the class of functions f for which there’s a nondeterministic polynomial-time Turingmachine M such that f (x) counts the number of M ’s accepting paths on input x. In other words,#P is the class of all “combinatorial counting problems”—problems that involve counting thenumber of solutions to an NP search problem.
GapP has several useful closure properties. For instance, if g(x, y, i) is a GapP function and
F (x, y, i, a1 , . . . , aq(n) ) can be computed by using (x, y, i) to build (in polynomial time) an unbounded
fan-in arithmetic formula of depth O(1) and then applying the formula to the integers (a1 , . . . , aq(n) )(for some polynomial q), the functionXh(x) =F (x, y, g(x, y, 1), g(x, y, 2), . . . , g(x, y, q(n)))
y∈{0,1}q(n)is in GapP. (In the application below, the function g(x, y, 1), g(x, y, 2), . . . , g(x, y, q(n)) will represent
the real and imaginary parts of certain complex numbers, and F (. . .) will compute the real (orimaginary) part of their product. GapP and its closure properties are discussed in [FFK94].) The
class PP is the class of languages L that are definable by {x : f (x) > 0} for some function f ∈ GapP.
Theorem 2.2.4. BQP ⊆ PP.
Proof. To simulate a quantum circuit on a given input x, it suffices to estimate the probabilityp(x) that the final measurement of the output bit gives value 1. The state of the computation ofp(n)a quantum circuit after each gate is described by a vector |zi in the Hilbert space C2
wherep(n) is the number of qubits that the circuit acts on (including the input qubits,
output qubit, andP
ancilla qubits). As usual
we
write
such
a
state
vector
in
the
form
|αi
=
α
|zi
where z ranges
z z
P
p(n)
over {0, 1}. If |φi = z φz |zi is the state at the conclusion of the computation then p(x) is thesum of |φz |2 over all z whose output bit is set to 1.
Each gate of the circuit acts on the quantum state via a unitary matrix. Thus |φi =Ut Ut−1 . . . U1 |σi where |σi = |σ(x)i is the initial state of the qubits and Uj is the unitary matrix corresponding to the jth gate. The entries of the matrices Uj are complex, but we will represent
them by pairs of dyadic rational numbers (where these dyadic rationals are close approximations to
the real and imaginary parts of the actual entries, and we assume without loss of generality thatthe denominators of all entries are the same power of two).
If P is the diagonal matrix such that Pz,z is equal to the value of the output bit corresponding
to basis state z then the acceptance probability p(x) satisfies:17

p(x) = hσ|U1−1 · · · Ut−1 P Ut · · · U1 |σi,
Using the standard connection between matrix multiplication and counting the number ofpaths in a graph, we can observe that p(x) is the sum (over all paths p from the start vertex to the terminal vertex in the graph) of the product of the edge weights encountered alongpath
P Qp (where the edge weights are given by the product of the edge weights. That is, p(x) =pi (weight of the i-th edge along path p).
Each of the matrices appearing in this product is exponentially large, but succinctly described:
for any basis states y, z the y, z entry of any of the matrices can be computed in time polynomial inn. Furthermore, by the closure properties of GapP discussed above and the fact that the entries ineach matrix have the same denominator, it follows that p(x) = f (x)/2q(n) for some polynomial q
and GapP function f . Thus p(x) > 1/2 if and only if f (x) − 2q(n)+1 > 0. Since f (x) − 2q(n)+1 is a
GapP function, this completes the proof.
It’s known that PP ⊆ P#P ⊆ PSPACE ⊆ EXP, where #P is the class of all combinatorial counting
problems, PSPACE is the class of problems solvable by a classical computer using polynomial memory,
O(1)and EXP is the class of problems solvable by a classical computer using 2ntime. So to summarize,
we haveP ⊆ BPP ⊆ BQP ⊆ PP ⊆ P#P ⊆ PSPACE ⊆ EXP.
Or in words: “quantum computers are at least as powerful as classical computers, and at most
exponentially more powerful.” This means, in particular, that quantum computers can’t solve
uncomputable problems like the halting problem; they can “merely” solve computable problems up
to exponentially faster. It also means that, in our present state of knowledge, we have no hope ofproving unconditionally that BPP 6= BQP (i.e., that quantum computers are strictly more powerfulthan classical probabilistic ones), since any such proof would imply P 6= PSPACE, which would be
essentially as big a deal as a proof of P 6= NP. The best we can do is get evidence for BPP 6= BQP,e.g. by finding examples of BQP problems that are considered unlikely to be in BPP.
Remark 2.2.5. One can show that it’s possible to choose the gates of a quantum circuit so thatthe resulting unitaries have all of their entries in {0, ±1/2, ±1}. In this case the GapP computation
can be carried out without introducing any approximation errors. This implies that the above
simulation of BQP extends to the class PQP, which is the quantum analog of PP, and shows that
PQP = PP.
Remark 2.2.6. It’s also known that BQPSPACE = PSPACE: that is, quantum computers canprovide at most a polynomial savings in space complexity. This is because there’s a generalizationof Savitch’s theorem, by Papadimitriou from 1985 [Pap85], which gives PPSPACE = PSPACE. HerePPSPACE is like PP but for space, and contains BQPSPACE by essentially the same argument thatshows BQP ⊆ PP. This immediately implies the desired equivalence. More precisely, we get thatany quantum algorithm using space s can be simulated classically using space O(s2 ). Ta-Shma[TS13] provided a candidate example where using a quantum algorithm might indeed provide thisquadratic space savings.

18

2.2.2

Quantum Oracle AccessAs with classical computation, it’s illuminating to consider quantum computation relative to an
oracle. As usual, an oracle just means an arbitrary language A ⊆ {0, 1}∗ . For almost any naturalcomplexity class C, it makes sense to define C A , or C relativized to the oracle A: that is, C
augmented by the ability to submit any input x to an oracle, and find out immediately whetherx ∈ A. (More generally, we can also consider oracles that are functions A : {0, 1}∗ −→ {0, 1}∗ .)In the setting of quantum circuits, an oracle A is accessed using “oracle gates.” There are twodifferent definitions of oracle gates, which turn out to be equivalent to each other. In the first
definition, each basis state of the form |x, z, wi gets mapped to |x, z ⊕ A(x), wi. Here x is an input,
A(x) is the oracle’s response to that input, z is an “answer qubit” where A(x) gets written, ⊕denotes XOR (the use of which makes the oracle gate unitary), and w is a “workspace register,”consisting of qubits that don’t participate in this particular query. In the second definition, eachbasis state of the form |x, z, wi gets mapped to (−1)z·A(x) |x, z, wi. In other words, the amplitude
gets multiplied by A(x), if and only if z = 1. To see the equivalence of the two types of oracle gate,
we simply need to observe that either one becomes the other if we conjugate the |zi register by a
Hadamard gate before and after the query.
Oracles provide a lens for exploring the relationships among complexity classes. Given twocomplexity classes C1 and C2 with C1 ⊆ C2 , we can ask:(a) Does the containment hold relative to every oracle?
(b) Are there oracles relative to which C1 = C2 ?
(c) Are there oracles relative to which C1 6= C2 (i.e., the containment is strict)?
It’s routine to show that the containments BPP ⊆ BQP ⊆ PSPACE hold relative to any oracle.
Since there are oracles A such that PA = PSPACEA (e.g., any PSPACE-complete oracle), it also
follows that BPPA = BQPA for those oracles. This leaves the third question: are there oracles
relative to which BPP is strictly contained in BQP?
The answer is yes. Bernstein and Vazirani [BV97] constructed an oracle A and a language
L ∈ BQPA , such that any classical randomized algorithm to decide L must make Ω(nlog n ) queries
to A. This was later improved by Simon [Sim94], who found an exponential separation between
quantum and classical query complexities.
In the rest of this lecture, we’ll state Simon’s problem and see why a quantum algorithm achieves
an exponential speedup for it. Then, in Lecture 3, we’ll put Simon’s problem into the more generalframework of the Hidden Subgroup Problem (HSP).
In Simon’s problem, we’re given oracle access to a function f : {0, 1}n −→ {0, 1}n , mapping
n-bit inputs to n-bit outputs. We’re promised that either(i) f is 1-to-1, or(ii) there exists a “secret string” s 6= 0n , such that for all x 6= y, we have f (x) = f (y) if and only
if x ⊕ s = y (where ⊕ denotes bitwise XOR).
The problem is to decide which, by making as few queries to f as possible.
Using a classical randomized algorithm, it’s not hard to see that Θ(2n/2 ) queries are necessary
and sufficient to solve this problem with high probability. (Note that, in oracle or query complexity,
19

as opposed to “ordinary” computational complexity, we can actually prove such exponential lower
bounds unconditionally, and on a routine basis!)
To see the sufficiency: we just keep querying f (x) for randomly chosen inputs x, until we happen
to have found a pair x =6 y such that f (x) = f (y), at which point we know that f is 2-to-1 andcan stop. If we don’t find such a collision pair after 2n/2 queries, then we guess that f is 1-to-1.
This works because of the famous Birthday√Paradox: if f is indeed 2-to-1, then we have constantprobability of√finding a collision pair after 2n = 2n/2 queries, for exactly the same reason why, ina room with 365 people, there’s a decent chance that at least two of them share a birthday.
To see the necessity: suppose that with 1/2 probability, f is a random 1-to-1 function from{0, 1}n to itself, and with 1/2 probability, it’s a random function satisfying condition (ii) above(with s 6= 0n chosen uniformly at random). It’s not hard to show that for any choice of queries, thedecision rule that minimizes the overall probability of error is to guess we’re in case (i) if and only if
the answers to all queries are different. But if the algorithm makes q queries to f , then in case (ii),the probability of answering correctly is at most the expected number of collision pairs (i.e., x 6= ysuch that f (x) = f (y)). This is q(q − 1)2n−1 , which is o(1) if q = o(2n/2 ).
On the other hand, there’s a quantum algorithm for Simon’s problem that uses only O(n) queries
to f , and nO(1) computational steps in total. That algorithm is as follows:(1) Prepare an equal superposition over all 2n possible inputs to f :X1√|xi|0n i.
2n x∈{0,1}n(2) Query f in superposition to get
X1√|xi|f (x)i.
2n x∈{0,1}n
We don’t actually care about the value of f (x); all we care about is what the computation off (x) does to the original |xi register.
(3) Measure the |f (x)i register (this step is not actually necessary, but is useful for pedagogical
purposes). If f is 1-to-1, then what’s left in the |xi register will be a single computational
basis state, |xi. If f is 2-to-1, then what’s left will be an equal superposition over two inputs
x and y with f (x) = f (y) and hence y = x ⊕ s:
|xi + |yi√.
2
The question now is: in case (ii), what measurement of the above superposition will tell us
anything useful about s? Clearly measuring in the computational basis is pointless, since sucha measurement will just return x or y with equal probability, revealing no information abouts. If we could measure the state twice, and see x and y, then we could compute s = x ⊕ y.
But alas, we can’t measure the state twice. We could repeat the entire computation from the
beginning, but if we did that, then with overwhelming probability we’d get a superposition
over a different (x, y) pair, so just like in the classical case, it would take exponentially many
repetitions before we’d learned anything about s.
20

(4) So here’s what we do instead. We apply Hadamard gates to each of the n qubits in the|xi register, and only then measure that register in the computational basis. What does
Hadamarding each qubit do? Well, it maps each basis state |xi toX1√(−1)x·z |zi.
2n z∈{0,1}nTherefore it maps √12 (|xi + |yi) to√1

X

2n+1 z∈{0,1}n(−1)x·z+y·z |zi.

When we measure the above state, which basis states z have a nonzero probability of being
observed? Well, any z for which the two contributions to its amplitude interfere constructively(i.e., are both positive or both negative), rather than interfering destructively (i.e., one ispositive and the other is negative). That means any z such thatx·z ≡y·z(mod 2).

That, in turn, means any z such that(x ⊕ y) · z ≡ 0(mod 2)— or equivalently, any z such that s · z ≡ 0 (mod 2). In conclusion, we don’t learn s when wemeasure, but we do learn a random z such that s · z ≡ 0—that is, a random mod-2 linear
equation that s satisfies.
(5) Now all that remains to do is to repeat steps (1) through (4) until we’ve learned enough abouts to determine it uniquely (assuming we’re in case (ii)). Concretely, every time we repeat
those steps, we learn another random linear equation that s satisfies:s · z1 ≡ 0

s · z2 ≡ 0(mod 2),(mod 2),...

We just need to continue until the only two solutions to the linear system are 0n and s itself.
A simple probabilistic analysis shows that, with overwhelming probability, this will happen
after only O(n) repetitions. Furthermore, we can easily check whether it’s happened, using
Gaussian elimination, in classical polynomial time. Thus, our overall algorithm uses O(n)quantum queries to f and polynomial computation time (with the latter dominated by classicalcomputation).

21

Lecture 3
Hidden Subgroup and Complexity of States and Unitaries
Lecturer: Scott Aaronson

3.1

Scribe: Michal Koucký and Pavel Pudlák

Hidden Subgroup Problem

We’re now going to look at the so-called Hidden Subgroup Problem HSP (G) over a finite group G,
which is a generalization of Simon’s problem from Lecture 2. In the HSP, we’re given black-box
access to some function f : G → {0, 1}∗ , which is constant on each coset (let’s say, each left-coset)of some hidden subgroup H ≤ G. On different cosets the function must take different values. We
know G, but the only way we can learn about H is by querying f . The problem is to determine thesubgroup H, for example by a list of its generators, by querying f as few times as possible. Or, in acommon variant of the problem, we just want to determine whether H is trivial or nontrivial.
Simon’s algorithm, which we covered in Lecture 2, solves this problem in quantum polynomial
time in the special case G = Zn2 :Theorem 3.1.1 ([Sim94]). HSP (Zn2 ) ∈ BQPf .
(Exercise for the reader: check that HSP (Zn2 ) is just Simon’s problem.)
Shor’s famous factoring algorithm is directly inspired by Simon’s algorithm. Indeed, Shor’salgorithm gives a classical reduction from factoring an integer N = pq to a different problem,
Period-Finding over the integers.
In Period-Finding, we’re given black-box access to a function f : Z → Z, and we need todetermine the smallest k > 0 such that f (x) = f (x + k) for all integers x. In the case of Shor’salgorithm, the function f happens to be f (x) = ax mod N , for some randomly chosen a. Shormakes three crucial observations:(1) The function f (x) = ax mod N can be computed in polynomial time, using the well-known
trick of repeated squaring. Thus, in this case, there’s no need for an oracle; the “oracle function”
can just be computed explicitly.
(2) The period of f always divides (p − 1)(q − 1), the order of the multiplicative group modulo N .
For this reason, if we can solve Period-Finding for various choices of a, that gives us enoughinformation to determine p and q. (This step is just classical number theory; it has nothing to
do with quantum computing.)(3) We can solve Period-Finding in quantum polynomial time, indeed with only O(1) queries to f .
This is the “hard” step, and the only step that actually uses quantum mechanics. Much of
22

the technical difficulty comes from the fact that Z is infinite, so we have to work only witha small finite part of Z by cutting it off somewhere. These issues are why Shor’s algorithm“almost” but doesn’t quite fit into the HSP framework. However, while the details are more
complicated, conceptually Shor’s algorithm is extremely similar to Simon’s algorithm from
Lecture 2—just with a secret period r in place of the “secret string” s, and with a discrete
Fourier transform in place of Hadamarding each qubit.
This leads to:
Theorem 3.1.2 ([Sho97]). Integer Factoring (when suitably phrased as a decision problem) is in
BQP.
Shortly afterward, Kitaev generalized both Simon’s and Shor’s algorithms, to conclude that
HSP (G) can be solved in quantum polynomial time for any abelian group G.
Theorem 3.1.3 ([Kit96]). For any finite abelian group G, HSP (G) ∈ BQPf .
Inspired by the success with abelian groups, many researchers tried to design quantum algorithms
for the HSP over various non-abelian groups. Unfortunately, after twenty years of effort, this program
has had very limited success, and almost all of it is for groups that are “close” in some way toabelian groups (for example, the Heisenberg group).
Why do people care about non-abelian HSP? One major reason is that the Graph Isomorphism
problem can be reduced to HSP over the symmetric group Sn . A second reason is that, as shown
by Regev [Reg04], the Approximate Shortest Vector problem can “almost” be reduced to HSP
over the dihedral group DN . (Here the “almost” is because Regev’s reduction assumes that the
HSP algorithm works via “coset sampling”: the approach followed by Simon’s algorithm, Shor’salgorithm, and essentially all other known HSP algorithms.)
Now, Graph Isomorphism and Approximate Shortest Vector are the two most famous “structured”
NP problems: that is, problems that aren’t known to be in P, but that also have strong theoreticalreasons not to be NP-complete, and that therefore plausibly inhabit an “intermediate zone” between
P and NP-complete. Assuming tentatively that NP 6⊂ BQP, which many people believe, these“structured” NP problems constitute a large fraction of all the interesting problems for which one
could hope to design a quantum algorithm with an exponential speedup over classical algorithms.
In the Graph Isomorphism (GI) problem, we’re given as input two n-vertex graphs G and H(say, by their adjacency matrices), and the problem is just to decide whether G ≡ H. The reduction
from GI to HSP (Sn ) is simple and works as follows. Given G and H, We define a function f from
S2n into graphs on 2n vertices as follows: f (σ) is the graph obtained by permuting by σ the disjoint
union of G and H. Determining whether the hidden subgroup of f can interchange the vertices of
G and H answers whether G and H are isomorphic. Since f can be computed easily given G and
H, a polynomial-time quantum algorithm for HSP (Sn ) would imply GI ∈ BQP.
(Of course, now we have Babai’s classical quasi-polynomial algorithm for GI [Bab16], which
implies a quantum quasi-polynomial algorithm for the same problem! But besides reducing quasipolynomial to polynomial, a quantum algorithm for HSP (Sn ) would also yield solutions to numerous
other isomorphism problems, like isomorphism of rings, multivariate polynomials, and linear codes,
which Babai’s algorithm doesn’t address.)
Meanwhile, a lattice is a set of vectors in Rn that’s closed under integer linear combinations. In
the Approximate Shortest Vector problem, the goal is to find a nonzero vector in a lattice L that’s at23√most a factor (say) n longer than the shortest nonzero vector in L. This problem is closely related
to solving HSP over the dihedral group Dn . A fast quantum algorithm for Approximate Shortest
Vector would mean that many of the public-key cryptographic schemes that weren’t yet broken
by Shor’s factoring algorithm would be broken by quantum computers as well. So for example,
the security of the Regev and Ajtai-Dwork cryptosystems, as well as Gentry’s fully homomorphic
encryption [Gen09], are based on the hardness of Approximate Shortest Vector or variants thereof.
Why might one even hope for a fast quantum algorithm to solve HSP over nonabelian groups?
In 1997, Ettinger, Høyer and Knill [EHK04] showed that at least from the perspective of querycomplexity, quantum computing is powerful enough. Indeed, using only polynomially (in log |G|)
many queries to f , a quantum algorithm can extract enough information to solve HSP (G) for any
finite group G, abelian or not. In Ettinger-Høyer-Knill’s algorithm, the post-processing after thequeries to f takes exponential time, but doesn’t require any extra queries to f .
Theorem 3.1.4 (Ettinger, Høyer, Knill 1997 [EHK04]). For every group G, HSP (G) is solvablewith O(log2 |G|) quantum queries to f . Furthermore, the queries can be efficiently constructed.
Proof. Take

1 X
p|xi|f (x)i.
|G| x∈G

Measure |f (x)i. We get, for some g ∈ G,

1 X
p
|ghi.
|H| h∈H

Call this state |gHi. More precisely, we’ll have a mixed state given by the density matrix
ρH := Eg [|gHihgH|].
For k = O(log2 |G|), repeat this procedure k times to get ρ⊗k
H . This is the only part that queries f .
Claim 3.1.5. ρ⊗k
H information-theoretically determines H.

This follows from the fact that G has ≤ |G|log |G| subgroups (because every subgroup has at
most log |G| generators).
Let H1 , . . . , Hr be a listing of all subgroups in decreasing order. Define measurements Mi suchthat Mi accepts ρHi and rejects ρHj for j > i with probability
1−1|G|log |G|.

Define Mi using the projection operator on the space spanned by {|gHi i ; g ∈ G}. Then if H ≥ Hi
it accepts with certainty. Otherwise it rejects with probability at least 1/2. (This is because|hHi |Hj i| ≤ √12 as can be easily verified.) If we use ρ⊗k
H , then we reject with probability
1−

1
1
≥1−
k
log
2
|G| |G|in the second case. Note that if i is the first one such that H ≥ Hi , then H = Hi . By the Quantum
Union Bound (Lemma 1.3.3), we can do all measurements Mi and almost preserve the state until
some Mi accepts.
24

3.2

Circuit Complexity

Can the EHK measurement be performed by a polynomial size quantum circuit? Could it be done
under some wild complexity assumption? For example, if P = PSPACE, then does it follow that
HSP (G) ∈ BQPf for all finite groups G?
(This question is interesting only for black-box access to G, as HSP (G) is clearly in NP for
explicit presentations of G.)
To investigate such questions, let’s now formally define a measure of quantum circuit complexity.
Definition 3.2.1. Given an n-qubit unitary transformation U , we let C (U ) be minimum size of aquantum circuit (say, over {H, P, Toffoli}) needed to implement U to entry-wise precision  (say, = 2−n ).
What can we say about this measure? Given a Boolean function f : {0, 1}N → {0, 1}, let
Uf : |x, ai 7→ |x, a ⊕ f (x))i. Then the following can be established by a standard counting
argument.
nObservation 3.2.2. There are 22 Boolean functions f , but only ≤T O(T ) quantum circuits withn
≤ T gates. Hence, for almost every f , we must have C (Uf ) = Ω 2n .
The above observation also holds if we relax the error  in approximating U to, say, 1/3. The
counting argument works because we have a discrete set of gates; for a continuous set of gates, wewould instead use a dimension argument (as mentioned in Lecture 2).
Observation 3.2.3. If f ∈ BQP, then C (Uf ) ≤ nO(1) . Thus, strong enough lower bounds on
C (Uf ) would imply ordinary complexity class separations.
Question 3.2.4. Are there unitaries U for which C (U ) > nω(1) would not imply anything aboutstandard complexity classes (e.g., P 6= PSPACE)—that is, for which we have a hope of proving
superpolynomial lower bounds on C (U ) unconditionally?
The above question is really asking: how hard is it to prove exponential lower bounds on quantum
circuit complexity for explicitly-given unitary matrices? To be more concrete, we could for example
ask: is there a “natural proof” barrier [RR97] for this lower bound problem? By this we mean:
are there polynomial-size quantum circuits that give rise to 2n × 2n unitary matrices that can’t bedistinguished from Haar-random U , say by any 2O(n) -time classical algorithm with access to theentries of the matrix? A natural guess is that such circuits exist, as a randomly-chosen quantum
circuit seems to produce such a matrix. But it remains open whether this could be shown undersome standard cryptographic assumption.
We can also study the quantum circuit complexity of unitary transformations relative to an
oracle A:
Definition 3.2.5. We let CA
 (U ) be the minimum size of a quantum circuit with A-oracle gatesthat -approximates U .
We can now state one of Scott’s favorite open problems about the complexity of unitarytransformations, a problem that will show up over and over in this course:
Question 3.2.6. The Unitary Synthesis Problem. Is it true that for every n-qubit unitaryO(1) ? (Here A is a Boolean function,transformation U , there exists an oracle A such that CA
 (U ) ≤ nwhich can take inputs that are more than n bits long—as it must, for counting reasons.)
25

What we’re here calling the Unitary Synthesis Problem was first raised in a 2006 paper of
Aaronson and Kuperberg [AK07]. They conjectured that the answer is no: that is, that there exist
unitaries (for example, Haar-random unitaries) that can’t be implemented in BQPA for any Boolean
oracle A. However, the best they were able to prove in that direction was the following:
Theorem 3.2.7 (Aaronson-Kuperberg [AK07]). There exist n-qubit unitaries U such that, forall oracles A, a polynomial-time quantum algorithm cannot implement U with just one query toA, assuming that the algorithm must implement some unitary matrix on the n qubits in question
regardless of which A it gets.

3.3

Quantum State Complexity

Now, let’s look at the complexity of generating a prescribed quantum state, as opposed to implementing a prescribed unitary matrix.
Definition 3.3.1. Given an n-qubit state |ψi, we let C (|ψi) be the minimum size of a quantum
circuit (over the set {H, P, Toffoli}) that maps |0i⊗m , for some m > n, to a state ρ such thatkρ − |ψihψ| ⊗ |0 · · · 0ih0 · · · 0|ktr ≤ .
If we allow garbage in the ancilla bits (and only consider the trace distance between the first n
qubits and |ψihψ|), then we call the measure C∗ (|ψi).
For general circuits, it’s not known whether there’s a separation between C and C∗ , or whether
it’s always possible to remove garbage. We know how to remove garbage in situations like this:|xi|garbage(f (x))i|f (x)iby copying the classical bit f (x)|xi|garbage(f (x))i|f (x)i|f (x)iand then undoing the computation of f to get |xi|00 · · · 0i|0i|f (x)i. However, in the case ofcomputing a quantum state |ψx i,|xi|garbage(ψx )i|ψx i,
we don’t know how to remove the garbage, since by the No-Cloning Theorem we can’t copy thequantum state |ψx i.
Question 3.3.2. Is there any plausible candidate for a separation between C (|ψi) and C∗ (|ψi)?
We now make some miscellaneous remarks about quantum state complexity.
First, just like with unitaries, it’s easy to show, by a counting argument, that almost all n-qubit
states |ψi satisfy C (|ψi) = 2Ω(n) . The challenge is whether we can prove strong lower bounds
on the circuit complexities of specific states. (But we’ll also see, in Lecture 3, how this challenge
differs from the analogous challenge for unitaries, by being more tightly connected to “standard”
complexity theory.)
Second, any state with large circuit complexity must clearly be highly entangled, since (forexample) any n-qubit separable state |ψi satisfies C (|ψi) = O(n). However, it’s important to26

understand that the converse of this statement is false; complexity is not at all the same thing as
entanglement. To illustrate, the state|00i + |11i ⊗n√
2
has a maximal entanglement for any state with the same number of qubits, but its complexity istrivial (only O(n)).
Fourth, it’s probably easy to prepare quantum states that have exponential circuit complexity,
using only polynomial time! The difficulty is merely to prepare the same complex state over and overagain. To illustrate this point, consider the following procedure: apply a random quantum circuit
to n qubits, initially set to |0i⊗n . Then measure the first n/2 qubits in the computational basis,
obtaining some outcome x ∈ {0, 1}n/2 . Let |ψx i be the resulting state of the remaining n/2 qubits.
As far as anyone knows, this |ψx i will satisfy C (|ψx i) = 2Ω(n) with overwhelming probability.
Fifth, here’s an extremely interesting open question suggested by Daniel Roy.
Question 3.3.3. Do there exist |ψi, |φi such that hψ|φi = 0,|ψi|ψi + |φi|φi√≤ nO(1) ,C
2but
C(|ψi), C(|φi) > nO(1) ?
The copies of |ψi and |φi are important because otherwise the problem is trivial: let |ψi satisfy
C(|ψi) > nO(1) . Then|0i⊗n + |ψi |0i⊗n − |ψi
√
√
,
2
2
both have exponential quantum circuit complexity, but a linear combination of the two (namely|0i⊗n ) is trivial.
Sixth, here’s a useful, non-obvious proposition about the behavior of quantum circuit complexity
under linear combinations (a version of this proposition is proven in Aaronson [Aar04], but probably
it should be considered “folklore”).
Proposition 3.3.4. If hψ|φi = 0, thenC(α|ψi + β|φi) ≤ O(C(|ψi) + C(|φi) + n).
Proof. It’s easy to prepare
α|0i|ψi + β|1i|φi.
(We’re ignoring the ancilla bits that should be put to 0.) Let U and V denote the unitary operators
used to construct |ψi and |φi respectively. Then the above state is
α|0iU |0i⊗n + β|1iV |0i⊗n .
Applying U −1 , we get
α|0i|0i⊗n + β|1iU −1 V |0i⊗n .
27

(3.1)

According to our assumption, we have
0 = hψ|φi = h0|⊗n U † V |0i⊗n = h0|⊗n U −1 V |0i⊗n .
Hence the amplitude of |0i⊗n in U −1 V |0i⊗n is 0. Let W be the unitary operator that implements
the reversible Boolean function(a0 , a1 , . . . , an ) 7→ (a0 ⊕ OR(a1 , . . . , an ), a1 , . . . , an ).
Applying W to (3.1) we switch 1 to 0:
α|0i|0i⊗n + β|0iU −1 V |0i⊗n .
Applying U we get
α|0iU |0i⊗n + β|0iV |0i⊗n ,which is the state we needed (with an extra ancilla bit |0i).
We remark that Proposition 3.3.4 can be generalized to any pair of states |ψi, |φi satisfyingkhψ|φik < 1 − ε, although in that case we pick up a multiplicative O(1/ε) factor in the circuit
complexity.

3.3.1

State Versus Unitary Complexity

So far, we discussed the problem of determining the circuit complexity of a given n-qubit unitarytransformation, and we introduced the Unitary Synthesis Problem: for every unitary U , does
there exist an oracle A such that U can be implemented in nO(1) time with oracle access to A?
We also discussed the closely-related question of whether, if (say) P = PSPACE, large classesof explicitly-describable n-qubit unitary transformations would then have nO(1) quantum circuit
complexity.
We then moved on to discuss the complexity of quantum states. Let’s now show that, in thesetting of quantum state complexity, the two problems mentioned in the previous paragraph bothhave positive answers.
Proposition 3.3.5. For every n-qubit state |ψi, there exists an oracle function A : {0, 1}∗ −→ {0, 1}
O(1) .
such that CA
 (|ψi) ≤ n
Proof. Suppose the state is|ψi = Σx∈{0,1}n αx |xi.
p
For initial prefixes of x of length w, |w| < n, define βw := Σy |βwy |2 . Suppose we knew β0 and β1 ,square roots of probabilities that the first qubit is either 0 or 1. Then we could prepare β0 |0i + β1 |1i.
Next, recurse: conditioned on the first qubit being |0i, we can put the second qubit in an
appropriate state. Continue in this way. Map β0 |0i + β1 |1i to




β00
β01
β01
β11
β0 |0i|0i +|1i + β1 |1i
|0i +
|1i ,
β0
β0
β0
β1
and so on. Then, as a last step, apply phases: letting γx := αx /kαx k, map each basis state |xi with
αx 6= 0 to γx |xi.
All we need now is an oracle A that encodes all of the βx ’s and γx ’s.
28

Proposition 3.3.5 illustrates the difference between the complexity of states and the complexityof unitaries. Some people assert that the two must be equivalent to each other, because of theso-called Choi-Jamiolkowski isomorphism, according to which the maximally-entangled stateN

1 X|ψU i := √|iiU |ii
N i=1
encodes all the information about the unitary transformation U . However, the issue is that there
might be easier ways to prepare |ψU i, other than by first preparing |ψI i and then applying U to thesecond register. To illustrate this, let σ : {0, 1}n → {0, 1}n be a one-way permutation—that is, apermutation that’s easy to compute but difficult to invert—and consider the stateX1|φi = √
|xi|σ(x)i.
2n x∈{0,1}nThis state is easy to make if we can first prepare |xi in the first register and then, conditioned
onP
that, prepare |σ(x)i in the second register. By contrast, suppose we needed to start with x |xi|xi,
and then map that to |φi by applying a unitary transformation to the second register only (with noaccess to the first register). To do that, we’d need the ability to pass reversibly between |xi and|σ(x)i, and therefore to invert σ. (See also Lecture 7, where this distinction shows up in the context
of AdS/CFT and wormholes.)As a further observation, given any n-qubit unitary transformation U , there’s an oracle A,
relative to which a polynomial-time quantum algorithm can apply an n-qubit unitary V that agrees
with U on any nO(1) rows. (The proof of this is left as an exercise.)
An interesting open problem is whether Proposition 3.3.5 is tight in terms of query complexity:
Question 3.3.6. For every n-qubit state |ψi, does there exist an oracle A such that |ψi can beprepared by a polynomial-time quantum algorithm that makes o(n) queries to A? What about 1
query to A?
Proposition 3.3.5 has the following corollary.
Corollary 3.3.7. If BQP = P#P , then C (|ψi) ≤ nO(1) for essentially all the explicit states |ψiwe’ll talk about.
Proof. For any |ψi whose amplitudes are computable in #P, we can use the recursive constructionof Proposition 3.3.5 to compute the βx ’s and γx ’s ourselves.
Corollary 3.3.7 means that, if we want to prove C (|ψi) > nO(1) for virtually any interesting state|ψi, then at a minimum, we’ll also need to prove BQP 6= P#P . For this reason, it might be easier toprove superpolynomial lower bounds on the complexities of unitaries than on the complexities ofstates.

29

Lecture 4
QSampling States and QMA
Lecturer: Scott Aaronson

4.1

Scribe: Valentine Kabanets and Antonina Kolokolova

QSampling States

In theoretical computer science, an efficiently samplable distribution means a probability distribution
over n-bit strings that we can sample, either exactly or approximately, by a classical algorithm
running in nO(1) time. (Here we’ll assume we’re in the setting of nonuniform complexity.) To give
two examples, the uniform distribution over perfect matchings of a bipartite graph G, and theuniform distribution over points in a polytope in Rn (truncated to some finite precision), are both
known to be efficiently samplable.
Now let D = {px }x be an efficiently samplable distribution. Then we can associate with D thequantum stateX √|ψD i =
px |xi,x∈{0,1}nwhich following Aharonov and Ta-Shma [ATS03], we call the QSampling state for D. We can thenask about the quantum circuit complexity of preparing |ψD i.
We do know that there’s a classical polynomial-time algorithm that takes as input a random
string r, and that outputs a sample xr from D. Suppose krk = m = nO(1) . Then by uncomputing
garbage, it’s not hard to give a polynomial-size quantum circuit that prepares a state of the formX1√
|ri|xr i.
2m r∈{0,1}m
Crucially, though, the above state is not the same as |ψD i! The trouble is the |ri register, which acts
as garbage—and not only that, but necessarily decohering garbage, for which we might introduce
the term nuclear waste (to distinguish it from garbage unentangled with the |xr i register).
Aharonov and Ta-Shma [ATS03] gave some nontrivial examples where a QSampling state canbe prepared by a polynomial-size quantum circuit, without the “nuclear waste.” For example, they
showed that given as input a bipartite graph G, one can efficiently prepare (close to) an equalsuperposition over all the perfect matchings of G. The proof of that required examining the detailsof the Markov Chain Monte Carlo algorithm of Jerrum, Sinclair, and Vigoda [JSV04], which is whatshowed how to sample a perfect matching. In other cases, however, we might have distributions
that are samplable but not QSamplable (though every QSamplable distribution is samplable).
But why do we even care about the distinction between the two? Why is getting rid of “nuclear
waste” important? Well, consider the following example.
30

Let G be a graph on n vertices. Let DG be the uniform distribution over all permutations ofvertices of G:{σ(G)}σ∈Sn .
The quantum version of this distribution is:X
1|σ(G)i,|ψDG i = p·
n!/|Aut(G)| σwhere σ(G) represents the result of applying the permutation σ to the vertices of G, and the sum
includes only one σ in each orbit.
(If G is rigid—i.e., has no non-trivial automorphisms—then |ψDG i will be a superposition over
all n! permutations of the G. Otherwise, it will be a superposition over n!/|Aut(G)| permutations,since there will be collisions.)
Claim 4.1.1. If C (|ψDG i) ≤ nO(1) via a uniform polynomial time algorithm, then Graph Isomorphism is in BQP.
Proof. Given n-vertex graphs G and H, we need to decide whether G ∼= H. Suppose we can prepare|ψDG i and |ψDH i. Then we can also prepare|0i|ψDG i + |1i|ψDH i√.
2
After doing so, apply a Hadamard gate to the first qubit to switch to the |+i, |−i basis, and thenmeasure the first qubit. As happens over and over in quantum information, we can use this trick totest whether the states |ψDG i and |ψDH i are equal or orthogonal.
In more detail, if |ψDG i = |ψDH i, then we obtain |+i ⊗ |ψDG i. Therefore we always see |+i.
Otherwise, if |ψDG i and |ψDH i are orthogonal, then we obtain the maximally mixed state in thefirst qubit. So in this case, we see a random bit.
If G ∼= H, then |ψDG i = |ψDG i, and otherwise these states are orthogonal, because they aresuperpositions over disjoint sets.
By contrast, note that if all we knew how to prepare was the “nuclear waste state”
1 X√|ri|xr i,2n rthen the two states could be orthogonal even when the graphs were not isomorphic. This is why weneed QSampling.
O(1)Note that, even given Babai’s breakthrough n(log n)algorithm for Graph Isomorphism [Bab16],
it’s still unclear how to prepare the QSampling states for GI in less than exponential time.
Observation 4.1.2. Suppose NP ⊆ BQP. Then C1/nO(1) (|ψD i ≤ nO(1) for every samplable distribution D. In other words, there is a weaker assumption than the BQP = P#P of Corollary 3.3.7,
which would make QSampling states easy to generate to within 1/nO(1) precision.
Proof. The approximate counting result of Stockmeyer [Sto83] says that, in BPPNP , one canapproximate any #P function to within a small multiplicative error. The βx numbers from therecursive sampling procedure of Proposition 3.3.5 are in #P.
31

Let’s now give a substantial generalization of Claim 4.1.1, due to Aharonov and Ta-Shma[ATS03].
Theorem 4.1.3 (Aharonov and Ta-Shma [ATS03]). Suppose QSampling states can be prepared inquantum polynomial time. Then SZK ⊆ BQP.
Here SZK is Statistical Zero-Knowledge: roughly speaking, the class of all languages L ⊆ {0, 1}∗
for which there exists a probabilistic protocol between Arthur and Merlin (a polynomial-time verifier
and an all-powerful but untrustworthy prover), whereby Arthur can be convinced that the input isin L without learning anything about the proof. The standard example of an SZK protocol is thefollowing protocol for Graph Non-Isomorphism:
Suppose Merlin wants to convince Arthur that two graphs, G and H, are not isomorphic.
Then Merlin says to Arthur: pick one of the graphs uniformly at random, randomly
permute its vertices, send it to me and I will tell you which graph you started with.
If Merlin always returns the right answer, then the graphs are almost certainly not
isomorphic—because if they were, then Merlin would give the right answer in each suchtest with probability only 1/2.
The class of all problems that have a protocol like that one is SZK.
Theorem 4.1.4 (Sahai-Vadhan [SV03]). The following problem, called Statistical Difference, is acomplete promise problem for SZK: Given efficiently samplable distributions D1 , D2 and promisedthat either kD1 − D2 k ≤ a or kD1 − D2 k ≥ b (where, say, a = 0.1 and b = 0.9), decide which.
For the proof of Theorem 4.1.4, we need b2 > a. So the “default constants of theoretical computerscience,” namely 1/3 and 2/3, turn out to work, but this is just a lucky coincidence!
Remark 4.1.5. The Hidden Subgroup Problem, for any group G, can be shown to be in SZK. But
SZK seems more general than HSP : an SZK problem need not have any group-theoretic structure.
Proof of Theorem 4.1.4. Because of [SV03], it suffices for us to say: Suppose we could prepare thestatesX √|ψD1 i =px |xi,x∈{0,1}nand|ψD2 i =X
x∈{0,1}n√qx |xi.

Then as before, make the state|0i|ψD1 i + |1i|ψD2 i√
2and measure the control qubit in the |+i, |−i basis. The probability to get the outcome |+i is thenP[|+i] =1 + RehψD1 |ψD2 i.
2Interestingly, the absolute phases of |ψD1 i and |ψD2 i (as determined by the procedures that
prepare them starting from |0i⊗n ) could actually matter in this test! But in any case, we can still32use the test to determine if the inner product is close to 1/2 (as it is in the orthogonal case) or far
from it.
There’s no classical analogue for this interference test. Interference matters: applying a Hadamard
gate to the control qubit gives|0i|ψD1 i + |1i|ψD2 i + |0i|ψD2 i − |1i|ψD1 i.
Cancellation happens only if |ψD1 i = |ψD2 i.
We have
X√
RehψD1 |ψD2 i =px qx = F (D1 , D2 ),xwhere the fidelity F (D1 , D2 ) satisfies the inequalities:
1 − ||D1 − D2 || ≤ F (D1 , D2 ) ≤p

1 − ||D1 − D2 ||2 .

Thus, if ||D1 − D2 || ≈ 1, then hψD1 |ψD2 i ≈ 0, while if ||D1 − D2 || ≈ 0 then hψD1 |ψD2 i ≈ 1.
In 2002, Scott proved that at least in the black-box or oracle model, there’s no efficient quantum
algorithm for SZK problems.
Theorem 4.1.6 ([Aar02]). There exists an oracle A such that SZKA 6⊂ BQPA .
This could be seen as strengthening an earlier result of Bennett et al. [BBBV97b]:
Theorem 4.1.7 ([BBBV97b]). There exists an oracle A such that NPA 6⊂ BQPA .
Theorem 4.1.6 was a corollary of a quantum lower bound for the following Collision Problem:
Given oracle access to a function f : {1, . . . , N } → {1, . . . , N }, where N is even and apromise that either f is 1-to-1 or 2-to-1, decide which. (This is a generalized version ofSimon’s problem, but without any group structure.)It’s easy to design a quantum algorithm that “almost” solves the collision problem with only 1query. To do so, we prepare the stateN

1 X√|xi|f (x)i.
N x=1
Just like in Simon’s algorithm, if we measure the |f (x)i register in the above state, then we’re left
with a state in the |xi register of the form
|xi + |yi√,2
for some (x, y) such that f (x) = f (y). If we could just measure the above state twice, to get bothx and y, we’d be done! The problem, of course, is that we can’t measure twice. We could repeat
the algorithm from the beginning, but if we did, we’d almost certainly get a different (x, y) pair.
In Simon’s algorithm, we were able to do an interference experiment that revealed a little bit ofcollective information about x and y—just enough so that, with sufficient repetitions, we could put
together the partial information to get what we wanted.
The result of Aaronson [Aar02] showed that the same isn’t possible for the Collision Problem:
33

Theorem 4.1.8 ([Aar02]). Any quantum algorithm for the Collision Problem needs Ω(N 1/5 ) queries.
√
This was improved by Yaoyun Shi [Shi02] to Ω(N 1/3 ), which is tight. (Classically, Θ( N )queries are necessary and sufficient.)
Now, observe that the Collision Problem is in SZK, via a protocol similar to that for Graph
Non-Isomorphism:
Arthur chooses a uniformly random x, then sends f (x) to Merlin and asks what x was.
If f is 1-to-1, then Merlin can always return the correct answer. If, on the other hand, f
is 2-to-1, then Merlin can answer correctly with probability at most 1/2. Furthermore, inthe honest case (the case that f is 1-to-1), Arthur gains zero information from Merlin’s
reply that he didn’t already know.
Another way to see that the Collision Problem is in SZK is to observe that it’s easily reducible
to the Statistical Difference problem (we leave this as an exercise for the reader).
Now, by Aharonov and Ta-Shma’s result, the fact that there’s an oracle separation between SZK
and BQP implies the following:
Corollary 4.1.9. There exists an oracle A relative to which there’s a samplable distribution D
that’s not QSamplable.
Ω(n) .
Indeed, one can get that relative to such an oracle, CA (|ψD i) ≥ 2

4.2

Quantum Witness States

Our second example of an interesting class of states is quantum witnesses. These are states that,when given to you, you can use to verify some mathematical statement—e.g., that an input x
belongs to a language L—efficiently.
Recall that MA (Merlin-Arthur) is the probabilistic generalization of NP: that is, it’s the classof languages L for which there exists a probabilistic polynomial-time algorithm A such that, for all
inputs x ∈ L, there’s a polynomial-size witness that causes A to accept x with probability at least
2/3, while for all x 6∈ L, no witness causes A to accept x with probability greater than 1/3. We
imagine an omniscient but untrustworthy wizard, Merlin, trying to convince a skeptical probabilistic
polynomial-time verifier, Arthur, of the statement x ∈ L. Unlike an oracle, Merlin can lie, so his
answers need to be checked.
We now define QMA, the quantum generalization of MA, which will lead us to the concept ofquantum witnesses.
Definition 4.2.1. QMA (Quantum Merlin-Arthur) is the class of languages L ⊆ {0, 1}n for which
there exists a polynomial-time quantum verifier V and polynomials r, q such that for all x:
x∈L⇒
x∈
/L⇒

∃|φx i P[V (x, |φx i, |00 . . . 0i) accepts ] ≥ 2/3∀|φi

P[V (x, |φi, |00 . . . 0i) accepts ] ≤ 1/3

Here, |φx i is a state on p(n) qubits, where n = |x|, and there are q(n) ancilla qubits |00 . . . 0i.
Note that, if some mixed state ρ causes Arthur to accept, then by convexity, at least one purestate in the mixture makes him accept with at least as great a probability. So we can assume
without loss of generality that Merlin’s witness is pure.
34

An obvious question is, can the completeness and soundness probabilities 2/3 and 1/3 in thedefinition of QMA be amplified, say to 0.999 and 0.001 (as they can for BPP and other probabilistic
complexity classes)?
The difficulty is that Arthur can’t reuse his witness state |φx i, since it will quickly become
corrupted. However, what Arthur can do instead is to ask Merlin for k witness states, check them
independently, and accept if at least (say) 60% cause him to accept. If x ∈ L, then Merlin can
simply give Arthur the same state k times, which will cause Arthur to accept with probability atleast 1 − 2−Ω(k) . If, on the other hand, x ∈/ L, any state of the form |φ1 i ⊗ · · · ⊗ |φk i will cause
Arthur to accept with probability at most 2−Ω(k) . One might worry that Merlin could entangle
the k witness states. If he does, however, that will simply make some of the witness states mixed.
Merlin would do as well or better by putting his “best” state, the state that maximizes Arthur’s
acceptance probability, in all k of the registers—and as we’ve seen, that state is pure without loss ofgenerality.
In 2005, Marriott and Watrous [MW05] proved a much more nontrivial result, with numerous
applications to QMA. We’ll simply state their result without proof.
Theorem 4.2.2 (Marriott and Watrous [MW05]). There exists a way to do in-place amplificationfor QMA: that is, to replace the (2/3, 1/3) probability gap by (1 − 2−k , 2−k ) for any desired k, byincreasing Arthur’s running time by an O(k) factor, and crucially, without increasing the size of thewitness state |φx i at all.

4.3

QMA-Complete Promise Problems

QMA can be seen as the quantum generalization of NP (or more precisely, as the quantum generalization of MA). Just like thousands of practical problems, in optimization, constraint satisfaction,etc., were shown to be NP-hard or NP-complete, so today there’s a growing list of quantum problems (albeit, so far merely dozens, not thousands!) that have been shown to be QMA-hard or
QMA-complete.
As a technicality, because of the (2/3, 1/3) gap in defining QMA, one needs to talk about
QMA-complete promise problems rather than QMA-complete languages—but that’s not a big deal
in practice. In fact, Goldrech [Gol06] has argued that complexity classes should have been definedin terms of promise problems in the first place, with languages just a special case. This point ofview is particularly natural in quantum complexity theory, where there are almost always naturalcomplete promise problems, but rarely natural complete languages.
Here’s the “original” QMA-complete promise problem, discovered by Kitaev (see [KSV02]), andlater improved by Kempe, Kitaev, and Regev [KKR06] among others.
Local Hamiltonians Problem (quantum generalization of MAX-2-SAT).
We’re given as input m two-outcome POVMs E1 , . . . , Em acting on at most 2 qubits
each out of n qubits total, as well as parameters q and ε ≥ 1/nO(1) . letA(|ψi) =nX
i=1

P[Ei accepts |ψi],and then let
p = max A(|ψi)|ψi35

The problem is to decide whether p ≥ q or p ≤ q − ε, promised that one of these is thecase.
Note that, if we restrict each Ei to measure in the computational basis, and either accept
or reject each of the four possibilities 00, 01, 10, 11 with certainty, then this problem
reduces to the NP-complete MAX-2-SAT problem.
It’s not hard to see that Local Hamiltonians is in QMA. The interesting part is the following:
Theorem 4.3.1 (see [KSV02]). Local Hamiltonians is QMA-complete. That is, any QMA problem
can be efficiently reduced to Local Hamiltonians.
We won’t prove Theorem 4.3.1 here. Intuitively, however, the result shows that ground states of
local Hamiltonians—or equivalently, solutions to “local” quantum constraint satisfaction problems,with constraints involving only 2 qubits each—can encode as much complexity as can arbitrary
quantum witness states.

4.4

Group Non-Membership

We’ll now give our first surprising example of a language in QMA—that is, of a class of mathematicalstatements that can be efficiently verified using quantum witnesses, but possibly not using classicalwitnesses.
Our example will involve the concept of a black-box group, which was introduced (like so much elsein this area) by Babai. A black-box group is simply a finite group G, typically of order exp(nO(1) ),for which we know polynomial-size strings labeling the generators hg1 , . . . , gk i, and also have accessto a black box that performs the group operations for us: that is, an oracle that returns the labels ofgroup elements gh and g −1 , given as input the labels of g and h. We also assume that this black box
can tell us whether two labels are of the same G element (or equivalently, that it can recognize alabel of the identity elements). In the quantum case, for reasons we’ll see, we’ll need one additional
assumption, which is that every element of G has a unique label.
The Group Membership Problem is now the following. In addition to the black-box groupG, we’re also given a subgroup H ≤ G, via a list of labels of its generators hh1 , . . . , hl i—as well as
an element x ∈ G. The problem is to decide whether x ∈ H.
We wish to decide this “efficiently”—by which we mean, in time polynomial in log |G|. Recall
that the group order |G| is thought of as exponential, and also that every finite group G has agenerating set of size at most log2 |G|.
We can easily produce more concrete examples of this problem, by replacing the black-box
groups G and H with explicit groups. For example: given a list of permutations of an n-element
set, decide whether they generate a target permutation. (In the 1960s, Sims [Sim70] showed how tosolve this problem in polynomial time.) Or: given a list of invertible matrices over a finite field,
we can ask whether they generate a given target matrix. (For this problem, Babai, Beals, andSeress [BBS09] gave a polynomial-time algorithm given an oracle for factoring—and therefore a
BQP algorithm—assuming the field is of odd characteristic.)
Let’s now consider the structural complexity of the Group Membership Problem. If x ∈ H, thenthere’s clearly a witness for that fact: namely, a sequence of operations to generate x starting fromthe generators hh1 , . . . , hl i of H. To make this witness efficient, we might need to introduce a newelement for each operation, and feed the new elements as inputs to later operations: for example,36

h3 = h1 h2 , then h4 = h23 h−1
1 h2 , etc. By a result of [BS84], there always exists such a “straight-line
program,” of size polynomial in log |H|, to prove that x ∈ H. Therefore Group Membership is inNP.
OK, but what if x is not in H? Does Group Non-Membership (GNM) also have NP witnesses?
In the black-box setting, the answer is easily shown to be “no” (indeed, it’s “no” even for cyclic
groups). For explicit groups, whether GN M ∈ NP is a longstanding open problem, related to theClassification of Finite Simple Groups and the so-called “Short Presentation Conjecture.”
But even if GN M 6∈ NP, that’s not the end of the story. Indeed, Babai observed that GN M
has an AM (Arthur-Merlin) protocol, in which Arthur sends a random challenge to Merlin and thenreceives a response.
Theorem 4.4.1. GN M ∈ AM.
Proof Sketch. The protocol involves yet another result of Babai [Bab91]: namely, given any blackbox group G, there is an algorithm, running in logO(1) |G| time, that takes a nearly-random walk on
G, and thus returns a nearly uniformly-random element g ∈ G.
Given this algorithm, Arthur simply needs to flip a coin, if it lands heads then sample a random
element from H, and if it lands tails then sample a random element from hH, xi (that is, the least
subgroup containing both H and x). Arthur then sends the element to Merlin and asks him how
the coin landed.
If x ∈ H then H = hH, xi, so Merlin must guess incorrectly with probability 1/2. If, on theother hand, x 6∈ H, then hH, xi has at least twice the order of H, so Merlin can guess correctly withprobability bounded above 1/2.
The above is actually a statistical zero-knowledge protocol, so it yields the stronger result that
GN M ∈ SZK.
On the other hand, one can show (see for example Watrous [Wat00]) that, at least in theblack-box setting, GN M 6∈ MA: that is, verifying group non-membership requires interaction.
Or it at least, it requires interaction classically! In 2000, Watrous discovered that Merlin canalso use quantum witnesses to prove group non-membership, without any need for answering randomchallenges from Arthur.
Theorem 4.4.2 (Watrous [Wat00]). GN M ∈ QMA.
Proof Sketch. The protocol is as follows. In the honest case, Merlin sends Arthur the “subgroupstate”
1 X|Hi = p|hi,
|H| h∈H
i.e. a uniform superposition over all the elements of H. Using |Hi together with the group oracle,
Arthur then prepares the state|0i|Hi + |1i|Hxi√,
2
where |Hxi is a uniform superposition over the elements of the right-coset Hx. (I.e., he puts acontrol qubit into the |+i state, then right-multiplies by x conditioned on the control qubit being|1i.) Then Arthur measures the control qubit in the |+i, |−i basis.

37

Just like we saw in Claim 4.1.1, if x ∈ H then H = Hx and |Hi = |Hxi, so this measurement will
always return |+i. If, on the other hand, x ∈/ H, then H and Hx are disjoint sets, so hH|Hxi = 0
and the measurement will return |+i and |−i with equal probability.
There is, however, one additional step: Arthur needs to verify that Merlin indeed gave him thesubgroup state |Hi, rather than some other state.
There’s no advantage for Merlin to send an equal superposition over a supergroup of H, sincethat would only decrease the probability of Arthur’s being convinced that x 6∈ H. Nor is there
any advantage in Merlin sending an equal superposition over a left-coset of such a group. Thus, itsuffices for Arthur to verify a weaker claim: that whatever state Merlin sent, it was (close to) an
equal superposition over a left-coset of a supergroup of H.
To verify this claim, as in the proof of Theorem 4.4.1, Arthur uses the result of Babai [Bab91]
that it’s possible, in classical polynomial time, to generate a nearly uniformly-random elementh ∈ H. Given a purported witness |ψi, Arthur generates such an element h, and then prepares thestate|0i|ψi + |1i|ψhi√,2where |ψhi is the state obtained by taking all the elements in the |ψi superposition and rightmultiplying them by h. Similar to the previous test, Arthur then measures his control qubit in the|+i, |−i basis, and accepts the witness state |ψi only if he observes the outcome |+i—in which case,|ψi is invariant under right-multiplication by random H elements, and hence (one can show) close
to a coset of a supergroup of H. Note that in the honest case, this test doesn’t even damage |ψi, so
Arthur can reuse the same state to verify that x 6∈ H.
Let’s make two remarks about the proof of Theorem 4.4.2.
First, we needed the assumption that every element of G has a unique label, because if thatassumption failed, then the states |Hi and |Hxi could have been orthogonal even in the case x ∈ H.
Second, given that (by Babai’s result) Arthur can efficiently sample a nearly-random H elementon his own, one might wonder why he needed Merlin at all! Why couldn’t he just prepare thewitness state |Hi himself? The answer, once again, is the “nuclear waste problem”: Arthur canefficiently prepare a state likeXr|ri|hr i,

where hr is a nearly-random H element. But the above state is useless for Watrous’s protocol,
because of the garbage register |ri. And it’s not known whether Arthur can remove |ri on his own;
he might need Merlin to provide the garbage-free state |Hi.
(We should mention that, even in the black-box setting, it remains an open problem whether
GN M ∈ BQP, so it’s conceivable that Arthur can always prepare |Hi on his own. But no one
knows how.)38

Lecture 5
QCMA, PostBQP, and BQP/qpoly
Lecturer: Scott Aaronson

Scribe: Adam Brown and Fernando Pastawski

In Lecture 4, we discussed quantum superpositions of the form
1 X
|hi,
|Hi := p|H| h∈H
where H is an exponentially-large finite group (say, a subgroup of a black-box group G). We saw
how such a superposition could be extremely useful if someone handed it to you (since you could use
it to decide membership in H in polynomial time), but also intractable to prepare yourself (becauseof the “nuclear waste” problem, and the distinction between sampling and QSampling).
In this lecture, we’ll look more closely at the question of whether being given a complicatedquantum state, one that you couldn’t prepare by yourself, can really enhance your computational
power. In particular, could it enhance your power beyond what would be possible if you were givena classical string of similar size?

5.1

QCMA

To study that question, we need to define one more complexity class: a cousin of QMA called QCMA,
which stands for the ironically-named “Quantum Classical Merlin Arthur.” QCMA is same thing as
QMA, except that now Merlin’s witness must be classical, while Arthur’s verification procedure canstill be quantum. Thus, QCMA provides an alternative quantum generalization of NP.
Clearly QCMA ⊆ QMA, since Arthur can simulate QCMA by immediately measuring a QMA
witness to collapse it onto a classical state or probability distribution thereof.

5.2

Bestiary

Before going further, let’s step back to explore how QCMA and QMA fit into the bestiary ofcomplexity classes.
There’s an interesting proof, which we won’t present here, that QMA ⊆ PP. There’s also a wholeplethora of classes such as QAM, where Arthur sends random challenge string to Merlin and Merlin
replies with a quantum state.
Then there’s QIP, the class of languages that admit a quantum interactive proof protocol, in whichquantum data can go back and forth between Arthur and Merlin for a polynomial number of rounds.
In a 2009 breakthrough, Jain, Ji, Upadhyay, and Watrous [JJUW11] showed that QIP = PSPACE:
that is, once we’re in the unbounded-round setting, quantum proofs give no advantage over classical39

Figure 5.1: Some relevant complexity classes, partially ordered by known inclusions.

proofs. On the other hand, Kitaev and Watrous [KW00] also showed that QIP(3) = QIP: thatis, 3-round quantum interactive proof protocols (an initial message from Merlin, a challenge from
Arthur, and then a response from Merlin) have the full power of unbounded-round systems, a
power that we now know to be simply PSPACE. Since classically, constant-round interactive proof
protocols give no more than AM, the ability to do all of QIP = PSPACE with only 3 rounds shows adramatic difference between the quantum and classical cases.

5.3

Grover’s Algorithm

Before continuing with our story, we’ll need one more extended digression, about the second most
famous quantum algorithm after Shor’s algorithm: namely, Grover’s algorithm [Gro96]!
Grover’s algorithm is usually presented
as a quantum algorithm to search a database of N√
records for a desired record in only O( N ) steps. More abstractly, the algorithm is given oracle
access to a Boolean function f : {1, . . . , N } → {0, 1}. Its goal is to decide whether there exists ani ∈ {1, ldots, N } such that f (i) = 1. Or, in a common variant, the algorithm needs to find i suchthat f (i) = 1, promised that there is a unique√ such i. In 1996, Grover [Gro96] gave a quantum
algorithm to solve this problem using only O( N ) queries to f . This is also known to be optimalfor quantum algorithms, by a result of Bennett, Bernstein, Brassard, and Vazirani [BBBV97a].
Just like the core of Shor’s algorithm is period-finding, the core of Grover’s algorithm is amore general procedure called amplitude amplification. In amplitude amplification, we consider two
nearly-orthogonal pure states |vi and |wi, which satisfy hv|wi| = ε. For the moment, we’ll assume
that ε is known, although this assumption can be lifted in “fixed-point” amplitude amplification.
We’re given a copy of |vi, and we want to convert it into |wi, or something close to |wi. To do this,we can use two quantum oracles: Uv = I − 2|vihv| and Uw = I − 2|wihw|.
The central result of amplitude amplification is that we can achieve this conversion task using40

only O(1/ε) queries to Uv and Uw , as follows:
1/ timesz}|{|wi ← . . . Uv Uw Uv Uw |vi|wi

Uv Uw |vi3✓|vip
✓ = arccos 1
|w? i

"⇡"

Uw |viFigure 5.2: The intermediate states in the relevant 2-dimensional subspace for amplitude amplification. This provides a “proof by picture” for why amplitude amplification works.
Why does amplitude amplification work? We can simplify the analysis by observing thatthe intermediate states are restricted to a purely 2-dimensional subspace: namely, the subspace⊥spanned by√ the basis states |vi and |wi (see Figure 5.3). Note that⊥|w i and |vi have an angle ofθ = arcos( 1 − ε) ≈ ε. Each reflection step increases the angle to |w i by θ and hence, the numberof steps to approach |wi is of the order 1/ε.
Grover’s algorithm works by taking the initial state to be the uniform positive superpositioni√over all basis states |vi = |1i+...+|Nand |wi = |ii be the basis state with index i such that f (i) = 1,Nthen we have ||vihw|| = √1N . Thus, amplitude amplification lets us find |ii in a time proportional to
√ 1
N.

5.4

QMA versus QCMAWith the complexity zoo and Grover’s algorithm out of the way, let’s now return to the complexity
class QCMA—and in particular, to the question of whether it equals QMA.
Since we saw in Lecture 4 that GN M ∈ QMA, one way to investigate this question is to ask
whether GN M ∈ QCMA. That is, in Watrous’s QMA protocol for Group Non-Membership, did theadvantage actually come from the quantum nature of the witness state |Hi? Or could one also
prove Group Non-Membership with a classical witness, verified using a quantum computer?
1

As a side remark, the state |vi does not by itself let us implement Uv , and this fact is used explicitly in quantum
money schemes (see Lectures 8 and 9). On the other hand, if we have some unitary U which prepares |vi, meaning forexample that U |0i = |vi, and we also have U −1 , then we can also implement Uv = U U0 U −1 , where U0 implements
the reflection around the |0i state.

41

One might hope to resolve this problem in an oracular way, by showing that any QCMA protocol
for Group Non-Membership would require Merlin to make a superpolynomial number of quantum
queries to the black-box group G. However, a result of Aaronson and Kuperberg [AK07] rules out
such an oracle lower bound, by showing that we actually can solve GN M using a QCMA protocolthat makes only logO(1) |G| queries to the group oracle.
Theorem 5.4.1 (Aaronson-Kuperberg [AK07]). There is a QCMA protocol for GN M that makes
polylog|G| queries to G, while using exponential post-processing time (in fact |G|polylog|G| ).
This is an “obstruction to an obstruction,” since it says that the QCMA query complexity of
GN M can only be lower-bounded by logO(1) |G|. I.e., even if GNM does not belong to QCMA,
we won’t be able to prove that using only query complexity: computational complexity would
necessarily also be involved.
To prove Theorem 5.4.1, we’ll need the following corollary of the Classification of Finite Simple
Groups:
Theorem 5.4.2. Any group of order exp(n) can be specified using nO(1) bits (in other words, thereO(1)k non-isomorphic groups of order k).
are most k log
We now sketch the proof of Theorem 5.4.1.
Proof Sketch for Theorem 5.4.1. The QCMA protocol works as follows. Merlin tells Arthur an
explicit model group Γ, which he claims is isomorphic to G. Merlin then needs to describe an
isomorphism Γ ≡ G in detail, and Arthur needs to verify the purported isomorphism. Once this isdone, Arthur can then verify that x ∈ H by simply checking that the corresponding statement istrue in the model group Γ, which requires no further queries to the G oracle.
In more detail, Merlin sends Arthur a list of generators e1 , . . . , ek ∈ Γ, with the property thatevery γ ∈ Γ can be written in the form eα1 1 . . . eαk k with k = polylog|Γ| and αi ∈ {0, 1}. Merlin also
tells Arthur a mapping ei → gi , which he claims can be extended to a full isomorphism between
the groups, ϕ : Γ → G. To define ϕ: for each element γ ∈ Γ, we take its lexicographically first
representation in the form γ = eα1 1 . . . eαk k , and then defineϕ(γ) := ϕ(eα1 1 ) . . . ϕ(eαk k ) = g1α1 . . . gkαk .
Merlin likewise gives Arthur a purported mapping from a model subgroup ∆ ≤ Γ to H ≤ G,
and from some element z ∈ Γ∆ to x ∈ G.
For simplicity, let’s restrict ourselves to how Arthur checks the claimed isomorphism ϕ : Γ → G(checking the other parts is analogous). There are two things that Arthur needs to check:
1. That ϕ is a homomorphism. According to a result by Ben-Or, Coppersmith, Luby,
and Rubinfeld [BOCLR04], this can be done efficiently by checking the homomorphism
ϕ(x · y) = ϕ(x) · ϕ(y) on randomly chosen inputs x and y. Even if it is not an exact
homomorphism, and this goes undetected by the test (which may only happen if there is an
epsilon fraction of incorrect entries, i.e. if it is close to a homomorphism), there is a further
theorem which guarantees that the map ϕ may actually be fixed into a homomorphism bytaking Φ(x) = majy ϕ(xy)ϕ(y −1 ) (i.e. simply taking some form of majority vote).

422. That the homomorphism is a 1-to-1 embedding. In other words, we must verify thatthe kernel of ϕ, or the subgroup of Γ mapping to the identity, is trivial. But this is just an
instance of the Hidden Subgroup Problem! (Indeed, the HSP with a normal subgroup, whichis thought to be easier than the general problem.) So we can use the algorithm of Ettinger,
Høyer, and Knill [EHK04] (Theorem 3.1.4 from Lecture 3), which lets us solve the HSP with
only polynomially many queries plus exponential post-processing.
Note that these checks don’t rule out that there could be additional elements of G that aren’t evenin the image of ϕ: that is, they verify that ϕ is an embedding, but not that it’s an isomorphism.
Fortunately, though, this distinction is irrelevant for the specific goal of verifying that x 6∈ H.
So the bottom line is that, if we want to prove an oracle separation between QMA and QCMA,
we’ll need a candidate problem that’s less “structured” than Group Non-Membership. In fact,
finding an oracle A such that QCMAA =6 QMAA remains a notorious open problem to this day.
In their 2007 paper, Aaronson and Kuperberg [AK07] were able to make some progress toward
this goal, by showing that there exists a quantum oracle U such that QCMAU 6= QMAU . Here,by a quantum oracle, they simply meant an infinite collection of unitary transformations, {Un }n ,that can be applied in a black-box manner. For convenience, we also assume the ability to apply
controlled-Un and Un−1 (though in this case, the Un ’s that we construct will actually be their own
inverses).
Theorem 5.4.3 (Aaronson and Kuperberg [AK07]). There exists a quantum oracle U = {Un }n≥1such that QMAU 6= QCMAU .
Proof Sketch. For each value of n, we choose an n-qubit pure state |ψi = |ψn i uniformly at random
from the Haar measure. We then design an n-qubit unitary transformation Un so that one of thefollowing holds: either(i) Un = I is the identity, or(ii) Un = I − 2|ψihψ| implements a reflection about |ψi.
Clearly, a witness for case (ii) is just |ψi itself. We now use that “the space of quantum states isbig,” in the sense that there existnN = 2Ω(2 )states |ψ1 i, . . . , |ψN i,

of n qubits each, such that hψj |ψi i ≤ ε for all pairs i =6 j ∈ {1, . . . , N }. We can achieve that, forexample, using states of the form
1 X
|ψj i := √(−1)fi (x) |xi,2n xwhere f1 , . . . , fN are randomly-chosen Boolean functions.
Now, in a QCMA protocol, Merlin can give Arthur a w-bit witness string (there are 2w possible
such strings). Let’s say that the Hilbert space of n-qubit states is fragmented into 2w regions, one
for each string that Merlin could send. Conditioned on being in a particular region, |ψi will still be
uniformly random. Now with high probability, the volume of that region is ∼ 1/2w in terms of theprobability mass. One can show that the best possible case, from the algorithm’s standpoint, is43

that we’ve localized |ψi to within a spherical cap (i.e., the set of all |vi such that |hv|ψi| ≥qh, forsome h). Here we can calculate that the behavior of h as a function of w is given by h ∼ w+1
2n .
Since Grover search andamplitude
amplificationareoptimal,
this
can
be
used
to
show
that
the
 n 
2
number of queries is Ω w+1.
As mentioned earlier, it remains open whether there exists a classical oracle A such that
QMAA 6= QCMAA . Very recently, Fefferman and Kimmel [FK15] presented interesting progresson this problem. Specifically, they separated QMA from QCMA relative to a classical oracle ofan unusual kind. A standard classical oracle receives an input of the form |x, yi and outputs|x, y ⊕ f (x)i, whereas theirs receives an input of the form |xi and outputs |π(x)i, where π is somepermutation. Furthermore, their oracle is probabilistic, meaning that the permutation π is chosenfrom a probability distribution, and can be different at each invocation.

5.5

Complexity of Preparing Witness States

Let’s now notice that there’s a fundamental question about the complexity of quantum states, which
is directly related to the QMA versus QCMA question:
Question 5.5.1. For every language L ∈ QMA, for every QMA verifier V for L, and for every inputx ∈ L, is there a polynomial-size quantum circuit to prepare a state |ψi such that V (x, |ψi) accepts
with high probability?
If the answer to the above question is yes, then it follows immediately that QMA = QCMA,
since Merlin could simply send Arthur a classical description of a circuit to prepare an accepting
QMA witness |ψi. However, the converse is not known: even if QMA = QCMA, there might still be
QMA verifiers for which all accepting witnesses are exponentially hard to prepare. In other words,
it’s possible that “QMA state preparation problems” are inherently harder than the corresponding
QMA decision problems.
Note that this contrasts sharply with the situation for classical NP, which has a well-known“search-to-decision reduction.” That is, given an oracle for an NP-complete decision problem such as
3SAT , we can actually find satisfying assignments for 3SAT instances in polynomial time wheneverthey exist, by using a simple divide-and-conquer trick that fixes one bit at a time. But no such
divide-and-conquer trick seems to work for preparing QMA witness states using a QMA decision
oracle. It ought to be possible, and might be interesting, to confirm this in a suitable relativizedworld.
One additional observation: by Corollary 3.3.7 from Lecture 3, we can always prepare QMA
witnesses efficiently if we make the stronger assumption that BQP = P#P .

5.5.1

Quantum Advice States

We now turn from quantum witness states to another extremely interesting family of complicatedstates: namely, quantum advice states. Unlike a witness state, an advice state can be trusted: it
doesn’t need to be verified. But there’s another difference: we want the same advice state to be
useful for deciding many different instances. Indeed, we’d like a family of advice states {|ψn i}n≥1that depend only on the input length n, and not on the input itself. Think of a graduate adviser
44

who’s honest but very busy, and only gives advice to his or her students based on which year they
are in.
This concept originates in classical complexity theory, and in particular, with the complexity
class P/poly.
Definition 5.5.2. P/poly is the class of languages L ⊆ {0, 1}∗ decidable by a polynomial-timeTuring machine which also receives a polynomial-size advice string an only dependent on the length
n of the input.
We now define the quantum analogue of P/poly.
Definition 5.5.3. BQP/qpoly is the class of languages L ⊆ {0, 1}∗ for which there exists a
polynomial-time quantum algorithm Q, and a set of polynomial-size quantum advice states {|ψn i}n≥1 ,such that Q(|xi|ψn i|0 · · · 0i) accepts with probability > 2/3 if x ∈ L and rejects with probability> 2/3 if x 6 ∈L for every x ∈ {0, 1}n .
Because any mixed state can be purified using twice as many qubits, we may assume the advice
states to be pure or mixed without changing the power of this complexity class.
What kinds of quantum states can be useful as quantum advice? We’ll try to explore thatquestion by studying the power of BQP/qpoly.
Just like we can ask whether QCMA = QMA, so we can ask whether BQP/poly = BQP/qpoly,
where BQP/poly represents BQP with polynomial-size classical advice. And just as Aaronson and
Kuperberg [AK07] gave a quantum oracle separating QCMA from QMA (Theorem 5.4.3), so ananalogous construction gives a quantum oracle separating BQP/poly from BQP/qpoly:
Theorem 5.5.4. There exists a quantum oracle U such that BQPU /qpoly 6= BQPU /poly.
Just like with QCMA versus QMA, it remains open whether there’s a classical oracle separating
BQP/poly from BQP/qpoly.
On the other hand, a variation of the Group Non-Membership Problem gives us an example ofsomething in BQPU /qpoly that’s not known to be in BQP/poly. Namely, what we can do is fix inadvance the group Gn and subgroup Hn as functions of n, and then only take an element x ∈ Gn as
input. The problem, as before, is to decide whether x ∈ Hn .
The adviser knows both Gn and Hn , and can provide |Hn i as the advice state. Since the adviser
is trusted, we don’t even need to check any longer that |Hn i is valid, yielding a simpler protocol
than before.

5.6

Upper-Bounding BQP/qpoly

For most complexity classes, such as QMA, it’s obvious that not all languages are contained in theclass. But in 2003, Harry Buhrman asked the following question: how can we even exclude thepossibility that BQP/qpoly equals ALL, the class of all languages?
We can think of the problem of deciding a language L on inputs of length n as computing an
n-input boolean function Ln : {0, 1}n → {0, 1}. Since the description of the quantum state |ψn iprovided by the adviser involves exponentially many amplitudes, the adviser could choose to provide
a state that encodes the entire truth table of Ln —for example,
X1|ψn i = n/2|xi|Ln (x)i.
2nx∈{0,1}45

However, it’s not clear how one would use this advice: note that measuring in the standard basis
gives only a 2−n probability of getting the answer for the desired input x.
We can exclude the possibility that BQP/qpoly = ALL by showing that
BQP/qpoly ⊆ Anything/poly.

(5.1)

This follows from a simple counting argument. Since one needs 2n bits to specify a function
Ln : {0, 1}n → {0, 1}, whereas the /poly adviser can provide only nO(1) bits, we find that for every
uniform complexity class C (that is, every class defined by a countable set of machines), almost all
languages L must lie outside of C/poly.
The reason why the naı̈ve counting argument doesn’t work for quantum advice is that, as we’veseen, there are doubly-exponentially many n-qubit states that are almost orthogonal to one another.
And in fact, there are complexity classes that really do become all-powerful when enhancedwith quantum advice! For example, let PQP be the quantum analogue of PP: that is, the class oflanguages decidable by a polynomial-time quantum algorithm that only needs to return the correct
answer with probability greater than 1/2. Then we have:
Proposition 5.6.1. PQP/qpoly = ALL.
Proof. We can simply use the aforementioned advice stateX
1√|xi|Ln (x)i.
2n x∈{0,1}n
The PQP algorithm that uses this state will measure the first register. If x is observed, then it
returns Ln (x), whereas if any input other than x observed, it returns 0 or 1 both with probability
1/2. This exponentially small bias toward the right answer is sufficient for a PQP machine tosucceed.
Thus, if we want to upper-bound BQP/qpoly, then we’ll need to use further structure in theway quantum states can be accessed and measured.
In 2004, Aaronson [Aar05a] proved that BQP/qpoly ⊆ PP/poly, which put the first upper boundon the power of quantum advice, and implied that BQP/qpoly =6 ALL. To explain how this works,
we need to introduce one more complexity class: PostBQP.
Definition 5.6.2. PostBQP is the same as BQP, except augmented with the power of postselection.
That is, we assume the ability to measure a single qubit, and “postselect” on a specific measurement
outcome (e.g., by projecting onto the |1i state). We also assume that the postselection measurement
yields the desired outcome with probability at least 1/ exp(nO(1) ) (if it doesn’t, then our machinedoesn’t define a PostBQP language). Conditioned on the postselection measurement succeeding, wethen measure a second qubit. If x ∈ L, then the measurement of the second qubit returns |1i withprobability at least 2/3, while if x ∈ L then it returns |1i with probability at most 1/3.
As a side note, why do we need to assume that the postselected qubit returns |1i with probability
at least 1/ exp(nO(1) )? Because otherwise, we might need more than nO(1) bits even to represent theprobability, and many of the basic properties of quantum computation (such as the Solovay-Kitaev
Theorem) would break down. If our gate set is reasonably “tame” (for example, if all the entries of
the unitary matrices are algebraic numbers), then one can prove that every polynomial-size circuit
46

that accepts with nonzero probability accepts with probability at least 1/ exp(nO(1) )—so in thatcase, no separate assumption is needed. On the other hand, there also exist exotic gate sets (forexample, involving Liouville numbers) for which this is false: that is, for which polynomial-size
circuits can generate nonzero probabilities that are doubly-exponentially small or even smaller. For
more about this, see Aaronson’s blog post [Aar14].
In terms of class inclusions, where does PostBQP fit in? It’s not hard to see thatNP ⊆ PostBQP ⊆ PP.
For the first inclusion, we construct a quantum circuit C associated to our favorite NP-complete
problem (say, C(x) = 1 if x satisfies a given 3SAT instance ϕ, and C(x) = 0 otherwise), and thenprepare the state√
1 − ε2 X√|xi|C(x)i + ε|NULLi|1i,(5.2)
2n x∈{0,1}nwhere (say) ε = 4−n . We then measure the second register, postselect on getting |1i, and thenaccept if and only if we find an x in the first register such that C(x) = 1.
For the second inclusion, we simply repeat the proof of BQP ⊆ PP (Theorem 2.2.4 in Lecture2), except that now we only sum over computational paths which give the desired outcome on thepostselected qubit.
In fact, Aaronson [Aar05b] showed that the converse statement, PP ⊆ PostBQP, holds as well:
Theorem 5.6.3 ([Aar05b]). PostBQP = PP.
We won’t prove Theorem 5.6.3 in this course, but will just make a few remarks about it. First,
Theorem 5.6.3 gives a surprising equivalence between a quantum complexity class and a classical one.
Indeed, the theorem can even be used to give alternative, “quantum” proofs of classical properties
of PP, such as the fact that PP is closed under intersection.
Theorem 5.6.3 can also be used to argue about the classical hardness of tasks such as BosonSampling [AA13]. This is because of the dramatic difference that Theorem 5.6.3 reveals between
PostBQP and its classical counterpart, PostBPP (also known as BPPpath ). In particular, it’s known
that
PostBPP ⊆ BPPNP ⊆ PH.
One striking statement—which is a consequence of the above fact together with Toda’s Theorem[Tod91] that PH ⊆ PPP —is that if PostBPP = PostBQP, then the polynomial hierarchy PH collapses
to the third level. This is much stronger evidence that PostBPP 6= PostBQP than we have that (say)BPP 6= BQP.
With PostBQP in hand, we’re ready to prove the limitation on quantum advice. In particular, we’ll
show how to simulate a quantum advice state by using classical advice together with postselection.
Theorem 5.6.4 ([Aar05a]). BQP/qpoly ⊆ PostBQP/poly = PP/poly.
Proof. We’ll consider an amplified advice state |ψi, consisting of n copies of the original advice
state |ψn i:|ψi = |ψn i⊗n .

47

1This lets us output the right answer with exponentially small error probability, exp(n). Let m be thenumber of qubits in |ψi; then m is still polynomial in n.
The idea will be to guess the quantum advice state |ψi without having any quantum access toit. We will start out with “the most naı̈ve guess” for |ψi, which we take to be the maximally mixed
state ρ0 = I/2m . The adviser will then help us update our guess, by providing a sequence of input
values x1 , x2 , . . . for which our provisional advice state would fail to lead to the right answer (i.e.,
would cause us to output the wrong answer with probability at least 1/3).
In more detail, let Q(x, |ψi) be the BQP/qpoly algorithm that we’re trying to simulate. Thenthe adviser will first send a classical value x1 ∈ {0, 1}n such that

P[Q(x1 , ρ1 ) = Ln (x)] < 2/3,
if such a value exists. We’ll then run Q(x1 , ρ1 ), and postselect on obtaining the right answer. After
this happens, let the state left over in the advice register be ρ2 .
Next the adviser again sends a classical value x2 such that
P[Q(x2 , ρ2 ) = Ln (x)] < 2/3,
if such a value exists, and so on.
If at any point there doesn’t exist a suitable xk , then the adviser is done: by construction, we’re
now left with an advice state ρk such that P[Q(x, ρk ) = Ln (x)] ≥ 2/3 for every input x ∈ {0, 1}n .
Note also that we can simulate postselecting multiple times by using a single postselection stepat the end.
Thus, the only remaining problem is to prove an upper bound on k, the number of iterations
until the refinement procedure terminates.
To prove such an upper bound, the first step is to choose an orthonormal basis containing the“true” m-qubit quantum advice state |ψi, and use that basis to expand the initial maximally mixed
state. Here we use the fact that the maximally mixed state can be written as an equal mixture of
the vectors in any orthonormal basis:
I=

1
2m

X
x∈{0,1}n|xihx| =12m

Xx∈{0,1}n|ϕi ihϕi |,(5.3)

where, say, |ϕ1 i = |ψi is the true advice state. By the Quantum Union Bound (Lemma 1.3.3), wehaveP[Q(|ψi) succeeds on x1 , . . . , xk ] > 0.9.
So

 k
  

2
I
0.9
≥P Q
succeeds on x1 , . . . , xk > m ,m3
2
2

where the first inequality follows from the way we defined the iterative procedure, and the second
follows from equation 5.3 and linearity. Solving for k, we find that the iterative process must end
with k = O(m).
Aaronson and Drucker [AD14] later gave the following improvement of Theorem 5.6.4:

48

Theorem 5.6.5 ([AD14]). BQP/qpoly ⊆ QMA/poly (i.e., a quantum computer with polynomial-size
quantum advice can be simulated by QMA with polynomial-size classical advice). Indeed, somethingstronger is true: polynomial-size trusted quantum advice can be simulated using polynomial-size
trusted classical advice together with polynomial-size untrusted quantum advice.
In other words, we can assume that the quantum advice state is simply a QMA witness state.
This may seem surprising, since quantum advice states need to satisfy exponentially many constraints
associated to different inputs.
Theorem 5.6.5 has an interesting implication: namely, if Question 5.5.1 has a positive answer—
that is, if all QMA witness states can be prepared by polynomial-size quantum circuits—thenthat would imply not merely QCMA = QMA, but BQP/poly = BQP/qpoly as well. This explains,perhaps, why these two complexity class questions have seemed so closely related, with every result
about one matched by a corresponding result about the other.
We’ll end by mentioning one more result in this direction, by Aaronson [Aar06] in 2006:
Theorem 5.6.6 ([Aar06]). QMA/qpoly ⊆ PSPACE/poly.
In other words, even if we combine quantum proofs and quantum advice in the same complexity
class, we still don’t get infinite computational power: everything we do can still be simulated using
polynomial-size classical advice and polynomial space. Surprisingly, this required a new proof, withthe sticking point being to show that QMA/qpoly ⊆ BQPSPACE/qpoly—i.e., that there’s a way toloop through all possible QMA witnesses, without destroying the /qpoly advice in the process. After
that, the same argument used to show that BQP/qpoly ⊆ PostBQP/poly also easily implies that
BQPSPACE/qpoly ⊆ PostBQPSPACE/poly = PSPACE/poly.

49

Lecture 6
Black Holes, Firewalls and Complexity
Lecturer: Scott Aaronson

Scribe: Toniann Pitassi

We now take a break from complexity theory to discuss the black-hole information problem. But
we promise: by the end of the lecture, this will bring us right back to complexity! (What doesn’t?)
A black hole has two main regions of interest. The first is the singularity in the middle. If you
ever jump into a black hole, be sure to visit the singularity; fortunately you won’t be able to miss
it! The other region of interest is the event horizon surrounding the singularity. The event horizonof a black hole is the boundary from inside of which no signals can escape. A black hole has somuch mass that it distorts the causal structure of spacetime, so signals can’t get from the interiorof the black hole to the exterior.
It’s a clear prediction of general relativity that a sufficiently large mass in a sufficiently small
volume will collapse to a black hole. Penrose and Hawking proved this in the 1960s. Einstein didn’t
think that black holes existed, but that was because he didn’t understand his own theory wellenough. Today we know that they do exist. Indeed, just before these lectures were given, LIGO
announced the most direct evidence yet for the reality of black holes: namely, a gravitational wave
signal that could only be caused by two spiralling black holes.
What are the puzzles about black holes that have made theoretical physicists so obsessed with
them?

6.1

Thermodynamics and Reversibility

The first puzzle is that the existence of black holes seems inconsistent with the Second Law ofThermodynamics. The Second Law says that entropy never decreases, and thus the whole universe isundergoing a mixing process (even though the microscopic laws are reversible). The problem is thatblack holes seem to provide a surefire way to decrease entropy. They’re like an entropy dumpster,since when you throw something into a black hole it goes away forever. Indeed, in classical generalrelativity, the No-Hair Theorem states that a black hole in equilibrium is completely characterized
by its position, velocity, mass, charge, and angular momentum. The attractor equations are suchthat there is no possibility of adding extra “hair”: in other words, no possibility of changing theshape of the event horizon by adding microscopic ripples and so forth to it. This means that, whenbits of information are thrown into a black hole, the bits seem to disappear from the universe, thus
violating the Second Law.
This troubled the late Jacob Bekenstein, a graduate student in the early 1970s. He thought that
thermodynamics must prevail, and did not accept that black holes were an exception. (He was a“conservative radical.”) After considering various thought experiments, he proposed that entropy
is proportional to A, the surface area of the event horizon, at a rate of about 1069 bits per meter50squared. In other words, he said that entropy scales like the surface area of the black hold, rather
than like the volume as one might have thought.
Bekenstein’s later arguments implied that 1069 bits per meter2 is actually the maximum entropy
that any physical system of a given surface area can store—since if a system had greater entropy,
then it would simply collapse to a black hole. In other words: for storage density, nothing beats
black holes. They’re the most compact hard drives allowed by the laws of physics, although they’reterrible for retrieval!
So black holes went from having no hair to being hairiest things in the universe—i.e., having the
maximum entropy of any system of the same surface area.
The story goes that Hawking didn’t like this. So he set out to refute it. One thing people were
saying was that in ordinary physics, anything that has an entropy also has a nonzero temperature.
But if black holes had a nonzero temperature, then they’d have to be giving off thermal radiation.
But that seems like an obvious absurdity, since black holes are defined as objects that nothing canescape from.
So then Hawking did a calculation, which was called “semi-classical” because it treated theradiation around a black hole quantum-mechanically, but still treated the curved spacetime as
being classical. The purpose of the calculation was to predict what energy fluctuations an external
observer would see in the vicinity of a black hole. Say that an observer, Alice, is sitting outside theevent horizon. Hawking’s calculation predicted that she would indeed see thermal radiation slowly
escaping from the black hole, and at exactly the rate that Bekenstein’s formula predicted.
(A popular, oversimplified view is that there are these “‘virtual particles” in the vacuum—
positive- and negative-energy excitations that are constantly forming and annihilating. What canhappen is that the negative-energy one falls in and the positive-energy one comes out, so the blackhole loses a tiny bit of mass/energy, which the external observer sees coming out.)
This slowly-escaping radiation from a black hole is called Hawking radiation. Recall that the
number of bits stored by a black hole scales like A ∼ r2 , where r is the radius of the event horizon.
By comparison, the evaporation time scales like r3 ∼ A3/2 . For a black hole the mass of our sun,the evaporation time would be approximately 1067 years.
In 1976, however, Hawking drew attention to a further puzzle. The semi-classical calculation
also predicts that the escaping radiation is thermal—so in particular, uncorrelated with the detailsof the information that fell into the black hole. In other words, each photon would come out in amixed state ρ, independent of the infalling matter.
So let’s come back to Alice. What does she see? Suppose she knows the complete quantum
state |ψi (we’ll assume for simplicity that it’s pure) of all the infalling matter. Then, after collapse
to a black hole and Hawking evaporation, what’s come out is thermal radiation in a mixed stateρ. This is a problem. We’d like to think of the laws of physics as just applying one huge unitarytransformation to the quantum state of the world. But there’s no unitary U that can be applied
to a pure state |ψi to get a mixed state ρ. Hawking proposed that black holes were simply a casewhere unitarity broke down, and pure states evolved into mixed states. That is, he again thoughtthat black holes were exceptions to the laws that hold everywhere else.
People discussed this problem for forty years or so. Most people (including even Hawking himself,
eventually) evolved to the point of view that in the true quantum-gravitational description of nature,
everything should be completely unitary. So if semi-classical field theory says otherwise, then thesemi-classical calculations are wrong—they’re just an approximation anyway to the real, unitary
calculations, and this is a case where they break down. (A familiar analogy is burning a book. The

51

smoke and ashes appear to have no correlation with what’s written in the book. But in reality, weknow that you could in principle recover the contents of the book from the smoke, ashes, and otherbyproducts, together with complete knowledge of the relevant laws of physics.) Reversibility has
been a central concept in physics since Galileo and Newton. Quantum mechanics says that the only
exception to reversibility is when you take a measurement, and the Many-Worlders say not eventhat is an exception.

6.2

The Xeroxing Problem

Alas, even if we believe that the evolution is unitary and the information comes out (and that thephysics of the future will explain how), there’s still a further problem. This is what physicists in the
1980s called the Xeroxing Problem. Let’s consider another thought experiment. This time, insteadof classical information, Alice drops a qubit into the black hole. From the perspective of someone
who’s inside the black hole and sees the qubit come in, it never leaves. But from the perspectiveof Alice, who stays outside (if we believe in reversibility), the qubit eventually has to come out insome scrambled form in the Hawking radiation. So this leads us to the conclusion that there are
two copies of the qubit, violating the No-Cloning Theorem.
To deal with this problem, Susskind and ’t Hooft proposed a concept called black hole complementarity. They argued that the qubit isn’t actually cloned, because the same observer would neveractually see both copies of the qubit. You might object: why couldn’t Alice just stay outside, wait
1067 years or whatever for the qubit to come out, and then once it comes out, immediately jump inand look for the other copy? Well, the calculations predict that by the time Alice jumps in, the“inside” manifestation of the qubit would have long ago hit the singularity, where Alice could nolonger access it. On the basis of thought experiments such as those, Susskind and Hooft proposedthat the inside and outside qubits were literally the same qubit (rather than two copies of the qubit),but measured or viewed in two different ways.

6.3

The Firewall Paradox

In 2012, Almheiri, Marolt, Polchinski and Sully (AMPS) wrote a paper [AMPS13] where they
proposed yet another thought experiment, which leads to yet another apparent problem, evenif we believe in black hole complementarity. The new thought experiment is called the firewall
paradox. In Scott’s view, the firewall paradox helped to sharpen the discussion around black holecomplementarity, because at the end of the day, it’s not about which mathematical formalism to use
or how to describe a state space—it’s simply about what an observer would experience in a certain
situation. And no one can claim to understand complementarity unless they have an answer to thatquestion.
The firewall paradox is more technical than the previous paradoxes and involves several ingredients. The first ingredient is a fact from Quantum Field Theory (QFT), which we’re going to ask
you to take on faith. The QFT fact is that if you look at the vacuum state of our universe, it has
an enormous amount of short-range entanglement. So if you’re jumping into a black hole, and you
see a photon of Hawking radiation just emerging from the event horizon, QFT predicts that there
must be a partner photon that is just inside the event horizon, entangled with the other one. We
can visualize this as a whole bunch of Bell pairs straddling the horizon. Taking the contrapositive,
if you didn’t see these Bell pairs as you crossed the event horizon, then you wouldn’t see a smooth52

spacetime. You would instead encounter an “end of spacetime,” a Planck-energy wall of photons at
which you’d immediately disintegrate. This is what’s referred to as the firewall.
The second ingredient that we’ll need is a modern, information-theoretic view of black holes,
as extremely efficient scramblers of information. In particular, when we let matter collapse toform a black hole, we can imagine that we start with n qubits in a simple state (say the |0 · · · 0i
state). And when the qubits come back out of the black hole in the form of Hawking radiation, we
can model that by a very complicated quantum circuit C—for some purposes, a random quantum
circuit—having been applied to the qubits. So we can think of the output state as a pseudorandom
pure state, and for many purposes, we can model it as being Haar-random. (Of course it can’t reallybe Haar-random, because the black hole formation time is only polynomial, whereas we know thata Haar-random pure state has 2Ω(n) circuit complexity with overwhelming probability.)
Abstracting the situation, we want to say something purely information-theoretic about Haarrandom states. Let’s consider a Haar-random pure state |ψi on n qubits. Look at the reduced(mixed) state, ρ, of the first k of these qubits, obtained by tracing out the remaining n − k qubits.
(In other words, look at the “marginal distribution” on the first k qubits.) This state will have the
form
ρ=

n−k
2X

i=1

pi |ψi ihψi |.

What does this state look like? There are two regimes of interest.
(1) k < n/2. In this case, rank(ρ) = 2k . Since 2n−k dominates 2k , there are enough terms in theabove sum to give a full rank matrix. Using concentration of measure inequalities, one canshow that the resulting state ρ will be very close to the maximally mixed state, Ik . (To build
intuition, it might help to consider the extreme case k = 1 or k = 2.)(2) k > n/2. In this case rank(ρ) = 2n−k < 2k . So in this regime, ρ is no longer the maximally
mixed state.
In conclusion, something very interesting happens when exactly half of the qubits have emerged
from the black hole (in the form of Hawking radiation). When half come out, the state ρ as seen by
the outside observer is no longer maximally mixed. Alice, our outside observer, can in principle start
to see correlations, between the Hawking photons themselves, and between them and the infalling
matter. This point in time when half of the qubits come out is called the Page Time, after Don
Page who studied it in the 1980s.
There’s a further thing that we can say. Looking at this state ρ in a bit more detail, whenk > n/2 qubits have come out, with overwhelming probability, any one of these k qubits that wepick is entangled with the remaining k − 1 qubits that have come out. (The proof of this is left as
an exercise.)Now back to the thought experiment. We imagine Alice, who’s outside the black hole and is an
all-powerful observer. Alice sets up a system of n qubits, in a known initial state, and lets themcollapse to form a black hole—evolving, in isolation from everything else in the universe (we’ll
assume for simplicity), according to unitary laws of physics that are completely known to Alice.
Then, as the black hole slowly evaporates, there’s a sphere of perfect photodetectors surrounding
the black hole, which catches all the photons of Hawking radiation as they escape, and routes theminto a quantum computer for processing.
53

Alice waits roughly 1067 years, until the black hole has passed its Page Time (but hasn’t yet
evaporated completely). Suppose 2n/3 of the qubits have come out in the form of Hawking radiation,
while n/3 remain in the black hole. Then we consider three subsystems:• R, consisting of the k = 2n/3 qubits that have come out,
• B, the very next qubit coming out, and• H, the remaining qubits that are still inside the black hole.
Now, what we concluded from our previous discussion (about states that are effectively like Haarrandom states) is that we expect B to be entangled with R. In more detail, the joint state of thesek + 1 qubits cannot be the maximally mixed state, and we further expect that B shares one bit ofentanglement with R. Thus, by applying a suitable unitary transformation to R alone, Alice shouldbe able to put some designated qubit of R (say, the “rightmost” one, for some arbitrary ordering of
the qubits) into a Bell pair with B.
So Alice does that, and then measures B and the last qubit of R to confirm that they really arein a Bell pair. And then Alice jumps into the black hole.
We already said that there exists another qubit inside the black hole (i.e., in H) that B is
maximally entangled with, since there’s nothing special about the event horizon in terms of spacetime
deformity. And this entanglement between B and H must also be observable as we cross the event
horizon. But this violates the Principle of Monogamy of Entanglement, from back in Lecture 1!
The same qubit B can’t be maximally entangled with two other qubits (or for that matter, evenentangled with one qubit and correlated with another). There’s simply no way to do everything
we’ve demanded, if all of Alice’s experiences are to be described using quantum mechanics.
So if we want to preserve quantum mechanics, or even the appearance of quantum mechanics,
then either Alice must be unable to observe entanglement between B and R, or else she must be
unable to observe entanglement between B and H. This is the firewall paradox.
There are a few possibilities for resolving the paradox:(1) We could throw up our hands and declare that “black holes are like Las Vegas”—that is, thatit’s outside the scope of science to understand what happens inside a black hole. (I.e., thatthe goal is to describe that part of the universe that we can receive signals from—in this case,the regions R and B outside the event horizon, where there’s no problem.)(2) We could say that there really is a firewall, or end of spacetime, at the event horizon. This
would be a radical change to black hole physics, but note that it’s compatible with unitarity.
Something weird happens to the infalling observer, but everything is fine for an outside
observer.
(3) We could give up on one of the basic assumptions of physics that led to this point. For
example, we could give up on unitarity. (In that case, something weird would happen for theoutside observer, who would see a truly mixed state.)(4) We could say that there exists a firewall if Alice does this crazy experiment, but not under“normal circumstances.” I.e., that whether there is or isn’t a firewall—what Alice perceives
as the nature of spacetime at the event horizon—depends on whether she switched on her
quantum computer and had it process the Hawking radiation in this bizarre way.
54

Scott, in common with many of the actual experts in this area (of which he’s not one), tends tofavor (4) as the “least bad option.” On this fourth view, the whole paradox arose from not taking
complementarity seriously enough. We were insisting on thinking of the qubits coming out as being
different from the ones going in, but complementarity has been telling us all along that they’rethe same. In other words, on the fourth view, H doesn’t exist: what we’ve been calling H is reallyjust R and B measured in a different basis. In normal circumstances one doesn’t notice this, but
sufficiently extreme processing of R and B can make it apparent.
However, if we want option (4), then we face a further question: namely, what do we mean by“normal circumstances”? Or more pointedly: can we draw any sort of principled distinction between
the types of unitary evolution of R and B that might create a firewall, and the “ordinary” types
that have no danger of creating one?

6.4

The HH Decoding Task

This brings us to the striking work of Harlow and Hayden (HH) [HH13], who abstracted the firewall
paradox into a purely computational problem, as follows:• The Harlow-Hayden Decoding Task. We’re given as input a description of a quantum
circuit C, which maps n qubits (say, in the initial state |0i⊗n ) to a tripartite state |ψiRBH ,where B is a single qubit. We’re promised that there exists a unitary transformation U , whichacts only on the R part of |ψiRBH , and which has the effect of putting B and the rightmost
qubit of R into the joint state √12 (|00i + |11i). The challenge is to apply such a U to the Rpart of |ψiRBH . 1
The HH Decoding Task is information-theoretically possible—indeed, the very statement of the
problem assures us that the desired unitary transformation U exists—but it might be computationallyintractable. For suppose again that R has k qubits for k > n/2. Then we argued before that the
reduced state ρRB can’t possibly have maximum rank. If, moreover, |ψiRBH is the output of arandom quantum circuit (as in the “scrambling” model of black holes discussed earlier), then afurther argument shows that ρRB will generically have entanglement between R and B. However,these arguments were abstract and non-effective, based on iterating through a basis for the whole
Hilbert space. If we tried to extract from the arguments an actual quantum circuit, acting on R, todistill the entanglement between R and B, that circuit would have exponential size.2
But the above, as Harlow and Hayden noted, merely means that the decoding task might becomputationally hard, not that it is. We’ve said nothing against the possibility that there could besome clever, general way, which we haven’t thought of yet, to convert the input circuit C into asmall circuit for the desired unitary U . In complexity theory, to make the case for an algorithm’s
existence being unlikely, we normally at the least want a reduction argument, showing that thealgorithm’s existence would have many surprising consequences for seemingly-unrelated problems.
This is precisely what Harlow and Hayden accomplished with the following theorem.
1

Throughout these lectures, we’ll assume for simplicity that the HH Decoding Task requires decoding the Bellpair √12 (|00i + |11i) perfectly. Relaxing this, to allow for approximate decoding, leads to technical complications but
doesn’t change anything conceptually.
2
We do, of course, know the quantum circuit C that maps |0i⊗n ) to |ψiRBH , and given access to all three registers,
it would be easy to apply C −1 . The difficulty, if one likes, is that we’re trying to uncover structure in |ψiRBH by
acting only on R.

55

Theorem 6.4.1 (Harlow-Hayden [HH13]). If the HH Decoding Task can be done in polynomial
time for arbitrary circuits C, then SZK ⊆ BQP.
Indeed, if there exist SZK problems that are exponentially hard for quantum computers, thenthe HH Decoding Task also requires exponential time.
One can interpret this as saying that, at least in Harlow and Hayden’s idealization, for a blackhole the mass of our sun, for Alice to do the preprocessing of the Hawking radiation necessary to67
create a firewall would be impossible in a mere ∼ 1067 years—it would instead take more like ∼ 210
years! And thus, we might argue, before Alice had even made a dent in the task, the black hole
would have long ago evaporated anyway, so there would be nothing for Alice to jump into and hence
no Firewall Paradox!
In the next section, we’ll follow Harlow and Hayden’s construction to prove a slightly weaker
result. We’ll then see how to prove results that strengthen Theorem 6.4.1 in several respects.

6.5

The Harlow-Hayden Argument

Our goal now is to prove that, if the HH Decoding Task can be done in polynomial time for arbitrary
circuits C, then a problem called “Set Equality” can also be solved in quantum polynomial time.
Set Equality is a special case of the Collision Problem, and is also a special case of Statistical
Difference, the canonical SZK-complete problem (the Collision Problem and Statistical Difference
were both defined in Lecture 4).
Definition 6.5.1. In Set Equality, we’re given black-box access to two injective functions, f, g :{1, ..., N } → {1, .., M }, where M ≥ 2N . We’re promised that either(i) Range(f ) = Range(g), or(ii) Range(f ) ∩ Range(g) = ∅.
The problem is to decide which.
Now, in the same paper [Aar02] where Aaronson proved the collision lower bound (Theorem
4.1.8), he also proved the following lower bound on the quantum query complexity of Set Equality:
Theorem 6.5.2 ([Aar02]). Any quantum algorithm for Set Equality must make Ω(N 1/7 ) queries tof and g.
In 2013, Zhandry [Zha13] strengthened Theorem 6.5.2, to show that any quantum algorithm for
Set Equality must make Ω(N 1/3 ) queries. Zhandry’s lower bound is tight.
If the functions f and g are described explicitly—for example, by circuits to compute them—thenof course we can no longer hope for a black-box lower bound. Even in that case, however, we cansay that an efficient (in this case, logO(1) N -time) quantum algorithm for Set Equality would let us,
for example, solve Graph Isomorphism in polynomial time—since given two graphs G and H, thesets {σ(G)}σ∈Sn and {σ(H)}σ∈Sn are equal if G ∼= H and disjoint otherwise. Indeed, the Statistical
Difference problem from Lecture 4 is just a slight generalization of Set Equality for explicit f, g,
and it follows from Theorem 4.1.4 of Sahai and Vadhan [SV03] that an efficient quantum algorithm
for Statistical Distance would imply SZK ⊆ BQP.
Without further ado, let’s show the reduction from Set Equality to the HH Decoding Task. The
reduction involves preparing the following state |ψiRBH :56

|ψiRBH = √1

X

2n+1 x∈{0,1}n(|x, 0iR |0iB |f (x)iH + |x, 1iR |1iB |g(x)iH ) .

It’s clear that |ψiRBH can be prepared by a polynomial-size circuit, given the ability to computef and g. But why does this state encode Set Equality?
Well, first suppose that Range(f ) ∩ Range(g) = ∅. In this case, because the two ranges are
disjoint, the H register decoheres any entanglement between R and B, exactly as if H had measured
B (or as happens in the GHZ state). So the reduced state ρRB is not entangled. Thus, the HH
Decoding Task is impossible because the promise is violated.
Second, suppose that Range(f ) = Range(g). In that case, Alice (acting on R) simply needs
to apply a permutation that maps each basis state |x, 0i to itself, and each basis state |x, 1i to|f −1 (g(x)), 1i. This yields the state√1X

2n+1 x∈{0,1}n(|x, 0iR |0iB + |x, 1iR |1iB ) |f (x)iH ,in which B and the rightmost qubit of R are jointly in the entangled state √12 (|00i + |11i), as
desired.
Thus, if HH Decoding were easy whenever the promise were satisfied, then given functions f, g
for which we wanted to solve Set Equality, we could first prepare the corresponding state |ψiRBH ,then try to perform HH Decoding, and then apply a measurement that projects onto √12 (|00i + |11i)
to check whether we’d succeeded. If Range(f ) = Range(g), we would find that we’d succeeded withprobability 1, while if Range(f ) ∩ Range(g) = ∅, we would find that we’d succeeded with probability
at most 1/2, which is the maximum possible squared fidelity of a separable state with the Bell pair
(we leave the proof of that as an exercise). Thus we can decide, with bounded error probability,
whether Range(f ) and Range(g) are equal or disjoint.
So, taking the contrapositive, if Set Equality is hard for a quantum computer, then so is the HH
Decoding Task.
Before going further, let’s address a few common questions about the HH argument.
(1) What role did black holes play in this complexity argument? Firstly, the black hole is what
prevents Alice from accessing H, thereby forcing her to apply complicated processing to R.
Secondly, the black hole is what “scrambles” the infalling qubits (admittedly, many moremundane physical systems would also scramble the qubits, though probably not as thoroughly
as a black hole). Thirdly, of course, the black hole is what led to the “paradox” in the firstplace! With most physical systems, there would be no particular reason for B and H to beentangled, and therefore no difficulty if we observe R and B to be entangled.
(2) Are Harlow and Hayden saying that a contradiction in the laws of physics is okay, so longas it takes exponential time to reveal? No, they aren’t. Approximate theories can and dohave contradictions. The HH view would say that general relativity and quantum field theory
work well in “ordinary” circumstances, but if Alice were somehow able to solve, in polynomial
time, a problem that we currently conjecture to be exponentially hard, then a full quantum
theory of gravity would be needed to describe her experiences. Note that physicists agree that
GR and QFT fail in some regime, but that regime is usually taken to be that of extremely
high energy and curvature (e.g., the Big Bang, or a black hole singularity). The novelty of57

the HH argument is that it suggests a breakdown of field theories, not at the Planck energy(there’s nothing high-energy in the HH Decoding Task), but instead in a regime of exponential
computational complexity.
(3) What if we had a microscopic black hole? Such a black hole would evaporate extremely quickly,
thereby making asymptotic complexity apparently irrelevant. The basic answer is that, if
microscopic black holes exist, then they’re fundamentally quantum-gravitational objects, so
the physicists don’t much care if they lead to a breakdown of smooth spacetime at their event
horizons. The firewall paradox only arises in the first place for “astrophysical-mass” black
holes, because those are the ones for which the physicists expected GR and QFT to describe
Alice’s experiences (as long as she restricts herself to low-energy experiments).
(4) Doesn’t the HH argument apply only to artificial, engineered quantum states? Why couldn’t
the states occurring in real black holes have some special symmetry (for example) that would
make the HH Decoding Task much easier than in the worst case? Of course, this is possible inprinciple, but what we know about “black holes as scramblers” suggests the opposite: that the
decoding task for generic black hole states should, if anything, be harder than for the special|ψiRBH ’s for which we’re able to give formal hardness reductions. For more about this, see
Section 6.5.2.
(5) In a subsequent paper, Oppenheim and Unruh [OU14] argued that, given enough precomputation, it would be possible to engineer a special black hole to which the HH hardness
argument didn’t apply. In their construction, the black hole qubits are maximally entangledwith qubits that remain outside the black hole, in Alice’s control—and before even letting theblack hole qubits collapse, Alice preprocesses their entangled partner qubits specifically tomake her later decoding task easier. Scott’s inclination is to bite the bullet and say yes, inthis extreme situation, the HH argument doesn’t apply! But if the argument applies to real,astrophysical black holes, then that’s already an extremely interesting conclusion.

6.5.1

Improvements to Harlow-Hayden

We’ll now discuss some improvements to HH argument due to Aaronson (paper still in preparation).
The first improvement concerns the complexity assumption: despite the lower bounds for Collision
and Set Equality, SZK 6⊂ BQP still strikes some people as a strong assumption.
In cryptography, the gold standard is to base whatever conclusion we want on the existence of
one-way functions, which is considered the minimal assumption for complexity-based cryptography.
A one-way function (OWF) is a family of functions fn : {0, 1}n −→ {0, 1}p(n) , for some polynomialp, such that(1) fn is computable in nO(1) time, but(2) for all polynomial-time algorithms A,
Px∈{0,1}n [f (A(f (x))) = f (x)] <(For simplicity, we often suppress the dependence on n.)58

1.
poly(n)Or in words: an OWF is a function that’s easy to compute but hard to invert—for which no
polynomial-time algorithm can find preimages with any non-negligible success probability.
It’s known (see Ostrovsky [Ost91]) that if there are hard SZK problems, then there are also
OWFs, but no one knows the converse. So the existence of OWFs is a weaker assumption than SZKbeing hard.
Of course, for present purposes, we’ll need OWFs that are hard to invert even by quantum
computers. But this is considered almost as safe an assumption as NP 6⊂ BQP. Certain specific
OWFs useful in public-key cryptography, such as those based on factoring and discrete logarithms,
can be inverted using Shor’s algorithm. But a general OWF f could be based (for example) on
simply iterating a cellular automaton or some other “unstructured” system, in which case, wewouldn’t currently know how to invert f any faster than by using Grover’s algorithm.
We’ll actually need injective OWFs, which are OWFs f with the additional property thatf (x) 6= f (y) for all x 6= y. But while no one knows how to convert an OWF into an injective one,the existence of injective OWFs is considered a safe assumption as well. Indeed, if f : {0, 1}n −→{0, 1}p(n) “behaves like a random function” and p(n)  2n, then probabilistic considerations
immediately suggest that f will be injective with overwhelming probability.
We can now state Aaronson’s two improvements to Harlow and Hayden’s Theorem 6.4.1:
Theorem 6.5.3 (Aaronson, not yet published). Suppose there exist injective OWFs that are hardto invert by quantum computers. Then the HH Decoding Task is hard.
Proof. Let f : {0, 1}n −→ {0, 1}p(n) be an injective OWF. Then consider the stateX 
1p(n)−n√|ψiRBH =|x 0, 0iR |0iB + |f (x), 1iR |1i |xiH
2n+1 x∈{0,1}nwhere the 0p(n)−n are ancilla bits. It’s not hard to see that the above state does have entanglement
between B and R. Indeed, we could distill the entanglement by applying a reversible transformation
U to R that mapped each basis state of the form |f (x), 1i to |x, 0p(n)−n , 1i, while acting as theidentity on basis states of the form |x, 0p(n)−n , 0i. (Such a U exists because f is injective.) The
only problem is that implementing such a U would require inverting f —and intuitively, this seems
inherent to any entanglement distillation procedure.
For a more formal proof: notice that, if U succeeds at putting B and the last qubit of R into a
Bell pair √12 |00i + |11i, then there must exist states {|φx i}x such thatU |x 0p(n)−n , 0i = |φx i|0i and U |f (x), 1i = |φx i|1i.
Now, let V be the p(n)-qubit unitary induced by U if we fix the last qubit of R to 0, and let W be
the unitary induced by U if we fix the last qubit of R to 1. Then
V |x 0p(n)−n i = |φx i,

W |f (x)i = |φx i.

(6.1)
(6.2)

But this means that, to invert f , we simply need to apply
V † W |f (x)i = V † |φx i = |x 0p(n)−n i.

59

(6.3)

Next, we give an improved construction based on injective OWFs, for which it’s hard even to
distill classical correlation between R and B.
Theorem 6.5.4 (Aaronson, not yet published). Suppose there exist injective OWFs that are hardto invert by quantum computers. Then not only is the HH Decoding Task hard, but it’s hard even to
distill classical correlation (let alone entanglement) between the R and B regions.
Proof. For this, we’ll need one more basic concept from cryptography, called a hardcore predicate for
an OWF f . A hardcore predicate is a single bit h(x) about the input x, which is “as hard to learn,
given only f (x), as it is to invert f outright”—that is, such that for all polynomial-time algorithms
A,
1
1
Px∈{0,1}n [A(f (x)) = h(x)] < +.
2 poly(n)A celebrated result of Goldreich and Levin [GL89] states that, given any injective OWF f , if we
define the slightly-modified OWF
g(x, s) := hf (x), si ,then h(x, s) = x · s( mod 2) is a hardcore predicate for g.
So let f be an injective OWF secure against quantum computers. Then consider the following
construction:
X
1|ψiRBH = √|f (x), s, aiR |(x · s) ⊕ aiB |x, siH .
22n+1 x,s∈{0,1}n ,a∈{0,1}
Again, clearly this state can be prepared efficiently. To see that it has entanglement between R and
B: observe that, if we applied a unitary U to R that inverted f (possible because f is injective),and then XORed x · s into the last qubit of R, we would have√1X

22n+1 x,s∈{0,1}n ,a∈{0,1}or equivalently√

1|x, s, (x · s) ⊕ aiR |(x · s) ⊕ aiB |x, siHX

22n+1 x,s∈{0,1}n ;a∈{0,1}|x, s, aiR |aiB |x, siH .

On the other hand, if you could detect any classical correlation between R and B—not evenentanglement—that would imply that given hf (x), si, you could guess the hardcore bit x · s better
than chance. But by Goldreich-Levin, that would imply that you could invert f , contrary toassumption.

6.5.2

The “Generic Case”

One might complain that the above hardness arguments concerned very special states |ψiRBH . Whatabout the “generic case” of interest for physics? Well, suppose one applied a random, polynomial-size

60

quantum circuit C, which acted across all three registers R, B, and H, like so:
R

•

B

•

H

•

•

•

•

As before, we want to apply a unitary UR to the R register in order to decode one qubit ofentanglement between R and B. Now, while we lack a rigorous result, intuitively, if anything thisseems even harder than decoding the entanglement for the special states |ψiRBH that we constructed
for the proofs of Theorems 6.4.1 and 6.5.3! For the special states, at least there was a classicalcomputational problem—namely, computing f −1 (g(x)) in the HH construction, or inverting theinjective OWF f in Aaronson’s constructions—such that, if we could solve that problem, then the
HH Decoding Task would be easy. Indeed, in both cases, the problem is in NP, meaning that the
HH Decoding Task would be easy for these specific states if NP ⊆ BQP.
For the generic case, by contrast, it’s not obvious that there’s any classical computational
problem, such that an efficient solution to that problem would make the HH Decoding Task easy.
In other words, we don’t have any general converse to Theorems 6.4.1 and 6.5.3. We know that, if
quantum-resistant injective OWFs exist, then the HH Decoding Task is hard, but we don’t evenknow whether if P = PSPACE (for example), then the generic HH Decoding Task is easy.
This directly relates to (and helps to motivate) the Unitary Synthesis Problem, and the othergeneral questions about the complexity of unitary transformations from Lecture 3.

6.5.3

Preskill’s Problem

We’ll end our discussion of the Harlow-Hayden argument with a beautiful problem, which wascommunicated to Scott by John Preskill. Preskill wondered: could one evade the HH argument byfeeding a black hole a daily diet of particles, in order to keep it alive for exponential time—enoughfor Alice to perform the HH Decoding Task? This then led to a followup question: if one tried to do
this, then would one necessarily generate quantum states at intermediate times with 2Ω(n) quantum
circuit complexity? Or, to put the question differently: is it possible to perform the HH Decoding
Task by applying a quantum circuit to R that has exp(n) gates, but that keeps the state complexity
upper-bounded by a polynomial throughout, so that for all t, we have Cε (|ψt i) ≤ nO(1) ?
For the special constructions of |ψiRBH above, based on Set Equality and injective OWFs, theanswer turns out to be yes. For in those cases, it’s not hard to see that one can solve the requisite
NP problems—that is, compute f −1 (g(x)) or f −1 (x)—in a way that takes exponential time but
never makes the current state much more complicated than |ψiRBH itself. On the other hand, forthe generic case, Preskill’s problem remains open: the entanglement-distilling circuits that one
could derive from the abstract dimension-counting arguments of this lecture would not only haveexponentially many gates, but would also produce intermediate states that plausibly have 2Ω(n)circuit complexity.
61Lecture 7
Complexity, AdS/CFT, and Wormholes
Lecturer: Scott Aaronson

Scribe: Vijay BalasubramanianIn this lecture, we’ll move on from firewalls to describe another recent connection between
quantum circuit complexity and quantum gravity.
The AdS/CFT correspondence is a conjectured (and well-supported, but not proven) duality
between quantum gravity in anti de-Sitter (AdS) spacetime and Conformal Field Theories (CFTs).
So what is AdS spacetime, and what is a CFT?
Anti de-Sitter (AdS) is the name given to universes with a negative cosmological constant.
Let’s consider such universes in d + 1 dimensions where the additional 1 is for the time dimension.
The spatial slices of such a universe are hyperbolic spaces. To visualize, we can conformally map
hyperbolic space to a finite disc in the plane (think of the pictures of M.C. Escher with repeating
figures in a disc shrinking as they approach the boundary which has been mapped from infinitely
far away to a finite distance). You can visualize an AdS spacetime (after this conformal mapping)as a solid, infinitely long cylinder. Time runs along the infinite length. An equal time slice is ahorizontal section of the cylinder, and each such section is a hyperbolic space. The interior of thecylinder is often referred to as the “bulk.” The boundary of the cylinder is the boundary of AdS
spacetime and is infinitely far way in the hyperbolic metric. In the AdS/CFT correspondence weconsider a quantum gravitational theory on AdS spacetime, generally a string theory, and study its
physics. Each such theory comes equipped with many kinds of fields and particles (generally an
infinite tower of objects with increasing masses, and a small number of light or massless degrees of
freedom which are most interesting to us since they are easy to excite).
Meanwhile, a Conformal Field Theory (CFT) is a quantum field theory that has a particularly
powerful symmetry, called conformal invariance. By saying that a quantum field theory “has asymmetry” we mean that the dynamical equations and energy functional of the theory are invariant
under transformation by the associated symmetry group. This usually means that the vacuum
state of the theory is invariant under the symmetry group, but that may not be the case (thevacuum can “break” the symmetry). Regardless of whether the vacuum itself is invariant under
the symmetry group action, all states and configurations of the quantum field can be usefullyorganized in representations of the symmetry group. In two dimensions (1 + 1) the conformal groupis infinite-dimensional and conformal field theories in 2D are highly constrained because of this. The
conformal group in more than 2 dimensions is finite dimensional, but still produces many constraints
on theories. In the case of the AdS/CFT correspondence, the relevant CFT (which we’ll say more
about below) is formulated on the conformal boundary of the the d + 1-dimensional AdS spacetime.
As described above, this boundary is d-dimensional, a (d − 1)-dimensional sphere plus time.
We can discretize the space and time on which the CFT is defined and idealize it as a quantum

62

circuit acting on a finite number of qubits:
A
Schematic
Quantum
F ieldT heory

•
•

•
• •
• •
•
•
• •
• •
•
•
•

Here the circuit is shown as acting locally between neighboring qubits because we’re interested inlocal CFTs, which have spatially local interactions. The CFT interactions are occurring “at all
times” and “between every pair of neighboring points,” so the above is just a very crude schematicto help the imagination. A CFT generally has a finite number of interacting quantum fields, but,importantly, does not contain dynamical gravity.
The AdS/CFT correspondence is a conjectured equivalence or duality between certain quantum
theories of gravity (string theories) acting in AdS spacetime and corresponding CFTs associated to
the AdS boundary. On the AdS side the theory is (d + 1)-dimensional. On the CFT side the theoryis d-dimensional. So if the equivalence is true, one dimension of the AdS space can be regarded
as “emergent” in the CFT, i.e. arising as an effective description of lower-dimensional dynamics.
Likewise on the AdS side the theory contains gravity. On the CFT side there is no gravity. So fromthe CFT perspective, the gravity is emergent also.
All very cool indeed—but what does it mean for two such theories to be “equivalent”? First,
the symmetries must match. Thus, the conformal group of the CFT is realized on the gravity side
as an isometry group. The CFT typically contains additional symmetries, which also get realized assymmetries of the theory on the AdS side. In addition, the objects in the two theories must be incorrespondence—that is, for each operator that creates objects and states in the CFT there must
be a corresponding quantum field in the AdS theory. In the proposed examples of the AdS/CFT
correspondence this is the case. In particular, in all such examples, the graviton field in AdS space isassociated to the stress-energy tensor of the dual CFT. It should be said that it’s rather non-trivial
to find examples of fully defined and self-consistent theories in different dimensions that can matchup in this way. Finally, once we have a dictionary matching up the objects and states on the
AdS and CFT sides, the remaining thing is to specify how to compute observable quantities—the
AdS/CFT duality states that you get the same answer for the observable by computing on eitherside of the correspondence. There’s an algorithm for systematically computing observables on the
CFT side (essentially correlation functions) and on the AdS side. In the cases where computations
have been possible on both sides they have always agreed, but a general proof of equivalence—andfor that matter, even a general, independent definition of the AdS theory—haven’t yet been given.

7.0.4

Susskind’s Puzzle

The map between bulk and boundary doesn’t seem to be “complexity-preserving.” That is, simple
states on one side can map onto complex states on the other.
To be concrete, let’s consider two separate regions of space connected by a non-traversible
wormhole. The non-traversibility occurs because the wormhole stretches rapidly. In generalrelativity, such wormholes are described by geometries called Einstein-Rosen (ER) bridges.

63

In the AdS/CFT correspondence, the CFT dual of the wormhole is a so-called “Thermofield
Double State” (TDS). This means that the state is maximally entangled between two identical
Hilbert spaces:N
1 X
T DS = √|iiA |iiB .
(7.1)
N i=1
Recalling that the weird properties of maximally entangled states were originally emphasized in a
famous paper of Einstein, Podolsky and Rosen (EPR), Susskind and Maldacena [MS13] summarized
this relation between ER bridges and entanglement by the slogan “ER = EPR.”
Now the wormhole gets longer as time passes. But what happens to the dual CFT state? The
state changes through some unitary evolution:
1 X t
T DS(t) = √V |iiA ⊗ (V −1 )t |iiB .
N iRecall, the maximally entangled state has the property that
N
N
1 X
1 X
√
V |ii ⊗ |ii = √|ii ⊗ V T |ii.
N i=1
N i=1

Thus, we actually haveN

1 X
T DS(t) = √|ii ⊗ U t |ii
N i=1
for some unitary U = V −1 V T .
Assume that U is implemented by a polynomial-sized quantum circuit. Then we can state
Susskind’s puzzle as follows: if we apply U U · · · U |0i⊗n , we’ll get something that very quickly“thermalizes.” To see this, we can consider what physicists call k-point correlation functions—or
equivalently, the local density matrices of k = O(1) qubits at a time. For example, the density
matrix of a single qubit will rapidly converge to the maximally mixed state, and similarly forthe state of any small number of qubits. Furthermore, after the local density matrices havethermalized in this way—namely, after about n log n gates have been applied—one can show that,with overwhelming probability, the local density matrices will remain in that thermalized condition
for doubly-exponential time.
But on the AdS side, Susskind pointed out, rapid thermalization is not what’s happening—rather,
the wormhole just keeps getting longer and longer. Thus, let |ψt i be the CFT state after a time t.
Then Susskind raised the question: what quantity f (|ψt i) is the CFT dual to the wormhole length?
He made an astonishing proposal: namely, the quantum circuit complexity of the state, i.e.,f (|ψt i) = Cε (|ψt i). In the following sections, we’ll discuss the heuristic justifications for Susskind’s
proposal, as well as some recent work aiming to prove rigorously that (under reasonable complexity
hypotheses) Cε (|ψt i) does indeed grow like f (|ψt i) should.

7.1

The Proposal

To recap, the CFT dual of the thermofield double state at time t is given byX1|ψt i = n/2|xi ⊗ U t |xi.
2nx∈{0,1}64

Our question was: what property of this state grows linearly with t, and as such can explain thewormhole’s linear growth in volume over time (which follows from general relativity)? No standard
information-theoretic measure seems to suffice. Instead, Susskind’s proposal is that the quantum
circuit complexity Cε (|ψt i) of the state |ψt i is what corresponds to the volume. Clearly,Cε (ψt ) ≤ t · poly(n),since we can generate ψt from n Bell pairs by simply applying U repeatedly t times. (Here we’re
assuming that U is a “simple” unitary that can be implemented by a quantum circuit of size poly(n),as is the case for other unitaries in nature.) One might expect that the upper bound above is tightand the circuit complexity does grow linearly, at least until time t ≈ 2n . Beyond that time, thecircuit complexity stops growing, since it’s easy to see that for any n-qubit state |ψi,Cε (ψ) ≤ 2n · poly(n),which follows by preparing the state one amplitude at a time. To summarize, one can expect thestate complexity to behave as shown in Figure 7.1.

C(|ψi)

n

≈ 2n

≈ 22

time

n

The reason for the dip is that once in roughly ∼ 22 steps, we can expect the “random-looking”|ψt i to happen to land near a low-complexity state. (This can also be seen by considering theneigenvalues of U ; by the pigeonhole principle, one can show that after at most ∼ 22 steps, we’ll
reach a t for which U t is very close to the identity, in which case the state has low complexity.) This
speculative behavior of the state complexity agrees with the known predictions for the volume of a
wormhole (based on quantum gravity). Other predictions on the behavior of the volume also agreewith this measure:
1. Imagine that partway through the process, instead of multiplying by U , we start multiplying
by U −1 . We’d expect the wormhole to start shrinking at the same speed it previously grew.
And indeed, this is exactly what happens to the state complexity.
2. More interestingly, imagine that before switching from U to U −1 , we apply once a unitary
V not related to U . In that case, the prediction from quantum gravity turns out to be thatthe wormhole would continue growing instead of shrinking as before. And indeed, that’s also
what we expect from the state complexity (see for example [SS14]):
Cε

 1
2n/2

X
x∈{0,1}n|xi ⊗ U −t V U t |xi ≈ 2t · poly(n).

65The idea that circuit complexity is dual to wormhole volume remains speculative: even if weagree that the two quantities are correlated, we know that in science correlations need not be causal,
but could be explained by some yet-unknown third factor.
We could also ask: if circuit complexity is dual to wormhole volume, then which variant of circuit
complexity are we talking about? For example, exact or approximate circuit complexity? Are ancillaqubits allowed? Must garbage be uncomputed (recall the discussion in Lecture 3)? Also, surely wecan’t expect the laws of physics to know about nontrivial efficient algorithms like (say) Edmonds’
algorithm for maximum matching, or the ellipsoid algorithm for convex programming. Yet thosealgorithms could in principle be the reason why a state had polynomial rather than exponential
quantum circuit complexity.
Nevertheless, right now circuit complexity is essentially the only proposal that produces theright answers in the cases of interest. Other quantities, like entropy, are non-starters, because theysaturate too quickly. There is the tautological proposal of defining the CFT dual of wormholevolume, for a given state |ψi, to be the minimum value of the time t that satisfies the equation|ψi = |ψt i. But this proposal would require detailed knowledge of the specific Hamiltonian orunitary U .
In summary, circuit complexity might ultimately turn out to be just one way among others todefine an “intrinsic clock” for a quantum state, to obtain t from |ψt i. But at present, we have noother principled way to do that. So for now, circuit complexity has established itself as a useful toolin the study of the AdS/CFT correspondence.

7.1.1

Lower Bounds

The preceding discussion left at least one question glaringly open: namely, can we prove any lower
bounds on Cε (|ψt i), for natural examples of unitary transformations U , showing that it really doesgrow linearly with t, as Susskind’s proposal would predict and require?
Alas, this is too much to hope for, in the present state of complexity theory. Here’s the reason:
Proposition 7.1.1. Suppose C(|ψbn i) > nω(1) , for some U that admits a polynomial-size quantum
circuit. Then PSPACE 6⊂ BQP/poly.
Proof. Consider the contrapositive: if PSPACE ⊂ BQP/poly, then we could prepare |ψt i for anyt ≤ bn in polynomial time, by computing the “aggregated amplitudes” βx and γx in PSPACE, as in
the method of Proposition 3.3.5 from Lecture 3.
(Incidentally, by a simple counting/dimension argument, analogous to that in Lecture 3, one canprove without much difficulty that C(|ψt i) will become exponentially large after doubly-exponential
ntime, t ∼ 22 . But this isn’t enough for Susskind’s proposal.)
As a consequence of Proposition 7.1.1, one can’t possibly prove that circuit complexity grows
linearly with time under unitary evolution, without also proving PSPACE 6⊂ BQP/poly.
Still, despite Proposition 7.1.1, perhaps we can prove a lower bound on Cε (|ψt i) assuming somereasonable complexity hypothesis? Indeed we can, as in the following result.
Theorem 7.1.2 (Aaronson-Susskind (paper still in preparation)). There’s an n-qubit unitarytransformation U , implemented by a polynomial-size quantum circuit, for which the following holds.
LetX
1|ψt i = n/2|yi ⊗ U t |yi.
2ny∈{0,1}

66

Then Cε (|ψt i) > nω(1) for some t > cn , unless PSPACE ⊂ PP/poly. Here 1 < c < 2 is an absolute
constant.
We remark that one can get a stronger conclusion at the cost of a stronger complexity assumption.
For example, if SPACE(n) requires PP-circuits of size 2Ω(n) , then Cε (|ψt i) = 2Ω(n) for time t = 2O(n) .
On the other hand, because of blowup in the reduction, we don’t currently know how to prove,on the basis of any “standard” complexity assumption, that Cε (|ψt i) grows linearly with t; thatremains a question for future work.
Proof of Theorem 7.1.2. Take U to be the step function of some reversible, computationally-universal
cellular automaton. For this construction, U can even be a classical reversible CA, but we do needit to be able to solve PSPACE-complete problems using polynomial memory and exponential time.
Fortunately, it’s well-known that there are many reversible CAs with this behavior. A result due
to Lange, McKenzie, and Tapp [LMT96] even assures us that, if we don’t care about exponential
overhead in time (as we don’t, in this case), then making a Turing machine reversible incurs only aconstant-factor overhead in the required memory.
So suppose toward a contradiction that Cε (|ψt i) ≤ nO(1) for all t ≤ 2n . Let L be a PSPACEcomplete language. Then we’ll see how to decide L in the complexity class PostBQP/poly = PP/poly.
The advice to the PostBQP machine will simply be a description of a small quantum circuit that
prepares the state |ψt i, for some t = cn that provides sufficient time for the PSPACE computation
to have returned its answer.
So the PostBQP/poly machine prepares this state |ψt i, and then postselects on the first register of|ψt i being in the state y = Sx , where Sx is the encoding of the input x used by the cellular automaton.
Conditioned on the first register being observed in the state |Sx i, the second register will be in thestate U t |Sx i, which encodes the information about whether x ∈ L. Therefore PSPACE ⊂ PP/poly
as desired.
(One fine point: we need ε exponentially small to make sure that the error in the preparation
doesn’t affect the post-selected state.)
Note that, in the proof of Theorem 7.1.2, we needed some condition on the unitary U . If, forexample, U = I were the identity, then clearly we’d never increase complexity no matter how often
U was applied.
Previously, some quantum gravity theorists had speculated that the relevant condition on U
would have something to do with its chaotic mixing behavior, or sensitive dependence on initialconditions. But the condition that we were actually able to use, for a hardness reduction, wasbasically computational universality. Universality might be related to chaos, but the exact nature of
the relationship is unclear.
The good news is that “being able to implement universal reversible computation” is an extremely
mild condition on a unitary or Hamiltonian—one that we can confidently expect the real laws ofquantum gravity (whatever they are) to satisfy. Thus, unlike with (say) the proofs of Theorems
6.4.1 and 6.5.3, Theorem 7.1.2 is not a case of a hardness reduction producing instances of thetarget problem unlike those that would ever arise in real life. Rather, this argument should apply
even to the physically-relevant choices of U .
If we care about the circuit complexity of approximating |ψt i—that is, about Cε (|ψt i) for large
values of ε—we can use a similar reduction, with the difference that now we need to start from a
PSPACE-complete language L with the property of worst-case/average-case equivalence. In otherwords, we need a problem that’s PSPACE-complete to solve even for (say) 90% of inputs x ∈ {0, 1}n ,67

so that even advice that let a PostBQP/poly machine prepare |ψbn i to within some constant error
would still let that machine decide PSPACE. Fortunately, such problems are well-known to exist; seefor example [AFK89]. (As an example, one can start with any PSPACE-complete Boolean function
f : {0, 1}n −→ {0, 1}, then take the unique extension of f as a multilinear polynomial over a large
finite field.)
As we alluded to before, there are several reasonable ways to define the “quantum circuit
complexity” of the state |ψt i, other than the way we chose. Some of those ways lead to interestingchanges to the picture of CFT complexity that we’ve outlined so far.
To illustrate, let’s consider a measure that we call separable complexity, and denote Csep,ε (|ψi).
This is defined as the size of the smallest separable quantum circuit C that generates |ψi to withinerror ε, starting from the initial stateX1√|xi|xi.
2n x∈{0,1}nHere, separable means that C must have no gates that cut across the boundary between the two
subsystems, i.e., it must act independently on both halves of the state. (Restricting to such circuits
seems reasonable, since the two halves of the state are located in two regions of space that are
only connected by a non-traversable wormhole!) We also don’t allow the use ancilla qubits in thisdefinition.
Because we assumed the initial state to be maximally entangled, the above is equivalent torequiring the circuit to act only on the second register. This is again because for any unitary U , wehaveXX
U |xi ⊗ |xi =|xi ⊗ U T |xi.
xx

We now observe that Csep,ε (|ψt i) = Cε (U t ): in other words, the separable circuit complexity of|ψt i, as a state, equals the circuit unitary complexity of U t as a unitary. To see this:• The ≤ direction is obvious—if we have a circuit to compute U t , then we can generate |ψt ifrom the maximally entangled state by acting only on the second register.
• The ≥ direction follows from the property of the maximally entangled state that for all
unitaries U 6= V ,X
X|xi ⊗ U |xi =6|xi ⊗ V |xi.
xxI.e., the only way to generate |ψt i from the maximally entangled state, by acting on thesecond register alone, is to apply U t itself. Furthermore, while in principle one could apply
circuits U and V to the two registers separately, it’s easy to see that one doesn’t gain anything
this way: one could instead just apply V U T to the second register, using a circuit with at
most C(U ) + C(V ) gates. (Here we assume, for simplicity, that our gate set is closed undertransposition. By the Solovay-Kitaev Theorem, dropping this assumption increases the circuit
complexity by at most a logO(1) (1/ε) factor.)
As a result, we see that if Csep,ε (|ψt i) ≤ nO(1) , then PSPACE ⊂ BQP/poly—a stronger conclusion
than the PSPACE ⊂ PP/poly that we got from Theorem 7.1.2 for the standard (non-separable)
complexity.
68

To summarize, we have the following chain of implications:nCsep,ε (|ψt i) ≤ nO(1) ⇔ Csep,ε (U b ) ≤ nO(1)⇓nPSPACE ⊂ BQP/poly ⇔ Cε (U b ) ≤ nO(1)⇓Cε (|ψt i) ≤ nO(1)⇓PSPACE ⊂ PP/poly
where U implements the step function of a reversible classical universal cellular automaton. It’s
open whether one can strengthen these results. Note also that a solution to the Unitary Synthesis
Problem, from Lecture 3, might let us reverse the first “down” implication.

69

Lecture 8
Private-Key Quantum Money
Lecturer: Scott Aaronson

Scribe: Oded Regev

We now start on our final application of the complexity of states and unitaries—one that, on its
face, seems about as remote as possible from quantum gravity, though it will turn out not to becompletely unrelated.
In the late 1960s, long before anyone even dreamed of quantum computation, Stephen Wiesner,then a graduate student, wrote a paper proposing to use quantum physics to construct unforgeablemoney. The paper was repeatedly rejected until it appeared 14 years later in SIGACT News [Wie83].
Because of the copyability of classical information, all existing approaches to electronic cash
have to rely either on a trusted third party like a bank or credit card agency, or sometimes on theentire Internet (in the case of Bitcoin’s block chain). To get around this, Wiesner’s basic idea was toexploit what we now call the No-Cloning Theorem (from Lecture 1), stating that there’s no way to
duplicate an unknown quantum state. Why couldn’t we use this phenomenon to create “quantum
banknotes,” which could be held and traded, yet which would be physically impossible to copy?
In implementing quantum money, the obvious engineering difficulty is that the users need totransport quantum states around (ideally, at room temperature and in their wallets), while keeping
them coherent for more than a tiny fraction of a second! It’s mainly this issue that’s so far prevented
the practical realization of quantum money—in contrast to quantum key distribution, a closelyrelated idea (also originating in Wiesner’s 1969 paper) that’s already seen some modest commercial
deployment. In any case, from now on we’ll ignore implementation issues and concentrate on thetheory of quantum money.
For simplicity, we’ll assume throughout that quantum money comes in only one denomination.
At a high level, quantum money needs to satisfy two requirements: it needs to be(1) unclonable (obviously), but also(2) verifiable—that is, users should be able to verify that a quantum money state presented tothem is a valid state and not some junk.

8.1

The Wiesner and BBBW Schemes

Wiesner’s proposal is now as follows. Each quantum banknote consists of two parts. The first partis an n-bit classical string s, called the serial number, chosen independently and uniformly for eachnote. Just like with today’s classical money, the serial number serves to identify each banknote
uniquely.

70

The second part is an n-qubit quantum state of the form
|0i|−i|1i|1i|+i · · · |0iwhich is chosen uniformly from among all 4n possible n-qubit tensor products of |0i, |1i, |+i, and|−i. The bank that generates the notes stores a database of pairs, (s, f (s)) where f (s) is a classicaldescription of the quantum state |ψs i generated for note s (note that f (s) is 2n bits long).
Clearly, if a user takes a note (s, |ψi) back to the bank, the bank can verify the note’s veracity.
Indeed, the bank simply needs to check in its database that s is a valid serial number, and then if it
is, measure each qubit of |ψs i in the appropriate basis ({|0i, |1i} or {|+i, |−i}) to make sure thatit’s in the state corresponding to f (s). A user who wants to verify a note needs to go to the bank(or send the note to the bank over a quantum channel).
What about counterfeiting? Assume the counterfeiter is given a legitimate banknote, (s, |ψs i).
Can he generate from it two notes that both pass the bank’s verification with high probability?
The naı̈ve strategy to do so would simply be to measure each qubit in (say) the standard basis
and then copy the result. This strategy succeeds with probability (5/8)n . (Why? Qubits that
happen to be in the standard basis are copied successfully; this happens with probability 1/2. The
remaining qubits are damaged by the measurement, so that the result has probability 1/4 of passing
both measurements.)
A less trivial strategy generates two entangled notes such that both pass verification withprobability (3/4)n . This turns out to be tight! Answering a question posed by Aaronson, this wasproven in 2012 by Molina, Vidick, and Watrous [MVW99], and independently by Pastawski et al.
[PYJ+ 11], using semidefinite formulations of the problem faced by the counterfeiter. (For somereason, from 1969 until 2012, people had been satisfied with handwavy, qualitative security analysesof Wiesner’s scheme.)
Strictly speaking, the results of [MVW99, PYJ+ 11] don’t constitute a full security proof, since(for example) they don’t consider a counterfeiter who starts with multiple legitimate banknotes,(s1 , |ψs1 i), . . . , (sm , |ψsm i). However, in recent unpublished work, Aaronson gives a general security
reduction that implies, as a special case, the full security of Wiesner’s scheme.
The obvious disadvantage of Wiesner’s scheme is the need to bring a banknote back to thebank in order to verify it. However, even if we set that aside, a second disadvantage is that inorder to verify, the bank (and all its branches) need to maintain a database of all banknotes everproduced. In 1982, Bennett, Brassard, Breidbart, and Wiesner (BBBW) [BBBW82] suggested using
a standard cryptographic trick to get rid of the giant database. Namely, they proposed replacing therandom function f (s) by a cryptographic pseudorandom function—or more precisely, by a function
fk : {0, 1}n −→ {0, 1}2n chosen from a pseudorandom function family (PRF) {fk }k . That way, thebank need only store a single secret key k. Given a banknote (s, |fk (s)i), the bank then verifies thenote by first computing fk (s) and then measuring each qubit of |fk (s)i in the appropriate basis, as
before.
Intuitively, by doing this we shouldn’t be compromising the security of the scheme, since a
pseudorandom function can’t be efficiently distinguished from a truly random function anyway.
More formally, we argue as follows: suppose a counterfeiter could successfully attack the BBBW
scheme. Then we could distinguish the pseudorandom function fk from a truly random function,
by running the attack with the given function and then checking whether the attack succeeds incounterfeiting. Given a pseudorandom function, the attack should succeed by assumption, whereas
given a truly random function, the attack can’t succeed because of the security of Wiesner’s originalscheme.
718.2

Formal Underpinnings

To make the above discussion rigorous, we must define what exactly we mean by quantum money,
and what properties we need it to satisfy. This was done by Aaronson [Aar09] in 2009.
Definition 8.2.1 ([Aar09]). A private-key quantum money scheme consists of two polynomial-timequantum algorithms:• Bank(k) generates a banknote $k corresponding to a key k. ($k can be a mixed statecorresponding, e.g., to a mixture over serial numbers.)• Ver(k, ρ) verifies that ρ is a valid note for the key k.
We say that the scheme has completeness error ε if valid banknotes $k generated by Bank(k) are
accepted by Ver(k, $k ) with probability at least 1 − ε. We say that the scheme has soundness
error δ if for all polynomial-time counterfeiters C outputting some number r of registers, and all
polynomials q,
P[Count(k, C($qk )) > q] < δ ,where Count is the procedure that runs Ver(k, ·) on each of the r registers output by C and counts
the number of times it accepts. (So informally, we’re asking that given q banknotes, C cannot
generate more than q banknotes, except with probability δ.)
Let’s also define a “mini-scheme” to be a scheme as above but with soundness restricted to q = 1
and r = 2, i.e., there’s only one bill in circulation and the counterfeiter is asked to produce twovalid bills.
Theorem 8.2.2 (Aaronson 2013, unpublished). We can build a private-key quantum money schemewith negligible completeness and soundness errors given• a secure mini-scheme, and• a pseudorandom function family (PRF) {fk }k secure against quantum attacks.
Proof Sketch. The construction is as follows. Given a mini-scheme M that generates a quantum
state $k , we define a money scheme M 0 whose bills are of the form
$0k,s := |sihs| ⊗ $fk (s) ,where s is chosen uniformly at random. For verification, the bank applies Ver(fk (s)).
We remark that when we apply this construction to the “mini-Wiesner” scheme (i.e., Wiesner’s
scheme without the serial number), we get the BBBW scheme. To get Wiesner’s original scheme,
we should replace fk by a truly random function f .
The proof of completeness is easy, while soundness (or security) uses a hybrid argument.
Intriguingly, the proof of soundness uses the PRF assumption twice: first one argues that breaking
M 0 implies either an attack on the PRF (i.e., that it can be distinguished from a uniform function)or an attack on M 0 as a mini-scheme; second, one argues that an attack on M 0 as a mini-scheme
implies either an attack on the PRF, or an attack on M (as a mini-scheme).

72What should we use as the PRF family? There are many constructions of PRF families incryptography based on various cryptographic assumptions. There’s also a general result, which saysthat the existence of a one-way function (the most basic of all cryptographic primitives, defined in
Lecture 6, without which there’s basically no crypto) is already enough to imply the existence of
PRFs. This implication is proved in two steps:
HILL

GGM

OWF =⇒ PRG =⇒ PRF ,The first step—that OWFs imply pseudorandom generators (PRGs), stretching n random bits intonO(1) pseudorandom bits—is due to Håstad et al. [HILL99]. The second step—that PRGs imply
PRFs, stretching n random bits into 2n pseudorandom bits—is due to Goldreich, Goldwasser, andMicali [GGM86]. Both steps are nontrivial, the first extremely so.
In our case, of course, we need a PRF family secure against quantum attacks. Fortunately,
as discussed in Lecture 6, there are many known candidate OWFs that are quantum-secure as
far as anyone knows. Also, one can show, by adapting the HILL and GGM arguments, thatquantum-secure PRFs follow from quantum-secure OWFs. The first step, that of HILL, applies
as-is to the quantum setting. The GGM step, however, breaks in the quantum setting, because it
makes crucial use of “the set of all inputs queried by the attacker,” and the fact that this set is of
at most polynomial size—something that’s no longer true when the attacker can query all 2n input
positions in superposition. Luckily, though, in 2012, Zhandry [Zha12] found a different proof of the
GGM security reduction that does apply to quantum attackers.1

8.3

Security/Storage Tradeoff

To summarize, we’ve seen that Wiesner’s scheme is unconditionally secure but requires a huge
database, and that it can be transformed as above to the BBBW scheme, which is only computationally secure but which doesn’t require a huge database. We also remarked that quantum-secure
PRFs, as needed in the BBBW scheme, are known to follow from quantum-secure OWFs.
Given the discussion above, one might wonder whether there are quantum money schemes thatare (1) information-theoretically secure, and (2) don’t require lots of storage. It turns out that such
schemes are impossible.
Theorem 8.3.1 (Aaronson 2013, unpublished). Any scheme in which the bank stores only n bits
can be broken by an exponential-time quantum counterfeiter, using only poly(n) legitimate money
states, and O(n) verification queries to the bank. (Alternatively, we can avoid the verification queries,
and instead get an output that passes verification with probability Ω(1/n).)
Proof. We fix the notation k ∗ ∈ {0, 1}n for the actual secret stored by the bank. “We” (that is,O(1) , and we need to achieve a non-negligible
the counterfeiter) are given the state $⊗mk∗ for m = n
probability of producing m + 1 or more quantum money states that all pass verification.
A naı̈ve strategy would be brute-force search for the key k ∗ , but that doesn’t work for obvious
reasons. Namely, we have only poly(n) legitimate bills at our disposal (and the bank is not thatnaive to issue us a brand-new bill if ours doesn’t pass verification!). And we can make only poly(n)queries to the bank.
1
On the other hand, for applications to quantum money, one can assume classical queries to the pseudorandomfunction fk —since the set of banknotes that the attacker possesses is a determinate, classical set—and thus one doesn’tstrictly speaking need the power of Zhandry’s result.

73

So instead, we’ll recurse on the set of “potential candidate secrets S,” and the crucial statement
will say that at any given iteration, S shrinks by at least a constant factor.
A word of warning: we do not promise to find the actual value k ∗ (e.g. if $k∗ = $k0 for someother k 0 , we can never distinguish between the two). We only claim that we can come up with a“linotype” S 3 k ∗ that’s good enough for forging purposes.
Initially, we don’t possess any knowledge of k ∗ , so we simply set S := {0, 1}n .
Now let S be our current guess. We generate (not surprisingly) the uniform mixture over thecorresponding bills:
1 X
σS =|$k ih$k ||S|k∈S

and submit it to the bank.
If σS is accepted, then S is our linotype; we can use it to print new bills.
The more interesting case is when Ver(k ∗ , σS ) rejects with high probability. Then, having
unlimited computational power, we can construct for ourselves the set U 3 k ∗ of all those k forwhich Ver(k, σS ) rejects with high probability. Next, we use poly(n) copies of the legitimate state$k∗ to find (we’ll later explain how to do it) some key k 0 ∈ U for which Ver(k 0 , $k∗ ) accepts withhigh probability. And lastly, we use this key k 0 to go over all individual states $k in the mixture σS ,and weed out all those k for which Ver(k 0 , $k ) rejects with high probability. Note that k ∗ survives(which is the only property we need to maintain). Meanwhile, the fact that at least a constantfraction of entries in S is removed follows from going through the definitions and from a simple
application of Markov’s inequality.
So all that’s left is to explain how to find k 0 using only poly(n) legitimate bills.
For that, we use two more ideas: error amplification and the “Almost As Good As New Lemma”(Lemma 1.3.1 from Lecture 1). Using error amplification and poly(n) copies of the legitimate bill,
we can assume the following without loss of generality:• Ver(k ∗ , $k∗ ) accepts with the overwhelming probability 1 − exp(−Cn), whereas• for any “bad” key k (defined as a key for which the original acceptance probability is less than0.8), Ver(k, $k∗ ) accepts with exponentially small probability exp(−Cn).
Now consider doing a brute-force search through U , say in lexicographic order, repairing our state$k∗ using the Almost As Good As New Lemma as we go along. Then the hope is that our state will
still be in a usable shape by the time we reach k ∗ —since any “bad” keys k that we encounter along
the way will damage the state by at most an exponentially small amount.
Unfortunately, the above doesn’t quite work; there’s still a technical problem that we need todeal with. Namely: what if, while searching U , we encounter keys that are “merely pretty good, but
not excellent”? In that case, the danger is that applying Ver(k, ·) will damage the state substantially,
but still without causing us to accept k.
One might hope to solve this by adjusting the definitions of “good” and “bad” keys: after all, if
k was good enough that it caused even an amplified verifier to have a non-negligible probability ofaccepting, then presumably the original, unamplified acceptance probability was at least (say) 0.7,
if not 0.8. The trouble is that, no matter how we set the threshold, there could be keys that fallright on the border, with a high enough acceptance probability that they damage our state, but nothigh enough that we reliably accept them.
To solve this problem, we use the following lemma, which builds on work by Aaronson [Aar06],
with an important correction by Harrow and Montanaro [HM16].
74

Lemma 8.3.2 (“Secret Acceptor Lemma”). Let M1 , . . . , MN be known 2-outcome POVMs, and letρ be an unknown state. Suppose we’re promised that there exists an i∗ ∈ [N ] such that
P[Mi∗ (ρ) accepts] ≥ p.
Then given ρ⊗r , where r = O



log4 Nε2, there’s a measurement strategy to find an i ∈ [N ] such that

P[Mi (ρ) accepts] ≥ p − ε,with success probability at least 1 − N1 .
Proof Sketch. The key ingredient is a result called the “Quantum OR Bound,” which states thefollowing:• Let M1 , . . . , MN be known 2-outcome POVMs, and let ρ be an unknown state. Then givenρ⊗r , where r = O(log N ), there exists a measurement strategy that accepts with overwhelming
probability if there exists an i such that P[Mi (ρ) accepts] ≥ 2/3, and that rejects withoverwhelming probability if P[Mi (ρ) accepts] ≤ 1/3 for all i.
To prove the Quantum OR Bound, the obvious approach would be to apply an amplified version of
Mi to ρ⊗r , for each i in succession. The trouble is that there might be i’s for which the amplified
measurement accepts with probability that’s neither very close to 0 nor very close to 1—in whichcase, the measurement could damage the state (compromising it for future measurements), yet
without leading to an overwhelming probability of acceptance. Intuitively, the solution should
involve arguing that, if this happens, then at any rate we have P[Mi (ρ) accepts] > 1/3, and therefore
it’s safe to accept. Or in other words: if we accept on the ith measurement, then either Mi (ρ)
accepts with high probability, or else our state was damaged by previous measurements—but in thelatter case, some of those previous measurements (we don’t know which ones) must have accepted ρwith a suitably high probability.
The trouble is that, if M1 , . . . , MN were chosen in a diabolical way, then applying them inorder could slowly “drag” the state far away from the initial state ρ⊗r , without any of the Mi ’s
accepting with high probability (even though the later measurements would have accepted ρ⊗r itself).
In 2006, Aaronson [Aar06] encountered this problem in the context of proving the containment
QMA/qpoly ⊆ PSPACE/poly, which we mentioned as Theorem 5.6.6 in Lecture 5. In [Aar06],
Aaronson claimed that one could get around the problem by simply choosing the Mi ’s in random
order, rather than in the predetermined (and possibly adversarial) order M1 , . . . , MN .
Unfortunately, very recently Harrow and Montanaro [HM16] found a bug in Aaronson’s proof ofthis claim. As they point out, it remains plausible that Aaronson’s random measurement strategy
is sound—but if so, then a new proof is needed (something Harrow and Montanaro leave as afascinating open problem).
In the meantime, though, Harrow and Montanaro recover the Quantum OR Bound itself, bygiving a different measurement strategy for which they are able to prove soundness. We refer thereader to their paper for details, but basically, their strategy works by first placing a control qubit in
the |+i state, and then applying the amplified measurements to ρ⊗r conditioned on the control qubit
being |1i, and periodically measuring the control qubit in the {|+i, |−i} basis to check whether themeasurements have damaged the state by much. We accept if either some measurement accepts, orthe state has been found to be damaged.
75Now, once we have the Quantum OR Bound, the proof of Lemma 8.3.2 follows by a simple
application of binary search (though this increases the number of copies of ρ needed by a further
polylog(N ) factor). More precisely: assume for simplicity that N is a power of 2. Then we first
apply the Quantum OR Bound, with suitably-chosen probability cutoffs, to the set of measurements
M1 , . . . , MN/2 . We then apply the OR Bound separately (i.e., with fresh copies of ρ) to the set
MN/2+1 , . . . , MN . With overwhelming probability, at least one of these applications will accept,
in which case we learn a subset of half the Mi ’s containing a measurement that accepts ρ withhigh probability—without loss of generality, suppose it’s M1 , . . . , MN/2 . We then recurse, dividing
M1 , . . . , MN/2 into two subsets of size N/4, and so on for log N iterations until we’ve isolated an i∗such that Mi∗ accepts with high probability. At each iteration we use fresh copies of ρ.
There’s just one remaining technical issue: namely, at each iteration, we start with a promisethat the region we’re searching contains a measurement Mi that accepts ρ with probability at least p.
We then reduce to a smaller region, which contains a measurement that accepts ρ with probability
at least p − δ, for some fudge factor δ > 0. Thus, if δ was constant, then we could only continue fora constant number of iterations. The solution is simply to set δ := logε N , where ε is the final error
bound in the lemma statement. This blows up the number of required copies of ρ, but only (onecan check) to
 4 
log N
O
.
ε2

8.3.1

Open Problems

As usual, we can now ask: is there any collapse of complexity classes, such as P = PSPACE, thatwould make the counterfeiting algorithm of Theorem 8.3.1 computationally efficient, rather thanmerely efficient in the number of legitimate bills and queries to the bank? We’ve seen that, if
quantum-secure OWFs exist, then the algorithm can’t be made efficient—but just like in the caseof firewalls and the HH Decoding Task, we don’t have a converse to that result, showing that if
counterfeiting is hard then some “standard” cryptographic assumption must fail.
Meanwhile, the proof of Lemma 8.3.2 raises a fascinating open problem about quantum state
tomography, and we can’t resist a brief digression about it.
Let ρ be an unknown state, and let E1 , . . . , EN be some list of known two-outcome POVMs.
Suppose we wanted, not merely to find an i∗ for which Tr(Ei∗ ρ) is large, but to estimate all Tr(Ei ρ)’s
to within some additive error ε > 0, with success probability at least (say) 0.99. What resources areneeded for this?
The task is trivial, of course, if we have O(N log N ) fresh copies of ρ: in that case, we just apply
every Ei to its own log N copies.
But suppose instead that we’re given only polylog N copies of ρ. Even in that case, it’s not hard
to see that the task is achievable when the Tr(Ei ρ)’s are promised to be bounded away from 1/2(e.g., either Tr(Ei ρ) > 2/3 or Tr(Ei ρ) < 1/3 for all i). For then we can simply apply the amplified
Ei ’s in succession, and use the Almost As Good As New Lemma to upper-bound the damage toρpolylog N .
We now raise the following open question:76

Question 8.3.3 (“The Batch Tomography Problem”). Is the above estimation task achievablewith only polylog N copies of ρ, and without a promise on the probabilities?
Note that this problem doesn’t specify any dependence on the Hilbert space dimension d, since
it’s conceivable that a measurement procedure exists with no dimension dependence whatsoever(as happened, for example, for the Quantum OR Bound and Lemma 8.3.2). But a nontrivial
dimension-dependent result (i.e., one that didn’t simply depend on full tomography of ρ) would also
be of interest.

8.4

Interactive Attacks

To return to quantum money, we’ve seen that there’s an inherent tradeoff between Wiesner-styleand BBBW-style private-key quantum money schemes. Whichever we choose, though, there’s animmediate further problem. Namely, a counterfeiter might be able to use repeated queries to thebank—a so-called interactive attack—to learn the quantum state of a bill.
Indeed, this could be seen as a security flaw in our original definition of private-key quantum
money. Namely, we never specified what happens after the customer (or, we might as well assume,
a counterfeiter) submits a bill for verification. Does the counterfeiter get back the damaged (that is,post-measured) bill if it’s accepted, or does the bank issue a brand-new bill? And what happens if
the bill doesn’t pass verification? The possibilities here vary from the bank being exceedingly naı̈ve,
and giving the bill back to the customer even in that case, to being exceedingly strict and calling
the police immediately. As we’ll see in Lecture 9, we can get schemes that are provably secure evenwith a maximally naı̈ve, bill-returning bank, but proving this requires work.
As for the original Wiesner and BBBW schemes, it turns out that both can be fully broken by
an interactive attack. To see this, let’s first consider the “naı̈ve bank” scenario: the bank returns
the bill even if it didn’t pass the verification. In that scenario, a simple attack on Wiesner’s scheme
was independently observed by Aaronson [Aar09] and by Lutomirski [Lut10].
The attack works as follows: the counterfeiter starts with a single legitimate bill,|$i = |θ1 i|θ2 i · · · |θn i.
The counterfeiter then repeatedly submits this bill to the bank for verification, swapping out
the first qubit |θ1 i for |0i, |1i, |+i, and |−i in sequence. By observing which choice of |θ1 i causes
the bank to accept, after O(log n) repetitions, the counterfeiter knows the correct value of |θ1 i with
only (say) 1/n2 probability of error. Furthermore, since the bank’s measurements of |θ2 i, . . . , |θn i
are in the correct bases, none of these qubits are damaged at all by the verification process. Next
the counterfeiter repeatedly submits |$i to the bank, with the now-known correct value of |θ1 i, but
substituting |0i, |1i, |+i, and |−i in sequence for |θ2 i, and so on until all n qubits have been learned.

8.4.1

The Elitzur-Vaidman Bomb Attack

Of course, the above counterfeiting strategy fails if the bank adopts the simple countermeasure ofcalling the police whenever a bill fails verification (or perhaps, whenever too many bad bills get
submitted with the same serial number)!
In 2014, however, Nagaj and Sattath [NS14] cleverly adapted the attack on Wiesner’s scheme,
so that it works even if the bank calls the police after a single failed verification. Their construction77

is based on the Elitzur-Vaidman bomb [EV93], a quantum effect that’s related to Grover’s algorithm
but extremely counterintuitive and interesting in its own right—so let’s now have a digression about
the Elitzur-Vaidman bomb.
Suppose someone has a package P that might or might not be a bomb. You can send to theperson a bit b ∈ {0, 1}. You always get the bit back. But if you send b = 1 (“I believe you have abomb in your package”) and P is a bomb, then it explodes, killing everyone. The task is to learn
whether or not P is a bomb without actually setting it off.
This is clearly impossible classically. For the only way to gain any information about P iseventually to dare the question b = 1, with all its consequences.
Not so quantumly! We can model the package P as an unknown 1-qubit operator, on a qubit |bithat you send. If there’s no bomb, then P simply acts as the identity on |bi. If there is a bomb,then P measures |bi in the {|0i, |1i} basis. If P observes |0i, then it returns the qubit to you, while
if P observes |1i, then it sets off the bomb.
Now letcos ε − sin ε
Rε =sin ε cos εbe a unitary that rotates |bi by a small angle ε > 0.
Then you simply need to use the following algorithm:• Initialize |bi := |0iπtimes:• Repeat 2ε– Apply Rε to |bi– Send |bi to P

• Measure |bi in the {|0i, |1i} basis• If the result is |0i then output “bomb”; if |1i then output “no bomb”
Let’s analyze this algorithm. If there’s no bomb, then the invocations of P do nothing, so |biπsimply gets rotated by an ε angle 2εtimes, evolving from |0i to |1i. If, on the other hand, there
is a bomb, then you repeatedly submit |bi = cos ε|0i + sin ε|1i to P , whereupon P measures |biin the standard basis, observing |1i (and hence setting off the bomb) with probability sin2 ε ≈ ε2 .
πThus, across all 2εinvocations, the bomb gets set off with total probability of order ε2 /ε = ε,which of course can be made arbitrarily small by choosing ε small enough. Furthermore, assuming
the bomb is not set off, the qubit |bi ends up in the state |0i, and hence measuring |bi reveals(non-destructively!) that the bomb was present. Of course, what made the algorithm work was theability of quantum measurements to convert an ε amplitude into an ε2 probability.
Nagaj and Sattath [NS14] realized that one can use a similar effect to attack Wiesner’s scheme
even in the case of a suspicious bank. Recall the attack of Aaronson [Aar09] and Lutomirski [Lut10],which learned a Wiesner banknote one qubit |θi i at a time. We want to adapt this attack so thatthe counterfeiter still learns |θi i, with high probability, without ever submitting a banknote thatfails verification. In particular, that means: without ever submitting a banknote whose ith qubit ismore than some small ε away from |θi i itself. (Just like in the earlier attack, we can assume thatthe qubits |θj i for j =6 i are all in the correct states, as we vary |θi i in an attempt to learn a classicaldescription of that qubit.)78

The procedure by Nagaj et al., like the previous procedure, works qubit by qubit: this is okay
since we get our bill back if it has been validated, and if we fail then we have more pressing issues
to worry about than learning the remaining qubits. So let’s assume n = 1: that is, we want to learn
a single qubit |θi ∈ {|0i, |1i, |+i, |−i}.
The algorithm is as follows: we (the counterfeiter) prepare a control qubit in the state |0i. Weπthen repeat the following, 2εtimes:• Apply a 1-qubit unitary that rotates the control qubit by ε counterclockwise.
• Apply a CNOT gate from the control qubit to the money qubit |θi.
• Send the money qubit to the bank to be measured.
To see why this algorithm works, there are four cases to consider:• If |θi = |+i, then applying a CNOT to |θi does nothing. So the control qubit just rotates byπ
an ε angle 2εtimes, going from |0i to |1i. In no case does the bank’s measurement yield theoutcome |−i.
• If |θi = |0i, then applying a CNOT to |θi produces the statecos(ε)|00i + sin(ε)|11i.
The bank’s measurement then yields the outcome |0i with probability cos2 (ε) ≈ 1 − ε2 .
Assuming |0i is observed, the state collapses back down to |00i, and the cycle repeats. By theunion bound, the probability that the bank ever observes the outcome |1i is at mostπsin2 (ε) = O(ε).
2ε• If |θi = |1i, then the situation is completely analogous to the case |θi = |0i.
• If |θi = |−i, then applying a CNOT to |αi produces the state(cos(ε)|0i − sin(ε)|1i) ⊗ |−i.
So at the next iteration, the control qubit gets rotated back to |0i (and nothing happens);
then it gets rotated back to cos(ε)|0i − sin(ε)|1i, and so on, cycling through those two states.
In no case does the bank’s measurement yield the outcome |+i.
To summarize, if |θi = |+i then the control qubit gets rotated to |1i, while if |θi is any of
the other three possibilities, then the control qubit remains in the state |0i (or close to |0i) withoverwhelming probability. So at the end, measuring the control qubit in the {|0i, |1i} basis lets us
distinguish |θi = |+i from the other three cases. By symmetry, we can repeat a similar procedure
for the other three states, and thereby learn |θi, using O(1/ε) trial verifications, with at most O(ε)
probability of getting caught. So by repeating the algorithm for each θi , we learn the entire billwith O(n/ε) trial verifications and at most O(nε) probability of getting caught.
While we explained these attacks for Wiesner’s scheme, the same attacks work with only minor
modifications for the BBBW scheme—or indeed, for any scheme where the banknotes consist ofunentangled qubits, and a banknote is verified by projectively measuring each qubit separately.
79However, having explained these attacks, we should also mention an extremely simple fix forthem. The fix is just that, rather than ever returning a bill to a customer after verification, the bankdestroys the bill, and hands back a new bill (with a new serial number) of the same denomination!
If this is done, then the original security definition that we gave for private-key quantum money
really does make sense.

8.5

Quantum Money and Black Holes

We end this lecture with the following observation. As we saw above, quantum-secure OWFs areenough to obtain a private-key quantum money scheme with small secret. It can be shown that if,
moreover, the OWFs are injective, they give us something additional: namely, an “injective” privatekey quantum money scheme, one where distinct serial numbers k 6= k 0 map to nearly-orthogonalbanknotes, |h$k |$k0 i| < ε. Now, we saw in Lecture 6 that injective, quantum-secure OWFs are alsoenough to imply that the HH Decoding Task is hard.
But is there any direct relationship between private-key quantum money and the HH Decoding
Task, not mediated by OWFs? It turns out that there is. To see this, in Aaronson’s first hardness
result for the HH Decoding Task (i.e., the first construction in Theorem 6.5.3), we simply need toreplace the injective OWF output |f (x)i by the output |$k i of an injective private-key quantum
money scheme, yielding the state|ψiRBH = √1

X

2n+1 k∈{0,1}n|k 0p(n)−n , 0iR |0iB + |$k , 1iR |1i)|kiH .

Then the same argument as in the proof of Theorem 6.5.3 shows that the ability to decodeentanglement between R and B in this state would imply the ability to pass from |$k i to |ki—and
therefore, the ability to break the private-key quantum money scheme. So we get the following
consequence, which perhaps exemplifies the strange connections in this course better than any othersingle statement:
Theorem 8.5.1. Suppose there exists a secure, private-key, injective quantum money scheme withsmall keys. Then the HH Decoding Task is hard.
(Or in words: “the ability to decode the Hawking radiation from a black hole implies the ability
to counterfeit quantum money.”)
Since injective OWFs imply injective private-key quantum money with small keys, but thereverse isn’t known, Theorem 8.5.1 is stronger than Theorem 6.5.3, in the sense that it bases thehardness of HH decoding on a weaker assumption.

80Lecture 9
Public-Key Quantum Money
Lecturer: Scott Aaronson

Scribe: Alexander Razborov

As the last lecture made clear, one interesting question is whether there’s any private-key quantum
money scheme where the banknote can be returned to the customer after verification, yet that’s stillsecure against interactive attacks. We’ll return to that question later in this lecture.
But as long as we’re exploring, we might as well be even more ambitious, and ask for what
Aaronson [Aar09] called a public-key quantum money scheme. By analogy to public-key cryptography,
this is a quantum money scheme where absolutely anyone can verify a banknote, not just the bankthat printed it—i.e., where verifying a banknote no longer requires taking it to the bank at all. And
yet, despite openly publishing a verification procedure, the bank still somehow ensures that no one
can use that procedure to copy a bill efficiently.
Following Aaronson [Aar09], and Aaronson and Christiano [AC12], we now give a more precise
definition of public-key quantum money, in the style of Definition 8.2.1.
Definition 9.0.2. A public-key quantum money scheme consists of three polynomial-time algorithms:• KeyGen(0n ), which outputs a pair k = (kpub , kprivate ) (this is probabilistic, of course);• Bank(k) = $k (exactly as in Definition 8.2.1);• Ver(kpub , ρ) (same as in Definition 8.2.1, except that now the verifier has access only to the
public part of the key).
Completeness and soundness errors are defined exactly as before, replacing k with kpub inappropriate places. Completeness is defined in the worst case (with respect to the choice of k),
whereas while defining the soundness, we average over the internal randomness of KeyGen.

9.1

Public-Key Mini-Schemes

Just like we had a notion of private-key mini-schemes, we have a corresponding notion of public-key
mini-schemes.
Definition 9.1.1. A public-key mini-scheme consists of two polynomial-time algorithms:• Bank(0n ), which probabilistically outputs a pair $ = (s, ρs ) (where s is a classical serial
number);• Ver($), which accepts or rejects a claimed banknote.
81The scheme has completeness error  if
P[Ver($) accepts] ≥ 1 − .
It has soundness error δ if for all polynomial-time counterfeiters mapping $ = (s, ρs ) into two
possibly entangled states σ1 and σ2 , we have
P[Ver(s, σ1 ), Ver(s, σ2 ) both accept] < δ.
Just like in the private-key case, to go from a mini-scheme to a full money scheme, one needs anadditional ingredient. In this case, the ingredient turns out to be a conventional digital signaturescheme secure against quantum attacks. We won’t give a rigorous definition, but roughly: a digital
signature scheme is a way of signing messages, using a private key kprivate , in such a way that• the signatures can be verified efficiently using a public key kpublic , and yet• agents who only know kpublic and not kprivate can’t efficiently generate any yet-unseen message
together with a valid signature for that message, even after having seen valid signatures forany polynomial number of messages of their choice.
Now, given a public-key mini-scheme plus a quantum-secure signature scheme, the constructionthat produces a full public-key money scheme was first proposed by Lutomirski et al. in 2010
[LAF+ 10], with the security analysis given by Aaronson and Christiano in 2012 [AC12].
The idea is simply to turn a mini-scheme banknote, (s, ρs ), into a full money scheme banknote
by digitally signing the serial number s, and then tacking on the signature as an additional part ofthe serial number:$k = (s, sign(k, s), ρs ).
To check the resulting banknote, one first checks the digital signature sign(k, s) to make surethe note $k really came from the bank rather than an impostor. One then checks (s, ρs ) using theverification procedure for the underlying mini-scheme. Intuitively, then, to print more money, acounterfeiter either needs to produce new bills with new serial numbers and new signatures, thereby
breaking the signature scheme, or else produce new bills with already-seen serial numbers, thereby
breaking the mini-scheme. This intuition can be made rigorous:
Theorem 9.1.2 (Aaronson-Christiano [AC12]). If there exists a counterfeiter against the public-key
quantum money scheme above, then there also exists a counterfeiter against either the mini-schemeor the signature scheme.
The proof of Theorem 9.1.2 is a relatively standard cryptographic hybrid argument, and istherefore omitted.
Now, we have many good candidates for quantum-secure signature schemes (indeed, it follows
from a result of Rompel [Rom90] that such schemes can be constructed from any quantum-secure
one-way function). Thus, the problem of public-key quantum money can be reduced to the problem
of constructing a secure public-key mini-scheme.

82

9.2

Candidates

How can we do that? Many concrete mini-schemes were proposed over the past decade, but alas,
the majority of them have since been broken, and those that remain seem extremely hard to analyze.
To give three examples:• Aaronson [Aar09], in 2009, proposed a scheme based on stabilizer states. This scheme wassubsequently broken by Lutomirski et al. [LAF+ 10], by using a nontrivial algorithm for finding
planted cliques in random graphs.
• There were several schemes based on random instances of the QMA-complete Local Hamiltonians problem (see Lecture 4). All these schemes were then broken by Farhi et al. [FGH+ 10]
in 2010, using a new technique that they called single-copy tomography. We’ll have more to
say about single-copy tomography later.
• In 2012, Farhi et al. [FGH+ 12] proposed another approach based on knot theory. In thisapproach, a quantum banknote is a superposition over oriented link diagrams sharing a given
value v of the Alexander polynomial (a certain efficiently-computable knot invariant), with theserial number encoding v. As of 2016, this scheme remains unbroken, but it remains unclear
how to say anything else about its security (for example, by giving a reduction).

9.3

Public-Key Quantum Money Relative to Oracles

Given the apparent difficulty of constructing a secure public-key mini-scheme, perhaps we should
start with an easier question: is there even an oracle A such that, if the bank, customers, andcounterfeiters all have access to A, then public-key quantum money is possible? If (as we’d hope)
the answer turns out to be yes, then we can work on replacing A by an explicit function.
In 2009, Aaronson [Aar09] showed that there’s at least a quantum oracle (as defined in Lecture5) relative to which public-key quantum money is possible.
Theorem 9.3.1 (Aaronson 2009 [Aar09]). There exists a quantum oracle U relative to which a
public-key mini-scheme exists.
Proof Sketch. We start by fixing a mapping from n-bit serial numbers s to n-qubit pure states |ψs i,
where each |ψs i is chosen independently from the Haar measure. Then every valid banknote will
have the form (s, |ψs i), and verifying a claimed a banknote (s, ρ) will consist of projecting ρ onto
the subspace spanned by |ψs i.
Now, the quantum oracle U is simply a reflection about the subspace spanned by valid banknotes:that is,U =I −2Xs∈{0,1}n|sihs| ⊗ |ψs ihψs |.

Given this U , verifying a banknote is trivial: we just delegate the verification to the oracle.
(Technically, U also includes a hidden component, accessible only to someone who knows the bank’s
secret key k, which maps |si|0 · · · 0i to |si|ψs i, and which the bank uses to print new bills.)
How do we prove this scheme secure? On the one hand, it follows immediately from the NoCloning Theorem that a counterfeiter who had only (s, |ψs i), and who lacked access to U , would
83not be able to print additional bills. On the other hand, if a counterfeiter only had access to U , andlacked any legitimate banknote, it’s not hard to see that the counterfeiter could produce a valid
banknote (s, |ψs i) using O(2n/2 ) queries to U —but, on the other hand, that Ω(2n/2 ) queries arealso necessary, by the optimality of Grover’s algorithm (see Lecture 5).
The interesting part is to show that, even if the counterfeiter starts with a valid banknote(s, |ψs i), the counterfeiter still needs Ω(2n/2 ) queries to U to produce a second valid banknote—i.e.,
to produce any state that has nontrivial overlap with |ψs i ⊗ |ψs i. This is a result that Aaronson[Aar09] calls the Complexity-Theoretic No-Cloning Theorem (since it combines the No-Cloning
Theorem with query complexity):• Given a Haar-random n-qubit pure state |ψi, together with a quantum oracle Uψ = I − 2|ψihψ|that reflects about |ψi, one still needs Ω(2n/2 ) queries to Uψ to produce any state that hasΩ(1) fidelity with |ψi ⊗ |ψi.
We won’t prove the Complexity-Theoretic No-Cloning Theorem here, but will just sketch themain idea. One considers all pairs of n-qubit pure states |ψi, |φi such that (say) |hψ|φi| = 1/2. One
then notices that a successful cloning procedure would map these pairs to |ψi⊗2 , |φi⊗2 that satisfy1hψ|⊗2 |φi⊗2 = |hψ|φi|2 = .
4In other words, for all these pairs, the procedure needs to decrease the inner product by
1/4 = Ω(1). Given any specific pair |ψi, |φi, it’s not hard to design a single query, to the oracles
Uψ , Uφ respectively, that would decrease the inner product by Ω(1). However, by using Ambainis’sadversary method [Amb02], one can show that no query can do this for most |ψi, |φi pairs, if thepairs are chosen Haar-randomly subject to |hψ|φi| = 1/2. Rather, any query decreases the expectedsquared fidelity,hi
E|ψi,|φi |ψ|φ|2 ,by at most O(2−n/2 ), where the expectation is taken over all such pairs. This then implies that, todecrease the squared fidelity by Ω(1) for all or even most pairs, we need to make Ω(2n/2 ) queries toU —i.e., just as many queries as if we were doing pure Grover search for |ψi, rather than startingwith one copy of |ψi and then merely needing to make a second one.

9.4

The Hidden Subspace Scheme

Because it delegates all the work to the oracle U , Theorem 9.3.1 gives us little insight about how
to construct secure public-key mini-schemes in the “real,” unrelativized world. As the next step
toward that goal, one naturally wonders whether public-key quantum money can be shown possible
relative to a classical oracle A (that is, a Boolean function accessed in quantum superposition).
This question was answered by the work of Aaronson and Christiano [AC12] in 2012.
Theorem 9.4.1 (Aaronson-Christiano 2012 [AC12]). There exists a classical oracle relative towhich public-key quantum money is possible.
Proof Sketch. The construction is based on “hidden subspaces.” In particular, let S ≤ Fn2 be asubspace of the vector space Fn2 , which is chosen uniformly at random subject to dim(S) = n/2.
84

(Thus, S has exactly 2n/2 elements.) Let
S ⊥ = {x | x · s ≡ 0 (mod2) ∀s ∈ S}
be S’s dual subspace, which also has dim(S ⊥ ) = n/2 and |S| = 2n/2 .
Then in our public-key mini-scheme, each banknote will have the form (dS , |Si), where• dS is an obfuscated classical description of the subspace S and its dual subspace (which wetake to be the serial number), and•

1 X|Si = p|xi
|S| x∈S
is a uniform superposition over S.

When we feed it the serial number dS as a “password,” the classical oracle A gives us access tothe characteristic functions χS , χS ⊥ of S and S ⊥ respectively. Using these, we can easily realize a
projection onto |Si. To do so, we just do the following to our money state (which is supposed to be|Si):• Apply χS , to check that the state has support only on S elements.
• Hadamard all n qubits, to map |Si to |S ⊥ i.
• Apply χS ⊥ , to check that the transformed state has support only on S ⊥ elements.
• Hadamard all n qubits again, to return the state to |Si.
As a technical point, the oracle also contains a one-way mapping (s1 , . . . , sn/2 ) → dS , which lets
the bank find the obfuscated serial number dS for a given bill |Si that it prepares, given a basis for
S, but doesn’t let a user learn the basis for S given dS , which would enable counterfeiting.
The key claim is this: any algorithm that breaks this mini-scheme—that is, maps |dS i|Si to|dS i|Si⊗2 —must make Ω(2n/4 ) queries to the oracles χS and χS ⊥ .
This claim, whose proof we omit, is a somewhat stronger version of the Complexity-Theoretic
No-Cloning Theorem from the proof of Theorem 9.3.1. It’s stronger because, in its quest to
prepare |Si⊗2 , the counterfeiting algorithm now has access not only to a copy of |Si and a unitarytransformation that implements I − 2|SihS|, but also the oracles χS and χS ⊥ . Nevertheless, again
by using Ambainis’s quantum adversary method, it’s possible to show that there’s no faster way
to prepare a new copy of |Si, than simply by doing Grover search on χS or χS ⊥ to search for abasis for S or S ⊥ —i.e., the same approach one would use if one were preparing |Si “de novo,” withno copy of |Si to begin with. And we know that Grover search for a nonzero element of S or S ⊥requires Ω(2n/4 ) queries to S or S ⊥ respectively.
There are two further ideas needed to complete the security proof. First, the argument basedon the Complexity-Theoretic No-Cloning Theorem implies that Ω(2n/4 ) oracle queries are needed
to prepare a state that has very high fidelity with |Si⊗2 . But what about preparing a state thatmerely has non-negligible (1/poly) fidelity with |Si⊗2 , which of course would already be enoughto break the mini-scheme, according to our security definition? To rule that out, Aaronson andChristiano give a way to “amplify” weak counterfeiters into strong ones, with only a polynomial
overhead in query complexity, in any money scheme where the verification consists of a projective85

measurement onto a 1-dimensional subspace. This, in turn, relies on recent variants of amplitude
amplification that converge monotonically toward the target state (in this case, |Si⊗2 ), rather than“overshooting” it if too many queries are made (see, for example, Tulsi, Grover, and Patel [TGP06]).
The second issue is that the Complexity-Theoretic No-Cloning Theorem only rules out acounterfeiter that maps |Si to |Si⊗2 for all subspaces S with dim(S) = n/2, or at least the vast
majority of them. But again, what about a counterfeiter that only succeeds on a 1/poly fraction ofsubspaces? To deal with this, Aaronson and Christiano show that the hidden subspace scheme has
a “random self-reducibility” property: any counterfeiter C that works on a non-negligible fractionof S’s can be converted into a counterfeiter that works on any S. This is proven by giving an
explicit random self-reduction: starting with a state |Si, one can apply a linear transformationthat maps |Si to some random other subspace state |T i, while also replacing the oracles χS or
χS ⊥ by “simulated oracles” χT or χT ⊥ , which use χS and χS ⊥ to recognize elements of T and T ⊥respectively.
Now, once that we have a public-key quantum money scheme that’s secure relative to a classicaloracle, Aaronson and Christiano [AC12] observed that we get something else essentially for free:namely, a private-key quantum money scheme where bills are returned after verification, yet that’s
secure against interactive attack. This solves one of the main problems left open by Lecture 8. Let’s
now explain the connection.
Theorem 9.4.2 (Aaronson-Christiano 2012 [AC12]). There exists a private-key quantum money
scheme secure against interactive attack (with no computational assumptions needed, though withthe bank maintaining a huge database).
Proof. Each banknote has the form |zi|Sz i, where |zi is a classical serial number, and |Sz i is anequal superposition over Sz , a subspace of Fn2 of dimension n/2. The bank, in a giant database,stores the serial number z of every bill in circulation, as well as a basis for Sz . When the user
submits |zi|Sz i to the bank for verification, the bank can use its knowledge of a basis for Sz to
decide membership in both Sz and Sz⊥ , and thereby implement a projection onto |Sz i. On the other
hand, suppose it were possible to map |zi|Sz i to |zi|Sz i⊗2 , using poly(n) queries to the bank (withthe submitted bills returned to the user on successful or even failed verifications). Then by using
the oracle A to simulate the queries to the bank, we could also map |dS i|Si to |dS i|Si⊗2 in thescheme of Theorem 9.4.1, and thereby break that scheme. But this would contradict Theorem 9.4.1.
It follows that mapping |zi|Sz i to |zi|Sz i⊗2 requires Ω(2n/2 ) queries to the bank.

9.5

Instantiation

In light of Theorem 9.4.1, an obvious question is whether it’s possible to “instantiate” the hidden
subspace construction, thus getting rid of the oracle A. This would require providing an “obfuscated”
description of the subspaces S and S ⊥ —one that let the user efficiently apply χS and χS ⊥ in orderto verify a banknote, yet that didn’t reveal a basis for S.
In their paper, Aaronson and Christiano [AC12] offered one suggestion for this, based on lowdegree polynomials. More concretely: assume that the serial number of a banknote |Si encodes two
sets of (say) degree-3 polynomials,
p1 , . . . , pm : Fn2 → F2 and q1 , . . . , qm : Fn2 → F2 ,86

for some m = O(n), such that p1 , . . . , pm simultaneously vanish on S (and only on S), while
q1 , . . . , qm simultaneously vanish on S ⊥ (and only on S ⊥ ). Given S, it’s easy to generate suchpolynomials efficiently—for example, by choosing random degree-3 polynomials that vanish on some
canonical subspace S0 (say, that spanned by the first n/2 basis vectors), and then acting on thepolynomials with a linear transformation that maps S0 to S. For additional security, we could also
add noise: an  fraction of the polynomials can be chosen completely at random.
Clearly, given these polynomials, we can use them to compute the characteristic functions χSand χS ⊥ , with no oracle needed. But given only the polynomials, there’s at least no obvious way torecover a basis for S, so one might hope that copying |Si would be intractable as well.
To give evidence for that, Aaronson and Christiano [AC12] gave the following security reduction.
Theorem 9.5.1 ([AC12]). Suppose the hidden subspace mini-scheme can be broken, with thefunctions χS and χS ⊥ implemented by sets of degree-3 polynomials p1 , . . . , pm : Fn2 → F2 and
q1 , . . . , qm : Fn2 → F2 respectively. Then there exists a polynomial-time quantum algorithm that,given the pi ’s and qi ’s, finds a basis for S with success probability Ω(2−n/2 ).
Proof. The argument is surprisingly simple. Suppose a counterfeiting algorithm C exists as in the
hypothesis, which maps |Si to |Si⊗2 using p1 , . . . , pm and q1 , . . . , qm . Then consider the following
algorithm to find a basis for S with ∼ 2−n/2 success probability:(1) Prepare a uniform superposition over all n-bit strings.
(2) Compute p1 , . . . , pm on the elements of the superposition, and condition on getting the all-0
outcome—thereby collapsing the superposition down to |Si with success probability 2−n/2 .
(3) If the measurement succeeds, then run C repeatedly, to map |Si to |Si⊗m for some m = Θ(n).
(4) Measure each of the copies of |Si in the computational basis to learn a basis for S.
An algorithm that finds a basis for S with exponentially-small success probability, Ω(2−n/2 ),might not sound impressive or unlikely. However, notice that if one tried to find a basis for S by
2
random guessing, one would succeed with probability only 2−Ω(n ) .

9.6

Attacks

Unfortunately, some recent developments have changed the picture substantially.
First, in 2014, Pena et al. [PFP15] proved that the noiseless version of the low-degree polynomial
scheme can be broken, if the scheme is defined not over F2 but over a finite field of odd characteristic.
Their proof used Gröbner basis methods, and it actually yielded something stronger than a breakof the money scheme: namely, a polynomial-time classical algorithm to recover a basis for S
given p1 , . . . , pm (the dual polynomials, q1 , . . . , qm , aren’t even needed). In the F2 case, Pena et al.
conjectured, based on numerical evidence, that their Gröbner basis techniques would at least yielda quasipolynomial-time algorithm.
In any case, the noisy version of the low-degree polynomial scheme wasn’t affected by theseresults, since the Gröbner basis techniques break down in the presence of noise.

87However, in a recent dramatic development, Christiano and others have fully broken the noisy
low-degree polynomial scheme. They did this by giving a quantum reduction from the problemof breaking the noisy scheme to the problem of breaking the noiseless scheme, which Pena et al.
already solved. (Thus, unlike Pena et al.’s result, this part of the attack is specific to quantum
money.)The reduction is extremely simple in retrospect. Given the polynomials p1 , . . . , pm and q1 , . . . , qm ,and given a money state |Si, our goal is to use measurements on |Si to decide which pi ’s and qi ’s
are “genuine” (that is, vanish everywhere on S), and which ones are “noisy” (that is, vanish on onlya ∼ 1/2 fraction of points in S).
Given a polynomial (say) pj , we can of course evaluate pj on |Si and then measure the result. If
pj is genuine, then we’ll observe the outcome 0 with certainty, while if pj is noisy, we’ll observe theoutcomes 0 and 1 with roughly equal probability. The problem with this approach is that, if pj isnoisy, then the measurement will destroy the state |Si, making it useless for future measurements.
Here, however, we can use the remarkable idea of single-copy tomography, which Farhi et al.
[FGH+ 10] introduced in 2010, in the context of breaking other public-key quantum money schemes.
The idea is this: after we make a measurement that corrupts |Si to some other state |ψi, we thenuse amplitude amplification (see Lecture 5) to restore |ψi back to |Si. Now, amplitude amplification
requires the ability to reflect about both the initial state |ψi and the target state |Si. But we cando this by using the polynomials p1 , . . . , pm and q1 , . . . , qm ! In particular, to reflect about |Si, we
negate the amplitude of each basis state iff a sufficient fraction of the pi ’s and qi ’s evaluate to 0,
while to reflect about |ψi, we negate the amplitude of each basis state iff a sufficient fraction of
the pi ’s and qi ’s evaluate to 0, and the polynomial pj that we just measured evaluates to whichever
measurement outcome we observed (0 or 1). This approach lets us proceed through the pi ’s andqi ’s, identifying which ones are noisy, without permanent damage to the state |Si.
Taking the contrapositive of Theorem 9.5.1, a remarkable corollary of the new attack is that,given a noisy set of low-degree polynomials p1 , . . . , pm and q1 , . . . , qm , there’s a polynomial-timequantum algorithm that recovers a basis for S with success probability Ω(2−n/2 ).
2
Again, a naı̈ve algorithm would succeed with probability only 2−Ω(n ) (with some cleverness,
one can improve this to 2−cn for some large constant c). We don’t know any quantum algorithm
for this problem that succeeds with probability Ω(1), nor do we know a classical algorithm thatsucceeds with probability Ω(2−n/2 ). Thus, the algorithm that emerges from this attack seems to bea genuinely new quantum algorithm, which is specialized to the regime of extremely small successprobabilities. The most surprising part is that this algorithm came from an attack on a quantum
money scheme; we wouldn’t know how to motivate it otherwise.

9.7

Future Directions

Returning to quantum money, though, what are the prospects for evading this attack on the
low-degree polynomial scheme? All that’s needed is some new, more secure way to instantiate theblack-box functions χS and χS ⊥ in Aaronson and Christiano’s hidden subspace scheme. As a sortof stopgap measure, one could instantiate χS and χS ⊥ using a recent idea in cryptography known
as indistinguishability obfuscation, or i.o. I.o. has the peculiar property that, when we use it toobfuscate a given function f , we can generally prove that, if there’s any secure way to obfuscate f ,and if moreover i.o. itself is secure, then i.o. yields a secure obfuscated implementation of f . In thiscase, the upshot would be that, if the characteristic functions of the subspaces S and S ⊥ can be88

obfuscated at all, then i.o. is one way to obfuscate them! Ironically, this gives us a strong argument
in favor of using i.o. even while giving us little evidence that any secure implementation is possible.
Other ideas include using implementing χS and χS ⊥ , or something like them, using lattice-based
cryptography, or returning to other ideas for quantum money, such as the Farhi et al. [FGH+ 12]
knot-based scheme, and trying to give them more rigorous foundations. In the meantime, there
are many other wonderful open problems about public-key quantum money. Here’s a particularfavorite: is public-key quantum money possible relative to a random oracle?
Besides quantum money, another fascinating challenge is copy-protected quantum software:that is, quantum states |ψf i that would be useful for evaluating a Boolean function f , but not for
preparing additional states that could also be used to evaluate f . In forthcoming work, Aaronson andChristiano show that copy-protected quantum software is “generically” possible relative to a classicaloracle. But it remains to give a secure “real-world” implementation of quantum copy-protection forgeneral functions f , or even a good candidate for one.

89

Lecture 10
Classification of Gate Sets
Lecturer: Adam Bouland and Luke Schaeffer

10.1

Scribe: Adam Bouland and Luke Schaeffer

Physical Universality

For much of this course, we considered questions of the form: given a universal quantum gate set,
which unitaries can we implement, and which states can we prepare, in polynomial time? In thisfinal lecture, we consider a different but related question: given a (possibly non-universal) gate set,
which unitaries can we implement at all? We’ll see some recent progress on this latter question, as
well as numerous open problems.
First, though, we need the concept of physical universality.
Definition 10.1.1. A set of k-qubit gates G = {g1 , . . . , g` } is called physically universal if there
exists a positive integer n0 ∈ N such that for all n ≥ n0 , gates from G densely generate SU(2n ), thespecial unitary group of dimension 2n on n qubits.
Let’s comment on the definition. First, we focus on SU since global phase is irrelevant, so we might
as well assume determinant 1. Second, note that physical universality is about implementing unitary
operations (specifically, all of SU(2n ) for sufficiently large n) rather than performing computation.
That is, it’s possible to be computationally universal (for quantum computation) but not physically
universal, for instance if we only generate SO(2n ), the special orthogonal group of dimension 2n .
Also, the n0 in the above definition is so that we only have to generate all unitaries on any
sufficiently large (i.e., larger than n0 ) number of qubits. It turns out there exist, for instance, 2-qubit
gates G that approximately generate all unitaries on 3 qubits, but don’t approximately generatesome 2-qubit gates, if we apply G to 2 qubits only. That is, such G can approximate I ⊗ U but
not U for some 2-qubit unitary U . Surely it’s good enough to generate I ⊗ U for most practical
purposes, so our definition of physical universality allows it.
Recall the Solovay-Kitaev theorem from Lecture 2 (also see [DN05]).
Theorem 10.1.2 (Solovay-Kitaev). If a set of gates G (closed under inverses) approximately generates all n-qubit unitaries, then we can ε-approximate any unitary on n qubits using O(exp(n) polylog(1/ε))
gates from G.
This theorem has, for the most part, let us ignore the gate set in this course. We can usuallyassume our gate set satisfies the conditions of the Solovay-Kitaev theorem, and therefore generates
any other O(1)-qubit gate we might prefer to use. Furthermore, using only O(polylog(1/ε)) gates
for an approximation of accuracy ε is an excellent trade-off.
90However, there are some drawbacks to the Solovay-Kitaev theorem. First, it assumes that thegate set is closed under inverses. It’s true that by the Poincaré recurrence theorem, we can find anO(1/ε) approximation in polynomial time, but this is insufficient for Solovay-Kitaev. It’s an open
problem whether we can remove the requirement of exact inverses from the theorem.
Second, the Solovay-Kitaev theorem requires a universal gate set. It doesn’t apply when the gate
set doesn’t densely generate the entire space. Indeed, there exist non-universal gate sets for which
the analogue of Solovay-Kitaev is false. For example, any irrational rotation Rθ in SO(2) ⊆ SU(2)will densely generate SO(2). But since the only thing we can do with Rθ is apply it repeatedly,
a counting argument shows that there aren’t enough different circuits to achieve O(polylog(1/ε))
accuracy approximations.
Even if we accept these drawbacks, there’s another issue: namely, is it even decidable whether agiven gate set is universal? To formalize the problem, let’s assume that each gate is given by its
unitary matrix. The matrix entries should be computable numbers at the very least, but let’s be on
the safe side and assume the entries are algebraic. It’s still not obvious how to decide whether agate set is physically universal, mainly because we lack an effective bound on n0 , the number of
qubits needed to “see” physical universality. That is, it could be that a gate set is extremely limited
until we have 10100 qubits of workspace and then, for some reason, it becomes able to approximate
any unitary quite easily. Admittedly, such a situation seems unlikely, but we must have some boundon n0 to prove decidability.
So, we turn to a theorem of Ivanyos [Iva07].
Theorem 10.1.3 (Ivanyos ’06). If a k-qudit (i.e., a d-dimensonal generalization of a qubit) gate
set doesn’t densely generate all unitaries on O(kd8 ) qubits, then it will never densely generate allunitaries.
For any given gate set, this theorem gives an upper bound on n0 . Decidability is still not trivial;
we need to compute the closure of a gate set with algebraic entries on a finite number of qubits.
Fortunately, this can be done, so physical universality of any gate set is decidable.
Another question: suppose we show a gate set G is universal for some particular n0 ≥ 2. Can weargue that it’s universal for all n ≥ n0 ? Yes, as it turns out. We use the fact that there are universal
two-qubit gates U (see Lecture 2 for examples). Since G generates U ⊗ In0 −2 , and U generates all
unitaries, it follows that G generates any unitary on n ≥ n0 qubits.
Lastly, let’s mention a result that shows that, when we discuss non-universal gate sets, we’reactually dealing with a measure-0 subset of all gate sets.
Theorem 10.1.4. A Haar-random 2-qubit gate is physically universal with probability 1.
This result was shown by Deutsch, Barenco and Ekert [Deu98] in 1995, and separately by Lloyd[Llo02] around the same time.

10.2

Difficulty of Classification

We’re interested in better criteria for deciding whether a gate set is universal, and if it’s not universal,
characterizing the set of unitaries it can generate. Let’s take perhaps the simplest possible open case;
suppose G is a 2-qubit gate set that’s closed under inverses. Again, since global phase is irrelevant,we can assume without loss of generality that every element of G has determinant 1. Then clearly
G generates a subgroup S of SU(4), the group of 4 × 4 complex matrices with determinant 1, or
91

the 4 × 4 special unitary group. Since our notion of generating a gate is approximate, S must be
closed in the topological sense (i.e., under taking limits). That is, we say we can generate U if we
can construct a sequence of unitaries that approaches U in the limit.
Why not approach the problem of determining S group-theoretically? Alas, despite the importance of SU(n) to physics and mathematics, much remains unknown about its subgroups, even forsmall n. Let’s survey what’s known.
First, SU(2) is a double cover of SO(3), the group of rotations in three dimensions, and the latterhas been understood since antiquity. Specifically, there are discrete groups corresponding to theplatonic solids (the tetrahedral group, the cubic/octahedral group, and the icosahedral/dodecahedralgroup), the cyclic and dihedral groups of every order, and the trivial group. There’s also the group of
all rotations in a plane, the group of symmetries of a disk, and the entire group. This is a complete
list of subgroups of SU(2).
For SU(3), the infinite subgroups were supposedly classified in 1913, but the classification wasn’t
completed until 2013, when Ludl fixed an error in a classification result from the ’70s. Finally,
most of the subgroups of SU(4) are known. More precisely, all of the exceptional subgroups areunderstood, but there are also known to exist infinite families of subgroups, and these subgroups
are poorly characterized.

10.3

Classification of Quantum Gates and Hamiltonians

We’ll look at three ways to make the classification problem more approachable. This section
covers the first two approaches: two-level unitaries and Hamiltonians. Then, Section 10.4.2 will
discuss classical reversible gates, and the recent solution to the “classical part” of the quantum gateclassification problem.

10.3.1

Two-Level Unitaries

Two-level unitaries ignore the usual tensor product structure of quantum gates, in favor of a direct
sum structure. Ordinarily, when we apply a 1-qubit gate G to an 8-dimensional system (i.e., theequivalent of three qubits), that means transforming the state vector by a tensor product matrix
G 0 0 0
0 G 0 0G ⊗ I4 = 0 0 G 0
0 0 0 GIn the two-level unitary model, we instead apply G to two modes (i.e., basis states) of the system,
instead of to a qubit. The result is that the matrix we apply has the formG 0
G ⊕ I6 =0 I6instead of a tensor product. Two-level unitaries are motivated by beamsplitters, and the kind ofquantum computation feasible with optics.
Reck et al. [RZBB94] proved the following important physical universality result:
Theorem 10.3.1 (Reck et al. ’94). The set of all two-level unitaries generates all of SU(n), for
any n ≥ 2.
92

This was later improved to a classification result by Bouland and Aaronson [BA14]:
Theorem 10.3.2 (Bouland and Aaronson ’14). Let U be any 2 × 2 matrix with determinant −1.
Then either
 iθ



iθ
1. U is of the form e0 −e0−iθ or e0iθ e0 and generates only trivial unitaries,
2. U is real and densely generates SO(n) for all n ≥ 3, or
3. U densely generates SU(n) for all n ≥ 3.
The proof relies heavily on “brute force” enumeration of the representations of subgroups ofSU(3). This underlines the importance for the classification problem of understanding the special
unitary group.

10.3.2

Hamiltonians

One view of quantum mechanics centers on the Schrödinger equation,dΨ= −iHΨ,dt
where Ψ is a wavefunction for the quantum system (what we’ve been calling the “state”), and H isa Hermitian operator called the Hamiltonian of the system. The Hamiltonian gives the total energyof the system.
For a finite-dimensional system, with a time-independent Hamiltonian H, the wave function
evolves over time t according to the unitary transformation
Ψ(t) = eiHt Ψ(0)where eiHt is a matrix exponential. Designing a quantum computer is about controlling the
Hamiltonian of a physical system to perform a sequence of gates. Many proposed designs assume the
Hamiltonian can be “switched” between several time-independent Hamiltonians. Then, by varying
how long we apply a Hamiltonian H, we can get any unitary gate in the set
GH = {eiHt : t ∈ R}.
As before, we assume we can apply any gate in GH to any pair of qubits, and in any order.
Now the problem is to decide whether GH is universal, for a given Hamiltonian H.
The main result on this problem is due to Childs et al. [CLMO11]:
Theorem 10.3.3 (Childs et al., ’11). A 2-qubit Hamiltonian is universal for 2 qubits, with noancillas allowed, unless (and only unless)• eiH does not generate entanglement, or• eiH shares an eigenvector with SWAP.

93

The proof makes heavy use of Lie algebras. Specifically, we consider the closure of {Hij : i 6=j ∈ n}, where Hij denotes the Hamiltonian H applied to qubits i and j, under linear combinations
over R and commutators [A, B] = AB − BA. If the closure is all Hermitian matrices, then GH is
physically universal.
On an intuitive level, it’s easy to see why gates which fail to generate entanglement aren’t
universal. Likewise, if eiH shares an eigenvector |φi with SWAP, then every gate in GH has |φi as
an eigenvector. Since we can only apply gates from GH and SWAP, |φi will then be an eigenvectorof everything we generate, which is therefore not all 2-qubit unitary operations. Note that on 3
qubits, this eigenvector argument no longer holds. In that case, it’s open which of these operations
are universal, and on how many qubits.
There’s been some partial progress on the problem of classifying commuting Hamiltonians. A
commuting Hamiltonian is a Hamiltonian H such that any two gates in GH , applied to any pairs ofqubits, commute. That is,
eiHab t1 eiHcd t2 = eiHcd t2 eiHab t1
for all a, b, c, d and t1 , t2 ∈ R. Alternatively, for 2 × 2 unitaries, this is equivalent to all gates in GH
being diagonal after a change of basis (i.e., a conjugate by a single-qubit U on every qubit). 1
Note that if H is a commuting Hamiltonian, then GH can’t be universal, because any unitary
we construct is diagonal in the same basis. However, a 2010 result of Bremner, Josza and Shepherd[BJS10] shows that a particular set of commuting Hamiltonians of this form can’t be classicallysimulated unless the polynomial hierarchy collapses.
Theorem 10.3.4 (Bremner, Josza, Shepherd [BJS10]). Suppose you can apply any Hamiltonian
which is diagonal in the X basis (i.e., after conjugation by the Hadamard gate on all qubits). Usingsuch circuits, one can sample from a probability distribution which cannot be exactly sampled inclassical polynomial time unless the polynomial hierarchy collapses.
The proof uses “postselection gadgets”: that is, gadgets built from commuting Hamiltoniangates which use postselection to simulate all of PostBQP. One argues that, if every probability
distribution generated by the commuting Hamiltonians can be sampled in BPP then PostBQP is
contained in PostBPP, and hence
PH ⊆ PPP = PPostBQP ⊆ PPostBQP ⊆ ∆P3 ,so the polynomial hierarchy collapses.
This was recently generalized by Bouland, Manc̆inski and Zhang [BMZ16].
Theorem 10.3.5 (Bouland, Manc̆inski and Zhang ’16). Any 2-qubit commuting Hamiltonian iseither classically simulable, or can perform a sampling task which can’t be done in classical polynomial
time unless the polynomial hierarchy collapses.
As before, the proof uses postselection gadgets built from the commuting Hamiltonian gates.
There’s some difficulty constructing inverses of these gadgets due to the non-unitarity of postselection.
1

Clearly diagonal matrices commute, but the converse is more involved.

94

10.4

Classification of Reversible Classical Gates

Suppose we wish to classify all quantum gate sets in terms of what subset of unitaries they generate.
Since classical reversible gates are a subset of quantum gates, we’d first need to classify classicalreversible gates. This classification was recently completed by Aaronson, Grier and Schaeffer[AGS15]. Before explaining their result, we’ll first describe what was previously known about thisproblem in the simpler setting of irreversible gates, which were classified in the early twentiethcentury.

10.4.1

Background

Classical circuits are usually described in terms of irreversible gates, such as AND, OR, NOT,
and NAND. In introductory electrical engineering courses, one learns that the NAND gate isuniversal—i.e. NAND gates can be used to construct any function, assuming we have access toancilla bits as input. A natural problem is to classify irreversible gate sets in terms of which sets ofBoolean functions that they can generate, assuming we have access to ancilla bits that don’t dependon the input.
We can easily see that certain gate sets won’t be universal. For instance, the AND and OR
gates are monotone, i.e. if two input strings x and y satisfy x ≤ y (where ≤ denotes bitwiseless-than-or-equal), then AND(x) ≤ AND(y). So AND and OR will only ever be able to generatemonotone functions. Likewise, the XOR gate is linear over F2 , and therefore can’t generate nonlinear
functions such as AND.
One interesting point is that it’s possible for non-universal gate sets to be universal in an encoded
sense. For instance, suppose that we represent 0 by the string 01 and 1 by the string 10. This is
known as the “dual rail” encoding of a bit. (This same encoding is also used in linear optics). Then
one can show that {AND, OR} is universal on this encoded space. To perform a logical NOT, one
merely needs to swap the bits of the encoded bit. (In the following, we’ll assume SWAP gates areincluded in the gate set.) To perform a logical AND, one takes the AND of the first bits of each
encoded bit. Therefore, in this construction one can perform logical NOT and AND gates, andhence achieve encoded universality.
The classification of ordinary (irreversible) Boolean gates was completed by Post [Pos41] in the
1920s, although he only published his work in 1941. Suppose we have a set of k-bit irreversible
gates, and we’re allowed ancillas which don’t depend on the input. Then there are only 7 possible
subsets of functions that we can generate:• All possible functions• All monotone functions• All functions computable with AND only
• All functions computable with OR only
• All functions computable with XOR only
• All functions computable with NOT only
• The empty set—i.e. only constant functions
95

>

XOR

NOT

MONO

AND

OR

⊥

Figure 10.1: Simplified Post’s Lattice
The relationships among these classes are shown in Figure 10.1.
Here an arrow is drawn from gate class A to gate class B if adding any element to B (which
isn’t already in B) boosts the set of functions generated to at least those generated by A. The
classification is striking in its simplicity, and takes a page or so to prove (we leave it as an exercise).
We should mention, however, that in his original work, Post did not make the simplifying
assumption that 0 and 1 ancillas are always available for free. And when one drops that assumption,
the classification (now known as Post’s lattice) becomes horrendously more complicated.

10.4.2

Classification of Reversible Gates

Recently, Aaronson, Grier and Schaeffer [AGS15] completed the classification of reversible Boolean
gates, analogous to the classification that we stated above for irreversible gates. One can motivate
this in two ways. First, classical reversible gates are a subset of unitary gates, so classifying theformer is a necessary step towards classifying all quantum gate sets. Second, even if we’re onlyinterested in classical computing, we might want to consider reversible gates because (in contrast to
irreversible gates) they don’t generate heat by dumping entropy into the environment.
In the following, we assume that the SWAP gate (i.e., relabeling of the bits) is always available
for free. We also assume that we’re allowed classical ancillas (in the state 0 or 1), but that at the endof the computation, the classical ancillas must be returned to their initial states. So in particular,
the final state of the ancillas can’t depend on the input to the function. One reason to make thisassumption is that it lets the classification extend naturally to quantum computing. In that context,
requiring the ancillas to return to their initial values ensures that if the classical circuit is queried insuperposition, the ancillas don’t become entangled with the input to the circuit. Therefore, thisclassification captures which classical functions can be computed (possibly in superposition) using
subsets of classical reversible gates.
Additionally, adding ancillas avoids some technical difficulties which seem artificial. For instance,96Toffoli

Fredkin
+ NOT

CNOT

CNOTNOT
+ NOT

F4 +
NOT

T6 +
NOT

CNOTNOTF4 +NOTNOTT6 +NOTNOT

NOT

Fredkin+ NOTNOT

T4

F4

T6

NOTNOT

···

C4

···

C8

···

.
.
.

···

Fredkin∅Figure 10.2: The inclusion lattice of reversible gate classes
if we’re not allowed ancillas, then using 3-bit permutations only (i.e., any 3 bit reversible gates),
it’s not possible to generate all possible 4-bit permutations—because 3-bit operations generate
even permutations when acting on 4 bits, so they can never generate an odd permutation of 4 bits.
Allowing ancillas removes this sign issue.
Aaronson, Grier, and Schaeffer’s classification is shown in Figure 10.2. To explain the diagram,
we need to define some terminology. The Toffoli gate is the Controlled-Controlled-NOT gate.
The Fredkin gate is the Controlled-SWAP gate. The NOTNOT gate applies NOT to two bits
simultaneously (this is weaker than the NOT gate because applying NOTNOT always preserves
the parity of the input string; it doesn’t give you the ability to apply a single NOT). The set Ck
consists of all gates that preserve Hamming weight mod k. The sets F4 , T4 , and T6 are exceptionalclasses of gates which will be defined shortly.
The classification is quite involved, so let’s discuss it from the top down. At the top is the
Toffoli class—this set contains all possible permutations of the bit strings. The classes along theupper right of the diagram are non-linear gate sets, all of which are encoded universal, either by the97dual rail encoding (x → xx̄), or the doubled encoding (x → xx), or the doubled dual rail encoding(x → xx̄xx̄). All of these gate sets have special properties with regard to parity. The Ck gatespreserve parity mod k. Fredkin+NOTNOT preserves parity mod 2. And Fredkin+NOT either
conserves or anti-conserves parity mod 2. (I.e. for any element of the Fredkin+NOT class, either
parity is preserved or flipped.) For the Ck classes, where k is prime, adding any gate outside theclass bumps the power all the way to that of Toffoli (i.e. all permutations)—hence these classes areconnected directly to the top of the diagram.
Next are the gate classes that are linear, but not orthogonal transformations of their input.
These include the classes generated by CNOT, CNOTNOT (the controlled-NOTNOT gate), and
CNOTNOT+NOT. These classes are not universal. In fact, computation with these gates iscontained in the complexity class ⊕L (“parity-L”), which is the power of counting the parity of thenumber of accepting paths of a non-deterministic logspace Turing machine.
Next are the gate classes that are orthogonal but nontrivial. These include three exceptionalclasses: those generated by gates that we call F4 , T6 , and T4 . The Tk gates take as input a k-bit x,
and replace x with x̄ if the parity of the bits of x is odd, and otherwise leave x fixed. The Fk gatestake as input a k-bit x, and replace x with x̄ if the parity of bits of x is even, and otherwise leave x
fixed.
The remaining gate classes, such as those generated by NOT or NOTNOT, are trivial. This
completes the classification.
One can prove without great difficulty that the classes in the diagram all distinct, have thecontainment relations shown, and are generated by the gate sets that we said. The hard part is toprove that there are no additional classes. Briefly, one does this by repeatedly arguing that any
gate G that fails to preserve the defining invariant of some class C1 , must therefore be usable togenerate a generating set for some larger class C2 . Depending on the C1 and C2 in question, thiscan require arguments involving, e.g., lattices, Diophantine equations, and Chinese remaindering.
We won’t say more here, but see [AGS15] for details.
√
If we allow quantum ancillas (e.g. the state |00i+|11i) in this model, then many of the classes in2
the diagram collapse. In particular, only six of the sets remain: Toffoli, Fredkin, CNOT, T4 , NOT,
and the empty set. An inclusion diagram for these is provided in Figure 10.3. As a result, if one
were trying to classify all quantum gate sets, one would probably want to start with this simplified
lattice.
Several open problems remain. First, can we extend this classification to trits (that is, a
3-symbol alphabet) rather than bits? Already for the case of irreversible gates, trits are much more
complicated: the trit lattice is known to have uncountable cardinality, in contrast to Post’s lattice,which has only countable cardinality.
More interestingly, can we classify all quantum gate sets acting on qubits, or even just (forexample) all the classes generated by 2-qubit gates? Can we prove a dichotomy theorem, sayingthat every quantum gate set is either physically universal, or else fails to be universal in one of a listof prescribed ways? Besides the classical gates, 1-qubit gates, stabilizer gates and their conjugates,
etc., does that list include anything not yet known? Finally, what can we say about the complexityof states and unitary transformations for the non-universal classes in the list?

98

TOFFOLI

CNOT

T4

FREDKIN

NOT⊥

Figure 10.3: Classification of Reversible Gates with Quantum Ancillas

99

Bibliography[AA13] S. Aaronson and A. Arkhipov. The computational complexity of linear optics. Theoryof Computing, 9(4):143–252, 2013. Earlier version in Proc. ACM STOC’2011. ECCC
TR10-170, arXiv:1011.3245. 47[Aar02] S. Aaronson. Quantum lower bound for the collision problem. In Proc. ACM STOC,
pages 635–642, 2002. quant-ph/0111102. 33, 34, 56[Aar04] S. Aaronson.
Multilinear formulas and skepticism of quantum computing.
In Proc. ACM STOC, pages 118–127, 2004.
quant-ph/0311039,
www.scottaaronson.com/papers/mlinsiam.pdf. 27[Aar05a] S. Aaronson. Limitations of quantum advice and one-way communication. Theoryof Computing, 1:1–28, 2005. Earlier version in Proc. IEEE Complexity’2004. quantph/0402095. 10, 11, 46, 47[Aar05b] S. Aaronson. Quantum computing, postselection, and probabilistic polynomial-time.
Proc. Roy. Soc. London, A461(2063):3473–3482, 2005. quant-ph/0412187. 47[Aar06] S. Aaronson. QMA/qpoly is contained in PSPACE/poly: de-Merlinizing quantum
protocols. In Proc. Conference on Computational Complexity, pages 261–273, 2006.
quant-ph/0510230. 12, 49, 74, 75[Aar09] S. Aaronson. Quantum copy-protection and quantum money. In Proceedings of the2009 24th Annual IEEE Conference on Computational Complexity, CCC ’09, pages
229–242, Washington, DC, USA, 2009. IEEE Computer Society. 72, 77, 78, 81, 83, 84[Aar14] S. Aaronson. PostBQP Postscripts: A Confession of Mathematical Errors. http://www.scottaaronson.com/blog/?p=2072, 2014. Blog post. 47[AC12] S. Aaronson and P. Christiano. Quantum money from hidden subspaces. In Proc.
ACM STOC, pages 41–60, 2012. arXiv:1203.4740. 81, 82, 84, 86, 87[AD14] S. Aaronson and A. Drucker. A full characterization of quantum advice. SIAM J.
Comput., 43(3):1131–1183, 2014. 48, 49[AFK89] M. Abadi, J. Feigenbaum, and J. Kilian. On hiding information from an oracle. J.
Comput. System Sci., 39(1):21–50, 1989. 68[AG04] S. Aaronson and D. Gottesman. Improved simulation of stabilizer circuits. Phys. Rev.
A, 70(052328), 2004. arXiv:quant-ph/0406196. 15

100

[AGS15] S. Aaronson, D. Grier, and L. Schaeffer. The classification of reversible bit operations.
2015. arXiv:1504.05155. 95, 96, 98[AK07] S. Aaronson and G. Kuperberg. Quantum versus classical proofs and advice. Theoryof Computing, 3(7):129–157, 2007. Previous version in Proceedings of CCC 2007.
arXiv:quant-ph/0604056. 26, 42, 43, 45[Amb02] A. Ambainis. Quantum lower bounds by quantum arguments. J. Comput. Sys. Sci.,
64:750–767, 2002. Earlier version in Proc. ACM STOC’2000. quant-ph/0002066. 84[AMPS13] A. Almheiri, D. Marolf, J. Polchinski, and J. Sully. Black holes: complementarity or
firewalls? J. High Energy Physics, (2):1–20, 2013. arXiv:1207.3123. 52[ATS03] D. Aharonov and A. Ta-Shma. Adiabatic quantum state generation and statisticalzero knowledge. In Proc. ACM STOC, pages 20–29, 2003. quant-ph/0301023. 30, 32[BA14] A. Bouland and S. Aaronson. Generation of universal linear optics by any beam splitter.
Phys. Rev. A, 89:062316, Jun 2014. 93[Bab91] L. Babai. Local expansion of vertex-transitive graphs and random generation in finitegroups. In C. Koutsougeras and J. S. Vitter, editors, Proceedings of the 23rd Annual
ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana,
USA, pages 164–174. ACM, 1991. 37, 38[Bab16] L. Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC
2016, pages 684–697, New York, NY, USA, 2016. ACM. 23, 31[BBBV97a] C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strengths and weaknesses ofquantum computing. SIAM J. Comput., 26(5):1510–1523, 1997. quant-ph/9701001. 40[BBBV97b] C. H. Bennett, E. Bernstein, G. Brassard, and U. V. Vazirani. Strengths and weaknessesof quantum computing. SIAM J. Comput., 26(5):1510–1523, 1997. 33[BBBW82] C. H. Bennett, G. Brassard, S. Breidbart, and S. Wiesner. Quantum cryptography, or
unforgeable subway tokens. In Proceedings of CRYPTO, pages 267–275. Plenum Press,
1982. 71
[BBS09] L. Babai, R. Beals, and Á. Seress. Polynomial-time theory of matrix groups. In
Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, STOC
’09, pages 55–64, New York, NY, USA, 2009. ACM. 36[BJS10] M. J. Bremner, R. Jozsa, and D. J. Shepherd. Classical simulation of commuting
quantum computations implies collapse of the polynomial hierarchy. Proceedings of
the Royal Society of London A: Mathematical, Physical and Engineering Sciences,467(2126):459–472, 2010. 94[BMZ16] A. Bouland, L. Mančinska, and X. Zhang. Complexity classification of two-qubit
commuting hamiltonians. ArXiv e-prints, February 2016. To appear in CCC ’16. 94

101

[BOCLR04] M. Ben-Or, D. Coppersmith, M. Luby, and R. Rubinfeld. Non-abelian homomorphism
testing, and distributions close to their self-convolutions. In Proceedings of RANDOM,
pages 273–285. Springer-Verlag, 2004. ECCC TR04-052. 42[BS84] L. Babai and E. Szemerédi. On the complexity of matrix group problems I. In 25th
Annual Symposium on Foundations of Computer Science, West Palm Beach, Florida,
USA, 24-26 October 1984, pages 229–240. IEEE Computer Society, 1984. 37[BV97] E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM J. Comput.,
26(5):1411–1473, 1997. Earlier version in Proc. ACM STOC’1993. 16, 19[CLMO11] A. M. Childs, D. Leung, L. Mančinska, and M. Ozols. Characterization of universal
two-qubit hamiltonian. Quantum Info. Comput., 11(1):19–39, January 2011. 93[Deu98] D. Deutsch. The Fabric of Reality. Penguin, 1998. 91[DN05] C. M. Dawson and M. A. Nielsen. The Solovay-Kitaev algorithm. eprint arXiv:quantph/0505030, May 2005. 16, 90[EHK04] M. Ettinger, P. Høyer, and E. Knill. The quantum query complexity of the hidden
subgroup problem is polynomial. Inform. Proc. Lett., 91(1):43–48, 2004. quantph/0401083. 24, 43[EV93] A. C. Elitzur and L. Vaidman. Quantum mechanical interaction-free measurements.
Foundations of Physics, 23(7):987–997, 1993. 78[FFK94] S. A. Fenner, L. J. Fortnow, and S. A. Kurtz. Gap-definable counting classes. J.
Comput. System Sci., 48(1):116–148, 1994. 17[FGH+ 10] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski, D. Nagaj, and P. Shor. Quantum
state restoration and single-copy tomography. Phys. Rev. Lett., 105(190503), 2010.
arXiv:0912.3823. 83, 88[FGH+ 12] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski, and P. Shor. Quantum money fromknots. In Proc. Innovations in Theoretical Computer Science (ITCS), pages 276–289,
2012. arXiv:1004.5127. 83, 89[FK15] B. Fefferman and S. Kimmel. Quantum vs classical proofs and subset verification.
CoRR, abs/1510.06750, 2015. 44[Gao15] J. Gao. Quantum union bounds for sequential projective measurements. PhysicalReview A, 92(5):052331, 2015. arXiv:1410.5688. 12[Gen09] C. Gentry. Fully homomorphic encryption using ideal lattices. In Proc. ACM STOC,
pages 169–178, 2009. 24[GGM86] O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. J. of
the ACM, 33(4):792–807, 1986. Earlier version in Proc. IEEE FOCS’1984, pp. 464-479.
73

102

[GL89] O. Goldreich and L. A. Levin. A hard-core predicate for all one-way functions. In
Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing,
STOC ’89, pages 25–32, New York, NY, USA, 1989. ACM. 60[Gol06] O. Goldreich. On promise problems: a survey. In Essays in Memory of Shimon Even,
pages 254–290. 2006. ECCC TR05-018. 35[Gro96] L. K. Grover. A fast quantum mechanical algorithm for database search. In Proc.
ACM STOC, pages 212–219, 1996. quant-ph/9605043. 40[HH13] D. Harlow and P. Hayden. Quantum computation vs. firewalls. arXiv:1301.4504, 2013.
55, 56[HILL99] J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby. A pseudorandom generator fromany one-way function. SIAM J. Comput., 28(4):1364–1396, 1999. 73[HM16] A. Harrow and A. Montanaro. Sequential measurements, disturbance and property
testing, 2016. arXiv:1607.03236. 74, 75[HRC02] A. W. Harrow, B. Recht, and I. L. Chuang. Efficient discrete approximations ofquantum gates. J. Math. Phys., 43(9):4445–4451, 2002. 16[Iva07] G. Ivanyos. Deciding universality of quantum gates. Journal of Algebra, 310(1):49–56,
2007. 91
[IW97] R. Impagliazzo and A. Wigderson. P = bpp if e requires exponential circuits: Derandomizing the xor lemma. In Proceedings of the Twenty-ninth Annual ACM Symposiumon Theory of Computing, STOC ’97, pages 220–229, New York, NY, USA, 1997. ACM.
16
[JJUW11] R. Jain, Z. Ji, S. Upadhyay, and J. Watrous. QIP = PSPACE. J. ACM, 58(6):30:1–30:27,
December 2011. 39[JSV04] M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation algorithm
for the permanent of a matrix with non-negative entries. J. of the ACM, 51(4):671–697,
2004. Earlier version in Proc. ACM STOC’2001. 30[Kit96] A. Kitaev. Quantum measurements and the abelian stabilizer problem, 1996. ECCC
TR96-003, quant-ph/9511026. 23[KKR06] J. Kempe, A. Kitaev, and O. Regev. The complexity of the Local Hamiltonian problem.
SIAM J. Comput., 35(5):1070–1097, 2006. quant-ph/0406180. 35[KSV02] A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi. Classical and Quantum Computation.
American Mathematical Society, Boston, MA, USA, 2002. 35, 36[KW00] A. Kitaev and J. Watrous. Parallelization, amplification, and exponential-time simulation of quantum interactive proof systems. In Proc. ACM STOC, pages 608–617, 2000.
40

103

[LAF+ 10] A. Lutomirski, S. Aaronson, E. Farhi, D. Gosset, A. Hassidim, J. Kelner, and P. Shor.
Breaking and making quantum money: toward a new quantum cryptographic protocol.
In Proc. Innovations in Theoretical Computer Science (ITCS), pages 20–31, 2010.
arXiv:0912.3825. 82, 83[Llo02] S. Lloyd. Computational capacity of the universe. Phys. Rev. Lett., 88, 2002. quantph/0110141. 91[LMT96] K. J. Lange, P. McKenzie, and A. Tapp. Reversible space equals deterministic space.
In Proc. ACM STOC, pages 212–219, 1996. 67[Lut10] A. Lutomirski. An online attack against Wiesner’s quantum money. arXiv:1010.0256,
2010. 77, 78[Maz15] J. Maziero. Non-monotonicity of trace distance under tensor products. Brazilian
Journal of Physics, 45(5):560–566, 2015. 12[MS13] J. Maldacena and L. Susskind. Cool horizons for entangled black holes. Fortschritte
der Physik, 61:781–811, September 2013. 64[MVW99] P. B. Miltersen, N. V. Vinodchandran, and O. Watanabe. Super-polynomial versus
half-exponential circuit size in the exponential hierarchy. In COCOON, pages 210–220,
1999. 71
[MW05] C. Marriott and J. Watrous. Quantum arthur-merlin games. Computational Complexity,
14(2):122–152, 2005. 35[NS14] D. Nagaj and O. Sattath. An adaptive attack on Wiesner’s quantum money based oninteraction-free measurement. arXiv preprint arXiv:1404.1507, 2014. 77, 78[Ost91] R. Ostrovsky. One-way functions, hard on average problems, and statistical zeroknowledge proofs (extended abstract). In Proceedings of the 6th Annual Structure inComplexity Theory Conference, pages 133–138, 1991. 59[OU14] J. Oppenheim and B. Unruh. Firewalls and flat mirrors: An alternative to the amps
experiment which evades the harlow-hayden obstacle. Journal of High Energy Physics,
2014(3):1–20, 2014. 58[Pap85] C. H. Papadimitriou. Games against nature. Journal of Computer and System Sciences,31(2):288 – 301, 1985. 18[PFP15] M. C. Pena, J. C. Faugère, and L. Perret. Algebraic cryptanalysis of a quantum money
scheme: the noise-free case. In Public-key cryptography—PKC 2015, volume 9020 ofLecture Notes in Comput. Sci., pages 194–213. Springer, Heidelberg, 2015. 87[Pos41] E. L. Post. The two-valued iterative systems of mathematical logic. Annals of
Mathematics Studies, 5, 1941. 95[PYJ+ 11] F. Pastawski, N. Y. Yao, L. Jiang, M. D. Lukin, and J. I. Cirac. Unforgeable noisetolerant quantum tokens. arXiv:1112.5456, 2011. 71
104

[Reg04] O. Regev. Quantum computation and lattice problems. SIAM J. Comput., 33(3):738–760 (electronic), 2004. 23[Rom90] J. Rompel. One-way functions are necessary and sufficient for secure signatures. In
Proc. ACM STOC, pages 387–394, 1990. 82[RR97] A. A. Razborov and S. Rudich. Natural proofs. J. Comput. Sys. Sci., 55(1):24–35,
1997. Earlier version in Proc. ACM STOC’1994, pp. 204-213. 25[RZBB94] M. Reck, A. Zeilinger, H. J. Bernstein, and P. Bertani. Experimental realization of any
discrete unitary operator. Phys. Rev. Lett., 73:58–61, Jul 1994. 92[Sen12] P. Sen. Achieving the Han-Kobayashi inner bound for the quantum interference channel.
In IEEE International Symposium on Information Theory Proceedings (ISIT), pages
736–740, 2012. arXiv:1109.0802. 12[Shi02] Y. Shi. Quantum lower bounds for the collision and the element distinctness problems.
In Proc. IEEE FOCS, pages 513–519, 2002. arXiv:quant-ph/0112086. 34[Sho97] P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms
on a quantum computer. SIAM J. Comput., 26(5):1484–1509, 1997. Earlier version in
Proc. IEEE FOCS’1994. quant-ph/9508027. 23[Sim70] C. Sims. Computational methods in the study of permutation groups. In Computational
Problems in Abstract Algebra, pages 169–183. Pergamon Press, 1970. 36[Sim94] D. Simon. On the power of quantum computation. In Proc. IEEE FOCS, pages
116–123, 1994. 19, 22[SS14] D. Stanford and L. Susskind. Complexity and shock wave geometries. Phys. Rev. D,
90:126007, Dec 2014. 65[Sto83] L. J. Stockmeyer. The complexity of approximate counting (preliminary version). In
D. S. Johnson, R. Fagin, M. L. Fredman, D. Harel, R. M. Karp, N. A. Lynch, C. H.
Papadimitriou, R. L. Rivest, W. L. Ruzzo, and J. I. Seiferas, editors, Proceedings of the
15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston,
Massachusetts, USA, pages 118–126. ACM, 1983. 31[SV03] A. Sahai and S. P. Vadhan. A complete problem for statistical zero knowledge. J.
ACM, 50(2):196–249, 2003. 32, 56[TGP06] T. Tulsi, L. Grover, and A. Patel. A new algorithm for fixed point quantum search.
Quantum Information and Computation, 6(6):483–494, 2006. quant-ph/0505007. 86[Tod91] S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865–
877, 1991. Earlier version in Proc. IEEE FOCS’1989, pp. 514-519. 47[TS13] A. Ta-Shma. Inverting well conditioned matrices in quantum logspace. In Proceedingsof the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC ’13, pages
881–890, New York, NY, USA, 2013. ACM. 18
105

[Wat00] J. Watrous. Succinct quantum proofs for properties of finite groups. In 41st Annual
Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000,
Redondo Beach, California, USA, pages 537–546. IEEE Computer Society, 2000. 37[Wie83] S. Wiesner. Conjugate coding. SIGACT News, 15(1):78–88, 1983. Original manuscript
written circa 1970. 70[Wil13] M. M. Wilde. Quantum information theory. Cambridge University Press, Cambridge,
2013. 11
[Wil13b] M. M. Wilde. Sequential decoding of a general classical-quantum channel. Proc. of theRoyal Society A, 469(2157):20130259, 2013. arXiv:1303.0808. 12[Win99] A. Winter. Coding theorem and strong converse for quantum channels. IEEE Trans.
Inform. Theory, 45(7):2481–2485, 1999. 10, 11[Zha12] M. Zhandry. How to construct quantum random functions. In 53rd Annual IEEE
Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ,
USA, October 20-23, 2012, pages 679–687, 2012. 73[Zha13] M. Zhandry. A note on the quantum collision problem for random functions.
arXiv:1312.1027, 2013. 56

106