Sampling Advantage & Complexity Evidence
Why sampling problems give the strongest evidence for advantage.
Evidence for quantum advantage from factoring rests on the hardness of one specific problem. Sampling offers something different: if a classical computer could mimic certain simple quantum circuits, the polynomial hierarchy would collapse. This lesson develops that argument from exact sampling to the noisy, approximate regime where real experiments live.
What you’ll learn
- Define sampling problems and weak simulation with multiplicative and additive (total-variation) error.
- Prove that multiplicative-error classical sampling of IQP circuits would collapse the polynomial hierarchy, via and Toda's theorem.
- Express IQP amplitudes as normalized gaps of degree-3 polynomials over .
- Reconstruct the Stockmeyer-based argument for approximate sampling and identify the conjectures it needs.
- Assess experiments, cross-entropy benchmarking, and classical spoofing under noise.
Sampling problems and simulation
A sampling problem asks, given , for a sample from a distribution . Quantum computers sample naturally: run the circuit, measure. A strong simulation computes output probabilities; a weak simulation only produces samples. Weak simulation is all that is needed to mimic a quantum device, so hardness results must target it.
Exact hardness: postselection and the hierarchy
Gates , CZ and CCZ multiply by for a cubic polynomial over .
Every amplitude is the normalized gap of a cubic polynomial. Computing such gaps exactly is #P-hard for degree 3, so strong simulation of IQP circuits is #P-hard.
For a single CCZ only has . Test it below.
For , then CCZ, then applied to , what is the probability of outcome ?
Show the answer
0.56
The amplitude is the gap divided by : , so . Each of the other seven outcomes has amplitude and probability .
Postselection supplies the bridge to the polynomial hierarchy. Aaronson (2005) proved . Bremner, Jozsa and Shepherd showed postselected IQP circuits are just as powerful, , using gadgets that realize Hadamards in the middle of a circuit by postselecting on measurement outcomes. Classically, by contrast, .
Multiplicative error on every outcome survives marginalization, and a ratio of two such probabilities is distorted by at most .
PostIQP languages can be decided with conditional error as small as desired (and symmetrically for out ), so with the postselected classical sampler decides them: .
Toda's theorem, then , self-lowness of BPP relative to an NP oracle, and the relativized Sipser–Gács–Lautemann theorem.
Approximate sampling: Stockmeyer, hiding, anticoncentration
Apply it to a hypothetical classical sampler using random bits : the probability is exactly such a . With an NP oracle, you can estimate the sampler's own output probabilities to multiplicative accuracy, even though you could never estimate the quantum ones that way.
Average over a uniformly random outcome .
Markov's inequality: for most the error is a small multiple of the average probability .
Hiding: appending gates maps outcome to without changing the circuit ensemble (for ensembles invariant under this). A random outcome of a fixed circuit looks like outcome of a random circuit.
Combine with Stockmeyer: an additive approximation of for most circuits .
Anticoncentration turns the additive error into a relative one where it matters. For Porter–Thomas statistics, .
Conjecture (average-case hardness). Approximating to that relative error for a fraction of circuits (for BosonSampling: of i.i.d. Gaussian matrices) is #P-hard. If so, , and Toda's theorem collapses PH to its third level. A fast classical approximate sampler plus the conjectures implies a collapse.
Status: anticoncentration is proven for random IQP circuits (Bremner, Montanaro & Shepherd 2016) and for random circuits of logarithmic depth in suitable architectures (Dalzell, Hunter-Jones & Brandão 2022). Computing output probabilities of random circuits exactly is #P-hard on average (Bouland, Fefferman, Nirkhe & Vazirani 2019, via worst-to-average-case reductions with polynomial interpolation; strengthened by Movassagh). But these reductions tolerate only errors exponentially smaller than the the sampling argument needs.
In the approximate-sampling argument, what is the role of anticoncentration?
- It makes the quantum device effectively noise-free
- It guarantees that typical output probabilities are not much smaller than , so an additive error of order is a small relative error for a constant fraction of outcomes
- It allows samples to be verified efficiently
- It is Stockmeyer's theorem in another form
Show the answer
B. It guarantees that typical output probabilities are not much smaller than , so an additive error of order is a small relative error for a constant fraction of outcomes
Without anticoncentration, most probabilities could be far below , and an additive estimate would carry no relative information about them.
Experiments, verification and spoofing
Google's 2019 Sycamore experiment sampled random circuits on 53 superconducting qubits with 20 cycles, collecting a million samples in about 200 seconds and estimating that a classical supercomputer would need about 10,000 years. Photonic experiments followed with Gaussian BosonSampling (Zhong et al. 2020; Madsen et al. 2022). Neither task is known to be useful; they test the complexity argument against real hardware.
The classical response has been strong. Tensor-network contraction methods exploiting the finite depth (for example Pan, Chen & Zhang 2022) produced samples for the 2019 circuits with comparable XEB. Noise is the deeper issue: for any constant noise rate per gate, noisy random-circuit sampling in the anticoncentrated regime has a polynomial-time classical algorithm (Aharonov, Gao, Landau, Liu & Vazirani 2023), whose polynomial degree grows as the noise rate falls. Experiments therefore live in a finite-size window, and the debate continues in Advantage Experiments & Classical Spoofing.
| Proposal | Exact / multiplicative hardness | Additive hardness | Experiments |
|---|---|---|---|
| BosonSampling (Aaronson & Arkhipov 2011) | PH collapse | permanent-of-Gaussians and permanent anticoncentration conjectures | Gaussian BosonSampling with photons, 2020 onward |
| IQP (Bremner, Jozsa & Shepherd 2011) | PH collapse | average-case hardness conjectured; anticoncentration proven | small-scale |
| Random circuit sampling (Boixo et al. 2018) | PH collapse; exact average-case #P-hardness | robustness gap open | Sycamore 2019, larger devices since |
Key takeaways
- Sampling advantage is phrased via weak simulation: multiplicative error collapses PH unconditionally; additive error requires extra conjectures.
- IQP amplitudes are normalized gaps of cubic polynomials over ; plus Toda's theorem gives the collapse if multiplicative-error classical sampling exists.
- Approximate hardness combines Stockmeyer counting, hiding, anticoncentration and an average-case #P-hardness conjecture whose robustness gap is still open.
- Experiments (Sycamore 2019, Gaussian BosonSampling) meet strong classical responses; noise makes the regime of advantage finite, and verification remains a central open problem.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Why would a classical sampler for IQP circuits with multiplicative error collapse the polynomial hierarchy?
- It would factor integers in polynomial time
- It would compute permanents exactly
- Postselecting it would decide every language, so , and Toda's theorem gives
- It would violate the no-cloning theorem
Show the answer
C. Postselecting it would decide every language, so , and Toda's theorem gives
Multiplicative error survives postselection with distortion at most , enough to decide PostIQP languages. Combining with Toda's theorem puts all of PH inside .
What does Stockmeyer's approximate counting contribute to the hardness argument?
- An NP-oracle algorithm that estimates the output probabilities of any efficient classical sampler to multiplicative accuracy
- A polynomial-time algorithm for permanents
- A proof that anticoncentration holds
- A method to verify quantum samples
Show the answer
A. An NP-oracle algorithm that estimates the output probabilities of any efficient classical sampler to multiplicative accuracy
A classical sampler's output probability is the fraction of random strings leading to a given output, a counting quantity Stockmeyer approximates in . That is what lets a hypothetical classical sampler be turned into an estimator of quantum probabilities.
Why can't linear XEB certify sampling experiments far beyond classical reach?
- XEB requires measuring in many different bases
- XEB requires quantum error correction
- XEB is zero for an ideal device
- It needs the ideal probabilities of the observed samples, whose computation takes exponential classical time
Show the answer
D. It needs the ideal probabilities of the observed samples, whose computation takes exponential classical time
The benchmark compares samples against ideal probabilities. Once the circuits are too large to simulate, the probabilities, and hence the score, cannot be computed.
Which statement about noisy random circuit sampling is supported by theory?
- Noise makes sampling harder for classical computers
- At any constant noise rate per gate, there is a polynomial-time classical algorithm in the anticoncentrated regime, though its polynomial degree grows as the noise rate decreases
- Noisy sampling is proven #P-hard to approximate
- Noise does not affect the XEB score
Show the answer
B. At any constant noise rate per gate, there is a polynomial-time classical algorithm in the anticoncentrated regime, though its polynomial degree grows as the noise rate decreases
Aharonov, Gao, Landau, Liu and Vazirani (2023) showed noisy random-circuit sampling is classically easy asymptotically. It does not refute finite-size experiments, but it shows advantage without error correction cannot scale indefinitely.
Further reading
- S. Aaronson & A. Arkhipov, "The computational complexity of linear optics", Theory of Computing 9, 143 (2013); STOC 2011.
- M. J. Bremner, R. Jozsa & D. J. Shepherd, "Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy", Proceedings of the Royal Society A 467, 459 (2011).
- A. Bouland, B. Fefferman, C. Nirkhe & U. Vazirani, "On the complexity and verification of quantum random circuit sampling", Nature Physics 15, 159 (2019).
- F. Arute et al., "Quantum supremacy using a programmable superconducting processor", Nature 574, 505 (2019).
- D. Hangleiter & J. Eisert, "Computational advantage of quantum random sampling", Reviews of Modern Physics 95, 035001 (2023).