Advantage Experiments & Classical Spoofing
Random circuit sampling, boson sampling and the classical response.
A sampling experiment is a bet that no classical computer can reproduce, within a given budget, the statistics a noisy quantum device produces. The theory says exact sampling would collapse the polynomial hierarchy; the practice says the device's output is 99.8% noise. This lesson makes both halves precise, then follows the classical counterattack.
What you’ll learn
- State the hardness results for exact, multiplicative and additive sampling, and prove the PH collapse via postselection.
- Analyze linear XEB: its value under Porter–Thomas and depolarizing noise, its statistical cost, and its weaknesses.
- Explain why classical simulation cost scales with target fidelity, and sketch the Pauli-path algorithm for noisy circuits.
- Describe boson and Gaussian boson sampling precisely, including the role of photon loss.
Sampling tasks and the hardness argument
Aaronson (2005): quantum polynomial time with postselection on exponentially unlikely outcomes equals PP.
With postselection gadgets, postselected acceptance probabilities are ratios of output probabilities of circuits in the family. A sampler accurate to a factor preserves which side of these ratios fall on, well enough to decide the same languages with classical postselection.
Classical postselection is weak: () is in (Han, Hemaspaandra & Thierauf 1997), which lies in by the relativized Sipser–Gács–Lautemann theorem.
Toda's theorem puts PH inside , and is closed under polynomial-time Turing reductions. So all of PH sits in its own third level.
Linear XEB, precisely
The benchmark is with . Under the Porter–Thomas model ( approximately across ), an ideal device scores , uniform guessing scores 0, and a globally depolarized device scores exactly . The statistical cost follows directly.
The estimator from samples, each requiring a classical computation of .
At low fidelity the samples are nearly uniform, and an exponential with mean 1 has variance 1.
Independent samples average down the noise.
How many samples (in millions) are needed to detect at five standard deviations?
Show the answer
6.25 million
gives . Each sample's must be computed classically, so even checking the experiment needs the very simulation capability the experiment claims to beat; hence the extrapolation from verifiable patch and elided circuits.
The classical response, quantified
| Method | What drives the cost | Impact on the 2019 claim |
|---|---|---|
| State vector (Schrödinger) | memory for amplitudes: tens of petabytes at | IBM's proposal of about 2.5 days, using Summit's disk storage |
| Schrödinger–Feynman hybrid | exponential in the number of gates across a cut of the qubits | basis of the 10,000-year estimate |
| Tensor-network contraction | contraction width, a treewidth-like property of the circuit graph; slicing trades memory for time | hours on GPU clusters by 2022 |
| Pauli paths (noisy circuits) | number of low-weight Pauli paths that survive the noise | polynomial time at constant noise rate, asymptotically |
Path-based and sliced tensor-network methods write the output as a sum of many contributions (paths, or slices of a cut). For random circuits these are nearly orthogonal and of similar weight.
Compute only a fraction of the contributions.
The normalized state has fidelity . Matching an experiment with is about 500 times cheaper than exact simulation (Markov, Fatima, Isakov & Boixo 2018 made this point for Schrödinger–Feynman simulation). Pan, Chen and Zhang (2022) obtained a million uncorrelated samples for the Sycamore circuits with estimated fidelity about 0.0037 in about 15 hours on 512 GPUs.
Boson sampling and Gaussian boson sampling
In boson sampling, photons enter the first modes of a Haar-random -mode interferometer , with so that collisions (two photons in one output mode) are rare. A collision-free outcome has probability . For a Gaussian with i.i.d. standard complex entries, , and small submatrices of Haar unitaries look like .
In Gaussian boson sampling, single-mode squeezed states with squeezing parameters enter the interferometer. For pure states and photon-number-resolving detectors, a collision-free pattern has probability
Since , hafnians generalize permanents. Threshold (click) detectors lead to a related function, the Torontonian.
Noninteracting fermions in an interferometer have outcome probabilities given by squared determinants. Why does fermion sampling offer no quantum advantage?
- Fermions cannot be made indistinguishable
- Determinants are computable in polynomial time, and noninteracting-fermion circuits are classically simulable
- Fermions always bunch into the same output mode
- The Pauli principle forbids interference between fermions
Show the answer
B. Determinants are computable in polynomial time, and noninteracting-fermion circuits are classically simulable
Determinants yield to Gaussian elimination in time, and fermionic linear optics (matchgates) is efficiently simulable classically. The minus signs that distinguish the determinant from the permanent are exactly what make it easy.
Key takeaways
- Exact or multiplicative-error classical sampling of postselection-universal circuit families would collapse PH to its third level (PostBQP = PP, PostBPP ⊆ BPP^NP, Toda).
- Additive-error hardness, the experimentally relevant kind, rests on anticoncentration plus unproven average-case #P-hardness conjectures.
- Linear XEB equals fidelity only under depolarizing-like noise; its estimator has standard error about , needs classical computation of every , and can be spoofed in some regimes.
- Classical costs scale roughly linearly with target fidelity, tensor networks cut Sycamore's estimate to hours, and Pauli-path truncation makes constant-noise random circuit sampling classically polynomial.
- Boson sampling uses permanents and GBS hafnians; photon loss is the main route to classical simulation.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Which conclusion follows if a classical polynomial-time algorithm could sample exactly from the output distributions of IQP circuits?
- Factoring is classically easy
- The polynomial hierarchy collapses to its third level
Show the answer
D. The polynomial hierarchy collapses to its third level
IQP with postselection equals PostBQP = PP. A classical exact sampler would give , and Toda's theorem then collapses PH to (Bremner, Jozsa & Shepherd 2011).
Why does an ideal, noiseless device score on a Porter–Thomas distribution?
- Because every bitstring has probability exactly
- Because , so
- Because the device outputs only the most likely bitstring
- Because XEB is normalized by the number of samples
Show the answer
B. Because , so
Sampling from itself weights each bitstring by , so the average of is for an exponential distribution with mean .
Why did the experiment's low fidelity (about 0.2%) help classical spoofers?
- For path-based and sliced tensor-network methods, simulating at fidelity costs roughly times the exact cost
- Low fidelity means the circuit was shallower than reported
- Low-fidelity samples are nearly uniform, which scores well on XEB
- It made the ideal probabilities easier to compute exactly
Show the answer
A. For path-based and sliced tensor-network methods, simulating at fidelity costs roughly times the exact cost
Keeping a fraction of nearly orthogonal contributions yields a state of fidelity about , so matching needs only about 0.2% of the exact work.
What does the Aharonov–Gao–Landau–Liu–Vazirani (2023) algorithm imply?
- The 2019 Sycamore samples were spoofed by this algorithm
- Noiseless random circuit sampling is classically easy
- At a constant noise rate per gate, uncorrected random circuit sampling cannot provide a scalable exponential advantage
- Error correction is unnecessary for quantum advantage
Show the answer
C. At a constant noise rate per gate, uncorrected random circuit sampling cannot provide a scalable exponential advantage
Noise damps high-weight Pauli paths, so truncation gives a polynomial-time classical sampler for noisy circuits. Scalable advantage needs error correction, or noise rates that fall as systems grow.
Further reading
- F. Arute et al., "Quantum supremacy using a programmable superconducting processor", Nature 574, 505 (2019).
- S. Aaronson & A. Arkhipov, "The computational complexity of linear optics", Theory of Computing 9, 143 (2013); STOC 2011.
- S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis & H. Neven, "Characterizing quantum supremacy in near-term devices", Nature Physics 14, 595 (2018).
- F. Pan, K. Chen & P. Zhang, "Solving the sampling problem of the Sycamore quantum circuits", Phys. Rev. Lett. (2022).
- D. Aharonov, X. Gao, Z. Landau, Y. Liu & U. Vazirani, "A polynomial-time classical algorithm for noisy random circuit sampling", Proc. STOC (2023).