Quantum Algorithms Database
Boson Sampling
A specialized computational task using photons (rather than qubits) believed to be exponentially hard to simulate classically, proposed as a near-term path to demonstrating quantum advantage.
Year
2011
Inventor(s)
Aaronson & Arkhipov
Speedup Type
Exponential Speedup
Difficulty
★★★★☆
The Problem
Sampling from the output distribution of identical photons passing through a network of optical components — a task with deep connections to permanent calculations in linear algebra.
How It Works
Sends single photons into a network of beam splitters and mirrors, then measures where they emerge; the resulting statistics are exponentially hard to compute classically as photon number grows.
Real-World Impact
Demonstrated experimentally at increasing scale (notably China's Jiuzhang photonic experiments); like random circuit sampling, primarily valuable as a quantum advantage benchmark rather than a practical application.