Quantum Supremacy and the Complexity of Random Circuit Sampling

Quantum supremacy

• RCS is motivated by quantum supremacy, which requires a near-term physically realizable task that classical computers cannot solve efficiently, even if the task is not useful.The broader context includes experimental progress toward systems of around 50 high-quality qubits.Source: §1 · p. 1

Paper contribution

• The paper shows that experimentally motivated RCS has strong complexity-theoretic evidence of classical intractability.This result connects the experimentally feasible and theoretically strong categories of supremacy proposals.Source: §1 · p. 2

RCS motivation

• RCS samples from the output distribution of random efficient quantum circuits and was designed for near-term superconducting-qubit experiments.The Google/UCSB proposal targeted a 2D array of 49 qubits.Source: §1 · p. 2

Paper contribution

• Computing a typical random-circuit output probability is as hard as computing a worst-case probability, establishing the needed worst-to-average-case reduction.The reduction is combined with prior anti-concentration results to place RCS on par with the strongest theoretical proposals.Source: §1 · p. 2

Verification gap

• The paper cautions that cross-entropy can score well for distributions far from the ideal distribution in total variation distance.This leaves the connection between practical verification tests and complexity-theoretic evidence open for RCS and other supremacy proposals.Source: §1 · p. 2

Hardness framework

• Worst-to-average-case hardness is needed because supremacy requires computational difficulty across typical outputs rather than concentration on one exponentially unlikely outcome.The paper contrasts this requirement with BosonSampling’s permanent-based average-case argument and the hiding technique for fixed outputs.Source: §2 · p. 3

Reduction method

• The reduction exploits Feynman path integrals, which express fixed-output probabilities as low-degree multivariate polynomials in circuit-gate parameters.Unlike permanents, quantum circuits lack the linear structure needed for a direct adaptation of the standard interpolation proof.Source: §2 · pp. 3–4
• Truncated-Taylor circuit probabilities become low-degree polynomials in θ, allowing interpolation from random instances to recover a worst-case probability.The truncation remains exponentially close to the corresponding random-circuit probabilities.Source: §2 · p. 4

Average-case hardness

• It is #P-hard to compute |⟨0|C′|0⟩|2 with probability 8/9 when C′ is drawn from a family of Haar-measure discretizations.This theorem supplies the central average-case hardness result for random quantum circuits.Source: §2 · p. 4

Limitations

• The truncated-circuit reduction is necessary but not sufficient for supremacy because it proves hardness for probabilities exponentially close to, rather than exactly identical with, the target probabilities.The paper notes an analogous unresolved robustness issue for average-case permanents.Source: §2 · p. 4

Robustness

• Anti-concentration makes most output probabilities reasonably large, so approximation errors may be smaller relative to the signal and potentially more tolerable to noise.For RCS, prior work supplies anti-concentration, making it the first proposal in the paper’s comparison with both properties simultaneously.Source: §2 · p. 4

Verification challenge

• Ideal output probabilities require exponential classical time, while experiments provide too few samples to observe or estimate all 2^50 outcomes.Verification therefore needs a statistical measure compatible with limited sampling and classical computational constraints.Source: §3 · p. 5

Cross-entropy

• Cross-entropy estimates agreement with the ideal distribution by averaging log ideal probabilities over experimental samples.Its construction is intended to make estimation possible from a small number of observed outputs.Source: §3 · p. 5

Cross-entropy limitations

• A nearly perfect cross-entropy score can coexist with a distribution arbitrarily far from the ideal distribution in total variation distance.Thus cross-entropy does not certify the closeness required by the complexity-theoretic arguments without strong device assumptions.Source: §3 · p. 5

Distributional signatures

• Porter–Thomas output shape is not sufficient as a standalone signature because a classical process resembling noisy quantum dynamics can approximate it.The paper therefore emphasizes relationships between specific output strings and their probabilities rather than distributional shape alone.Source: §3 · p. 5

Open problem

• Directly linking verification tests such as cross-entropy or HOG to standard complexity assumptions remains open for all discussed supremacy proposals.HOG can be connected to QAUTH, but connecting that conjecture to non-collapse of the polynomial hierarchy remains challenging.Source: §3 · p. 5

RCS definition

• RCS samples y with probability |⟨y|C|0^n⟩|^2 from a random circuit over a fixed architecture, within total variation distance ε.The circuit architecture specifies the graph and gates, while the Haar distribution independently randomizes each gate.Source: A Worst-to-average-case reduction · pp. 9–10

Motivation

• The reduction targets average-case output probabilities because worst-case quantum-circuit probabilities are #P-hard, whereas classical-circuit probabilities are easier under polynomial-hierarchy assumptions.This spread of hardness across outputs is needed for robustness to experimental noise.Source: A Worst-to-average-case reduction · p. 10

A Worst-to-average-case reduction

• Theorem 1 establishes the analogue of BosonSampling’s necessary worst-to-average-case result for Random Circuit Sampling.This supports the conjecture that approximating most RCS output probabilities is #P-hard.Source: A Worst-to-average-case reduction · p. 10

Anti-concentration

• Prior results establish anti-concentration for RCS, a property that can help make average-case hardness robust to noise.The paper notes that anti-concentration had not been proven for BosonSampling or FourierSampling at this point.Source: A Worst-to-average-case reduction · p. 10

Polynomial structure

• The Feynman path integral expresses each fixed-output probability as a low-degree polynomial in circuit gate entries, with degree twice the number of gates.This polynomial structure is the basis for interpolation.Source: §A.1 · p. 11

Obstruction

• Naïve linear interpolation fails because sums of unitary matrices need not be unitary, so A + tB may not define valid quantum circuits.The permanent’s linear interpolation argument therefore cannot be directly transferred to circuits.Source: §A.1 · p. 12

Perturbed Haar construction

• Multiplying gates by perturbed Haar matrices produces circuits close to random, but e^-iθh_j is not polynomial in θ and cannot directly support interpolation.The perturbed distribution is useful for randomness but insufficient by itself for the reduction.Source: §A.1 · p. 12

Truncated construction

• Replacing each exponential with a truncated Taylor series yields probabilities that remain close to the perturbed proposal while becoming low-degree polynomials in θ.Polynomial interpolation can then recover the worst-case value from probabilities at several θ values.Source: §A.1 · pp. 12–13

Theorem 1

• Computing 8/9 of p0(C′) values under the truncated perturbed Haar distributions D′ is #P-hard when worst-case p0(C) computation has additive precision 2^-poly(n) hardness.This is Theorem 1’s formal worst-to-average-case conclusion.Source: §A.1 · p. 13

Necessity

• Because Conjecture 6 implies Theorem 1, Theorem 1 is a necessary condition for the proposed RCS hardness conjecture.An exact algorithm over D′ would yield an approximate algorithm over Haar-random circuits.Source: §A.2 · pp. 13–14

Transfer theorem

• Theorem 12 transfers an efficient average-case probability algorithm from D′ to Haar-random circuits with ε′ = ε + 1/exp(n) and δ′ = δ + 1/poly(n).Thus an algorithm for the truncated distribution would imply one for the Haar distribution.Source: §A.2 · p. 13

Output closeness

• Fact 14 states that paired circuits from the joint construction have exponentially close output probabilities when the truncation degree K is sufficiently large.Taylor-series approximation preserves the relevant probabilities closely enough for the transfer.Source: §A.2 · p. 14

Distribution closeness

• Fact 15 states that the perturbed circuit distribution is O(1/poly(n)) close in total variation distance to the Haar distribution.The proof obtains this by choosing θ sufficiently small relative to the number of gates.Source: §A.2 · p. 14

Reduction chain

• Lemmas 16 and 17 successively convert an algorithm for D′ into one for D and then into one for Haar-random circuits.The second step uses total-variation closeness and discards an independent unused circuit input.Source: §A.2 · pp. 15–16

Proof strategy

• Theorem 1’s proof uses polynomial interpolation to equate average-case and worst-case hardness for truncated perturbed circuits.The construction exploits the inherent polynomial structure of output probabilities.Source: §A.3 · p. 16

Polynomial construction

• For fixed Haar gates, q(θ) = p0(C′(θ)) is a degree-2mK polynomial because each truncated gate entry has degree K.The Feynman path integral converts the circuit amplitude into a polynomial, and squaring gives degree 2mK.Source: §A.3 · p. 16

Average-case guarantee

• A machine correct on 8/9 of sampled circuits is correct for at least 2/3 of θ values for at least 2/3 of Haar-gate choices.Such gate choices are called good and permit robust interpolation.Source: §A.3 · p. 16

Error correction

• Berlekamp–Welch reconstructs the degree-2mK polynomial from noisy samples {(θ_l, O(θ_l))} and returns the estimate q(1).The method tolerates erroneous evaluations provided enough sampled points are correct.Source: §A.3 · p. 16, Figure 2 · p. 17

Worst-case recovery

• At θ = 1, q(1) is within 2^-poly(n) of the worst-case probability p0(C) when K = poly(n).The approximation error is bounded by 2^{O(nm)}/((K)!)^m and becomes inverse-exponentially small for polynomial K.Source: §A.3 · p. 17

A.4 Sampling implies average-case approximations in the polynomial hierarchy

• An approximate sampler is a classical probabilistic polynomial-time algorithm that receives a circuit and accuracy parameter and samples from a distribution close in total variation distance to the circuit’s output distribution.The paper defines average-case approximation as producing a good estimate for most random inputs, while allowing failures on the remainder.Source: §A.4 · p. 17
• The resulting sampler-to-estimator implication would collapse PH to its third level under Conjecture 6.Theorem 22 gives a BPP^NP algorithm for a #P-hard average-case problem, while BPP^NP ⊆ Σ3 and Toda’s theorem gives the stated collapse.Source: §A.4 · p. 18
• Stockmeyer’s theorem enables multiplicative estimation of sampler output probabilities using an NP oracle by counting random strings mapped to each outcome.Applying this to an approximate quantum sampler yields estimates for most output probabilities of any circuit.Source: §A.4 · p. 18
• An approximate sampler would imply an average-case approximate solution for p0(C) on random circuits in BPP^NP.Theorem 22 transfers approximate sampling to estimating a fixed output probability over Haar-random circuits from a fixed architecture.Source: §A.4 · pp. 17–18
• A hiding argument converts estimates for random output probabilities into estimates of p0(C) for random circuits when the architecture is closed under output-bit Pauli X gates.For Cy, the output relabeling satisfies ⟨y|C|0⟩ = ⟨0|Cy|0⟩, and the architecture distribution remains unchanged.Source: §A.4 · p. 19

A.5 Connecting with worst-case hardness and anti-concentration

• Architectures containing the constant-depth nearest-neighbor brickwork circuit have #P-hard worst-case output probabilities.The brickwork architecture is universal under post-selection, and Lemma 24 applies whenever it is contained in the target architecture.Source: §A.5 · p. 20
• The architecture requirement for worst-case hardness is mild: it only needs to contain a simple constant-depth nearest-neighbor circuit on a 2D grid.Universal resource-state constructions establish the required post-selected computational power.Source: §A.5 · pp. 19–20
• Anti-concentration means that most output probabilities are reasonably large, preventing additive approximation error from overwhelming the signal.The paper defines anti-concentration through constants κ and γ for a fixed architecture.Source: §A.5 · p. 20
• Anti-concentration converts additive average-case estimates into nontrivial multiplicative estimates for most circuits.Lemma 26 gives multiplicative error ǫ · κ for a 1 − δ − γ fraction of circuits when additive error is bounded by ±ǫ/2^n for a 1 − δ fraction.Source: §A.5 · p. 20
• Random circuits of depth O(n) on a 2D grid have both average-case #P-hardness and anti-concentration.Approximate two-design behavior implies anti-concentration, while the architecture condition supplies the worst-case hardness needed by the reduction.Source: §A.5 · pp. 19–21

B.1 Technical preliminaries

• The analysis uses N = 2^n for the domain size and interprets high probability as 1 − o(1).The section also specifies that probability distributions are over strings x ∈ {0,1}^n unless otherwise stated.Source: §B.1 · p. 21
• The Porter–Thomas distribution models the output probabilities of Haar-random quantum circuits and supports analysis of their coarse-grained statistics.The joint distribution of several fixed outcomes is approximated by independent Porter–Thomas copies.Source: §B.1 · pp. 21–22
• The notation pU(x) denotes the probability of observing x after applying Haar-random U to the all-zero input state.P(x) denotes the distribution of this probability over the choice of Haar-random unitary.Source: §B.1 · p. 21
• For any fixed outcome x, Haar-random circuit probabilities are approximated by the Porter–Thomas distribution up to O(1/N^c).Fact 29 states that the distribution P(x) differs from Porter–Thomas by at most O(1/N^c) for any c > 0.Source: §B.1 · p. 21
• Although the exact distribution P is not close in total variation to Porter–Thomas, normalized Porter–Thomas reproduces relevant coarse-grained features with high probability.The paper uses this replacement heuristically and explains that the renormalization factor is close to one by concentration of measure.Source: §B.1 · p. 22

B.2 The cross-entropy supremacy proposal

• Cross-entropy estimates the distance between an experimental device’s output distribution and the ideal random-circuit distribution using sampled outcomes and their ideal probabilities.Only the ideal probabilities of the observed strings need to be computed, requiring k ≪ N samples.Source: §B.2 · p. 22
• The empirical cross-entropy estimate converges to CE(pdev, pU), allowing inference of cross-entropy difference from the ideal reference value log N + γ.Here pdev is the device distribution tuned to implement U, and γ is Euler’s constant.Source: §B.2 · p. 22
• For an ideal device and Haar-random U, the expected cross-entropy difference is near one, but experimental noise makes exact attainment unrealistic.The Google/UCSB group expected CED > 0.1 on a 40–50 qubit device, while CED close to 1 is needed for proper operation.Source: §B.2 · p. 22

• Theorem 30 gives distributions with total variation distance at least 0.99 from ideal while their cross-entropy difference is exponentially close to 1.This holds with probability 1 − o(1) over Haar-random unitaries.Source: §B.3 · p. 23
• The rescaled distribution assigns zero probability to most outputs and concentrates probability on the remainder, preserving nearly ideal cross-entropy despite low entropy.Its construction reduces entropy while maintaining a similar cross-entropy value.Source: §B.3 · p. 23
• For k = 500, the rescaled distribution has total variation distance greater than 0.99 with high probability, while its cross-entropy difference remains exponentially close to the ideal score.The expected distance is 0.99(1 − 1/k).Source: §B.3 · p. 23
• Thus, cross-entropy difference does not behave like a metric and cannot by itself establish the total-variation closeness required by the hardness arguments.The question is whether high cross-entropy certifies closeness for general distributions; the section answers negatively.Source: §B.3 · p. 23
• Under the assumption that device noise mixes the ideal distribution with the uniform distribution, cross-entropy close to ideal implies total-variation closeness.However, empirical support from a 9-qubit device does not establish that this assumption is verifiable for a 49-qubit device.Source: §B.3 · p. 24

Verification consequence

• Because a classical physical process can approximately reproduce the Porter–Thomas shape, the exponential probability profile is not itself a signature of quantumness.The argument applies to a process resembling a noisy or decoherent quantum system.Source: §B.4 · pp. 24–25

Classical construction

• A classical system of n+m bits with random environment settings and a random permutation produces observed system outputs by effectively throwing 2^m balls into 2^n bins.When m is sufficiently large, the observed values are approximately independent because each observed bin contains 2^m possible environment outputs.Source: §B.4 · p. 25
• For m=n, the classical process has an approximately Poisson distribution with mean 1 across bins, including under sufficiently large-wise-independent permutations.This follows because the number of balls per bin is approximately Poisson in the large-n limit.Source: §B.4 · p. 25
• The resulting Poisson statistics form a natural classical imposter of the Porter–Thomas distribution and become finer as the discretization parameter m increases.The analogy extends to randomness assumptions: Porter–Thomas arises from sufficiently large unitary k-designs, while Poisson statistics arise from sufficiently large k-wise-independent permutation families.Source: §B.4 · p. 25

Verification consequence

• RCS cannot be verified purely from outcome-distribution shape; verification must incorporate the correspondence between observed strings and their ideal probabilities, as cross-entropy difference does.Computing cross-entropy difference requires evaluating ideal output probabilities for experimentally observed samples.Source: §B.4 · pp. 24–25

Heavy Output Generation

• HOG requires at least two-thirds of experimental samples to have above-median ideal probability, with the median threshold ln(2)/N inherited from Porter–Thomas.The proposal asks the device to output mostly “heavy” strings.Source: §B.5 · p. 26
• The ideal device satisfies HOG, and concentration of measure means relatively few samples can provide a good estimate of HOG.This leaves some tolerance for experimental error.Source: §B.5 · p. 26

Relationship between measures

• Cross-entropy and HOG both estimate an expectation of a function of ideal output probabilities over samples from the experimental distribution.Cross-entropy uses f(x)=log(1/x), whereas HOG uses an indicator function for heavy outputs.Source: §B.5 · p. 26

Verification limitation

• Neither high cross-entropy nor high HOG implies closeness to the ideal distribution in total variation distance.Both measures project a high-dimensional output distribution onto one dimension, so they act only as proxies for supremacy.Source: §B.5 · p. 26
• Cross-entropy and HOG are distinct measures because they capture different one-dimensional projections of the experimental output distribution.Their shared structure does not make them equivalent verification tests.Source: §B.5 · p. 26