Boson Sampling

Aaronson-Arkhipov (2011): sampling from the output distribution of n indistinguishable photons through an m-mode linear optical network is #P-hard classically. The probability of each outcome is the squared permanent of a submatrix — and computing permanents is #P-complete.

n = 4
m = 8
V = 95%
Output probability: P(S) = |Perm(U_S)|² / s₁!s₂!...s_m!
Computing Permanent is #P-hard (Valiant 1979) — no efficient classical algorithm known
Quantum advantage: n photons, m≈n² modes → exponential classical hardness