PaperlayerView exact revision on arXiv

Source-linked AI summary

Complexity-Theoretic Foundations of Quantum Supremacy Experiments

Scott Aaronson, Lijie Chen

arXiv:1612.05903v2quant-phcs.CC

TL;DR

Quantum supremacy experiments need theoretically grounded ways to establish classical hardness from observed quantum outputs. This paper develops positive and negative results for approximate quantum sampling, showing how hardness assumptions support observable-output tests while clarifying limits on simulation and supremacy claims.

  • Problem

    Verifying sampling conditions is extraordinarily difficult, and sampling hardness does not automatically imply hardness for the corresponding relation problem.

    Source: §1.2 · p. 5

  • Method

    The paper studies general quantum-circuit sampling through positive and negative results under computational assumptions, alongside simulation analyses and oracle constructions.

    Source: §1.3 · p. 6, §1.4 · p. 12

  • Results

    Under QUATH, HOG is hard; the paper also establishes a constant-versus-linear Fourier Sampling separation and derives oracle-based positive and impossibility results.

    Source: §1.3 · pp. 7, 9, §1.4 · p. 12

  • Takeaways & Limitations

    The results provide theoretical guidance for designing and evaluating quantum supremacy experiments, while identifying assumptions required for classical-hardness claims.

    Source: §1 · p. 3, §1.3 · p. 8

    Known simulation algorithms do not refute QUATH, but the hardness argument applies only to general quantum-circuit sampling, not BosonSampling or IQP.

    Source: §1.3 · p. 8

Abstract

from arXiv · show

In the near future, there will likely be special-purpose quantum computers with 40-50 high-quality qubits. This paper lays general theoretical foundations for how to use such devices to demonstrate "quantum supremacy": that is, a clear quantum speedup for some task, motivated by the goal of overturning the Extended Church-Turing Thesis as confidently as possible. First, we study the hardness of sampling the output distribution of a random quantum circuit, along the lines of a recent proposal by the the Quantum AI group at Google. We show that there's a natural hardness assumption, which has nothing to do with sampling, yet implies that no efficient classical algorithm can pass a statistical test that the quantum sampling procedure's outputs do pass. Compared to previous work, the central advantage is that we can now talk directly about the observed outputs, rather than about the distribution being sampled. Second, in an attempt to refute our hardness assumption, we give a new algorithm, for simulating a general quantum circuit with n qubits and m gates in polynomial space and m^O(n) time. We then discuss why this and other known algorithms fail to refute our assumption. Third, resolving an open problem of Aaronson and Arkhipov, we show that any strong quantum supremacy theorem--of the form "if approximate quantum sampling is classically easy, then PH collapses"--must be non-relativizing. Fourth, refuting a conjecture by Aaronson and Ambainis, we show that the Fourier Sampling problem achieves a constant versus linear separation between quantum and randomized query complexities. Fifth, we study quantum supremacy relative to oracles in P/poly. Previous work implies that, if OWFs exist, then quantum supremacy is possible relative to such oracles. We show that some assumption is needed: if SampBPP=SampBQP and NP is in BPP, then quantum supremacy is impossible relative to such oracles.

1 Introduction

The paper develops complexity-theoretic foundations for quantum supremacy as a near-term test of quantum speedup, addressing the challenges of establishing classical hardness and verification. It does so through sampling-based experiments, simulation algorithms, oracle separations, query-complexity gaps, and related proof techniques and assumptions.

1 Introduction

  • Quantum supremacy aims to demonstrate a quantum speedup over the best known or conjectured classical algorithms, while recognizing that finite experiments cannot decisively settle the asymptotic ECT.A convincing experiment should exhibit a large, growing quantum/classical gap, match theoretical predictions, and pass consistency checks such as losing the speedup when quantum behavior is removed.Source: §1 · p. 2

1.1 Supremacy from Sampling

  • Sampling is emphasized because special-purpose quantum devices may achieve classically hard sampling without universal computation, while approximate classical simulation can imply that PH collapses to its third level.This route may also avoid the large practical overhead of full quantum fault tolerance and is motivated by stronger complexity-theoretic evidence than exists for factoring or BPP ≠ BQP.Source: §1.1 · p. 3

1.2 Theoretical Challenges

  • Sampling-based supremacy faces three central challenges: verifying outputs, proving hardness under approximate noisy sampling, and establishing meaningful hardness relative to efficiently computable P/poly oracles.Verification may require classical exponential time, existing approximate-sampling arguments rely on substantial conjectures such as Gaussian permanent hardness, and oracle separations can mislead about the unrelativized world.Source: §1.2 · pp. 4–5

1.3 Our Contributions

  • The paper studies approximate sampling of random quantum circuits, proving that QUATH implies hardness of Heavy Output Generation and giving a polynomial-space, m^O(n)-time simulation algorithm for arbitrary n-qubit, m-gate circuits.HOG asks for outputs whose probabilities exceed the distribution median; it is quantumly easy and classically exponentially verifiable, while QUATH avoids directly assuming sampling hardness and the new simulator also admits depth-based improvements and memory-time tradeoffs.Source: §1.3 · pp. 6–7
  • QUATH-based hardness applies to general quantum circuit sampling because gate count m ≫ n controls classical guessing advantage, while circuit depth must also exclude limited-entanglement simulations.The analysis explains why the argument does not extend to BosonSampling or IQP and how the d^O(n)-time simulation algorithm quantifies hardness gained from increased depth.Source: §1.3 · p. 8
  • An oracle A with SampBPP^A = SampBQP^A and infinite PH shows that strong approximate-sampling supremacy theorems must use non-relativizing techniques [AA13] [BMS15] [BMS16].This resolves the oracle question posed by Aaronson and Arkhipov and contrasts approximate sampling with exact sampling.Source: §1.3 · pp. 8–9
  • Fourier Sampling has a 1-versus-linear quantum–randomized query separation: one quantum query suffices, whereas randomized algorithms require Ω(2^n) queries for sufficiently small ε.This refutes the Aaronson–Ambainis conjecture [AA15] and supports near-maximal separations for approximate sampling.Source: §1.3 · p. 9
  • For P/poly oracles, one-way functions imply quantum–classical separations, including classically exponential-time hardness for approximate Fourier Sampling under subexponential inversion security.Conversely, if SampBPP = SampBQP and NP ⊆ BPP, then SampBPP^A = SampBQP^A for every A ∈ P/poly.Source: §1.3 · p. 10
  • The paper presents a smooth tradeoff: stronger oracle models permit weaker assumptions, while unrelativized supremacy currently requires assumptions separating classical complexity classes.The central contributions include QUATH, P/poly-oracle models, and the sum-products simulation observation.Source: §1.3 · p. 10, §1.4 · p. 11

1.4 Techniques

  • The proof that QUATH implies HOG hardness reduces high-probability-output finding to estimating a transition amplitude slightly better than chance.Random self-reduction supplies the reduction, while random-circuit outputs are shown to be nonuniform with Ω(1) probability by inspecting only the final gate.Source: §1.4 · p. 11
  • The polynomial-space simulation recursively slices an n-qubit depth-d circuit into halves, yielding d^O(n) time, with divide-and-conquer refinements for grid-local circuits and interpolation with Schrödinger simulation.The oracle construction hides the PH-infinite component so PH algorithms can find it but SampBQP algorithms cannot, preserving approximate sampling equivalence through quantum linearity.Source: §1.4 · pp. 11–12
  • The Fourier Sampling lower bound tracks acceptance sensitivity to a Fourier coefficient, while P/poly-oracle separations use pseudorandom permutations, hidden periods, and PAC-learning-style simulation.The converse simulation samples oracle queries, guesses a consistent P/poly function under NP ⊆ BPP, and uses linearity to bound disagreement effects.Source: §1.4 · p. 12

2 Preliminaries

This section establishes notation and foundational definitions for quantum circuits, locality, sampling classes, oracle algorithms, quantum-state distinguishability, and concentration bounds. These preliminaries support the paper’s later analyses of quantum sampling and supremacy.

2 Preliminaries

  • The paper uses [n] for integers 1 through n and logarithms base 2.Source: §2 · p. 12

2.1 Quantum Circuits

  • Quantum circuits use unitary two-qubit gates, with explicit notation for qubits, gate order, circuit depth, layers, and subcircuits.Each gate acts as a two-qubit unitary tensored with identity on all other qubits; oracle gates may be exceptions.Source: §2.1 · p. 13, Definitions for SampBPP and SampBQP · p. 13

Base Graphs and Grids

  • The circuit base graph connects qubits whenever a gate acts on both, and the paper specializes locality to H × W grids.Source: Base Graphs and Grids · p. 13

Definitions for SampBPP and SampBQP

  • SampBPP and SampBQP classify sampling problems whose distributions can be approximated within ε by classical or quantum polynomial-time algorithms, respectively.Oracle versions are defined analogously.Source: Definitions for SampBPP and SampBQP · p. 13

A Canonical Form of SampBQP Oracle Algorithms

  • A SampBQP oracle algorithm can be put into three stages: classically generate a polynomial-size oracle circuit, measure its output, then classically postprocess the outcome.The resulting algorithm is indexed by its oracle tuple O1, O2, . . . , Ok.Source: A Canonical Form of SampBQP Oracle… · p. 14

2.3 Distinguishing Two Pure Quantum States

  • Helstrom’s decoder gives the optimal success probability for distinguishing two pure states, while nearby states induce nearby measurement distributions.The corollary relates the distance between pure states to the total variation distance between distributions produced by a quantum sampling procedure.Source: §2.3 · p. 14

2.4 A Multiplicative Chernoff Bound

  • The section states a multiplicative Chernoff bound for sums of independent variables in [0, 1] and extends it to variables bounded in [0, τ] by rescaling.Source: §2.4 · p. 15

3 The Hardness of Quantum Circuit Sampling

The section defines Heavy Output Generation (HOG) for random grid circuits and shows a simple quantum sampler succeeds with overwhelming probability. Assuming QUATH, no polynomial-time classical algorithm can solve HOG with probability at least 0.99.

3.1 Preliminaries

  • The section defines heavy outputs as strings whose probabilities exceed the median of the circuit’s computational-basis output distribution.The advantage adv(C) is the probability that a computational-basis measurement produces a heavy output, compared with guessing a random string.Source: §3.1 · p. 15, Conditional distribution νgrid · p. 16

3.2 Random quantum circuit on grids

  • Random grid circuits use Haar-random two-qubit gates acting only on adjacent qubits of a √n × √n grid.The construction places n qubits on the grid and selects adjacent pairs according to the stated schedule before applying each gate.Source: §3.2 · p. 15

Lower bound on adv(C)

  • The quantum sampler’s heavy-output advantage is supported by a lemma whose expectation proof uses randomness from only the final gate.The authors conjecture that adv(C) is large with overwhelming probability and note that sampling from the uniform circuit distribution approximates ν_grid with error exp{−Ω(n)} under the conjecture.Source: Lower bound on adv(C) · p. 16, §3.5 · p. 18

3.3 The HOG Problem

  • A quantum algorithm solves HOG with probability 1 − exp{−Ω(k)} by independently measuring the circuit k times.HOG requires at least a 2/3 fraction of outputs to be heavy, and ν_grid conditions circuits on adv(C) ≥ 0.7, enabling the Chernoff-bound guarantee.Source: §3.3 · p. 16

3.4 Classical Hardness Assuming QUATH

  • Assuming QUATH, no polynomial-time classical algorithm can solve HOG with probability at least 0.99.QUATH asserts that no polynomial-time classical algorithm decides whether 0^n is heavy with success probability 1/2 + Ω(2^-n).Source: §3.4 · p. 17

3.5 Proof for Lemma 3.1

  • The lemma’s proof reduces nonuniformity of computational-basis measurement outcomes to heavy-output advantage using independent two-dimensional Haar-random state buckets.Basis states are partitioned into pairs differing on the final qubit, so only amplitudes within each bucket interact.Source: §3.5 · pp. 17–19

4 New Algorithms to Simulate Quantum Circuits

This section develops polynomial-space algorithms for simulating general and grid-local quantum circuits, plus time-space trade-offs. The grid-specific methods exploit balanced cuts to achieve faster simulation under locality assumptions.

4.1 Polynomial-Space Simulation Algorithms for General Quantum Circuits

  • For general circuits, the recursive simulator computes ⟨y|C|x⟩ in O(n · (2d)^(n+1)) time and O(n log d) space.It recursively splits the circuit by depth and sums over intermediate computational-basis states.Source: §4.1 · pp. 19–20

4.2 Faster Polynomial Space Simulation Algorithms for Grid Quantum Circuits

  • For grid-embedded circuits, balanced cuts yield a simulator running in 2^O(d√n) time and O(d · n log n) space.The recursion cuts the grid into subinstances of size between n/3 and 2n/3, decomposes crossing gates, and recurses on fewer qubits.Source: §4.2 · pp. 20–22
  • Combining the grid and general algorithms extends faster grid simulation across the full depth range while retaining O(d · n log n) space.The grid algorithm is used when d is at most c√n, and the general recursive algorithm otherwise.Source: §4.2 · pp. 22–23

4.3 Space-Time Trade-off Schemes

  • A general trade-off scheme computes ⟨y|C|x⟩ using O(2^(n−k) log d) space, with running time adjustable through the parameter k.The method decomposes the Hilbert space into 2^k subspaces and recursively propagates vectors between them.Source: §4.3 · pp. 23–24
  • The trade-off scheme is further improved for grid circuits by incorporating the faster shallow-depth grid simulator.For depths at most c√n, the improved method makes 2^(2(n−k)) calls to the grid algorithm, while deeper circuits use the trade-off recursion.Source: §4.3 · p. 24

5 Strong Quantum Supremacy Theorems Must Be Non-Relativizing

This section constructs an oracle relative to which SampBPP and SampBQP coincide while PH remains infinite, establishing that strong quantum-supremacy theorems must be non-relativizing. It proves the sampling equivalence and PH infinitude using random-bit hiding and constant-depth circuit lower bounds, including an average-case lower bound for the Sipser function.

5 Strong Quantum Supremacy Theorems Must Be Non-Relativizing

  • There exists an oracle O′ = TQBF⊕O such that SampBPPO′ = SampBQPO′ while PHO′ is infinite.This follows from Theorem 5.1, which holds with probability 1 over O drawn from DO, and its corollary.Source: §5 · p. 24, The Distribution DO on Oracles · p. 26

5.1 Intuition

  • The construction must simultaneously make SampBPP equal SampBQP and keep PH infinite, motivating separate treatment of the two requirements.A TQBF oracle equalizes the sampling classes, while prior relativized constructions make PH infinite, but combining them requires hiding random oracle bits.Source: §5.1 · pp. 24–25

A Failed Attempt: Direct Combination

  • Directly combining TQBF with a random oracle fails because SampBQP can Fourier-sample the random bits, whereas SampBPP cannot [AA15].Thus PH remains infinite, but SampBQP ≠ SampBPP in the naive construction.Source: A Failed Attempt: Direct Combination · p. 25

Another Failed Attempt: Hiding a “Secret Random String” in a Secret Location

  • Hiding one random string in a secret location also fails because a SampBQP algorithm can guess the location on some input and obtain the string.The intended design requires PH to find the string while SampBQP cannot, but input-dependent guessing defeats this scheme.Source: Another Failed Attempt: Hiding a… · p. 25

Hiding the “Secret Random String” in a Bunch of OR’s

5.3 SampBPPTQBF,O = SampBQPTQBF,O with Probability 1

  • With probability 1, every SampBQP oracle algorithm has a SampBPP simulator whose output distribution is sufficiently close, yielding SampBPPTQBF,O = SampBQPTQBF,O.The proof replaces oracle gates by simpler gates, bounds the resulting deviations, and hardwires finitely many exceptional input-accuracy pairs.Source: §5.3 · pp. 26–27

5.3 SampBPPTQBF,O = SampBQPTQBF,O with Probability 1.

  • The constructed classical algorithm is a SampBPP algorithm, using only poly(n, 1/ε) oracle queries and computations implementable in polynomial time with a TQBF oracle.Its output distribution matches the quantum sampling procedure with probability at least 1 − exp(−(2^n + ε^−1)).Source: §5.3 · p. 31

5.4 PHTQBF,O is Infinite with Probability 1.

  • The proof of the second part of Theorem 5.1 uses the connection between PH and constant-depth circuit lower bounds to show that PH^TQBF,O is infinite with probability 1.The supplied passage identifies constant-depth circuit lower bounds as the route to the oracle result.Source: §5.4 · p. 31

The Average Case Constant-depth Circuit Lower Bound.

  • Any circuit C′ in the stated shallow-circuit class agrees with the explicit read-once monotone Sipser_d formula on at most (1/2 + n^−Ω(1/d)) · 2^n inputs.This average-case lower bound is based on the construction described in [RST15].Source: The Average Case Constant-depth… · p. 31

Dn as a Distribution on {0, 1}22n.

The section encodes functions sampled from D_n as binary strings, then establishes a distributional constant-depth lower bound for (Sipser_d ◦ OR). This lower bound yields near-zero correlation for shallow circuits and implies PH^O is infinite with probability 1 under O ∼ D_O.

Dn as a Distribution on {0, 1}22n.

  • Each function f:{0,1}^2n→{0,1} is bijectively encoded as a string x_f∈{0,1}^2^2n via lexicographic indexing.Sampling x from D_n means sampling f∼D_n and setting x=x_f; each block B_n,p corresponds to a consecutive 2^n-bit segment.Source: Dn as a Distribution on {0, 1}22n · p. 32

Distributional Constant-Depth Circuit Lower Bound over Dn

  • Lemma 5.5 gives a distributional lower bound: depth-(d−1), size-S circuits have limited agreement with (Sipser_d ◦ OR) under D_n.The function is defined on N^2 inputs with N=2^n, while the displayed passage omits the complete numerical agreement bound.Source: Distributional Constant-Depth Circuit… · p. 32
  • By the standard connection between PH and AC^0, the lower bound implies PH^O is infinite with probability 1 when O∼D_O.This is the stated consequence for the second part of Theorem 5.1.Source: Distributional Constant-Depth Circuit… · p. 32
  • Consequently, every polynomial-size depth-(d−1) circuit has at most 1/2+o(1) correlation with the function under D_n.The function itself has a polynomial-size formula of depth d+1, creating the separation used in the theorem.Source: Distributional Constant-Depth Circuit… · p. 32
  • The proof averages distributions that activate one selected input per block, fixes a favorable selection, and restricts the circuit to contradict the Sipser_d lower bound.This establishes the lemma by reducing agreement on the composed function to agreement with Sipser_d for a depth-(d−1), size-S circuit.Source: Distributional Constant-Depth Circuit… · p. 33

6 Maximal Quantum Supremacy for Black-Box Sampling and Relation Problems

This section establishes near-maximal classical query lower bounds for two Fourier-based black-box problems while exhibiting an exact one-query quantum algorithm for both. Fourier Fishing requires Ω(N/log N) randomized queries, whereas Fourier Sampling requires Ω(N) queries for constant error.

6.2 Fourier Fishing and Fourier Sampling

  • Fourier Fishing asks for a z with |bf(z)| ≥ 1, while Fourier Sampling asks for a distribution within ε of Df.Both problems provide oracle access to f: {0,1}^n → {−1,1}.Source: §6.2 · p. 34

A Simple 1-Query Quantum Algorithm

  • A one-query quantum algorithm exactly solves Fourier Sampling and solves Fourier Fishing with probability adv(f).It applies Hadamard gates, queries f once, applies Hadamard gates again, and measures in the computational basis.Source: A Simple 1-Query Quantum Algorithm · p. 34

6.3 The Ω(N/ log N) Lower Bound for Fourier Fishing

  • Randomized algorithms need Ω(N/log N) queries to solve promise-Fourier Fishing with success probability SuccR + Ω(1).With high probability over a uniformly random function, queried Fourier contributions remain too small for any o(N/log N)-query algorithm to beat SuccR by a constant.Source: §6.3 · pp. 34, 36

6.4 The Optimal Ω(N) Lower Bound for Fourier Sampling

  • For every ε < SuccQ − SuccR ≈ 0.483, Fourier Sampling already requires Ω(N/log N) randomized queries.An approximate sampler with total variance at most ε would yield a Fourier Fishing algorithm with success at least SuccQ − ε.Source: §6.4 · p. 36
  • Fourier Sampling requires Ω(N) queries for some constant error ε, giving the optimal classical lower bound.The proof reduces sampling to a Boolean acceptance problem and shows that o(N) queries cannot satisfy the required acceptance constraints.Source: §6.4 · pp. 36, 41

7 Quantum Supremacy Relative to Efficiently-Computable Oracles

The section establishes quantum–classical separations relative to efficiently computable P/poly oracles using pseudorandom constructions. Assuming classical one-way functions, it obtains BPP^O ≠ BQP^O and hardness of Fourier Fishing and Fourier Sampling under stronger assumptions.

7 Quantum Supremacy Relative to Efficiently-Computable Oracles

  • Assuming classical one-way functions, there exists an oracle O ∈ P/poly such that BPP^O ≠ BQP^O; subexponentially secure one-way functions also make Fourier Fishing and Fourier Sampling hard for P/poly oracles.These assumptions are purely classical and do not reference quantum algorithms.Source: §7 · p. 41, On the Existence of PRFs · p. 42

7.1 Preliminaries

  • The section defines a P/poly oracle as a language in P/poly, with O_n denoting its restriction to n-bit inputs.Source: §7.1 · p. 41

(Quantum) Pseudorandom Functions and Permutations

  • The constructions use pseudorandom functions and permutations, whose security is defined against classical or quantum polynomial-time distinguishers making ordinary or quantum queries.The section also distinguishes exponentially secure and subexponentially secure classical security.Source: (Quantum) Pseudorandom Functions and… · p. 42

On the Existence of PRFs

  • One-way functions imply secure pseudorandom functions and permutations, while subexponentially secure one-way functions imply exponentially secure pseudorandom functions.The latter assumption is identified with the assumption used in the natural proofs barrier.Source: On the Existence of PRFs · p. 42

7.2 A Construction from Zhandry [Zha12]

  • To prove the separations, the paper modifies a construction from Zhandry by first constructing a pseudorandom permutation and function with useful properties.Source: §7.2 · p. 43

Definitions of PRPraw and PRFmod

Assuming one-way functions, the section defines a secure raw pseudorandom permutation PRPraw and derives PRFmod from it using an additional prime parameter. PRFmod retains the raw domain and image but is a function rather than a permutation.

PRPraw

  • PRPraw is a secure pseudorandom permutation with key space Kraw and domain Xraw interpreted as [N], where N = |Xraw|.Its existence is assumed from one-way functions via Lemma 7.4.Source: Definitions of PRPraw and PRFmod · p. 43

PRFmod

  • PRFmod uses key space Kmod = Kraw × A, where A is the set of primes in [√...].The supplied definition specifies that the modular construction augments each raw key with a prime from A.Source: Definitions of PRPraw and PRFmod · p. 43
  • PRFmod has domain and image both equal to Xraw, so Xmod = Xraw and Ymod = Xraw.The construction preserves the raw space on both input and output sides.Source: Definitions of PRPraw and PRFmod · p. 43
  • The construction is called PRFmod rather than PRPmod because it is no longer a pseudorandom permutation.The modular transformation therefore does not preserve the permutation property.Source: Definitions of PRPraw and PRFmod · p. 43

Properties of PRPraw and PRFmod

The section establishes a quantum-classical separation for PRPraw and PRFmod, constructs a P/poly oracle separating BPP from BQP under one-way functions, and proves P/poly-promise hardness for Fourier Fishing and Fourier Sampling under subexponentially secure one-way functions.

Properties of PRPraw and PRFmod

  • PRPraw and PRFmod are classically secure PRFs, yet quantum algorithms recover the hidden a and distinguish them with advantage 1 −ε [Zha12].No classical algorithm distinguishes the two with non-negligible advantage, while quantum access to PRFmod(k,a) recovers a with probability at least 1 −ε.Source: Properties of PRPraw and PRFmod · p. 43

7.3 BPP vs BQP

  • Assuming one-way functions exist, there is an oracle O ∈P/poly such that BPP^O ≠ BQP^O.The oracle encodes independently sampled PRPraw and PRFmod truth tables, enabling a BQP machine to decide the resulting unary language while no BPP machine can do so with non-negligible advantage.Source: §7.3 · pp. 43–44

7.4 Fourier Fishing and Fourier Sampling

  • Under subexponentially strong one-way functions, no polynomial-time classical algorithm solves promise-Ffishing even when the oracle function belongs to P/poly.The proof constructs an exponentially secure PRF and derives the lower bound by showing that any successful solver would distinguish it from a truly random function.Source: §7.4 · pp. 44–45
  • Under the same assumption, no polynomial-time classical algorithm solves Fsampling with the stated error guarantee, even when the oracle function belongs to P/poly.An approximate sampler would yield a Fourier Fishing solver, forcing its error to satisfy ε ≥SuccQ −SuccR.Source: §7.4 · p. 45

8 Complexity Assumptions Are Needed for Quantum Supremacy Relative to Efficiently-Computable Oracles

The section shows that complexity assumptions are necessary for quantum supremacy relative to efficiently computable oracles: if SampBPP = SampBQP and NP ⊆ BPP, then every P/poly oracle fails to separate classical and quantum sampling power.

Theorem 8.1

  • If SampBPP = SampBQP and NP ⊆ BPP, then every oracle O ∈ P/poly satisfies SampBPP^O = SampBQP^O, and consequently BPP^O = BQP^O.Thus, under these assumptions, quantum supremacy is impossible relative to any P/poly oracle.Source: §8 · p. 45

Simulation lemma

  • The proof simulates each quantum oracle algorithm by replacing oracle gates sequentially with PAC-learned approximators while controlling the cumulative state error.The approximator agrees with the oracle function on sampled inputs, and a union bound controls errors across all oracle-gate replacements.Source: §8 · pp. 45–47
  • The resulting classical oracle algorithm is efficient because sampling tasks use SampBPP = SampBQP, while finding each approximator uses NP ⊆ BPP.The final sampling step is also reduced to SampBPP, establishing the required SampBPP oracle simulation.Source: §8 · p. 48

9 Open Problems

The paper closes by identifying open questions about its hardness assumptions, simulation algorithms, sampling models, query-complexity thresholds, and oracle separations. These include testing QUATH and Conjecture 1, extending unrelativized implications, and weakening assumptions needed for BPP–BQP separation.

Hardness assumptions

  • Open problems include determining whether QUATH holds and whether random quantum circuits produce unbalanced distributions with 1 −1/ exp(n) probability.QUATH concerns guessing whether |⟨0|C|0⟩|2 is above or below the median; Conjecture 1 concerns random-circuit output distributions.Source: §9 · p. 48

Relativization and sampling

  • It remains open whether SampBPP = SampBQP collapses PH in the unrelativized world, despite an oracle where SampBPP = SampBQP but PH is infinite.An affirmative answer would follow from Aaronson and Arkhipov’s Permanentof-Gaussians Conjecture [AA13].Source: §9 · p. 48

Classical simulation

  • The optimality of the polynomial-space simulation algorithm is unknown, including whether mO(n) can become 2O(n) · mO(1) and how sampling or small-bias amplitude guessing changes the problem.The open questions concern both output sampling and guessing amplitudes sufficiently to refute QUATH.Source: §9 · p. 48

Other sampling models

  • Analogous observed-output hardness results for BosonSampling and IQP remain open because their amplitude-guessing advantage is at least 1/ exp(n), unlike random circuits’ 1/ exp(m) for m ≫n.The existing argument therefore does not apply directly to BosonSampling or IQP.Source: §9 · p. 48

Fourier Sampling

  • The exact error threshold for an Ω(N) classical query lower bound for Fourier Sampling remains unknown, beyond the proved result at ε = 1 40000.The target threshold separates an o(N)-query algorithm at error ε from an Ω(N)-query requirement for every smaller error.Source: §9 · p. 48

Oracle separations

  • For an oracle O in P/poly separating BPP from BQP under one-way functions, it remains open whether the assumption can be weakened to NP̸ ⊂BPP.The existing separation assumes that one-way functions exist.Source: §9 · p. 48

A Other Results on Oracle Separations in P/poly … A.3 BQP vs SZK

This section develops oracle separations and characterizations relative to P/poly, including unconditional and conditional results involving P, NP, BPP, BQP, and SZK. It also constructs an oracle in P/poly separating BQP from SZK.

A.1 P, BPP, BQP vs NP

  • Unconditionally, some O ∈ P/poly separates P^O from NP^O, while equality P^O = NP^O would imply NP ⊂ P/poly; analogous containments into BPP^O or BQP^O require NP ⊂ P/poly or NP ⊆ BQP/poly.The separation P^O ≠ NP^O follows from the NP-versus-BPP/BQP oracle containments and their corollary.Source: §A.1 · p. 53

A.2 P vs BPP

  • The standard E-circuit lower-bound assumption is sufficient for P^O = BPP^O for every O ∈ P/poly, and its failure yields an oracle with P^O ≠ BPP^O.The sufficient direction uses a strong pseudorandom generator with logarithmic seed length, while the converse is proved by diagonalizing with GapMaj encoded in oracle bits.Source: §A.2 · p. 54

A.3 BQP vs SZK

  • Assuming quantum-secure one-way functions, an oracle O ∈ P/poly separates SZK^O from BQP^O using quantum-secure pseudorandom 2-to-1 functions and the permutation-versus-2-to-1 quantum lower bound.The construction is distinguishable by SZK but not by polynomial-time quantum algorithms; quantum-secure pseudorandom permutations follow from quantum one-way functions via Zhandry [Zha16].Source: A Other Results on Oracle Separations… · p. 53, §A.3 · pp. 55–56
  • Assuming one-way functions, another oracle O ∈ P/poly separates BQP^O from SZK^O by adapting a PRF-based construction that makes the resulting distributions hard for SZK protocols.For every protocol, either it is invalid on many oracles or it fails to distinguish the constructed distributions with sufficiently high probability; otherwise it would break PRFmod.Source: §A.3 · pp. 56–57
  • A quantum algorithm would find a collision in PRFmod with probability Ω(1), contradicting pseudorandom-function security because truly random functions resist non-negligible-probability collision finding.The algorithm samples using a random index, records queried positions, and identifies the differing index with constant probability.Source: §A.3 · pp. 57–58
  • The constructed oracle encodes randomly selected pairs (f_n,z_n) and defines a unary language L whose membership depends on which distribution generated each pair.A quantum algorithm distinguishes the distributions by recovering the hidden index a, placing L in BQP^O.Source: §A.3 · p. 58
  • Every SZK protocol either is invalid with probability 0.05 or cannot distinguish the two distributions with constant probability, so it cannot decide L with bounded error.Since there are countably many protocols, L is outside SZK^O with probability 1, yielding BQP^O ⊄ SZK^O.Source: §A.3 · p. 58
  • The oracle O belongs to P/poly, completing the claimed oracle separation.Source: §A.3 · p. 58

B Missing Proofs in Section 3

This section supplies proofs of Lemmas 3.6 and 3.7, using an ordered list of amplitude deviations for the first and a Gaussian construction of random pure states for the second.

Proof of Lemma 3.6

  • Lemma 3.6 sorts the values |⟨u|w⟩|2 − 2^-n and analyzes the first nonnegative entry through two cases.The proof sets N = 2^n, orders the deviations, and defines Δ = dev(|u⟩).Source: B Missing Proofs in Section 3 · pp. 58–59

Proof of Lemma 3.7

  • Lemma 3.7 represents a random pure state by normalizing four independent N(0,1) variables.The proof then expresses the resulting density using the displayed Gaussian factor and a polar-coordinate substitution.Source: B Missing Proofs in Section 3 · p. 59

C Missing Proofs in Section 6

This section supplies the missing proof of Lemma 6.5 by establishing the concentration inequality through variance bounds and a two-case calculation of E[adv(f)^2].

Proof of Lemma 6.5

  • The proof of Lemma 6.5 establishes the concentration inequality by bounding the variance.The argument proceeds through an explicit calculation of the relevant second moment.Source: C Missing Proofs in Section 6 · p. 60
  • The calculation of E[adv(f)^2] separates the cases z1 = z2 and z1 ≠ z2.For z1 = z2, the proof sets z = z1 = z2; for z1 ≠ z2, it assumes without loss of generality that z1 = 0^N.Source: C Missing Proofs in Section 6 · p. 60
  • In the z1 ≠ z2 case, the proof partitions inputs into A and B according to whether (z2 · x) equals 0 or 1, then combines both cases.The sets are A = {x ∈ {0, 1}^n : (z2 · x) = 0} and B = {x ∈ {0, 1}^n : (z2 · x) = 1}.Source: C Missing Proofs in Section 6 · pp. 60–61

D Missing Proofs in Section 7 … E.3 Distribution of adv(C) : Approximate Normal Distribution

The section completes the proof of Lemma 7.5 and numerically supports Conjecture 1 by showing classical security, quantum distinguishability, and distributions consistent with the conjectured threshold. The simulations find approximately exponential normalized probabilities and approximately normal adv(C), with means close to Cthr.

D Missing Proofs in Section 7

  • PRFmod is classically secure because replacing PRPraw by a random function is indistinguishable except when queries collide modulo a, an event with negligible probability.With polynomially many queries and exponential N, the collision probability is negligible; combining this with PRPraw’s classical PRF security completes the first statement.Source: D Missing Proofs in Section 7 · pp. 61–62
  • The algorithm yields a distinguisher between PRPraw and PRFmod: it accepts when f(1)=f(1+a), with probability 0 for permutations and at least 1−ε for PRFmod.Source: D Missing Proofs in Section 7 · p. 62

E Numerical Simulation For Conjecture 1

  • The numerical study tests Conjecture 1’s claim that random circuits satisfy adv(C)≥Cthr−ε with probability 1−1/exp(n), first examining probability distributions and then adv(C).The simulations also examine the decreasing rate of the standard variance of adv(C).Source: E Numerical Simulation For Conjecture 1 · pp. 62–63

E.1 Numerical Simulation Setting

  • The simulations use n=9 or n=16, choosing m=n^2 as specified in Conjecture 1.These choices ensure that √n is an integer.Source: §E.1 · p. 63

E.2 Distribution of probList(C|0⟩) : Approximate Exponential Distribution

E.3 Distribution of adv(C) : Approximate Normal Distribution

  • adv(C) approximately follows a normal distribution, with mean close to Cthr for both tested circuit ensembles, and the mean is even closer in the µ16,256grid case.The µ9,81grid experiment used 105 i.i.d. samples and the µ16,256grid experiment used another 105 i.i.d. samples.Source: §E.3 · pp. 63–64

E.4 The Empirical Decay of Variance

This section numerically tests whether the variance of adv(C) under μ_n,n^2 decreases as O(1/n), supporting Conjecture 1. Because the grid distribution permits only five simulated square sizes, the study uses a general random two-qubit-gate distribution instead.

Motivation

  • The experiment targets the conjecture that the variance σ of C_thr is O(1/n) as n →+∞, which is informally equivalent to Conjecture 1 if adv(C) approaches a normal distribution with mean C_thr.The section frames empirical variance decay as a test of this conjectured asymptotic behavior.Source: §E.4 · p. 64

Distribution choice

  • Numerical simulations find that adv(C) has nearly the same distribution under μ_grid for n = 3 or 4 and under μ_general.This motivates replacing the grid distribution in the variance experiment because μ_grid requires n to be a perfect square.Source: §E.4 · pp. 64–65

Variance decay

  • The variance of adv(C) decreases faster than 1/x across n = 2,…,16, supporting Conjecture 1.For each n, the variance was estimated from 1000 i.i.d. samples drawn from μ_general.Source: §E.4 · pp. 65–66, Figure 5 · p. 66

Related papers

Loading 1612.05903v2…