Simple Algorithm
Quantum Computing · Rydberg State · 30 min

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 A=∑pwpA = \sum_p w_p over paths. If all wp≥0w_p\ge0 (a classical Markov chain, or imaginary-time evolution under a stoquastic Hamiltonian), sample paths with probability ∝wp\propto w_p: the estimator has bounded relative variance. With signs, the natural estimator samples from ∣wp∣\abs{w_p} and averages the sign:

DerivationThe average-sign bound
  1. A=∑pwp=W Ep∼π ⁣[sgn⁡wp],W=∑p∣wp∣,  πp=∣wp∣WA = \sum_p w_p = W\,\mathbb{E}_{p\sim\pi}\!\left[\operatorname{sgn} w_p\right], \qquad W = \sum_p\abs{w_p},\ \ \pi_p = \frac{\abs{w_p}}{W}

    Factor out the total weight WW; what remains is the average sign ⟨s⟩=A/W\expval{s} = A/W.

  2. A^=WM∑k=1Msgn⁡wpk,Var(A^)=W2(1−⟨s⟩2)M\hat A = \frac{W}{M}\sum_{k=1}^{M}\operatorname{sgn} w_{p_k}, \qquad \mathrm{Var}(\hat A) = \frac{W^2\left(1 - \expval{s}^2\right)}{M}

    Each sample is ±W\pm W, so its variance is W2(1−⟨s⟩2)W^2(1-\expval{s}^2).

  3. Var(A^)∣A∣≈1∣⟨s⟩∣M⟹M≈1ε2⟨s⟩2\frac{\sqrt{\mathrm{Var}(\hat A)}}{\abs{A}} \approx \frac{1}{\abs{\expval{s}}\sqrt{M}} \quad\Longrightarrow\quad M \approx \frac{1}{\varepsilon^2\expval{s}^2}

    Relative error ε\varepsilon costs O(1/(ε2⟨s⟩2))\order{1/(\varepsilon^2\expval{s}^2)} samples.

  4. ⟨s⟩=gap⁡(f)2m\expval{s} = \frac{\operatorname{gap}(f)}{2^m}

    For a Hadamard-plus-CCZ circuit every path has weight ±2−h/2\pm2^{-h/2}. With mm free variables, generic circuits have gap⁡(f)\operatorname{gap}(f) exponentially smaller than 2m2^m, so the sample count is exponential.

Predict before you look

A signed sum has average sign ⟨s⟩=10−3\expval{s} = 10^{-3}. Roughly how many samples, in millions, are needed for 10% relative error?

Show the answer

100 million

M≈1/(ε2⟨s⟩2)=1/(10−2⋅10−6)=108M \approx 1/(\varepsilon^2\expval{s}^2) = 1/(10^{-2}\cdot10^{-6}) = 10^{8}, i.e. 100 million. Each further factor of 10 in ⟨s⟩\expval{s} costs a factor of 100 in samples. In quantum Monte Carlo ⟨s⟩\expval{s} typically decays exponentially in system size and inverse temperature.

Exact amplitudes are #P-hard

DerivationProof of (a): signed counting via kickback
  1. Let g:{0,1}n→{0,1}g:\{0,1\}^n\to\{0,1\} be computable in polynomial time, e.g. "assignment xx satisfies formula ϕ\phi". Bennett's construction gives a reversible Toffoli/X circuit Rg:∣x⟩∣b⟩∣0a⟩↦∣x⟩∣b⊕g(x)⟩∣0a⟩R_g:\ket{x}\ket{b}\ket{0^a}\mapsto\ket{x}\ket{b\oplus g(x)}\ket{0^a} (garbage is removed by uncomputation).

  2. Rg ∣x⟩∣−⟩∣0a⟩=(−1)g(x)∣x⟩∣−⟩∣0a⟩R_g\,\ket{x}\ket{-}\ket{0^a} = (-1)^{g(x)}\ket{x}\ket{-}\ket{0^a}

    With the target in ∣−⟩=HX∣0⟩\ket{-} = HX\ket{0}, the bit flip becomes a phase (phase kickback).

  3. ⟨0n∣H⊗nOgH⊗n∣0n⟩=12n∑x(−1)g(x)=gap⁡(g)2n\bra{0^n}H^{\otimes n}O_gH^{\otimes n}\ket{0^n} = \frac{1}{2^n}\sum_x(-1)^{g(x)} = \frac{\operatorname{gap}(g)}{2^n}

    The Hadamard layers turn the phase oracle into a signed count.

  4. #g=2n−gap⁡(g)2\#g = \frac{2^n - \operatorname{gap}(g)}{2}

    An exact amplitude therefore yields #SAT, which is #P-complete. Rewriting Toffolis as H CCZ HH\,\mathrm{CCZ}\,H gives (b), with a cubic phase polynomial. ■\blacksquare

Stockmeyer, Toda, and the collapse

DerivationExact classical sampling would collapse PH (Bremner–Jozsa–Shepherd 2011)
  1. Suppose a classical randomized polynomial-time algorithm A(r)\mathcal{A}(r), r∈{0,1}qr\in\{0,1\}^{q}, outputs xx with probability exactly px(C)p_x(C) for every IQP circuit CC.

  2. p0(C)=Pr⁡r[A(r)=0n]=#{r:A(r)=0n}2qp_0(C) = \Pr_r[\mathcal{A}(r) = 0^n] = \frac{\#\{r : \mathcal{A}(r) = 0^n\}}{2^{q}}

    The classical sampler's probability is a positive count of random strings: a #P function.

  3. Stockmeyer approximates this count to multiplicative error in FBPPNP\mathsf{FBPP}^{\mathsf{NP}}. But multiplicative approximation of p0p_0 for worst-case IQP circuits is #P-hard, so P#P⊆BPPNP\mathsf{P}^{\#\mathsf{P}}\subseteq\mathsf{BPP}^{\mathsf{NP}}.

  4. PH⊆P#P⊆BPPNP⊆Σ3P\mathsf{PH}\subseteq\mathsf{P}^{\#\mathsf{P}}\subseteq\mathsf{BPP}^{\mathsf{NP}}\subseteq\Sigma_3^{\mathsf{P}}

    The first inclusion is Toda's theorem (1991); the last is the relativized Sipser–Gács–Lautemann theorem BPP⊆Σ2P\mathsf{BPP}\subseteq\Sigma_2^{\mathsf{P}}.

  5. So PH=Σ3P\mathsf{PH} = \Sigma_3^{\mathsf{P}}: 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 1≤c<21 \le c < \sqrt2 of pxp_x (BJS 2011). Aaronson & Arkhipov (2011) run the identical argument for boson sampling, where px=∣Per(Ax)∣2p_x = \abs{\mathrm{Per}(A_x)}^2. ■\blacksquare

Check your understanding

In the collapse argument, why can Stockmeyer's algorithm be applied to the classical sampler but not directly to the quantum circuit?

  1. Because the quantum circuit is too large to write down
  2. 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
  3. Because Stockmeyer's algorithm needs a quantum oracle
  4. 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. Pr⁡r[A(r)=0n]\Pr_r[\mathcal{A}(r)=0^n] is such a count. The quantum p0=(gap⁡(f)/2n)2p_0 = (\operatorname{gap}(f)/2^n)^2 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 ε\varepsilon. 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 2−n2^{-n}.

StatementStatus
Exact amplitudes of universal or IQP circuits are #P-hardTheorem (worst case)
Multiplicative approximation of p0p_0 is #P-hardTheorem (worst case)
Exact or multiplicatively close classical sampling ⇒\Rightarrow PH collapsesTheorem (BJS 2011; Aaronson–Arkhipov 2011)
Exact amplitudes of random circuits are #P-hard on averageTheorem, but robust only to very small errors (Bouland, Fefferman, Nirkhe & Vazirani 2019)
Additive-error sampling is classically hardConjecture (average-case hardness plus anticoncentration)
Random circuit sampling with a constant noise rate per gateClassically simulable in polynomial time asymptotically (Aharonov, Gao, Landau, Liu & Vazirani 2023)

Key takeaways

  • Signed sums defeat sampling: estimating A=W⟨s⟩A = W\expval{s} to relative error ε\varepsilon costs ≈1/(ε2⟨s⟩2)\approx 1/(\varepsilon^2\expval{s}^2) 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 BPPNP\mathsf{BPP}^{\mathsf{NP}} (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.

Question 1

Why can Monte Carlo estimate the output probability of a classical randomized circuit efficiently, but not a generic quantum amplitude?

  1. Classical circuits have fewer paths
  2. The classical path weights are nonnegative, while quantum path weights carry signs, so the average sign can be exponentially small
  3. Quantum amplitudes are complex numbers, which computers cannot sample
  4. 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 1/⟨s⟩21/\expval{s}^2, and for generic circuits ⟨s⟩=gap⁡/2m\expval{s} = \operatorname{gap}/2^m is exponentially small.

Question 2

Stockmeyer's algorithm approximates #P counts to within a multiplicative (1±ε)(1\pm\varepsilon) factor in which class?

  1. FP\mathsf{FP}
  2. FBQP\mathsf{FBQP}
  3. FBPPNP\mathsf{FBPP}^{\mathsf{NP}}, within the third level of PH
  4. Only in FP#P\mathsf{FP}^{\#\mathsf{P}}
Show the answer

C. FBPPNP\mathsf{FBPP}^{\mathsf{NP}}, within the third level of PH

Approximate counting needs randomness plus an NP oracle, placing it in BPPNP⊆Σ3P\mathsf{BPP}^{\mathsf{NP}}\subseteq\Sigma_3^{\mathsf{P}}. Exact counting is #P-complete and believed far harder.

Question 3

If a classical algorithm could sample exactly from the output distribution of every IQP circuit in polynomial time, what would follow?

  1. The polynomial hierarchy would collapse to its third level
  2. P = NP
  3. Factoring would be classically easy
  4. 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 BPPNP\mathsf{BPP}^{\mathsf{NP}}, but these equal #P-hard IQP probabilities, so P#P⊆BPPNP\mathsf{P}^{\#\mathsf{P}}\subseteq\mathsf{BPP}^{\mathsf{NP}}, and Toda's theorem collapses PH to Σ3P\Sigma_3^{\mathsf{P}}.

Question 4

Which statement is a proven theorem rather than a conjecture?

  1. Classical samplers cannot reach small total-variation distance from random-circuit output distributions
  2. Approximating ∣Per(X)∣2\abs{\mathrm{Per}(X)}^2 for i.i.d. Gaussian XX is #P-hard
  3. Random circuit sampling with constant noise per gate stays classically hard as n→∞n\to\infty
  4. 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).