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 complexity-theoretic evidence that quantum sampling tasks resist efficient classical simulation. This paper develops hardness arguments and simulation algorithms, proves limits on relativizing and oracle-based results, and establishes a constant-versus-linear query separation for Fourier Sampling. Its conclusions are conditional in important cases, including QUATH and cryptographic assumptions.

  • Problem

    Quantum supremacy requires convincing evidence that approximate quantum sampling is classically hard, despite unresolved verification, noise, and complexity-assumption challenges.

  • Method

    The paper combines a verification test for random quantum-circuit outputs, amplitude-based hardness analysis, recursive circuit simulation, oracle constructions, and Fourier-query lower bounds.

  • Results

    The paper shows that QUATH implies HOG hardness, gives polynomial-space m^O(n)-time circuit simulation, proves strong approximate-sampling theorems must be non-relativizing, and establishes a constant-versus-linear Fourier Sampling separation.

  • Takeaways & Limitations

    Quantum supremacy evidence can target observed outputs and general circuit sampling, while its strongest complexity-theoretic guarantees depend on explicit assumptions and non-relativizing techniques.

  • Takeaways & Limitations

    The hardness argument based on QUATH does not apply to BosonSampling or IQP, and the paper’s falsification analysis leaves QUATH unresolved.

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

Quantum supremacy experiments seek convincing evidence of quantum speedups that challenge the Extended Church-Turing Thesis, but require complexity-theoretic standards for hardness and verification. This paper addresses sampling hardness, simulation algorithms, non-relativizing barriers, query separations, and oracle-based limits.

  • 1 Introduction: Quantum supremacy targets a clear quantum speedup on a task, rather than a full fault-tolerant universal quantum computer, to challenge the Extended Church-Turing Thesis in practice.The ECT asserts that physical processes can be simulated by deterministic or probabilistic Turing machines with at most polynomial overhead.
  • 1 Introduction: Sampling-based experiments face major challenges in verification, approximate-noise robustness, and establishing hardness beyond individual instances.The paper emphasizes that verification may itself require classical exponential time and that approximate sampling must tolerate experimentally realistic errors.
  • 1.3 Our Contributions: The paper studies approximate sampling of general quantum-circuit output distributions, especially random circuits relevant to planned experiments using 40 to 50 superconducting qubits.Its results address all three stated challenges while focusing on assumptions under which classical hardness can be proved or shown necessary.
  • 1.3 Our Contributions: If QUATH is true, HOG is hard, allowing hardness reasoning to target amplitude-estimation algorithms rather than sampling or relation problems.The key shift is from algorithms that sample outputs to algorithms that estimate amplitudes with only a minuscule advantage over random guessing.
  • 1.3 Our Contributions: A recursive sum-of-products algorithm simulates an n-qubit, m-gate circuit in polynomial space and m^O(n) time, with improved bounds involving circuit depth d.The paper also gives a smooth tradeoff with the 2^n-memory Schrödinger algorithm and discusses nearest-neighbor circuits.
  • 1.3 Our Contributions: Known simulation algorithms do not refute QUATH, while the hardness argument applies to general quantum-circuit sampling because m ≫ n can control classical guessing advantage.The analysis also connects circuit depth to both resistance against limited-entanglement simulation and greater protection requirements against decoherence.

2 Preliminaries

The preliminaries define the circuit, grid, and approximate sampling frameworks used throughout the paper, together with basic quantum-state distinguishing and concentration tools.

  • Quantum circuits: Quantum circuits use unitary two-qubit gates, with depth defined by partitioning gates into layers acting on disjoint qubit pairs.The circuit’s base graph records which qubit pairs interact, and locality is formalized through grid embeddings.
  • Quantum circuits: A grid of size H × W has vertices arranged in H rows and W columns, with edges joining Manhattan-distance-one neighbors.
  • Sampling classes: SampBPP contains sampling problems approximable by classical probabilistic polynomial-time algorithms, while SampBQP uses quantum algorithms instead.Oracle versions are defined analogously.
  • Sampling classes: A canonical SampBQP oracle algorithm constructs a quantum circuit, measures it to obtain z, and classically postprocesses z into the final sample.The circuit may use a fixed collection of oracle gates.
  • Quantum-state tools: Helstrom’s decoder gives the optimal success probability for distinguishing two pure states, while nearby states induce nearby measurement distributions.The preliminaries also introduce concentration bounds for sums of independent bounded random variables.

3 The Hardness of Quantum Circuit Sampling

This section proposes Heavy Output Generation for random local quantum circuits and proves its classical hardness from QUATH, while analyzing the circuit’s heavy-output advantage.

  • Random circuits: The circuit ensemble places n qubits on a √n × √n grid and applies Haar-random two-qubit gates to adjacent qubits.The first n gates ensure every qubit is involved; later gates use uniformly random adjacent pairs.
  • Random circuits: The expected heavy-output advantage is large, and the proof uses randomness from only the final gate, even if all earlier gates are adversarially fixed.The analysis relates output non-uniformity to heavy-output advantage.
  • HOG: HOG asks for k output strings from a random circuit such that at least a 2/3 fraction are heavy.A string is heavy when its output probability exceeds the circuit’s median output probability.
  • HOG: A quantum algorithm solves HOG with probability 1 − exp{−Ω(k)} by repeatedly simulating and measuring the circuit.The guarantee follows because the conditioned circuit has adv(C) ≥ 0.7 and a Chernoff bound controls the fraction of heavy outputs.
  • Hardness assumption: QUATH assumes no polynomial-time classical algorithm decides whether 0^n is heavy with success probability 1/2 + Ω(2^−n).Thus, even an exponentially small advantage over trivial guessing is ruled out.
  • Hardness assumption: Assuming QUATH, no polynomial-time classical algorithm solves HOG with probability at least 0.99.The reduction randomizes an input string and transforms heaviness of 0^n into heaviness of that string in a distributed-identical circuit.

4 New Algorithms to Simulate Quantum Circuits

The paper develops polynomial-space simulation algorithms for general and grid-local quantum circuits, including time-space trade-offs that approach exponential-in-qubit rather than exponential-in-gate dependence.

  • General circuits: For arbitrary circuits of depth d, matrix elements can be computed in O(n · (2d)^(n+1)) time and O(n log d) space.A recursive divide-and-sum procedure splits the circuit into two depth-halved subcircuits.
  • Grid-local circuits: For grid-local circuits, matrix elements can be computed in 2^O(d√n) time and O(d · n log n) space.The algorithm cuts the grid into balanced pieces, decomposes crossing gates, and recursively solves the resulting subinstances.
  • Grid-local circuits: The grid-local algorithm improves on a comparable tensor-network method by retaining similar time while using substantially less space.The comparison passage states that the earlier method uses 2^O(d√n) space, whereas this algorithm uses only polynomial space.
  • Combined bounds: The combined algorithm achieves O(2^n) time with polynomial space for sufficiently small depth and combines this with the general method across the full depth range.The resulting theorem applies to circuits whose interaction graph embeds explicitly into a two-dimensional grid.
  • Trade-offs: The paper also gives time-space trade-off schemes, including a bound with O(2^(n−k) log d) space.The parameter k trades additional computation against reduced space usage.

5 Strong Quantum Supremacy Theorems Must Be Non-Relativizing

The oracle construction shows that SampBPP and SampBQP can coincide while the polynomial hierarchy remains infinite, establishing that strong supremacy implications must be non-relativizing.

  • Goal: The section constructs an oracle relative to which SampBPP = SampBQP yet PH is infinite.The construction must simultaneously equalize approximate classical and quantum sampling while preserving an infinite polynomial hierarchy.
  • Failed construction: A naive TQBF-plus-random-oracle construction fails because quantum Fourier Sampling can access the random oracle bits while classical sampling cannot.The failure leaves SampBQP strictly larger than SampBPP in that relativized world.
  • Oracle construction: The successful construction hides random bits as ORs of many inputs, allowing PH to recover them while preventing efficient quantum algorithms from accessing them, even on lucky inputs.This addresses the loophole in which a quantum algorithm guesses the random string’s location.
  • Oracle construction: For oracles drawn from DO, with probability 1, SampBPP^TQBF,O = SampBQP^TQBF,O and PH^TQBF,O is infinite.The distribution independently constructs oracle components so their ORs expose uniform random bits to PH.
  • Classical simulation: The classical simulation uses polynomially many oracle queries and PSPACE computations implemented in polynomial time with a TQBF oracle.Hardwiring finitely many bad input pairs completes the simulation for every SampBQP oracle algorithm with probability 1.

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

This section defines Fourier Fishing and Fourier Sampling, presents a one-query quantum algorithm, and proves randomized-query lower bounds up to Ω(N) for sampling.

  • Problem definitions and quantum algorithm: The one-query Hadamard-query-Hadamard-measurement algorithm solves Fourier Sampling exactly and Fourier Fishing with probability adv(f).The function is accessed as an oracle f:{0,1}^n→{−1,1}.
  • Success baselines: For uniformly random functions, SuccQ is the quantum algorithm’s Fourier Fishing success probability, while SuccR is the success probability of a uniform random output.These constants provide the baseline comparison used in the query lower bounds.
  • Fourier Fishing lower bound: Ω(N/log N) randomized queries are necessary for Fourier Fishing to exceed the uniform-random success probability by a constant.The lower bound applies to promise-Ffishing and rules out o(N/log N)-query algorithms achieving SuccR+Ω(1).
  • Fourier Sampling lower bounds: Ω(N/log N) randomized queries are necessary for Fourier Sampling whenever the allowed error satisfies ε < SuccQ − SuccR ≈ 0.483.The reduction transfers the Fourier Fishing lower bound to sampling through total variation error.
  • Fourier Sampling lower bounds: A constant ε>0 suffices for an optimal Ω(N) randomized-query lower bound for Fourier Sampling.The proof reduces sampling to a Boolean acceptance problem and derives a contradiction for algorithms using fewer than linearly many queries.

7 Quantum Supremacy Relative to Efficiently-Computable Oracles

This section sets up quantum supremacy relative to efficiently computable oracles using classical and quantum security notions for pseudorandom functions and permutations.

  • Oracle framework: The oracle framework studies separations among BPP, BQP, P, NP, and SZK relative to P/poly oracles.The section defines P/poly membership through the corresponding oracle language and its input-length restrictions.
  • Security definitions: A classically secure pseudorandom function is indistinguishable from a truly random function by every polynomial-time classical adversary.Exponential security strengthens this requirement to classical adversaries running in 2^O(n) time, while subexponential security excludes adversaries running in 2^{n^o(1)} time.
  • Security definitions: Quantum security requires indistinguishability even for quantum-query adversaries running in polynomial time.The section gives analogous definitions for pseudorandom functions and permutations.
  • Assumptions: One-way functions imply secure pseudorandom functions and permutations, including exponentially secure PRFs from subexponentially secure one-way functions.These are explicitly classical assumptions and do not refer to quantum algorithms.
  • Construction strategy: The construction strategy builds a pseudorandom permutation and a modified pseudorandom function whose properties support oracle-based quantum-classical separations.The section introduces these objects before proving their relevant properties.

Definitions of PRPraw and PRFmod

The section constructs PRPraw from a secure pseudorandom permutation and defines PRFmod by modifying its input through an additional prime parameter.

  • PRPraw: PRPraw is a secure pseudorandom permutation with key-space Kraw and domain Xraw interpreted as [N].The construction assumes one-way functions to obtain the secure primitive.
  • PRFmod: PRFmod uses key-space Kmod=Kraw×A, where A is the set of primes in a specified interval.Its input is transformed by a modular expression before applying the underlying permutation.
  • PRFmod: PRFmod has domain and image both equal to Xraw, but it is called a pseudorandom function rather than a permutation because it is no longer bijective.The modification preserves the underlying set while changing the mapping structure.

Properties of PRPraw and PRFmod

The constructed primitives are classically indistinguishable yet quantumly distinguishable, enabling P/poly-oracle separations and Fourier-sampling hardness under one-way-function assumptions.

  • Primitive properties: PRPraw and PRFmod are both classically secure PRFs, so no classical algorithm distinguishes them with non-negligible advantage.This classical indistinguishability is the basis for hiding the oracle’s type from BPP machines.
  • Primitive properties: A quantum algorithm recovers the hidden parameter a from PRFmod with probability at least 1−ε and distinguishes PRPraw from PRFmod with advantage 1−ε.These quantum capabilities create the separation unavailable to classical algorithms.
  • BPP versus BQP: Assuming one-way functions exist, there is an oracle O∈P/poly such that BPP^O≠BQP^O.The oracle encodes functions drawn from PRPraw or PRFmod, and a BQP machine decides which family generated each function.
  • Fourier Fishing and Sampling: Assuming subexponentially secure one-way functions, promise-Fourier Fishing is not solvable in polynomial time even when the oracle function belongs to P/poly.The proof uses exponentially secure pseudorandom functions and a contradiction with distinguishability from truly random functions.
  • Fourier Fishing and Sampling: Under the same assumption, no polynomial-time classical algorithm solves Fourier Sampling with the stated error guarantee for P/poly oracle functions.The reduction from sampling to Fourier Fishing yields the threshold ε≥SuccQ−SuccR.

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

This section shows that complexity assumptions are necessary for quantum supremacy relative to P/poly oracles, while proving a converse under SampBPP = SampBQP and NP ⊆ BPP.

  • Oracle limitations: Theorem 8.1 states that if SampBPP = SampBQP and NP ⊆ BPP, then SampBPP^O = SampBQP^O for every O ∈ P/poly.Consequently, BPP^O = BQP^O.
  • Simulation strategy: The proof transforms any SampBQP oracle algorithm into a SampBPP oracle algorithm by replacing oracle gates with learned approximating functions.The construction uses sampling from an induced distribution and finds each approximator in NP, converted to BPP under the assumptions.
  • Simulation strategy: The oracle-gate replacement procedure relies on representing the P/poly oracle as polynomial-size circuits and recursively approximating its gates.The oracle restriction belongs to SIZE(q(n)), enabling the circuit-based replacement framework.
  • Simulation strategy: The simulation uses polynomial space and controls accumulated replacement error across all oracle gates before classically sampling the final circuit.The final circuit is measured and its classical postprocessing is simulated after the oracle gates have been replaced.

9 Open Problems

The paper closes with open questions about its hardness assumptions, simulation algorithm, sampling models, and oracle-separation results.

  • Random-circuit sampling: The paper leaves open whether QUATH and the conjectured output-distribution imbalance for random quantum circuits are true.These questions concern the threshold assumption and whether random circuits sample an unbalanced distribution with probability 1 − 1/exp(n).
  • Classical simulation: The paper asks whether its m^O(n)-time, polynomial-space simulation algorithm is optimal or can be improved while preserving polynomial space.It also asks whether sampling alone or small-bias amplitude guessing permits lower complexity.
  • Random-circuit sampling: The authors ask whether conditional hardness results about observed outputs extend to BosonSampling or IQP models.The Section 3 argument does not directly apply because those models provide only 1/exp(n) guessing advantage rather than 1/exp(m).
  • Fourier Sampling: The authors proved an Ω(N) classical query lower bound for Fourier Sampling only at error ε = 1/40000 and ask for the exact threshold.They seek the boundary between o(N)-query algorithms and algorithms requiring Ω(N) queries.
  • Oracle separations: The paper asks whether the one-way-function assumption for P/poly oracle separation can be weakened to NP ⊄ BPP.It also asks whether SampBPP = SampBQP would collapse PH in the unrelativized world.

A Other Results on Oracle Separations in P/poly

This appendix characterizes several complexity-class separations relative to P/poly oracles, under assumptions ranging from unconditional constructions to classical and quantum one-way functions.

  • P, BPP, BQP, and NP: There is an oracle O ∈ P/poly such that P^O ≠ NP^O, while P^O = NP^O would require NP ⊂ P/poly.The corresponding containment obstruction also applies to BPP and BQP simulations of NP.
  • P versus BPP: The standard derandomization assumption implies P^O = BPP^O for every O ∈ P/poly, and its converse is also established.If no sufficiently hard function in E exists, some P/poly oracle separates P from BPP.
  • BQP versus SZK: Assuming one-way functions, P/poly oracles can separate BQP from SZK and SZK from BQP.The BQP-versus-SZK constructions use pseudorandom-function and pseudorandom-permutation ideas, with quantum-secure assumptions needed for one direction.
  • Overview: Figure 1 summarizes which class containments hold for every P/poly oracle and which separations occur for some such oracle.Its notation distinguishes universal containments from existential oracle separations.

A.2 P vs BPP

This section proves a necessary-and-sufficient hardness condition for separating P from BPP with P/poly oracles, using derandomization assumptions and diagonalization.

  • Derandomization direction: A function f ∈ E with circuit complexity at least 2^εn for sufficiently large n implies P^O = BPP^O for every O ∈ P/poly.The proof sketch invokes a strong pseudorandom generator that fools fixed polynomial-size circuits.
  • Converse direction: Conversely, if every f ∈ E has infinitely many n with circuit complexity below 2^εn, some O ∈ P/poly satisfies P^O ≠ BPP^O.Thus the hardness condition is not only sufficient but necessary for universal P/poly-oracle derandomization.
  • Converse direction: The separating oracle encodes GapMaj instances into selected oracle lengths and uses diagonalization against each polynomial-time oracle machine.At each stage, unqueried oracle bits are set adversarially while preserving efficient computability of the oracle slices.
  • Converse direction: GapMaj outputs 1 for Hamming weight at least 2N/3 and 0 for Hamming weight at most N/3, leaving the intermediate range undefined.The construction exploits this promise gap when defining the oracle language.

B Missing Proofs in Section 3

The proof develops a random-state construction and analyzes sorted deviations from uniform probabilities through a threshold index and two cases.

  • For N = 2^n, it sorts the deviations |⟨u|w⟩|^2 − 2^-n over all computational basis states and denotes them a_1 through a_N.
  • The argument selects the first nonnegative deviation index t and splits the proof according to whether t is at least N/2 + 1.
  • The two cases are combined to obtain the lemma, completing the proof.
  • The proof generates a random pure state from four independent standard normal variables, then normalizes the resulting coordinates.

C Missing Proofs in Section 6

The proof of Lemma 6.5 bounds the variance of adv(f) by separating equal and unequal query-point cases and analyzing the resulting Fourier-type partition.

  • The concentration proof proceeds by bounding the variance of adv(f).
  • The calculation of E[adv(f)^2] separates the cases z_1 = z_2 and z_1 ≠ z_2.
  • For unequal points, the proof assumes z_1 = 0^N without loss of generality and partitions inputs into sets A and B according to (z_2 · x).
  • Using the definitions of b_f(z_1) and b_f(z_2), the unequal-point contribution is expressed through the difference b_fA − b_fB.
  • The two cases are combined to finish the lemma’s variance calculation.

D Missing Proofs in Section 7

The proof constructs a modular-periodic function from a pseudorandom permutation, establishes classical security, and uses quantum period finding to distinguish the resulting oracle from a raw permutation.

  • The modular function is written f mod a(x) := f((x − 1) mod a + 1), creating repeated oracle inputs at period a.
  • A classical polynomial-time algorithm cannot distinguish the modular construction from a random function unless it queries two points congruent modulo the hidden period.
  • Because the underlying permutation has a unique period, Boneh–Lipton quantum period finding recovers that period with negligible failure probability.
  • The distinguisher recovers a period and accepts when f(1) = f(1 + a), yielding advantage 1 − ε against the modular oracle while accepting with probability zero for a permutation.
  • The numerical evidence examines exponential behavior of normalized output probabilities, normal behavior of adv(C), and concentration near C_thr.

E.4 The Empirical Decay of Variance

The section tests the variance component of Conjecture 1 numerically and finds faster-than-inverse decay, while also comparing grid and general circuit distributions.

  • The Empirical Decay of Variance: The conjecture is recast as whether the variance σ of C_thr is O(1/n) as n → +∞ when adv(C) approaches a normal distribution centered near C_thr.
  • General Circuit Distribution: The grid distribution requires n to be a perfect square, leaving only five quickly simulable sizes: n ∈ {1, 4, 9, 16, 25}.
  • General Circuit Distribution: The general distribution instead applies Haar-random two-qubit gates to uniformly chosen qubit pairs, allowing any positive integer n.
  • General Circuit Distribution: For n = 3 and n = 4, simulations show nearly identical adv(C) distributions under µ_general and µ_grid, supporting use of the general distribution.
  • The Empirical Decay of Variance: For each n from 2 through 16, the study draws 1000 independent circuits from µ_n,n^2 and computes the variance of their adv(C) values.
  • The Empirical Decay of Variance: The observed variance decreases faster than 1/x, supporting Conjecture 1.
Loading 1612.05903v2…