Simple Algorithm
Quantum Computing · Rydberg State · 30 min

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 PostBQP=PP\mathsf{PostBQP} = \mathsf{PP} and Toda's theorem.
  • Express IQP amplitudes as normalized gaps of degree-3 polynomials over F2\mathbb{F}_2.
  • 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 xx, for a sample from a distribution Dx\mathcal{D}_x. 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

DerivationIQP amplitudes are polynomial gaps
  1. D=∑x(−1)f(x)∣x⟩ ⁣⟨x∣,f(x)=∑iaixi+∑i<jbijxixj+∑i<j<kcijkxixjxk(mod2)D = \sum_x(-1)^{f(x)}\dyad{x},\qquad f(x) = \sum_ia_ix_i + \sum_{i<j}b_{ij}x_ix_j + \sum_{i<j<k}c_{ijk}x_ix_jx_k\pmod2

    Gates ZZ, CZ and CCZ multiply ∣x⟩\ket{x} by (−1)f(x)(-1)^{f(x)} for a cubic polynomial ff over F2\mathbb{F}_2.

  2. ⟨y∣H⊗nDH⊗n∣0n⟩=12n∑x(−1)f(x)+y⋅x=#{x:f(x)+y⋅x=0}−#{x:f(x)+y⋅x=1}2n\bra{y}H^{\otimes n}DH^{\otimes n}\ket{0^n} = \frac{1}{2^n}\sum_x(-1)^{f(x)+y\cdot x} = \frac{\#\{x: f(x)+y\cdot x = 0\}-\#\{x: f(x)+y\cdot x = 1\}}{2^n}

    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.

  3. f=x0x1x2:gap=8−2⋅1=6,⟨000∣H⊗3 CCZ H⊗3∣000⟩=68=34f = x_0x_1x_2:\qquad\text{gap} = 8-2\cdot1 = 6,\qquad\bra{000}H^{\otimes3}\,\mathrm{CCZ}\,H^{\otimes3}\ket{000} = \tfrac68 = \tfrac34

    For a single CCZ only x=111x = 111 has f=1f = 1. Test it below.

Predict before you look

For H⊗3H^{\otimes3}, then CCZ, then H⊗3H^{\otimes3} applied to ∣000⟩\ket{000}, what is the probability of outcome 000000?

Show the answer

0.56

The amplitude is the gap divided by 232^3: 6/8=3/46/8 = 3/4, so P(000)=9/16≈0.56P(000) = 9/16\approx0.56. Each of the other seven outcomes has amplitude ±14\pm\tfrac14 and probability 116\tfrac1{16}.

Postselection supplies the bridge to the polynomial hierarchy. Aaronson (2005) proved PostBQP=PP\mathsf{PostBQP} = \mathsf{PP}. Bremner, Jozsa and Shepherd showed postselected IQP circuits are just as powerful, PostIQP=PP\mathsf{PostIQP} = \mathsf{PP}, using gadgets that realize Hadamards in the middle of a circuit by postselecting on measurement outcomes. Classically, by contrast, PostBPP⊆BPPNP\mathsf{PostBPP}\subseteq\mathsf{BPP}^{\mathsf{NP}}.

DerivationProof
  1. Pr⁡q[out∣post]=q(out,post)q(post)∈[1c2, c2]⋅Pr⁡p[out∣post]\Pr_q[\text{out}\mid\text{post}] = \frac{q(\text{out},\text{post})}{q(\text{post})}\in\Big[\frac{1}{c^2},\ c^2\Big]\cdot\Pr_p[\text{out}\mid\text{post}]

    Multiplicative error on every outcome survives marginalization, and a ratio of two such probabilities is distorted by at most c2c^2.

  2. Pr⁡p[out=1∣post]≥1−δ ⇒ Pr⁡q[out=1∣post]≥1−δc2>12when c2<2(1−δ)\Pr_p[\text{out} = 1\mid\text{post}]\ge1-\delta\ \Rightarrow\ \Pr_q[\text{out}=1\mid\text{post}]\ge\frac{1-\delta}{c^2}>\frac12\quad\text{when } c^2<2(1-\delta)

    PostIQP languages can be decided with conditional error δ\delta as small as desired (and symmetrically for out =0= 0), so with c<2c<\sqrt2 the postselected classical sampler decides them: PP⊆PostBPP\mathsf{PP}\subseteq\mathsf{PostBPP}.

  3. PH⊆PPP=PPostBPP⊆PBPPNP⊆BPPNP⊆Σ3p\mathsf{PH}\subseteq\mathsf{P}^{\mathsf{PP}} = \mathsf{P}^{\mathsf{PostBPP}}\subseteq\mathsf{P}^{\mathsf{BPP}^{\mathsf{NP}}}\subseteq\mathsf{BPP}^{\mathsf{NP}}\subseteq\Sigma_3^{\mathsf p}

    Toda's theorem, then PostBPP⊆BPPNP\mathsf{PostBPP}\subseteq\mathsf{BPP}^{\mathsf{NP}}, self-lowness of BPP relative to an NP oracle, and the relativized Sipser–Gács–Lautemann theorem. ■\blacksquare

Approximate sampling: Stockmeyer, hiding, anticoncentration

Apply it to a hypothetical classical sampler S(U,r)S(U, r) using random bits rr: the probability qU(z)=Pr⁡r[S(U,r)=z]q_U(z) = \Pr_r[S(U,r) = z] is exactly such a pp. 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.

DerivationFrom a TV-close sampler to estimating p_U(0^n) (Aaronson & Arkhipov)
  1. ∑z∣qU(z)−pU(z)∣≤2ε ⟹ Ez∣qU(z)−pU(z)∣≤2ε2n\sum_z\abs{q_U(z)-p_U(z)}\le2\varepsilon\ \Longrightarrow\ \mathbb{E}_z\abs{q_U(z)-p_U(z)}\le\frac{2\varepsilon}{2^n}

    Average over a uniformly random outcome zz.

  2. Pr⁡z[∣qU(z)−pU(z)∣≥2εδ 2n]≤δ\Pr_z\Big[\abs{q_U(z)-p_U(z)}\ge\frac{2\varepsilon}{\delta\,2^n}\Big]\le\delta

    Markov's inequality: for most zz the error is a small multiple of the average probability 2−n2^{-n}.

  3. pU(z)=pUz(0n),Uz:=Xz Up_U(z) = p_{U_z}(0^n),\qquad U_z := X^{z}\,U

    Hiding: appending XX gates maps outcome zz to 0n0^n without changing the circuit ensemble (for ensembles invariant under this). A random outcome of a fixed circuit looks like outcome 0n0^n of a random circuit.

  4. Pr⁡U[∣q~−pU(0n)∣≤ε′2n]≥1−δ,q~∈FBPPNP,ε′=O(ε/δ)\Pr_U\Big[\abs{\tilde q-p_U(0^n)}\le\frac{\varepsilon'}{2^n}\Big]\ge1-\delta,\qquad\tilde q\in\mathsf{FBPP}^{\mathsf{NP}},\quad\varepsilon' = \order{\varepsilon/\delta}

    Combine with Stockmeyer: an additive approximation of pU(0n)p_U(0^n) for most circuits UU.

  5. Pr⁡U[pU(0n)≥α2n]≥β⟹relative error O(ε′/α) on a constant fraction of instances\Pr_U\Big[p_U(0^n)\ge\frac{\alpha}{2^n}\Big]\ge\beta\quad\Longrightarrow\quad\text{relative error }\order{\varepsilon'/\alpha}\text{ on a constant fraction of instances}

    Anticoncentration turns the additive error into a relative one where it matters. For Porter–Thomas statistics, Pr⁡[2np≥1]=e−1\Pr[2^np\ge1] = e^{-1}.

  6. Conjecture (average-case hardness). Approximating pU(0n)p_U(0^n) to that relative error for a 1−δ1-\delta fraction of circuits (for BosonSampling: ∣Per⁡(X)∣2\abs{\operatorname{Per}(X)}^2 of i.i.d. Gaussian matrices) is #P-hard. If so, P#P⊆BPPNP\mathsf{P}^{\#\mathsf{P}}\subseteq\mathsf{BPP}^{\mathsf{NP}}, 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 2−n/poly⁡2^{-n}/\poly the sampling argument needs.

Check your understanding

In the approximate-sampling argument, what is the role of anticoncentration?

  1. It makes the quantum device effectively noise-free
  2. It guarantees that typical output probabilities are not much smaller than 2−n2^{-n}, so an additive error of order ε/2n\varepsilon/2^n is a small relative error for a constant fraction of outcomes
  3. It allows samples to be verified efficiently
  4. It is Stockmeyer's theorem in another form
Show the answer

B. It guarantees that typical output probabilities are not much smaller than 2−n2^{-n}, so an additive error of order ε/2n\varepsilon/2^n is a small relative error for a constant fraction of outcomes

Without anticoncentration, most probabilities could be far below 2−n2^{-n}, and an additive ε/2n\varepsilon/2^n 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.

ProposalExact / multiplicative hardnessAdditive hardnessExperiments
BosonSampling (Aaronson & Arkhipov 2011)PH collapsepermanent-of-Gaussians and permanent anticoncentration conjecturesGaussian BosonSampling with photons, 2020 onward
IQP (Bremner, Jozsa & Shepherd 2011)PH collapseaverage-case hardness conjectured; anticoncentration provensmall-scale
Random circuit sampling (Boixo et al. 2018)PH collapse; exact average-case #P-hardnessrobustness gap openSycamore 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 F2\mathbb{F}_2; PostIQP=PP\mathsf{PostIQP} = \mathsf{PP} 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.

Question 1

Why would a classical sampler for IQP circuits with multiplicative error c<2c<\sqrt2 collapse the polynomial hierarchy?

  1. It would factor integers in polynomial time
  2. It would compute permanents exactly
  3. Postselecting it would decide every PostIQP=PP\mathsf{PostIQP} = \mathsf{PP} language, so PP⊆PostBPP⊆BPPNP\mathsf{PP}\subseteq\mathsf{PostBPP}\subseteq\mathsf{BPP}^{\mathsf{NP}}, and Toda's theorem gives PH⊆BPPNP\mathsf{PH}\subseteq\mathsf{BPP}^{\mathsf{NP}}
  4. It would violate the no-cloning theorem
Show the answer

C. Postselecting it would decide every PostIQP=PP\mathsf{PostIQP} = \mathsf{PP} language, so PP⊆PostBPP⊆BPPNP\mathsf{PP}\subseteq\mathsf{PostBPP}\subseteq\mathsf{BPP}^{\mathsf{NP}}, and Toda's theorem gives PH⊆BPPNP\mathsf{PH}\subseteq\mathsf{BPP}^{\mathsf{NP}}

Multiplicative error survives postselection with distortion at most c2<2c^2<2, enough to decide PostIQP languages. Combining with Toda's theorem puts all of PH inside BPPNP⊆Σ3p\mathsf{BPP}^{\mathsf{NP}}\subseteq\Sigma_3^{\mathsf p}.

Question 2

What does Stockmeyer's approximate counting contribute to the hardness argument?

  1. An NP-oracle algorithm that estimates the output probabilities of any efficient classical sampler to multiplicative accuracy
  2. A polynomial-time algorithm for permanents
  3. A proof that anticoncentration holds
  4. 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 FBPPNP\mathsf{FBPP}^{\mathsf{NP}}. That is what lets a hypothetical classical sampler be turned into an estimator of quantum probabilities.

Question 3

Why can't linear XEB certify sampling experiments far beyond classical reach?

  1. XEB requires measuring in many different bases
  2. XEB requires quantum error correction
  3. XEB is zero for an ideal device
  4. It needs the ideal probabilities pU(z)p_U(z) of the observed samples, whose computation takes exponential classical time
Show the answer

D. It needs the ideal probabilities pU(z)p_U(z) 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.

Question 4

Which statement about noisy random circuit sampling is supported by theory?

  1. Noise makes sampling harder for classical computers
  2. 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
  3. Noisy sampling is proven #P-hard to approximate
  4. 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).