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)
Scott Aaronson and Alex Arkhipov
Speedup Type
Exponential Speedup
Difficulty
★★★★☆
Overview
Boson sampling is a task in which identical photons are sent through a network of beam splitters and their output positions are measured. The probability of each outcome is given by the permanent of a matrix, a quantity that is extremely hard to compute classically. Aaronson and Arkhipov showed that if a classical computer could sample the same distribution efficiently, a widely believed conjecture in computer science, that the polynomial hierarchy is infinite, would collapse.
Boson sampling is not a universal quantum computation and has no known practical application. Its value is that it needs only linear optics and photon detection, so it is a more modest route to demonstrating a quantum advantage than building a full quantum computer.
The problem it solves
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.
History and background
Aaronson and Arkhipov introduced the problem in their 2011 paper The Computational Complexity of Linear Optics, presented at the ACM Symposium on Theory of Computing. In 2013 four groups in Brisbane, Oxford, Vienna, and Rome ran the first small experiments with three or four photons. Progress was slow because producing many indistinguishable single photons on demand is difficult.
A variation proposed by Hamilton and colleagues in 2017, Gaussian boson sampling, replaces single photons with squeezed light, which is much easier to generate. In 2020 a group at the University of Science and Technology of China reported Jiuzhang, detecting up to 76 photons, followed by Jiuzhang 2.0 with 113 photons in 2021 and Jiuzhang 3.0 with up to 255 photons in 2023. Xanadu's Borealis, published in 2022, used 216 squeezed modes. Classical simulation has pushed back: Oh and colleagues in 2024 described a classical algorithm that reproduced the results of some experiments by exploiting photon loss, and other groups have proposed similar spoofing methods.
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.
Photons are bosons, which means that when two identical photons enter a beam splitter at the same time, they bunch together and exit through the same port, an effect called Hong-Ou-Mandel interference. In a large network, such interference happens everywhere, and the resulting probabilities depend on how many ways the photons can travel from inputs to outputs.
Mathematically, the amplitude for a particular output pattern is the permanent of a submatrix of the network's unitary matrix. The permanent resembles the determinant but with all plus signs. The determinant can be computed quickly, but computing the permanent of a general matrix is #P-hard, as Valiant showed in 1979. The fastest known classical methods for the permanent of an n by n matrix take time of order n times 2 to the n.
Nature, in effect, computes these permanents for free. Aaronson and Arkhipov argued that even approximate classical sampling of the output distribution would imply unlikely consequences in complexity theory, which is what supports the claim of hardness.
Step by step
- Prepare n identical single photons, one in each of n input modes of an m-mode optical network, with m much larger than n.
- Send the photons through a randomly chosen linear optical interferometer, a network of beam splitters and phase shifters, described by an m by m unitary matrix.
- Detect the number of photons in each output mode using single-photon detectors.
- Record the output pattern, a list of occupation numbers for the m modes. Each run yields one sample.
- Repeat many times to collect samples whose distribution follows the squared magnitude of permanents.
- Validate the results with statistical tests against models of the ideal distribution and alternatives such as distinguishable photons or thermal states.
A worked example
Take two photons entering two ports of a 50:50 beam splitter, which is the simplest case. Classical particles would exit in different ports half the time. Two identical photons never do: they always exit together, either both in one port or both in the other, each with probability one half. This is the Hong-Ou-Mandel effect and it corresponds to the permanent of a two-by-two matrix.
Scaling up, with 50 photons in 2,500 modes, the output distribution depends on permanents of 50 by 50 matrices, which take on the order of 50 times 2 to the 50 operations each to compute exactly. The photonic device samples directly from the distribution in microseconds per sample, apart from the loss and detection overheads.
Complexity and resources
| Item | Detail |
|---|---|
| Classical hardness | Exact sampling is hard unless the polynomial hierarchy collapses; the best known algorithms for permanents are exponential |
| Quantum resources | Linear optics and photon detection only, no feed-forward or entangling gates |
| Mode count | The original proof suggests m on the order of n squared modes for the collision-free regime |
| Largest experiments | 255 detected photons (Jiuzhang 3.0, 2023); 216 modes (Borealis, 2022) |
| Main obstacle | Photon loss and imperfect indistinguishability reduce hardness arguments |
What hardware it needs
- A source of squeezed light or single photons, a low-loss interferometer, and high-efficiency photon-number-resolving detectors.
- Control over photon indistinguishability and phase stability.
- Large-scale classical computing for validation.
Applications
- Demonstrating quantum advantage with photonic hardware.
- Gaussian boson sampling applications proposed for graph problems, such as finding dense subgraphs, and for computing molecular vibronic spectra, which remain research topics.
- Testing complexity-theoretic conjectures.
Limitations and caveats
- No practical application has been shown beyond demonstrations.
- Photon loss makes the problem easier for classical simulation, and several experiments have been matched or approached by classical algorithms.
- It is not a universal quantum computer, and it is not error-corrected.
Common misconceptions
- Boson sampling does not compute permanents on request. It samples from a distribution related to them.
- It does not break cryptography.
- A claimed advantage can be undone by a better classical algorithm, as in some Gaussian boson sampling cases.
How it compares
- Random circuit sampling achieves a similar goal with superconducting qubits and gates.
- Gaussian boson sampling is the practical variant that uses squeezed light and is the basis of Jiuzhang and Xanadu's Borealis.
- Universal photonic computing, as pursued by Xanadu and PsiQuantum, adds error-corrected gates.
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.
Why it matters
Boson sampling was the first problem designed to show quantum advantage with a restricted device and a rigorous complexity argument. It started a research line that includes the Jiuzhang and Borealis experiments, and influenced the design of random circuit sampling.
It also illustrates how theory and experiment interact: hardness arguments assume ideal devices, while noise and loss give classical algorithms openings, which keeps pushing both sides to improve.
Frequently asked questions
What is boson sampling?
A task in which photons pass through a network of beam splitters and the output pattern is measured, with probabilities given by permanents of matrices.
Why is it hard for classical computers?
The probabilities depend on matrix permanents, which are #P-hard to compute, and efficient classical sampling would imply unlikely collapses in complexity theory.
What is Gaussian boson sampling?
A variant in which squeezed light replaces single photons. It is easier to implement and was used in the Jiuzhang and Borealis experiments.
Is boson sampling useful?
Not yet. Proposed uses in chemistry and graph problems are research ideas that have not been shown to beat classical methods.
Has a classical computer reproduced boson sampling results?
Some Gaussian boson sampling experiments have been matched or approximated by classical algorithms that exploit photon loss, so claims have been revised.
Keep learning
- Related algorithm: Random Circuit Sampling (Quantum Supremacy Experiments)
- Related algorithm: Bernstein-Vazirani Algorithm
- Related algorithm: Quantum Walk Algorithms
- Related algorithm: Quantum Annealing
This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.