Hardness Arguments for Sampling Problems

A sampling problem does not ask a computer to decide a yes/no question or compute a function — it asks it to draw a sample $x$ from a target distribution $\mathcal{D}$ . Quantum devices do this natively: measuring the $n$ -qubit state $|\psi\rangle=U|0\rangle^{\otimes n}$ in the computational basis returns the string $x$ with probability $p(x)=|\langle x|U|0\rangle^{\otimes n}|^2$ . The defining question of quantum supremacy theory is whether an efficient classical algorithm could sample from this very same distribution. Hardness arguments for sampling answer "no — not unless something believed false happens to complexity theory," and the something is the collapse of the polynomial hierarchy. The argument is a reduction with a characteristic three-legged shape. First, the individual output probabilities $p(x)$ encode a #P-hard quantity: a sum over $2^n$ Feynman paths that, for the right circuit family, becomes an Ising partition function or the permanent of a matrix, $\mathrm{Per}(A)$ , which Valiant proved #P-complete. Second, Stockmeyer's approximate-counting theorem says a classical sampler — merely a black box that emits $x$ with the right frequency — lets a machine with an NP oracle estimate any $p(x)$ multiplicatively. Third, chaining these places a #P-hard number in $\mathrm{FBPP}^{\mathrm{NP}}\subseteq\Sigma_3^p$ , the third level of the hierarchy, and Toda's theorem $\mathrm{PH}\subseteq\mathrm{P}^{\#\mathrm{P}}$ then folds all of PH into that level. That collapse is regarded as nearly as implausible as $\mathrm{P}=\mathrm{NP}$ . This is the backbone of the Sycamore and Jiuzhang experiments. It separates cleanly what is proven — worst-case exact-sampling hardness — from what remains conjectured — average-case approximate hardness, which additionally needs anticoncentration and an average-case #P-hardness conjecture.

Key takeaways

Quantum circuit families — BosonSampling, IQP, random circuit sampling — produce output distributions $p(x)=|\langle x|U|0\rangle|^2$ that no efficient classical algorithm can sample from, even approximately, unless the polynomial hierarchy collapses.
The engine is a two-part reduction: the probabilities are #P-hard to compute (via a permanent or an Ising partition function), and a hypothetical classical sampler would let a $\mathrm{BPP}^{\mathrm{NP}}$ machine estimate those probabilities by Stockmeyer counting.
Stockmeyer turns sampling into approximate counting in $\mathrm{FBPP}^{\mathrm{NP}}\subseteq\Sigma_3^p$ ; a #P-hard number landing there forces PH into its third level through Toda's theorem $\mathrm{PH}\subseteq\mathrm{P}^{\#\mathrm{P}}$ .
Anticoncentration is the indispensable extra ingredient for the realistic error model: it guarantees probabilities are typically $\Omega(1/N)$ so that the additive slack a total-variation sampler is allowed stays a small multiplicative error, keeping Stockmeyer's estimate valid.
Only worst-case exact hardness is unconditional (modulo non-collapse of PH); approximate-sampling hardness rests on two open conjectures — average-case #P-hardness and anticoncentration.
Key idea: a classical sampler for $p(x)=|\langle x|U|0\rangle|^2$ , fed to Stockmeyer's counter inside $\mathrm{FBPP}^{\mathrm{NP}}$ , would place a #P-hard probability in the third level of the polynomial hierarchy, and Toda's theorem then collapses PH — so no such sampler exists unless PH collapses. Anticoncentration upgrades this from exact to approximate sampling.

The core insight

A classical sampler for $p(x)=|\langle x|U|0\rangle|^2$ , fed to Stockmeyer's counter inside $\mathrm{FBPP}^{\mathrm{NP}}$ , would place a #P-hard probability in the third level of the polynomial hierarchy; Toda's theorem then collapses PH — so no such sampler exists unless PH collapses. Anticoncentration upgrades this from exact to approximate sampling.

Where this lives today

The framework stopped being abstract in 2019, when Google's Sycamore processor sampled from a pseudo-random depth-20 circuit on 53 superconducting qubits, drawing a few million bitstrings and reporting a cross-entropy fidelity near $0.2\%$ — small, but statistically decisive, and claimed to require thousands of years on the best classical supercomputer of the day. Anticoncentration there is supplied by Porter–Thomas statistics, and the hardness of estimating individual probabilities is underwritten by the Bouland–Fefferman–Nirkhe–Vazirani average-case-via-polynomial-interpolation argument. The photonic route runs in parallel: the Jiuzhang experiments implement Gaussian BosonSampling — the permanent replaced by the hafnian — detecting up to 76 photons across 100 modes. Both claims live in active tension with classical algorithms: improved tensor-network contractions and noise-exploiting spoofers have repeatedly narrowed or contested specific fidelity margins, precisely because constant-rate noise erodes anticoncentration and drags the output toward uniform. That contest is the frontier: the theory pins down exactly which regime — enough depth for Porter–Thomas, few enough errors to keep fidelity above the spoofing threshold — a device must reach, and the two open conjectures (average-case #P-hardness, anticoncentration for realistic ensembles) mark exactly what still separates a demonstration from a theorem.

The physical picture

Read a single output probability $p(x)$ as a tiny window onto a gigantic sum over $2^n$ Feynman amplitudes. Evaluating that sum exactly is not a search but a count — the #P regime, where you must tally accepting paths rather than merely find one. A classical sampler looks strictly weaker than an exact calculator: it just emits strings with the right frequencies. Stockmeyer's theorem exposes a hidden bridge between them. From nothing but oracle access to a sampler, a machine equipped with an NP oracle can estimate any individual output probability to within a multiplicative factor. Applied to a probability that is #P-hard, that estimation power is too much — it would let a low, fixed level of the complexity hierarchy compute what should demand the very top. The polynomial hierarchy PH is the tower $\mathrm{P}\subseteq\mathrm{NP}\subseteq\Sigma_2^p\subseteq\Sigma_3^p\subseteq\cdots$ of problems defined by alternating quantifiers, and it is widely believed to be strictly infinite. A sampling-hardness proof is a proof by contradiction against that belief: assume the efficient classical sampler exists, turn the Stockmeyer crank, and out drops a #P-hard quantity sitting in $\Sigma_3^p$ . Toda's theorem then squeezes the entire infinite tower down into that one level. The first figure traces this collapse pipeline end to end.

Figure

The collapse pipeline. Assume a classical sampler with q(x) = p(x) and combine it with the fact that p(x) is #P-hard. Stockmeyer approximate counting places a multiplicative estimate in FBPP with an NP oracle, contained in Σ₃ᵖ. A #P-hard number in Σ₃ᵖ gives P^#P ⊆ Σ₃ᵖ, and Toda's theorem PH ⊆ P^#P then collapses the whole hierarchy to its third level — believed false.

Anticoncentration is about the shape of the histogram of the $2^n$ probabilities, and it decides whether the pipeline survives realistic noise. If $p$ were a delta spike — all its mass on one lucky outcome — a classical sampler could ignore every small probability and still land within total-variation distance $\epsilon$ , revealing nothing about them. Anticoncentration forbids that: it certifies the distribution is spread, with a constant fraction of outcomes carrying probability $\Omega(1/N)$ . Then the additive slack $\sim\epsilon/N$ that a total-variation sampler is permitted is small compared with the typical probability, so the sampler's implied estimate of $p(x)$ stays multiplicatively accurate — precisely what the reduction consumes. The second figure shows where that constant fraction comes from for random circuits: the Porter–Thomas law.

Figure

Porter–Thomas statistics for a Haar-random circuit. The rescaled probability Np follows the exponential density Pr(Np = t) = e^{−t} with mean t = 1. The shaded tail t ≥ 1 has area e^{−1} = 0.368, so 36.8 percent of all outcomes exceed the mean probability 1/N — a constant fraction independent of n. The collision probability Σ p(x)² ≈ 2/N is twice the uniform value, certifying anticoncentration.

The whole edifice is a reduction, not a lower bound proved from first principles. We never show quantum sampling is hard in isolation; we show that if it were classically easy, the complexity universe would rearrange itself implausibly. The strength of the conclusion is exactly the strength of the belief "PH does not collapse" — decisive for exact sampling, and contingent on two further conjectures for the approximate case that real hardware actually inhabits.

The core equations

The object whose hardness is at stake is the Born-rule output distribution of a quantum circuit. Everything downstream is a statement about computing, estimating, or bounding this one function.

p(x)=\big|\langle x|U|0\rangle^{\otimes n}\big|^2 \qquad (1)

where: $U$ — the $n$ -qubit unitary the circuit implements; $x\in\{0,1\}^n$ — a computational-basis measurement outcome; $p(x)$ — the probability of observing $x$ , the quantity whose classical hardness we study; $N=2^n$ — Hilbert-space dimension, the number of possible outcomes. Reading it: a quantum device samples $x\sim p$ in one shot; the question is whether a classical machine can imitate that draw. Each amplitude in (1) is itself a sum over exponentially many computational paths through the circuit's gates — the discrete Feynman sum. For the right gate sets its real and imaginary parts become a counting problem.

\langle x|U|0\rangle=\sum_{\text{paths }\gamma}A(\gamma)=\sum_{s}e^{i\pi f(s)} \qquad (2)

where: $\gamma$ — a path, i.e. a choice of intermediate basis strings between the circuit's layers; $A(\gamma)$ — its complex amplitude, a product of gate matrix elements; $f(s)$ — a low-degree polynomial (quadratic/cubic) over $\mathbb{F}_2$ for IQP/Ising circuits. Reading it: the real part $\mathrm{Re}\sum_s(-1)^{f(s)}=\#\{f=0\}-\#\{f=1\}$ is a gap of satisfying assignments — a GapP quantity, #P-hard to evaluate for general $f$ . For BosonSampling the same probability wears a different, iconic face: the permanent of a matrix, whose all-plus signs are exactly what make it hard.

\mathrm{Per}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^{n}A_{i,\sigma(i)},\qquad p(\text{output})\propto|\mathrm{Per}(A)|^2 \qquad (3)

where: $A$ — an $n\times n$ submatrix of the interferometer's transfer unitary; $S_n$ — the symmetric group; $\sigma$ — a permutation. Reading it: for $n$ indistinguishable photons through a passive linear-optical network, boson symmetrization replaces the determinant (fermions, alternating signs, easy) with the permanent (bosons, all-plus, #P-complete by Valiant 1979). Now the reduction's hinge. A classical sampler is a randomized circuit $C(r)$ that maps random bits $r$ to an output; its distribution is a count of preimages, and Stockmeyer's theorem estimates that count multiplicatively with only an NP oracle.

q(x)=\frac{|\{r:C(r)=x\}|}{2^{|r|}},\qquad \frac{q(x)}{1+\delta}\le\hat q(x)\le(1+\delta)\,q(x),\quad \hat q\in\mathrm{FBPP}^{\mathrm{NP}} \qquad (4)

where: $q(x)$ — the sampler's output probability; $\hat q(x)$ — a multiplicative estimate; $\delta$ — relative error, driven to $1/\mathrm{poly}$ by repetition; $\mathrm{FBPP}^{\mathrm{NP}}\subseteq\mathrm{FP}^{\Sigma_2^p}$ sits at the second-to-third level. Reading it: sampling access alone buys you approximate counting, which is the whole reason a mere sampler is as dangerous as a calculator. Counting is the ceiling of the entire quantifier hierarchy — this is Toda's theorem, the tool that converts "a hard number in a low level" into "the whole hierarchy in that level."

\mathrm{PH}\subseteq\mathrm{P}^{\#\mathrm{P}} \qquad (5)

where: $\mathrm{PH}=\bigcup_k\Sigma_k^p$ — the polynomial hierarchy; $\mathrm{P}^{\#\mathrm{P}}$ — polynomial time with a #P (counting) oracle. Reading it: every language decided by any fixed number of alternating quantifiers reduces to a single #P query, so if that #P power is trapped inside $\Sigma_3^p$ , then $\mathrm{PH}\subseteq\Sigma_3^p$ and the tower collapses. The realistic error model needs the histogram to be spread. Anticoncentration states this two equivalent ways — a tail bound and a second-moment (collision) bound.

\Pr_x\!\left[p(x)\ge\frac{c}{N}\right]\ge\gamma,\qquad \sum_x p(x)^2\le\frac{K}{N} \qquad (6)

where: $c,\gamma,K$ — constants independent of $n$ ; for Haar-random / Porter–Thomas statistics $K=2$ and $\gamma=e^{-c}$ . Reading it: the collision probability $\sum_x p(x)^2$ equals $1/N$ for the perfectly flat distribution; a value $\le K/N$ certifies the distribution is no more than a constant factor peakier than uniform. Finally, the bridge that makes total-variation closeness usable — it converts a global $\epsilon$ into a typical per-outcome error, which anticoncentration then renders multiplicative.

\tfrac{1}{2}\sum_x|q(x)-p(x)|\le\epsilon\;\Rightarrow\;\mathbb{E}_{x\sim U}\,|q(x)-p(x)|\le\frac{2\epsilon}{N} \qquad (7)

where: $q$ — the classical sampler's distribution; $\epsilon$ — the total-variation-distance budget; $U$ — the uniform draw over $x$ . Reading it: averaged over the $N$ outcomes, the sampler's per-outcome error is only $2\epsilon/N$ , so on the anticoncentrated outcomes where $p(x)\ge c/N$ the relative error is $O(\epsilon/c)$ — small, and Stockmeyer's estimate survives.

Derivation AExact classical sampling collapses the polynomial hierarchy

The goal is to run the full BJS/AA reduction: starting only from the assumption that some classical polynomial-time randomized algorithm samples exactly from $p(x)=|\langle x|U|0\rangle|^2$ , derive that a #P-hard quantity would be computable inside the third level $\Sigma_3^p$ of the polynomial hierarchy, so that Toda's theorem forces the entire hierarchy to collapse to $\Sigma_3^p$ — an implication regarded as almost as implausible as $\mathrm{P}=\mathrm{NP}$ . We assume the sampler for contradiction, expose its output as a count of preimages, apply Stockmeyer, encode a #P-hard number into $p$ , and chain the containments.

Step 1. Let $\mathcal{S}(r)$ be the assumed sampler; exactness means its distribution over the random tape $r$ satisfies $q(x)=\Pr_r[\mathcal{S}(r)=x]=p(x)$ for every $x$ . Because $\mathcal{S}$ is a poly-size circuit, $q(x)=|\{r:\mathcal{S}(r)=x\}|/2^{|r|}$ is literally a fraction of accepting random tapes. Why: this rewrites the physically-defined probability as a combinatorial preimage count, the exact object Stockmeyer's theorem knows how to estimate.

Step 2. Apply Stockmeyer's approximate-counting theorem to that preimage count: a machine in $\mathrm{FBPP}^{\mathrm{NP}}\subseteq\mathrm{FP}^{\Sigma_2^p}$ outputs $\hat p(x)$ with $\hat p(x)\in(1\pm\delta)\,p(x)$ for any $\delta=1/\mathrm{poly}(n)$ . Why: sampling access alone, with nothing but an NP oracle, already yields a multiplicative estimate of the probability — the step that makes a mere sampler as powerful as a calculator.

Step 3. Choose $U$ so that $p(x)$ encodes a #P-hard number — a normalized Ising partition function for IQP, or $\propto|\mathrm{Per}(A)|^2$ for BosonSampling. Even a multiplicative approximation of such a $p(x)$ is #P-hard, because GapP is closed under the relevant operations and the sign/magnitude carries the count. Why: this plants the hardness inside the very probability the sampler reproduces, so estimating it is estimating a #P-hard quantity.

Step 4. Combine: the estimate $\hat p(x)$ of a #P-hard quantity now lives in $\mathrm{FP}^{\Sigma_2^p}\subseteq\Sigma_3^p$ , hence $\mathrm{P}^{\#\mathrm{P}}\subseteq\Sigma_3^p$ . Why: a #P-hard value computable at the third level drags the whole counting oracle down to that level, since #P-hardness means everything in #P reduces to it.

Step 5. Invoke Toda: $\mathrm{PH}\subseteq\mathrm{P}^{\#\mathrm{P}}\subseteq\Sigma_3^p$ , so the polynomial hierarchy collapses to its third level — believed false, completing the contradiction and proving no exact classical sampler exists. Why: Toda supplies the final lever, converting a single trapped #P query into the collapse of an infinite tower of quantifier alternations.

Go deeper · Derivation B · 2 minAnticoncentration lifts exact hardness to approximate hardness

Derivation BAnticoncentration lifts exact hardness to approximate hardness

The goal is to extend the collapse from an idealized exact sampler to the physically relevant device that need only reproduce $p$ within total-variation distance $\epsilon$ . We show that if the probabilities anticoncentrate and estimating $p(x)$ for a random $x$ is #P-hard — the average-case conjecture — then even an additive-error sampler yields, on a constant fraction of outcomes, a genuine multiplicative estimate of a #P-hard number, so the same Toda collapse follows. We push the global $\epsilon$ down to a typical per-outcome error, bound the bad outcomes with Markov, and use anticoncentration to convert additive error into multiplicative error.

Step 1. Total-variation closeness $\tfrac12\sum_x|q(x)-p(x)|\le\epsilon$ means the average per-outcome error over uniform $x$ is $\mathbb{E}_{x\sim U}|q(x)-p(x)|=\tfrac1N\sum_x|q(x)-p(x)|\le 2\epsilon/N$ . Why: a global distance budget becomes a per-outcome budget of order $1/N$ , the scale of a typical probability itself.

Step 2. By Markov's inequality, $\Pr_x[\,|q(x)-p(x)|>\alpha/N\,]\le 2\epsilon/\alpha$ , so for all but a $2\epsilon/\alpha$ fraction of outcomes the additive error is at most $\alpha/N$ . Why: it pins the sampler's error below $\alpha/N$ on the overwhelming majority of strings, isolating a large "good" set.

Step 3. Anticoncentration supplies a large denominator: $\Pr_x[p(x)\ge c/N]\ge\gamma$ , a constant fraction of outcomes with probability $\Omega(1/N)$ . On the intersection of this set with the good set, the relative error is $\frac{|q(x)-p(x)|}{p(x)}\le\frac{\alpha/N}{c/N}=\frac{\alpha}{c}\ll 1$ . Why: only because the typical probability is as large as the error scale does an additive error of size $\alpha/N$ become a small multiplicative error — this is the exact role anticoncentration plays.

Step 4. On that constant fraction of $x$ , then, $q(x)$ multiplicatively approximates $p(x)$ ; feeding $q$ through Stockmeyer (Step 2 of the previous derivation) produces a multiplicative estimate of $p(x)$ in $\Sigma_3^p$ for those outcomes. Why: the additive-error sampler is now doing, on typical outcomes, exactly what the exact sampler did on all outcomes.

Step 5. Assume the average-case #P-hardness conjecture: estimating $p(x)$ for a random $x$ is #P-hard. Then a #P-hard average-case quantity has been placed in $\Sigma_3^p$ , and Toda collapses PH exactly as before. Why: this is the second, unproven pillar — worst-case hardness alone is not enough, since the reduction only controls typical $x$ , so hardness must hold for typical instances too.

Go deeper · Derivation C · 1 minPorter–Thomas statistics and the anticoncentration constant

Derivation CPorter–Thomas statistics and the anticoncentration constant

The goal is to prove anticoncentration outright for the ensemble that matters to random circuit sampling — Haar-random unitaries — by computing the distribution of a single output probability and its first two moments, and reading off both the tail fraction $\gamma=e^{-c}$ and the collision constant $K=2$ that the previous derivation assumed. We treat a column of a Haar unitary as a uniformly random unit vector, take the large- $N$ limit to the exponential Porter–Thomas law, and evaluate the moments.

Step 1. For Haar-random $U$ the fixed-input probability $p(x)=|\langle x|U|0\rangle|^2$ is $|c|^2$ for a component $c$ of a random unit vector in $\mathbb{C}^N$ ; its exact law is $\Pr(p)=(N-1)(1-p)^{N-2}$ , which converges as $N\to\infty$ to the exponential $\Pr(Np=t)\to e^{-t}$ . Why: this is the Porter–Thomas distribution — the rescaled probability $Np$ is a unit-mean exponential, the fingerprint of a fully scrambled circuit.

Step 2. The first moment is fixed by normalization: $\sum_x\mathbb{E}[p(x)]=1$ over $N$ equivalent outcomes gives $\mathbb{E}[p]=1/N$ , i.e. $\mathbb{E}[Np]=1$ . Why: the mean probability is pinned to the uniform value $1/N$ no matter how spread the distribution is; the mean cannot by itself distinguish flat from peaked.

Step 3. The second moment separates the two: for the exponential law $\mathbb{E}[(Np)^2]=2$ , so $\mathbb{E}[p^2]=2/N^2$ (exactly $2/[N(N+1)]$ at finite $N$ ), and the collision probability is $\sum_x p(x)^2\approx N\cdot 2/N^2=2/N$ . Why: this is twice the uniform collision value $1/N$ , so $K=2$ — the distribution is spread, exactly the second-moment form of anticoncentration.

Step 4. The tail follows directly from the exponential: $\Pr_x[p(x)\ge c/N]=\int_c^\infty e^{-t}\,dt=e^{-c}$ , so $\gamma=e^{-c}$ ; taking $c=1$ gives $\gamma=1/e\approx 0.368$ of outcomes above the mean probability $1/N$ — a constant independent of $n$ . Why: a constant fraction of outcomes sit at or above the mean, which is precisely the tail-bound form of anticoncentration the reduction needs. *The key numerical results from this derivation — moments $\mathbb{E}[Np]=1$ , $\mathbb{E}[(Np)^2]=2$ , collision $2/N$ , tail $e^{-c}$ , and the numerical value $1/e=0.3679$ — follow from standard Porter–Thomas / random-matrix theory.*

Limiting cases

The conclusion swings sharply with the error model and with which conjectures one accepts. The table below is the map of what is unconditional and what is not.

Case	Result	Meaning
Exact sampling	$q(x)=p(x)\ \forall x$	Unconditionally hard: no classical poly-time sampler unless PH collapses to $\Sigma_3^p$ . Needs only #P-hardness of $p(x)$ plus Stockmeyer plus Toda — no anticoncentration or average-case assumption.
Multiplicative approximate	$\lvert q(x)-p(x)\rvert\le c\,p(x)$	Also unconditionally collapse-implying for small $c<1$ , since multiplicative closeness preserves the #P-hard estimate. Physically unrealistic — no device guarantees per-outcome multiplicative accuracy.
Additive / TVD approximate	$\tfrac12\sum_x\lvert q(x)-p(x)\rvert\le\epsilon$	The physically relevant model. Hardness is CONJECTURAL: requires both anticoncentration and an average-case #P-hardness conjecture (Permanent-of-Gaussians, or the random-circuit Polynomial conjecture).
Noisy / depth-limited	$F\to 0$ as $n\to\infty$	With constant per-gate noise and no error correction, fidelity decays exponentially; the output drifts to uniform, anticoncentration and hardness both wash out, and classical spoofing becomes possible at large $n$ .

Common trapThe unconditional result covers only exact worst-case sampling, not the experiment on the bench

The clean, proven statement is worst-case exact-sampling hardness. The hardness of approximate sampling — the only kind a real, noisy device could ever refute — is not proven: it stands on two open conjectures, (i) average-case #P-hardness of the output probability (Permanent-of-Gaussians for BosonSampling, the Polynomial conjecture for random circuits), and (ii) anticoncentration for the specific ensemble. Conflating "PH would collapse" (a clean implication of easy exact sampling) with "this experiment is classically hard" (which additionally needs both conjectures) is the single most common error in reading these results. A second trap: Stockmeyer estimates the probabilities multiplicatively, not the decision problem — the entire error budget must be tracked through total-variation distance, which is exactly why anticoncentration is load-bearing.

Worked examples

1 · Porter–Thomas, collision, and cross-entropy for a Sycamore-scale circuit (fully worked)

A random circuit acts on $n=53$ qubits, so $N=2^{53}$ . Assuming ideal Porter–Thomas statistics, find the mean output probability, the fraction of strings above it, the collision probability, and the ideal value of the linear cross-entropy benchmark $F_{\mathrm{XEB}}=N\,\langle p(x_i)\rangle_{\text{samples}}-1$ . Then interpret a measured $F_{\mathrm{XEB}}\approx 0.002$ .

Step 1. Dimension and mean. $N=2^{53}=\mathbf{9.007\times10^{15}}$ outcomes, so the mean probability is $\mathbb{E}[p]=1/N=\mathbf{1.11\times10^{-16}}$ . Every string is astronomically unlikely individually — a device that hit any particular target string would be the suspicious one.

Step 2. Fraction above the mean. From the Porter–Thomas tail $\Pr_x[p(x)\ge c/N]=e^{-c}$ with $c=1$ , a fraction $e^{-1}=\mathbf{0.368}$ of the $9\times10^{15}$ strings carry more than the mean probability. A constant $36.8\%$ independent of $n$ — this is anticoncentration, made concrete.

Step 3. Collision probability. $\sum_x p(x)^2\approx 2/N=\mathbf{2.22\times10^{-16}}$ , exactly twice the uniform value $1/N$ . The factor $2$ (Porter–Thomas $K=2$ ) is what guarantees the additive error of a total-variation sampler stays multiplicatively small on typical strings.

Step 4. Ideal XEB. For samples drawn from the true distribution, $\langle p(x_i)\rangle=\sum_x p(x)\cdot p(x)=\sum_x p(x)^2\approx 2/N$ , so $F_{\mathrm{XEB}}=N\cdot(2/N)-1=\mathbf{1}$ . For a machine outputting uniform noise, $\langle p(x_i)\rangle=\tfrac1N\sum_x p(x)=1/N$ , giving $F_{\mathrm{XEB}}=N\cdot(1/N)-1=\mathbf{0}$ . The benchmark reads $1$ for a perfect quantum sampler and $0$ for pure noise — and it works only because the distribution anticoncentrates, so that high- $p$ strings appear more often.

Step 5. Interpret the measurement. A measured $F_{\mathrm{XEB}}\approx 0.002$ means the device sampled with roughly $\mathbf{0.2\%}$ fidelity — its output is $99.8\%$ noise, $0.2\%$ signal — yet that sliver is statistically decisive over a few million samples, and reproducing even it is the claimed classically hard task. The XEB is a direct dividend of anticoncentration: no spread, no benchmark.

2 · Why the BosonSampling permanent is hard: the fermion–boson contrast

Fifty photons ( $n=50$ ) pass through a passive interferometer with $m=O(n^2)\approx 2500$ modes. Each output amplitude is $\mathrm{Per}(A)$ of a $50\times 50$ complex submatrix. Compare the classical cost of the permanent (bosons) with the determinant (fermions) of the same-size matrix.

Step 1. Naive permanent. Summing over all permutations costs $n!=50!=\mathbf{3.04\times10^{64}}$ terms — utterly infeasible; more than the number of atoms in the observable universe.

Step 2. Best known permanent algorithm. Ryser's formula evaluates $\mathrm{Per}(A)$ in $O(n\,2^n)$ operations: $50\cdot 2^{50}=\mathbf{5.63\times10^{16}}$ operations. A huge improvement over $50!$ , but still exponential — and no polynomial algorithm is known, consistent with #P-completeness.

Step 3. The fermion contrast. Swap bosons for fermions and the amplitude becomes $\det(A)$ , computable by Gaussian elimination in $O(n^3)=50^3=\mathbf{1.25\times10^{5}}$ operations — trivially polynomial. The only formal difference between $\det$ and $\mathrm{Per}$ is the alternating sign $\mathrm{sgn}(\sigma)$ : the determinant's cancellations enable elimination, the permanent's all-plus signs forbid it.

Step 4. The lesson. Fermion sampling (all $\det$ ) is classically easy; boson sampling (all $\mathrm{Per}$ ) is classically hard, and the divide is a single sign. The hardness of BosonSampling is the #P-completeness of the permanent, $5.6\times10^{16}\gg 1.25\times10^{5}$ operations for the same $50\times 50$ matrix — a gap that grows exponentially with photon number.

Physics of the portrait

Sampling hardness is not one person's theorem but a chain forged across four decades — Valiant's permanent, Stockmeyer's counter, Toda's collapse, and the quantum syntheses of Bremner–Jozsa–Shepherd and Aaronson–Arkhipov. The portrait is the argument itself.

Origins · 1 minsampling hardness and how this was discovered

sampling hardness

the collapse argument that easy classical sampling forces PH ⊆ Σ₃ᵖ · quantum computational complexity

The sampling-hardness argument is a rare object in physics: a claim about laboratory hardware whose entire force is borrowed from pure complexity theory, assembled from parts that were built for unrelated reasons. Leslie Valiant supplied the foundation stone in 1979, proving that computing the permanent of a 0/1 matrix is #P-complete — the counting analogue of NP-completeness — even though the superficially identical determinant is easy. Larry Stockmeyer added the second piece in 1983, showing that approximate counting, and hence estimating the acceptance probability of any circuit, sits in the polynomial hierarchy at the level of an NP oracle over BPP. Seinosuke Toda proved in 1991 the astonishing containment $\mathrm{PH}\subseteq\mathrm{P}^{\#\mathrm{P}}$ : a single counting query is at least as powerful as the entire tower of alternating quantifiers. For two decades these lived as landmarks of classical complexity with no quantum tenant. Then in 2004–2011 Michael Bremner, Richard Jozsa, and Dan Shepherd showed that even the humble commuting circuits of IQP produce distributions whose classical simulation would collapse PH, and in 2011–2013 Scott Aaronson and Alex Arkhipov built the same conclusion for linear-optical BosonSampling, wrapping Valiant's permanent in a photonic experiment and adding the anticoncentration and average-case machinery that the noisy, approximate world demands. The modern picture — worst-case exact hardness proven, average-case approximate hardness conjectured — completes what Valiant began: a tabulated impossibility turned into the theoretical backbone of every quantum-advantage experiment.

History

1979

— Valiant proves the permanent is #P-complete

1983

— Stockmeyer places approximate counting in the polynomial hierarchy

1991

— Toda proves PH ⊆ P^#P, counting dominates the hierarchy

2004

— Terhal and DiVincenzo link constant-depth circuit simulation to complexity collapse

2011

— Bremner, Jozsa and Shepherd show classical simulation of IQP collapses PH

2013

— Aaronson and Arkhipov prove the BosonSampling hardness program

Going further

References. Aaronson & Arkhipov, "The Computational Complexity of Linear Optics," Theory of Computing 9 (2013) 143 · Bremner, Jozsa & Shepherd, "Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy," Proc. R. Soc. A 467 (2011) 459 · Bremner, Montanaro & Shepherd, "Average-case complexity versus approximate simulation of commuting quantum computations," PRL 117 (2016) 080501 · Stockmeyer, "The complexity of approximate counting," STOC 1983 · Toda, "PP is as hard as the polynomial-time hierarchy," SIAM J. Comput. 20 (1991) 865 · Valiant, "The complexity of computing the permanent," Theoret. Comput. Sci. 8 (1979) 189 · Bouland, Fefferman, Nirkhe & Vazirani, "On the complexity and verification of quantum random circuit sampling," Nature Physics 15 (2019) 159 · Arute et al., "Quantum supremacy using a programmable superconducting processor," Nature 574 (2019) 505 · Nielsen & Chuang, Quantum Computation and Quantum Information, §3.2 · Kitaev, Shen & Vyalyi, Classical and Quantum Computation, counting-classes chapter. The key relations used throughout this article are: $p(x)=|\langle x|U|0\rangle|^2$ with its Feynman path-sum expansion; the BosonSampling amplitude $\propto\mathrm{Per}(A)$ , with the permanent #P-complete by Valiant; Stockmeyer's approximate counting in $\mathrm{FBPP}^{\mathrm{NP}}\subseteq\mathrm{FP}^{\Sigma_2^p}$ ; Toda's $\mathrm{PH}\subseteq\mathrm{P}^{\#\mathrm{P}}$ and the resulting $\Sigma_3^p$ collapse. The Porter–Thomas moments are $\mathbb{E}[Np]=1$ , $\mathbb{E}[(Np)^2]=2$ , collision $\sum_x p^2\approx 2/N$ , and tail $e^{-c}$ . The two conjectures — average-case #P-hardness and anticoncentration for realistic ensembles — remain open. Numerical anchors: $2^{53}=9.007\times10^{15}$ , $1/e=0.368$ , $50\cdot 2^{50}=5.63\times10^{16}$ , $50^3=1.25\times10^5$ .

Prerequisites. The Complexity Class BQP · BQP is Contained in PP and PSPACE · BQP versus P, NP, and PSPACE. Leads to. MIP* = RE · The Local Hamiltonian Problem.

Ask the tutor: Ask me to walk the sampler-to-Stockmeyer-to-Toda chain line by line, or to show exactly how anticoncentration turns a total-variation-distance sampler into a multiplicative estimate of a #P-hard probability.

Why is a mere classical sampler as dangerous as a machine that computes p(x) exactly?

Because sampling access secretly grants estimation power. A classical sampler is a circuit $C(r)$ that maps random bits to outputs, so its probability $q(x)$ is literally the fraction of random tapes that produce $x$ — a preimage count. Stockmeyer's theorem says that counting the accepting inputs of a circuit, approximately, can be done in the polynomial hierarchy with an NP oracle. So from the sampler alone, a $\mathrm{FBPP}^{\mathrm{NP}}$ machine can estimate $q(x)=p(x)$ multiplicatively — you never needed the exact calculator. That is exactly why "just sampling" is not a weaker task in the sense that matters: it still exposes the #P-hard number hiding inside $p(x)$ .

What does "the polynomial hierarchy collapses" actually mean, and why is it a disaster?

PH is the infinite tower $\mathrm{P}\subseteq\mathrm{NP}\subseteq\Sigma_2^p\subseteq\Sigma_3^p\subseteq\cdots$ , where each level adds one more alternating "there exists / for all" quantifier. The universal belief is that the tower is strictly increasing — each quantifier genuinely buys new power. A "collapse to the third level" means every one of those infinitely many levels equals $\Sigma_3^p$ : all the higher quantifier alternations were secretly free. That would be a structural earthquake in complexity theory, on par with $\mathrm{P}=\mathrm{NP}$ in how strongly it is disbelieved. So proving "easy classical sampling $\Rightarrow$ PH collapses" is a very strong form of evidence that easy classical sampling is impossible.

Why does exact-sampling hardness not need anticoncentration, while approximate hardness does?

An exact sampler reproduces $p(x)$ perfectly for every $x$ , so Stockmeyer estimates each $p(x)$ multiplicatively regardless of how small it is — no assumption about the shape of the distribution is required. A total-variation (additive) sampler is only globally close: it can be wildly wrong on individual small-probability strings as long as the errors sum to at most $\epsilon$ . On a string with tiny $p(x)$ the additive error can swamp the value, destroying the multiplicative estimate. Anticoncentration rescues the argument by guaranteeing a constant fraction of strings have $p(x)=\Omega(1/N)$ , where the bounded additive error $\sim\epsilon/N$ is only a small multiplicative error — so the estimate survives on typical strings.

What is anticoncentration in one clean statement, and how is it measured?

Anticoncentration says the output distribution is spread out rather than concentrated on a few strings: a constant fraction of outcomes carry probability $\Omega(1/N)$ , equivalently the collision probability $\sum_x p(x)^2$ is only a constant factor $K$ above the perfectly-flat value $1/N$ . For Haar-random circuits, Porter–Thomas statistics give $K=2$ and a fraction $e^{-c}$ of outcomes above $c/N$ . Operationally it is what makes the linear cross-entropy benchmark work: high-probability strings must appear noticeably more often than low-probability ones, which only happens if the distribution is spread but not uniform. Without anticoncentration a sampler could ignore all small probabilities and still look close in total-variation distance.

Are the Sycamore and Jiuzhang experiments proven to be classically hard?

No — and this is the crucial nuance. What is proven is that exact classical sampling from these distributions would collapse PH. What the experiments actually do is approximate, noisy sampling, whose hardness additionally requires two open conjectures: average-case #P-hardness of the output probability, and anticoncentration for the specific ensemble. Both are supported by strong evidence (polynomial-interpolation arguments for average-case hardness, Porter–Thomas for anticoncentration) but neither is a theorem. On top of that, constant-rate noise without error correction erodes anticoncentration and lets classical spoofing algorithms close in — which is why specific fidelity claims have been actively contested rather than settled.

Where exactly does the permanent enter, and why not the determinant?

For $n$ indistinguishable photons through a passive linear-optical network with transfer unitary $U$ , the transition amplitude to a given output configuration is the permanent of the corresponding $n\times n$ submatrix $A$ , and the measured probability is $\propto|\mathrm{Per}(A)|^2$ . The permanent, $\sum_\sigma\prod_i A_{i,\sigma(i)}$ , differs from the determinant only by dropping the sign $\mathrm{sgn}(\sigma)$ . That single change is decisive: the determinant's alternating signs allow Gaussian elimination in $O(n^3)$ time, while the permanent's all-plus signs make it #P-complete (Valiant 1979), with the best known algorithm (Ryser) still exponential at $O(n\,2^n)$ . Bosons pick out the permanent because their wavefunction is symmetric under exchange; fermions pick the determinant and are classically easy.