PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Scott Aaronson

arXiv:1607.05256v1quant-phcs.CCgr-qc

TL;DR

How many operations are needed to prepare a quantum state is a central question in quantum circuit complexity. These lecture notes use state and unitary complexity as a connecting thread, and show that PQP = PP for a suitable gate set.

  • Problem

    Quantum state complexity asks how many operations are needed to prepare a given state.

    Source: §1.1 · p. 6

  • Method

    The notes use the complexity of states and unitaries as a connecting thread.

    Source: §1.1 · p. 6

  • Results

    With gates whose unitary entries lie in {0, ±1/2, ±1}, the notes show that PQP = PP.

    Source: §2.4.1 · p. 23

  • Takeaways & Limitations

    A gate set that is not universal can still be universal on an encoded space, as {AND, OR} is under dual-rail encoding.

    Source: §10.4.1 · p. 100

    In QSampling, the constructed state differs from |ψD⟩ because the |r⟩ register is decohering garbage.

    Source: §4.1 · p. 35

Abstract

from arXiv · show

These are lecture notes from a weeklong course in quantum complexity theory taught at the Bellairs Research Institute in Barbados, February 21-25, 2016. The focus is quantum circuit complexity---i.e., the minimum number of gates needed to prepare a given quantum state or apply a given unitary transformation---as a unifying theme tying together several topics of recent interest in the field. Those topics include the power of quantum proofs and advice states; how to construct quantum money schemes secure against counterfeiting; and the role of complexity in the black-hole information paradox and the AdS/CFT correspondence (through connections made by Harlow-Hayden, Susskind, and others). The course was taught to a mixed audience of theoretical computer scientists and quantum gravity / string theorists, and starts out with a crash course on quantum information and computation in general.

Lecture 1

Lecture 1 lays the quantum-mechanical foundations for a course connecting quantum state and unitary complexity to topics in quantum computing theory. It covers states, transformations, measurements, multipartite systems and entanglement, then develops tools including trace distance to analyze measurement disturbance and the cumulative effects of sequential measurements.

1.1 Introduction

  • The course systematically uses the difficulty of preparing states and applying unitaries to connect topics including quantum proofs and advice, quantum money, black holes and AdS/CFT.Its stated focus is the complexity of quantum states and unitary transformations.Source: §1.1 · p. 6

1.2.1 Quantum States, Unitary Transformations, and Measurements

  • Quantum states are normalized complex-amplitude vectors; unitaries preserve inner products, while measurements yield outcomes according to squared amplitudes and collapse the state.The notes present quantum mechanics as a mathematical generalization of probability theory, replacing probabilities with complex amplitudes.Source: §1.2.1 · pp. 7, 8, 10

1.2.2 Multipartite Systems, Entanglement, and Density Matrices

  • Multipartite states combine systems by tensor products; entangled states are nonseparable, and mixed states are represented without redundant decompositions by density matrices.For density matrix ρ, a unitary U produces UρU†, and measurement in the stated basis yields outcome i with probability ρii.Source: §1.2.2 · pp. 10–11
  • The No Communication Theorem states that Alice’s chosen measurements and unitary transformations on a shared bipartite state cannot change Bob’s local density matrix.This rules out instantaneous signaling through entanglement.Source: §1.2.2 · p. 12
  • Randomly chosen measurement bases distinguish entanglement from classical shared randomness, although entanglement itself enables no faster-than-light communication.Any classical simulation of entanglement would require faster-than-light communication.Source: §1.2.2 · p. 13

1.2.3 More General Operations and Measurements

  • POVMs describe measurements using positive semidefinite operators summing to identity, allow more than N outcomes, and are equivalent to projective measurements with an ancilla.For outcome i, the probability is Tr(E_iρ); the formalism does not specify the post-measurement state.Source: §1.2.3 · p. 13
  • Superoperators package combinations of unitaries, measurements, and ancillary systems, while any mixed state can be purified by tracing out part of a larger pure state.For an N-dimensional mixed state, N^2 dimensions suffice for such a purification.Source: §1.2.3 · pp. 13–14

1.2.4 Measuring Distances Between Quantum States

  • Trace distance bounds how much a two-outcome POVM’s acceptance probability changes between nearby states, is invariant under unitaries, and cannot increase when subsystems are traced out.If the trace distance is at most ε, acceptance probability changes by at most ε; fidelity provides another state-distance measure, generalizing overlap to mixed states.Source: §1.2.4 · pp. 14–15

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

  • The “Almost As Good As New” Lemma [Aar05a] shows that a measurement outcome occurring with probability 1−ε leaves the state close to its original form after undoing the operation and discarding the ancilla.The result is closely related to the “Gentle Measurement Lemma”, whose standard formulation concerns a two-outcome POVM conditioned on a likely outcome.Source: §1.3 · pp. 15–17
  • When each of k measurements succeeds with probability at least 1−ε on the original state, the Quantum Union Bound [Aar06] bounds cumulative disturbance by O(k√ε).The proof uses the triangle inequality and the fact that each measurement changes the state by at most √ε in trace distance.Source: §1.3 · p. 17

Lecture 2

Lecture 2 introduces constraints on quantum states and tools for studying quantum circuits, relating quantum computation to classical complexity through simulation bounds and oracle-based query separations. It illustrates the contrast with Simon’s problem, where a quantum algorithm recovers a hidden string using O(n) queries and classical postprocessing.

2.1 The No-Cloning Theorem

  • No procedure can clone an arbitrary quantum state: unitary cloning would be nonlinear, and general superoperators cannot increase trace distance.The superoperator proof derives a contradiction because cloning increases the trace distance between distinct pure states.Source: §2.1 · p. 18

2.2 Monogamy of Entanglement

  • If Alice and Bob are maximally entangled, their joint state factors from Charlie’s, so Alice and Charlie share neither entanglement nor classical correlation.In the example, Bob and Charlie’s reduced state is an unentangled mixed state, unlike the entangled pure Bell pair of Alice and Bob; for mixed states, distillable entanglement can be less than entanglement of formation.Source: §2.2 · pp. 18–19

2.3 Quantum Circuits and Universal Gate Sets

  • Circuit complexity C(U) is the minimum number of one- and two-qubit gates implementing U exactly, and almost all n-qubit unitaries require at least 4^n gates.A finite gate set is universal if it approximates any unitary to arbitrary precision; {Toffoli,H,Phase} is universal, while {CNOT,H,Phase} is classically simulable in polynomial time by the Gottesman–Knill theorem [AG04].Source: §2.3 · pp. 20–21

2.3.1 The Solovay-Kitaev Theorem

  • For any physically universal gate set, Solovay–Kitaev approximates a target unitary to entrywise accuracy ϵ using log^O(1)(1/ϵ) gates, omitting dependence on n [DN05].For gate sets with certain special properties, the count is O(log 1/ϵ), which is optimal [HRC02].Source: §2.3.1 · p. 21

2.4 Relations to Complexity Classes

  • BQP comprises languages efficiently decidable by polynomial-size, P-uniform quantum circuit families over a finite universal gate set, and BPP ⊆ BQP.As in BPP, BQP’s error bounds can be amplified by repetition and majority vote.Source: §2.4 · pp. 21–22

2.4.1 Classical Simulation of Quantum Computation

  • Quantum computation can be simulated within PP, with PP ⊆ P^#P ⊆ PSPACE ⊆ EXP; thus it is at most exponentially more powerful than classical computation.With gates whose entries are in {0, ±1/2, ±1}, the simulation is exact and yields PQP = PP; BQPSPACE = PSPACE, and space s quantum algorithms can be simulated classically in space s^2. The notes state that proving BPP ≠ BQP unconditionally would imply P ≠ PSPACE.Source: §2.4.1 · pp. 23–24

2.4.2 Quantum Oracle Access

  • Some oracles satisfy BPP^A = BQP^A, while Bernstein and Vazirani found an oracle separation requiring classical Ω(n log n) queries, later improved by Simon to an exponential quantum–classical query-complexity separation.For Simon’s problem, classical randomized algorithms require Θ(2^(n/2)) queries to solve it with high probability.Source: §2.4.2 · p. 24
  • For q=o(2^(n/2)) classical queries, the probability of correctly distinguishing Simon’s cases is o(1), bounded by the expected number of collision pairs.The passage gives the decision rule of guessing the 1-to-1 case exactly when all queried answers differ.Source: §2.4.2 · p. 25
  • Hadamard gates make measurement yield a random z satisfying s · z ≡ 0 (mod 2), a linear equation that constrains the hidden string.In the 2-to-1 case, the measured input register is a superposition of x and x ⊕ s; measuring it directly would reveal no information about s.Source: §2.4.2 · pp. 25–26
  • O(n) quantum queries to f and polynomial computation time suffice to determine Simon’s hidden string with overwhelming probability.The algorithm repeats measurements until the only solutions to the resulting linear system are 0^n and s, then checks this with classical Gaussian elimination.Source: §2.4.2 · pp. 25–26
  • Repeating the procedure yields enough random linear equations to leave only 0^n and s as solutions after O(n) repetitions with overwhelming probability.Gaussian elimination checks this condition in classical polynomial time.Source: §2.4.2 · p. 26

Lecture 3

Lecture 3 surveys the Hidden Subgroup Problem and quantum circuit complexity for unitaries and states, including efficient algorithms for abelian groups and limits and open questions for non-abelian groups. It examines oracle access and explicit-state preparation, the distinction between preparing a state and implementing a unitary encoding the same information, and the challenges of proving complexity lower bounds.

3.1 Hidden Subgroup Problem

  • Integer factoring is in BQP, and HSP over any finite abelian group is in BQP_f.Shor’s algorithm solves period-finding in quantum polynomial time with O(1) function queries; its quantum step parallels Simon’s algorithm using a discrete Fourier transform.Source: §3.1 · pp. 27–28
  • Non-abelian HSP remains largely unsolved despite its links to Graph Isomorphism and approximate lattice-vector problems; polynomially many queries suffice, but EHK post-processing takes exponential time [Reg04] [EHK04].Regev’s approximate-lattice-vector reduction assumes coset sampling, while Ettinger, Høyer, and Knill show that O(log^2 |G|) queries suffice and can be efficiently constructed.Source: §3.1 · pp. 28–29

3.2 Circuit Complexity

  • For almost every Boolean function f, implementing its oracle unitary requires superpolynomial circuit size, while f in BQP has polynomial-size implementation.These counting-based bounds motivate the open Unitary Synthesis Problem: whether every n-qubit unitary has polynomial complexity relative to some Boolean oracle.Source: §3.2 · p. 30
  • Aaronson and Kuperberg showed that some unitaries cannot be implemented with one oracle query by any polynomial-time quantum algorithm that always implements a unitary [AK07].Whether every unitary can be implemented in polynomial time relative to some oracle remains open.Source: §3.2 · p. 31

3.3 Quantum State Complexity

  • Almost all n-qubit states have complexity 2^Ω(n), but high entanglement alone does not imply high complexity; random-circuit measurement can yield states believed to have exponential complexity.Any separable n-qubit state has O(n) complexity, and the measured-state claim is that the resulting state has 2^Ω(n) complexity with overwhelming probability, as far as anyone knows.Source: §3.3 · pp. 31–32
  • For states ψ and φ with circuit complexity greater than polynomial, a linear combination can still be trivial; a proposition bounds the complexity of suitable linear combinations using the component circuits [Aar04].The proposition extends to pairs with |⟨ψ|φ⟩| < 1 − ε, at a multiplicative O(1/ε) cost.Source: §3.3 · pp. 32–33

3.3.1 State Versus Unitary Complexity

  • Every n-qubit state can be prepared in polynomial time relative to an oracle encoding the construction’s amplitudes and phases.The construction recursively prepares qubits using square roots of conditional probabilities, then applies phases to basis states.Source: §3.3.1 · p. 33
  • For a one-way permutation σ, a state correlating |x⟩ with |σ(x)⟩ is easy to prepare, but producing it from shared |x⟩ registers by acting only on the second requires inverting σ.The example shows why easy preparation of a state encoding a unitary’s information does not establish that the unitary itself is easy to implement.Source: §3.3.1 · p. 34
  • For any n-qubit unitary U, some oracle lets a polynomial-time quantum algorithm apply a unitary agreeing with U on any n^O(1) rows.The proof is left as an exercise.Source: §3.3.1 · p. 34
  • It remains open whether every n-qubit state can be prepared with o(n) oracle queries, or even one query.This asks whether Proposition 3.3.5 is tight in query complexity.Source: §3.3.1 · p. 34
  • If BQP = P#P, then essentially all explicit states discussed have polynomial approximate circuit complexity, so proving superpolynomial lower bounds for virtually any interesting state would require BQP ≠ P#P.For states whose amplitudes are computable in #P, the recursive construction computes the required parameters.Source: §3.3.1 · p. 34

Lecture 4

Lecture 4 examines quantum state preparation and proof complexity, distinguishing efficiently samplable distributions from preparable states and connecting that distinction to Graph Isomorphism and Statistical Zero-Knowledge. It also develops QMA and related results, including Local Hamiltonians and black-box group non-membership protocols that contrast classical and quantum witnesses.

4.1 QSampling States

  • Efficient classical sampling alone does not prepare a QSampling state: the direct quantumized sampler retains entangled random-seed garbage, while some distributions, such as perfect matchings, are QSamplable [ATS03].Aharonov and Ta-Shma showed that perfect-matching QSampling can be prepared efficiently using details of the Jerrum–Sinclair–Vigoda sampling algorithm [JSV04].Source: §4.1 · p. 35
  • Polynomial-size preparation of the graph-permutation QSampling states would put Graph Isomorphism in BQP, because isomorphic graphs yield equal states and nonisomorphic graphs yield orthogonal states.A Hadamard-basis measurement distinguishes equal from orthogonal states; the notes say it remains unclear whether these states can be prepared in less than exponential time even given Babai’s algorithm [Bab16].Source: §4.1 · p. 36
  • If NP ⊆ BQP, every samplable distribution has a QSampling state preparable to precision 1/n^O(1), while an oracle separation shows SZK is not contained in BQP [Aar02].The notes also give Aaronson’s Collision Problem lower bound of Ω(N^1/5) queries, improved by Shi to the tight Ω(N^1/3) [Shi02].Source: §4.1 · pp. 36, 38, 39
  • If QSampling states are efficiently preparable, then SZK ⊆ BQP; the Statistical Difference test uses interference to distinguish distributions whose QSampling states have inner product near 1 or 0 [ATS03].The test measures a control qubit after combining the two prepared states; the overlap behavior follows from the fidelity bounds for Statistical Difference.Source: §4.1 · pp. 37–38

4.2 Quantum Witness States

  • QMA consists of languages L with a polynomial-time quantum verifier V: yes-instances have a witness accepted with probability at least 2/3, while every no-instance witness is accepted with probability at most 1/3.The verifier receives the input, a witness, and initialized |00...0⟩ ancillas.Source: §4.2 · p. 39

4.3 QMA-Complete Promise Problems

  • The Local Hamiltonians promise problem is QMA-complete: any QMA problem reduces efficiently to it, so local quantum constraints can encode the complexity of arbitrary quantum witnesses.The problem uses two-outcome measurements acting on at most two qubits and asks whether the maximum acceptance probability is at least q or at most q − ε.Source: §4.3 · pp. 40–41

4.4 Group Non-Membership

  • Group Membership is in NP because a polynomial-size straight-line program certifies that x is generated by H’s generators.The program introduces intermediate elements for operations so later operations can use them.Source: §4.4 · p. 41
  • In black-box groups, GNM has no NP witnesses and is not in MA, whereas whether explicit-group GNM is in NP remains open.Classical verification therefore requires interaction in the black-box setting.Source: §4.4 · p. 42
  • GNM is in AM and SZK: Arthur samples from H or ⟨H,x⟩, and when x∉H the latter has at least twice H’s order, enabling Merlin to distinguish the cases (Babai).When x∈H, the two subgroups coincide, so Merlin guesses Arthur’s coin incorrectly with probability 1/2.Source: §4.4 · p. 42
  • GNM is in QMA: Merlin supplies a subgroup state, and Arthur’s coset comparison returns |+⟩ surely if x∈H but gives |+⟩ or |−⟩ equally if x∉H (Watrous).Arthur must also verify that the purported witness is close to an equal superposition over a left coset of a supergroup of H.Source: §4.4 · p. 42
  • Arthur verifies Merlin’s QMA witness by testing invariance under right-multiplication by a random H element, which implies the state is close to a coset of a supergroup of H.In the honest case, the test does not damage the witness, allowing Arthur to reuse it for the non-membership test.Source: §4.4 · pp. 42–43
  • Watrous’s QMA protocol assumes unique element labels, and Merlin may be needed to provide garbage-free |H⟩ because Arthur’s own preparation leaves an unusable garbage register.Whether black-box GNM is in BQP remains open; Arthur may not be able to prepare |H⟩ himself.Source: §4.4 · p. 43

Lecture 5

Lecture 5 examines how quantum witnesses and advice affect computational power, contrasting them with classical information and considering how their effects can be separated or bounded. It focuses on differing consequences across complexity classes, including upper bounds and simulations for classes with quantum advice.

5.1 QCMA

  • QIP = PSPACE and QIP(3) = QIP, so three-round quantum interactive proofs reach PSPACE, unlike classical constant-round protocols, which give no more than AM.The three rounds consist of an initial message from Merlin, a challenge from Arthur, and Merlin’s response.Source: §5.1 · pp. 44–45

5.2 QMA versus QCMA

  • A QCMA protocol for Group Non-Membership uses polylog|G| queries but exponential post-processing, so query complexity alone cannot establish a stronger lower bound.Merlin supplies a model group and purported isomorphism; Arthur tests the homomorphism and uses a hidden-subgroup algorithm to check that the embedding is one-to-one.Source: §5.2 · pp. 45–46
  • Aaronson and Kuperberg [AK07] construct a quantum oracle U for which QMA^U ≠ QCMA^U, using Haar-random n-qubit states.A classical oracle separating the classes remains open; Fefferman and Kimmel [FK15] showed a separation for a probabilistic permutation oracle.Source: §5.2 · pp. 46–48
  • If every accepting QMA witness had a polynomial-size preparation circuit, then QMA = QCMA, but that equality alone does not imply such circuits exist.QCMA restricts Merlin to a classical witness while Arthur may still verify it quantumly.Source: §5.1 · p. 44, §5.2 · p. 49

5.2.1 Quantum Advice States

  • A quantum oracle separates BQP/qpoly from BQP/poly, while a Group Non-Membership variant is in BQP^U/qpoly but not known to be in BQP/poly.The adviser can provide the trusted state |H_n⟩ because the groups G_n and subgroups H_n are fixed by input length.Source: §5.2.1 · pp. 49–50

5.3 Upper-Bounding BQP/qpoly

  • The lecture rules out BQP/qpoly = ALL, but the classical counting argument does not transfer directly because exponentially sized quantum advice comes from a doubly-exponential set of nearly orthogonal states.The highlighted passage states the exclusion without specifying the bound used to establish it.Source: §5.3 · p. 50
  • PQP/qpoly = ALL: an exponentially small bias toward the correct answer still suffices for a PQP machine.The algorithm measures the advice register and gives the correct answer when the input is observed; otherwise it answers randomly.Source: §5.3 · p. 50
  • PostBQP = PP; if PostBPP = PostBQP, the polynomial hierarchy collapses to its third level using Toda’s Theorem [Tod91].The notes present this as stronger evidence for PostBPP ≠ PostBQP than for BPP ≠ BQP.Source: §5.3 · pp. 51–52
  • BQP/qpoly ⊆ PostBQP/poly = PP/poly, via classical counterexamples that refine a maximally mixed advice guess in O(m) rounds.The process stops when the refined state answers every input correctly with probability at least 2/3.Source: §5.3 · pp. 52–53
  • BQP/qpoly ⊆ QMA/poly, replacing trusted quantum advice with trusted classical advice and untrusted quantum advice of polynomial size.If every QMA witness state can be prepared by polynomial-size quantum circuits, then BQP/poly = BQP/qpoly.Source: §5.3 · p. 53
  • QMA/qpoly ⊆ PSPACE/poly [Aar06], so combining quantum proofs and quantum advice still yields a class simulable with polynomial-size classical advice and polynomial space.The proof requires looping through possible QMA witnesses without destroying the /qpoly advice.Source: §5.3 · p. 53

Lecture 6

The lecture turns to the black-hole information problem, promising to connect it back to complexity. It introduces the event horizon and singularity as key regions before asking what makes black holes puzzling to physicists.

Black Holes, Firewalls and Complexity

  • The lecture temporarily leaves complexity theory to discuss the black-hole information problem, promising to return to complexity by the end.Source: Lecture 6 · p. 54
  • The event horizon marks the boundary beyond which signals cannot escape a black hole’s interior, while the singularity lies at its center.The black hole’s mass distorts spacetime’s causal structure, preventing signals from reaching the exterior.Source: Lecture 6 · p. 54
  • The lecture frames black holes as a source of puzzles that have captured theoretical physicists’ attention.Source: Lecture 6 · p. 54

6.1 Thermodynamics and Reversibility

The section traces black-hole thermodynamics from Bekenstein’s area-based entropy proposal to Hawking radiation and the resulting information-loss puzzle. It concludes that black-hole evolution should be unitary, with semiclassical calculations breaking down as an approximation.

6.1 Thermodynamics and Reversibility

  • Bekenstein’s arguments imply that black holes store the maximum entropy allowed for a given surface area, making them the most compact hard drives permitted by physics.The proposed entropy is about 1069 bits per meter squared and scales with event-horizon area rather than volume.Source: §6.1 · p. 55
  • Hawking’s semiclassical calculation predicted that an outside observer would see thermal radiation escaping at the rate Bekenstein’s formula predicted.The calculation treated radiation quantum-mechanically while keeping curved spacetime classical.Source: §6.1 · p. 55
  • Hawking radiation is predicted to be thermal and uncorrelated with infalling information, so a pure infalling state appears to become mixed after evaporation.Hawking proposed that black holes might therefore violate unitarity, unlike the usual reversible evolution of quantum states.Source: §6.1 · p. 55
  • The black-hole information puzzle challenges the Second Law and reversibility, but the prevailing view is that quantum-gravitational evolution remains unitary and semiclassical calculations fail as an approximation.The section also gives an evaporation-time scaling of r3 ∼ A3/2, compared with stored bits scaling as A ∼ r2.Source: §6.1 · pp. 54–56

6.2 The Xeroxing Problem

The Xeroxing Problem is that a qubit seems to remain inside a black hole while also emerging in Hawking radiation, apparently violating the No-Cloning Theorem. Black hole complementarity proposes that the inside and outside manifestations are the same qubit, viewed in different ways.

6.2 The Xeroxing Problem

  • A qubit dropped into a black hole seems to stay inside while emerging in scrambled form in Hawking radiation, implying two copies and a violation of the No-Cloning Theorem.This is the Xeroxing Problem.Source: §6.2 · p. 56
  • Black hole complementarity argues that no observer can see both manifestations: by the time Alice re-enters after the qubit emerges, its inside manifestation has hit the singularity.This addresses the objection that Alice could wait for the qubit to emerge and then jump in to find the other copy.Source: §6.2 · p. 56
  • Susskind and ’t Hooft proposed that the inside and outside qubits are literally the same qubit, measured or viewed in two different ways.Source: §6.2 · p. 56

6.3 The Firewall Paradox

The firewall paradox pits the entanglement required for a smooth horizon against the correlations an outside observer can extract from post-Page-time Hawking radiation. It sharpens black hole complementarity into a question about what an observer would experience.

The Firewall Paradox

  • AMPS [AMPS13] proposed the firewall thought experiment, which Scott says sharpened complementarity by making the issue what an observer would experience.Source: §6.3 · p. 56
  • QFT predicts that Hawking radiation just outside the horizon is entangled with a partner just inside; without these Bell pairs, an infalling observer encounters a Planck-energy firewall.The firewall is described as an end of spacetime where the observer would immediately disintegrate.Source: §6.3 · pp. 56–57
  • Modeling evaporation as a complex circuit makes radiation pseudorandom and Haar-like; its k-qubit marginal is maximally mixed for k < n/2, but rank-deficient and non-maximally mixed for k > n/2.The black-hole formation time is polynomial, unlike the 2^Ω(n) circuit complexity of a Haar-random state with overwhelming probability.Source: §6.3 · p. 57
  • At the Page Time, when half the qubits have emerged, the outside state is no longer maximally mixed and Alice can in principle see correlations; above half, each emitted qubit is entangled with the others with overwhelming probability.The Page Time is named for Don Page, who studied it in the 1980s.Source: §6.3 · p. 57
  • After the Page Time, when 2n/3 qubits have emerged as Hawking radiation and n/3 remain inside, Alice can apply a suitable unitary to R to Bell-pair B with a designated qubit in R.Source: §6.3 · p. 58
  • Other proposed resolutions limit scientific claims to the exterior, accept a unitary-compatible firewall, or abandon unitarity, with the latter making the outside observer see a truly mixed state.Source: §6.3 · p. 58
  • Scott favors making the firewall contingent on Alice’s extreme processing: complementarity identifies H with R and B in another basis, but leaves “normal circumstances” undefined.This view treats the paradox as arising from not taking complementarity seriously enough.Source: §6.3 · pp. 58–59

6.4 The HH Decoding Task

Harlow and Hayden [HH13] frame firewall preparation as a task of decoding a Bell pair by acting only on part of a quantum state. They show that efficient decoding for arbitrary input circuits would imply a surprising complexity-class containment, while the task remains information-theoretically possible.

6.4 The HH Decoding Task

  • Given a circuit C preparing |ψ⟩RBH, HH decoding asks for a unitary acting only on R that makes B and R’s rightmost qubit a perfect Bell pair [HH13].The lectures assume perfect decoding; allowing approximate decoding adds technical complications but does not change the conceptual picture.Source: §6.4 · p. 59
  • Although the promised unitary exists, generic scrambling arguments for k > n/2 give only abstract constructions, and extracting a decoder from them would require an exponential-size circuit.The arguments establish non-maximum rank and, for random-circuit outputs, generically entanglement between R and B; they do not rule out a clever general efficient algorithm.Source: §6.4 · p. 59
  • If arbitrary-circuit HH decoding is polynomial-time, then SZK ⊆ BQP; if SZK problems are exponentially hard for quantum computers, decoding requires exponential time [HH13].The task’s exponential-time hardness is conditional on the existence of such exponentially hard SZK problems.Source: §6.4 · p. 60
  • In HH’s idealization, preprocessing Hawking radiation for a solar-mass black hole would take roughly 21067 years rather than a mere 1067 years, exceeding the black hole’s lifetime [HH13].The notes use this estimate to argue that Alice would not finish the preprocessing before the black hole evaporated.Source: §6.4 · p. 60

6.5 The Harlow-Hayden Argument

The Harlow–Hayden argument reduces Set Equality to decoding entanglement, so efficient decoding would solve Set Equality and Set Equality hardness implies decoding hardness. The section strengthens that hardness result and distinguishes special constructions from the unresolved generic case.

6.5 The Harlow-Hayden Argument

  • Efficient HH decoding for arbitrary circuits would solve Set Equality: equal ranges yield a Bell pair, while disjoint ranges violate the decoding promise, giving a bounded-error test.By contraposition, if Set Equality is hard for quantum computers, so is the HH Decoding Task.Source: §6.5 · pp. 60–61
  • Zhandry [Zha13] strengthened Set Equality’s quantum query lower bound to tight Ω(N^1/3); for explicit functions, an efficient algorithm would also yield polynomial-time Graph Isomorphism.The section also notes that efficient quantum algorithms for Statistical Distance would imply SZK ⊆ BQP.Source: §6.5 · p. 60

6.5.1 Improvements to Harlow-Hayden

  • Quantum-secure injective one-way functions suffice to make HH decoding hard, and Aaronson’s stronger construction makes even classical correlation between R and B hard to distill.The latter argument uses a hardcore predicate: detecting correlation would help predict its bit and thereby invert the function, contrary to the assumption; Goldreich and Levin supply the predicate result.Source: §6.5.1 · pp. 63–64

6.5.2 The “Generic Case”

  • For generic states produced by a random polynomial-size circuit across R, B, and H, decoding intuitively seems harder, but no general converse to the special-state hardness results is known.Even if P = PSPACE, the text says it is unknown whether generic HH decoding would be easy; generic black-hole states may be harder than the special states used in formal reductions.Source: §6.5 · p. 62, §6.5.2 · pp. 64–65

6.5.3 Preskill’s Problem

  • Preskill’s question remains open generically: can decoding use exponentially many gates while every intermediate state retains polynomial circuit complexity?For the special Set Equality and injective-OWF constructions, the answer is yes; generic dimension-counting circuits plausibly produce intermediate states of complexity 2^Ω(n).Source: §6.5.3 · pp. 65–66

Lecture 7

Lecture 7 presents circuit complexity as a possible link between CFT states and wormhole growth in AdS/CFT, then examines the complexity-theoretic limits on proving that link. The duality is conjectured, and its proposed complexity interpretation remains speculative.

Lecture 7

  • AdS/CFT conjectures an equivalence between gravity theories in (d + 1)-dimensional AdS and d-dimensional boundary CFTs, where gravity and an extra dimension emerge from the CFT description.The correspondence matches symmetries and operators, and predicts agreement of observables computed on either side, though a general proof is not known.Source: Lecture 7 · p. 68

7.0.4 Susskind’s Puzzle

  • After about n log n gates, local density matrices of O(1) qubits thermalize and, with overwhelming probability, remain thermalized for doubly-exponential time, despite continued wormhole growth.Susskind proposed that the CFT state’s circuit complexity, rather than its rapidly thermalizing local properties, corresponds to wormhole length.Source: §7.0.4 · p. 69

7.1 The Proposal

  • Susskind’s proposal identifies state complexity with wormhole volume: reversing U should reverse complexity growth, while inserting an unrelated V before U^-1 should let growth continue.The predicted complexity behavior also includes speculative dips when the evolving state returns near a low-complexity state. The proposal remains unproven, and the appropriate complexity variant is unsettled.Source: §7.1 · pp. 70–71

7.1.1 Lower Bounds

  • For a polynomial-size-circuit U, proving superpolynomial state complexity at some time would imply PSPACE ⊄ BQP/poly, so unconditional linear-growth lower bounds are out of reach absent that separation.A counting argument gives exponential complexity only after doubly-exponential time, which is insufficient for Susskind’s proposal.Source: §7.1.1 · p. 71
  • For a polynomial-size-circuit U implementing universal reversible computation, some t > c^n gives Cε(|ψt⟩) > n^ω(1), unless PSPACE ⊂ PP/poly.The construction uses a reversible universal cellular automaton; such universality is presented as a mild condition expected of physically relevant dynamics. Stronger exponential bounds require stronger assumptions, and linear-in-time growth remains unproved under standard assumptions.Source: §7.1.1 · pp. 71–72
  • Separable complexity of the thermofield-double state equals the unitary complexity of Ut; if it is polynomial, then PSPACE ⊂ BQP/poly, stronger than the standard-complexity implication.Separable circuits act independently on the two halves and use no ancillas.Source: §7.1.1 · p. 73

Lecture 8

Lecture 8 examines private-key quantum money, tracing its development from Wiesner’s no-cloning idea through security models involving storage limits, bank queries, and counterfeiting attacks. It also connects injective private-key quantum money to the hardness of decoding Hawking radiation and raises an open tomography problem.

8.1 The Wiesner and BBBW Schemes

  • The optimal counterfeiter can make two Wiesner notes that both pass verification with probability (3/4)^n, a tight bound proved independently by Molina, Vidick, and Watrous and Pastawski et al. [PYJ+11].Aaronson’s later general security reduction is described as establishing full security, including against counterfeiters given multiple legitimate notes.Source: §8.1 · p. 76
  • BBBW replaces Wiesner’s per-note database with a pseudorandom function keyed by one secret, trading unconditional security for computational security.The bank derives each note’s qubit states from its serial number and key; security follows by reduction to the PRF and Wiesner security.Source: §8.1 · p. 76, §8.3 · p. 78

8.2 Formal Underpinnings

  • Aaronson’s 2013 unpublished theorem shows that a secure mini-scheme and a quantum-secure PRF yield a full private-key scheme with negligible completeness and soundness errors.The construction uses a serial number and verifies with the PRF-derived key; its soundness argument invokes the PRF assumption twice.Source: §8.2 · p. 77
  • Quantum-secure PRFs follow from quantum-secure one-way functions using adapted HILL and GGM arguments, with Zhandry’s proof repairing the GGM step for quantum attackers.The classical GGM argument breaks when an attacker can query inputs in superposition.Source: §8.2 · p. 78

8.3 Security/Storage Tradeoff

  • Any scheme whose bank stores only n bits can be broken by an exponential-time quantum counterfeiter using poly(n) legitimate notes and O(n) verification queries, or no queries with success probability Ω(1/n).This Aaronson 2013 unpublished result establishes that information-theoretic security cannot be combined with small bank storage.Source: §8.3 · p. 78
  • The Secret Acceptor Lemma finds a highly accepting measurement among known candidates by combining the Quantum OR Bound with recursive binary search.The Quantum OR Bound uses O(log N) copies to distinguish whether some measurement accepts with probability at least 2/3 from the case where all accept with probability at most 1/3; Harrow and Montanaro [HM16] give a sound strategy that checks for state damage.Source: §8.3 · pp. 80–81
  • Setting the iteration’s fudge factor δ := ε log N lets the security/storage argument continue beyond a constant number of iterations, at the cost of requiring more copies of ρ.Each reduction to a smaller search region lowers the acceptance guarantee from p to at least p − δ.Source: §8.3 · p. 81

8.3.1 Open Problems

  • Batch tomography asks whether all N measurement probabilities can be estimated to additive error ε with polylog N copies absent a probability-gap promise; the answer remains open.With O(N log N) fresh copies the task is straightforward, while a gap promise such as probabilities above 2/3 or below 1/3 permits sequential amplified measurements with polylog N copies.Source: §8.3.1 · pp. 81–82

8.4 Interactive Attacks

  • Repeated interactive queries fully break the original Wiesner and BBBW schemes; under a naïve bill-returning bank, an attack learns Wiesner’s qubits by testing candidate states [Lut10].For each qubit, the counterfeiter observes which candidate makes the bank accept, while correctly based measurements leave the other qubits undamaged.Source: §8.4 · p. 82

8.4.1 The Elitzur-Vaidman Bomb Attack

  • Nagaj and Sattath’s Elitzur-Vaidman-style attack learns an n-qubit Wiesner bill using O(n/ε) trial verifications with at most O(nε) probability of being caught, while avoiding failed verifications.The attack also applies with minor modifications to BBBW and schemes of unentangled qubits verified by separate projective measurements; destroying each submitted bill and issuing a new one is a simple fix.Source: §8.4.1 · pp. 83–85

8.5 Quantum Money and Black Holes

  • Theorem 8.5.1 shows that secure private-key injective quantum money with small keys implies the HH Decoding Task is hard, making HH hardness follow from a weaker assumption than injective quantum-secure OWFs.The reverse implication from injective private-key quantum money to injective OWFs is not known.Source: §8.5 · p. 85

Lecture 9

Lecture 9 examines security questions and constructions for quantum money, including interactive attacks on private-key money and public-key schemes whose notes are publicly verifiable but hard to copy. It also relates counterfeiting low-degree polynomial money to hidden-subspace recovery and surveys attacks and possible directions for quantum money and copy-protection.

9.1 Public-Key Mini-Schemes

  • A quantum-secure signature scheme lifts a public-key mini-scheme to full money: any counterfeiter then breaks either the mini-scheme or the signature scheme [LAF+10] [AC12].The bank signs each mini-scheme note’s serial number; verification checks the signature and then the note. Since quantum-secure signatures can be built from quantum-secure one-way functions, the central challenge is a secure public-key mini-scheme.Source: §9.1 · p. 87

9.2 Candidates

  • Existing candidates were mostly broken, while the knot-based scheme remained unbroken as of 2016 but lacked a clear security analysis [LAF+10] [FGH+10] [FGH+12].The stabilizer-state scheme was broken using a planted-clique algorithm, and Local Hamiltonian schemes by single-copy tomography; the knot scheme encodes an Alexander-polynomial value in superpositions of link diagrams.Source: §9.2 · p. 88

9.3 Public-Key Quantum Money Relative to Oracles

  • Aaronson proved a public-key mini-scheme exists relative to a quantum oracle, with counterfeiting requiring Ω(2^(n/2)) oracle queries even when starting with a valid note.Notes encode independently Haar-random n-qubit states, and verification projects onto the corresponding state; the oracle reflects about valid notes. The lower bound follows from a complexity-theoretic no-cloning theorem, where each query decreases expected squared fidelity by at most O(2^(-n/2)).Source: §9.3 · pp. 88–89

9.4 The Hidden Subspace Scheme

  • Aaronson and Christiano showed public-key quantum money is possible relative to a classical oracle, using obfuscated descriptions of hidden subspaces and their duals [AC12].The notes are uniform superpositions over subspaces of dimension n/2; the oracle supplies characteristic functions used to project onto the note state. Counterfeiting requires Ω(2^(n/4)) queries, even with a note and access to those functions.Source: §9.4 · pp. 89–90
  • The hidden-subspace construction also yields private-key money secure against interactive attacks without computational assumptions, provided the bank maintains a huge database [AC12].The bank stores each note’s serial number and a basis for its associated subspace; returning submitted notes after verification does not enable efficient counterfeiting, which would require Ω(2^(n/2)) bank queries.Source: §9.4 · p. 91

9.5 Instantiation

  • Aaronson and Christiano proposed encoding hidden subspaces through degree-3 polynomials that identify each subspace and its dual, as a possible route to instantiating the oracle scheme [AC12].With m = O(n) polynomials, these descriptions compute the characteristic functions without an oracle, while the passages introduce—but do not complete—the theorem’s security-reduction claim.Source: §9.5 · pp. 91–92
  • A counterfeiting algorithm can be converted into basis recovery with success probability Ω(2^-n/2), by making Θ(n) copies of the hidden-subspace state and measuring them.The notes compare this with random guessing, which succeeds with probability only 2^-Ω(n^2).Source: §9.5 · p. 92

9.6 Attacks

  • Pena et al. broke the noiseless scheme over finite fields of odd characteristic, recovering a basis in classical polynomial time without the dual polynomials; they conjectured quasipolynomial time in the F2 case.Their Gröbner-basis techniques break down in the presence of noise, so the noisy scheme was unaffected by that result.Source: §9.6 · p. 92
  • Christiano and others broke the noisy low-degree polynomial scheme by giving a quantum reduction from breaking it to breaking the noiseless scheme.Single-copy tomography uses amplitude amplification to restore a money state after measurements, enabling identification of noisy polynomials without permanently damaging the state; the reduction is specific to quantum money.Source: §9.6 · p. 93
  • A polynomial-time quantum algorithm recovers a basis from noisy low-degree polynomials with success probability Ω(2^-n/2), via the contrapositive of the scheme-breaking result.The notes contrast this with naive random guessing, which succeeds with probability only 2^-Ω(n^2), and report no known classical algorithm matching Ω(2^-n/2) or quantum algorithm achieving Ω(1).Source: §9.6 · p. 93

9.7 Future Directions

  • Proposed directions include obfuscation or lattice-based implementations of the hidden-subspace functions, stronger foundations for knot-based quantum money, and secure real-world copy-protection for general functions.Indistinguishability obfuscation is presented as a stopgap: if secure obfuscation of the subspace characteristic functions is possible and i.o. is secure, i.o. would provide an implementation; the notes also ask whether public-key quantum money is possible relative to a random oracle. Aaronson and Christiano’s forthcoming work shows copy-protected software generically possible relative to a classical oracle.Source: §9.7 · pp. 93–94

Lecture 10 · 10.1 Physical Universality

Lecture 10 shifts from what universal gate sets can implement efficiently to what unitaries a given gate set can implement at all. Physical universality concerns dense generation of all sufficiently large n-qubit special unitaries, and the section presents a decidability bound and related results.

Lecture 10

  • The course’s final lecture asks which unitaries a possibly non-universal gate set can implement at all, rather than which unitaries a universal set can implement in polynomial time.Source: §10.1 · p. 95

10.1 Physical Universality

  • Physical universality means densely generating SU(2^n) for every sufficiently large n, unlike computational universality, which can hold for a set generating only SO(2^n).The definition allows a gate set that generates I ⊗ U without generating U on the smaller register.Source: §10.1 · p. 95
  • The Solovay–Kitaev theorem gives O(exp(n) polylog(1/ε)) gates for ε-approximating any n-qubit unitary when the gate set approximately generates all such unitaries and is closed under inverses.Source: §10.1 · p. 95
  • Solovay–Kitaev’s exact-inverse requirement remains an open problem to remove; Poincaré recurrence yields only an O(1/ε) approximation.Source: §10.1 · p. 96
  • Solovay–Kitaev does not apply to non-universal sets, and irrational rotations in SO(2) show that some such sets lack polylogarithmic-accuracy approximations.Repeated application of one irrational rotation produces too few distinct circuits to achieve O(polylog(1/ε)) accuracy.Source: §10.1 · p. 96
  • Ivanyos’s bound shows physical universality is decidable: a k-qudit gate set that fails to densely generate all unitaries on O(kd^8) qubits never does so [Iva07].The bound on n0 reduces the question to computing the closure of the gate set on finitely many qubits, which is possible for algebraic entries.Source: §10.1 · p. 96
  • If a gate set is universal on n′ ≥ 2 qubits, it is universal on every n ≥ n′ because it generates a universal two-qubit gate tensored with identity.Source: §10.1 · p. 96
  • A Haar-random two-qubit gate is physically universal with probability 1, as shown by Deutsch, Barenco and Ekert and separately by Lloyd [Llo02].Source: §10.1 · p. 96

10.2 Difficulty of Classification

Classifying whether a gate set is universal amounts to characterizing the subgroup it generates, but subgroup knowledge for SU(4) remains incomplete. For approximate generation by inverse-closed two-qubit gates, that subgroup is topologically closed in SU(4).

10.2 Difficulty of Classification

  • An inverse-closed two-qubit gate set, with global phase ignored, generates a topologically closed subgroup S of SU(4) under approximate generation.Approximate generation means constructing a sequence of unitaries that approaches the target in the limit.Source: §10.2 · pp. 96–97
  • SU(2) has a complete subgroup classification via its double cover SO(3), including finite rotation groups and the planar rotation, disk-symmetry, and full groups.The finite groups include those of the platonic solids, cyclic and dihedral groups of every order, and the trivial group.Source: §10.2 · p. 97
  • Most SU(4) subgroups are known, including all exceptional ones, but known infinite families remain poorly characterized.This limits a straightforward group-theoretic approach to classifying two-qubit gate sets.Source: §10.2 · p. 97
  • The infinite subgroups of SU(3) were classified in 1913, but the classification was not completed until Ludl fixed a 1970s error in 2013.The notes contrast this completed classification with the poorly characterized infinite families in SU(4).Source: §10.2 · p. 97

10.3 Classification of Quantum Gates and Hamiltonians

The section classifies quantum gates and Hamiltonians through two-level unitaries and Hamiltonian-generated circuits. It identifies conditions for universality and shows that some commuting Hamiltonians enable classically hard sampling despite not being universal.

10.3.1 Two-Level Unitaries

  • Two-level unitaries generate all of SU(n) for n ≥2, using operations on pairs of basis modes rather than tensor-product gates.This model is motivated by beamsplitters and optical quantum computation.Source: §10.3.1 · p. 97
  • [BA14] classify determinant −1 two-level gates: they generate only trivial unitaries, densely generate SO(n) when real, or densely generate SU(n), for n ≥3.The proof uses brute-force enumeration of representations of subgroups of SU(3).Source: §10.3.1 · p. 98

10.3.2 Hamiltonians

  • [CLMO11] show that a 2-qubit Hamiltonian is universal without ancillas except when eiH does not entangle or shares an eigenvector with SWAP.The proof uses the Lie-algebra closure of pairwise Hamiltonians; the eigenvector argument does not extend to 3 qubits, where universality remains open.Source: §10.3.2 · pp. 98–99
  • Commuting Hamiltonians diagonal in the X basis can sample distributions not exactly sampleable in classical polynomial time unless the polynomial hierarchy collapses [BJS10].The proof uses postselection gadgets to simulate PostBQP.Source: §10.3.2 · p. 99
  • [BMZ16] show that any 2-qubit commuting Hamiltonian is either classically simulable or enables sampling that is classically hard unless the polynomial hierarchy collapses.Their proof uses postselection gadgets and faces difficulty constructing gadget inverses because postselection is non-unitary.Source: §10.3.2 · p. 99

10.4 Classification of Reversible Classical Gates

Aaronson, Grier, and Schaeffer [AGS15] classify reversible Boolean gate sets, a step toward classifying quantum gate sets. The classification depends on the allowed gates and ancilla model, and distinguishes universal, restricted, exceptional, and trivial classes.

10.4.1 Background

  • With dual-rail encoding, {AND, OR} is universal on encoded bits: swapping each bit pair implements NOT, and AND on first bits implements logical AND.The encoding represents 0 as 01 and 1 as 10; SWAP gates are assumed available.Source: §10.4.1 · p. 100

10.4.2 Classification of Reversible Gates

  • The classification assumes free SWAP gates and classical ancillas initialized to 0 or 1 that must return unchanged, preventing entanglement with superposed inputs.Allowing ancillas also avoids a sign obstruction: without them, 3-bit gates on 4 bits generate only even permutations.Source: §10.4.2 · pp. 101–102
  • The Toffoli class contains all bit-string permutations; nonlinear classes above it are encoded universal, while prime-k Ck classes reach Toffoli when any outside gate is added.The nonlinear classes use dual-rail, doubled, or doubled dual-rail encodings; Ck gates preserve Hamming weight modulo k.Source: §10.4.2 · pp. 102–103
  • Other classes include linear gates contained in ⊕L, exceptional orthogonal F4/T6/T4 classes, and trivial classes such as NOT and NOTNOT.Fredkin+NOTNOT preserves parity mod 2, while Fredkin+NOT either preserves or flips it.Source: §10.4.2 · p. 103
  • To rule out additional classes, the proof shows that a gate violating a class’s defining invariant can generate a larger class; some cases use lattices, Diophantine equations, and Chinese remaindering [AGS15].The authors state that verifying the displayed classes, containments, and generators is comparatively easy.Source: §10.4.2 · p. 103
  • In the model described, the lattice collapses to six classes—Toffoli, Fredkin, CNOT, T4, NOT, and the empty set; open questions include trit and quantum-gate classifications.The quantum questions include a possible universality dichotomy and the complexity of states and unitaries for non-universal classes.Source: §10.4.2 · p. 103

Related papers

Loading 1607.05256v1…