Interference & the Hardness of Simulation
Why cancelling signs make classical simulation hard.
Monte Carlo can estimate any sum of positive terms by sampling. Give the terms signs and it collapses, because the answer can be exponentially smaller than the terms. That sign problem is, in a precise complexity-theoretic sense, why we believe quantum circuits cannot be simulated efficiently.
What you’ll learn
- Quantify why sampling estimates positive sums efficiently but fails on signed sums (the average-sign bound).
- Prove that exact output amplitudes are #P-hard, and state the multiplicative-approximation version.
- Prove, via Stockmeyer counting and Toda's theorem, that exact classical sampling of IQP circuits would collapse the polynomial hierarchy.
- Separate the worst-case theorems from the average-case conjectures behind quantum-advantage experiments, and explain the role of noise.
Positive sums are easy, signed sums are not
Any amplitude, partition function or transition probability can be written over paths. If all (a classical Markov chain, or imaginary-time evolution under a stoquastic Hamiltonian), sample paths with probability : the estimator has bounded relative variance. With signs, the natural estimator samples from and averages the sign:
Factor out the total weight ; what remains is the average sign .
Each sample is , so its variance is .
Relative error costs samples.
For a Hadamard-plus-CCZ circuit every path has weight . With free variables, generic circuits have exponentially smaller than , so the sample count is exponential.
A signed sum has average sign . Roughly how many samples, in millions, are needed for 10% relative error?
Show the answer
100 million
, i.e. 100 million. Each further factor of 10 in costs a factor of 100 in samples. In quantum Monte Carlo typically decays exponentially in system size and inverse temperature.
Exact amplitudes are #P-hard
Let be computable in polynomial time, e.g. "assignment satisfies formula ". Bennett's construction gives a reversible Toffoli/X circuit (garbage is removed by uncomputation).
With the target in , the bit flip becomes a phase (phase kickback).
The Hadamard layers turn the phase oracle into a signed count.
An exact amplitude therefore yields #SAT, which is #P-complete. Rewriting Toffolis as gives (b), with a cubic phase polynomial.
Stockmeyer, Toda, and the collapse
Suppose a classical randomized polynomial-time algorithm , , outputs with probability exactly for every IQP circuit .
The classical sampler's probability is a positive count of random strings: a #P function.
Stockmeyer approximates this count to multiplicative error in . But multiplicative approximation of for worst-case IQP circuits is #P-hard, so .
The first inclusion is Toda's theorem (1991); the last is the relativized Sipser–Gács–Lautemann theorem .
So : the polynomial hierarchy collapses to its third level, which is widely believed false. The same conclusion follows from a sampler whose probabilities are within a multiplicative factor of (BJS 2011). Aaronson & Arkhipov (2011) run the identical argument for boson sampling, where .
In the collapse argument, why can Stockmeyer's algorithm be applied to the classical sampler but not directly to the quantum circuit?
- Because the quantum circuit is too large to write down
- Because the classical sampler's probability is a count of random strings (a sum of positive terms), while the quantum probability is the square of a signed sum
- Because Stockmeyer's algorithm needs a quantum oracle
- Because quantum probabilities are irrational numbers
Show the answer
B. Because the classical sampler's probability is a count of random strings (a sum of positive terms), while the quantum probability is the square of a signed sum
Approximate counting works for #P functions, which count objects. is such a count. The quantum arises from cancellation between signed paths, and approximating such gaps is #P-hard. Interference is exactly the gap between the two.
From worst case to experiments
Real devices are noisy, so the relevant question is whether a classical sampler can come within total-variation distance . Here the Stockmeyer argument only yields additive approximations of most probabilities. Turning that into hardness needs two further ingredients: average-case #P-hardness of approximating a typical probability (for boson sampling, the Permanent-of-Gaussians conjecture) and anticoncentration, meaning typical probabilities are not much smaller than .
| Statement | Status |
|---|---|
| Exact amplitudes of universal or IQP circuits are #P-hard | Theorem (worst case) |
| Multiplicative approximation of is #P-hard | Theorem (worst case) |
| Exact or multiplicatively close classical sampling PH collapses | Theorem (BJS 2011; Aaronson–Arkhipov 2011) |
| Exact amplitudes of random circuits are #P-hard on average | Theorem, but robust only to very small errors (Bouland, Fefferman, Nirkhe & Vazirani 2019) |
| Additive-error sampling is classically hard | Conjecture (average-case hardness plus anticoncentration) |
| Random circuit sampling with a constant noise rate per gate | Classically simulable in polynomial time asymptotically (Aharonov, Gao, Landau, Liu & Vazirani 2023) |
Key takeaways
- Signed sums defeat sampling: estimating to relative error costs samples, exponential for generic circuits.
- Exact (and multiplicatively approximate) output probabilities of quantum circuits are #P-hard in the worst case, by phase kickback of an arbitrary #P predicate.
- Positive counts are approximable in (Stockmeyer), so exact or multiplicatively close classical sampling of IQP or boson sampling would collapse PH (via Toda).
- Advantage experiments need additional average-case and anticoncentration conjectures, and constant noise makes random circuit sampling classically easy asymptotically.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Why can Monte Carlo estimate the output probability of a classical randomized circuit efficiently, but not a generic quantum amplitude?
- Classical circuits have fewer paths
- The classical path weights are nonnegative, while quantum path weights carry signs, so the average sign can be exponentially small
- Quantum amplitudes are complex numbers, which computers cannot sample
- Classical randomness is pseudo-random
Show the answer
B. The classical path weights are nonnegative, while quantum path weights carry signs, so the average sign can be exponentially small
Both sums have exponentially many paths. With nonnegative weights the relative variance of the natural estimator is bounded; with signs it scales as , and for generic circuits is exponentially small.
Stockmeyer's algorithm approximates #P counts to within a multiplicative factor in which class?
- , within the third level of PH
- Only in
Show the answer
C. , within the third level of PH
Approximate counting needs randomness plus an NP oracle, placing it in . Exact counting is #P-complete and believed far harder.
If a classical algorithm could sample exactly from the output distribution of every IQP circuit in polynomial time, what would follow?
- The polynomial hierarchy would collapse to its third level
- P = NP
- Factoring would be classically easy
- Nothing: sampling and computing probabilities are unrelated
Show the answer
A. The polynomial hierarchy would collapse to its third level
Stockmeyer would approximate the sampler's (positive) probabilities in , but these equal #P-hard IQP probabilities, so , and Toda's theorem collapses PH to .
Which statement is a proven theorem rather than a conjecture?
- Classical samplers cannot reach small total-variation distance from random-circuit output distributions
- Approximating for i.i.d. Gaussian is #P-hard
- Random circuit sampling with constant noise per gate stays classically hard as
- Exact or multiplicatively close classical sampling of IQP circuits would collapse PH
Show the answer
D. Exact or multiplicatively close classical sampling of IQP circuits would collapse PH
The multiplicative-error collapse is a theorem (BJS 2011). Additive-error hardness and the Permanent-of-Gaussians statement are conjectures, and constant-noise random circuit sampling in the anticoncentrating regime has a polynomial-time classical algorithm.
Further reading
- L. Stockmeyer, "The complexity of approximate counting", Proc. 15th ACM STOC (1983).
- S. Toda, "PP is as hard as the polynomial-time hierarchy", SIAM J. Comput. 20, 865 (1991).
- M. J. Bremner, R. Jozsa & D. J. Shepherd, "Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy", Proc. R. Soc. A 467, 459 (2011).
- S. Aaronson & A. Arkhipov, "The computational complexity of linear optics", Theory of Computing 9, 143 (2013); STOC 2011.
- M. Troyer & U.-J. Wiese, "Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations", Phys. Rev. Lett. 94, 170201 (2005).