Algorithm Zoo · Sampling
Boson Sampling
First described: Aaronson, Arkhipov, 2011
The problem
Sample from the output distribution of indistinguishable bosons (photons) passing through a linear interferometer.
Permanent of an n×n matrix is #P-hard. Boson sampling is conjectured hard to sample classically under reasonable complexity assumptions. Gaussian boson sampling (GBS) is the squeezed-light variant that USTC's Jiuzhang and Xanadu's Borealis machines implement.
Best classical
Tensor-network and matrix-permanent estimation methods — actively improving.
Quantum complexity
O(n) modes; depth bounded by interferometer.
Our verdict
A clean complexity-theoretic candidate for advantage that photonic hardware actually runs. The Jiuzhang and Borealis experiments are real, the photons are real, the math is hard — but the classical chase keeps reducing the gap and the sampling task has no application. Useful research, not a product.
When to use it
- Photonic-quantum-computing benchmarks.
- Specific applications (graph similarity, molecular vibronic spectra) where GBS has been tailored — speedup unproven, but the application is non-trivial.
When not to use it
- Generic sampling tasks — the output distribution is not directly useful.
- When you need post-selection-free results — photon loss eats fidelity.
Classical baseline
Oh et al. (Phys. Rev. Lett. 2023) showed classical algorithms reproduce Jiuzhang-class GBS distributions efficiently when photon loss is accounted for. The arms race resembles RCS — each hardware advance prompts a tighter classical attack.
Hardware cost
Xanadu Borealis: 216 squeezed modes, 288 photonic gates. Photonic systems can scale well in number of modes; squeezing quality and loss are the practical limits.
Key papers
- The computational complexity of linear optics ↗
Aaronson, Arkhipov · 2013 · Theory of Computing
- Quantum computational advantage using photons ↗
Zhong et al. · 2020 · Science
Deep-dive tutorials
Last verified: 2026-05-24