Boson sampling and Gaussian boson sampling
Algorithms and benchmarks / Sampling and quantum advantage tests
Photons sent through a large network of beam splitters produce output patterns whose probabilities are very hard to compute classically. It was proposed to show a quantum computational advantage with linear optics.
- Era
- Noisy intermediate-scale (NISQ)
- Problem class
- Sampling and quantum advantage tests
- Speedup
- Exact classical sampling would collapse the polynomial hierarchy (Aaronson and Arkhipov 2010); the approximate case rests on conjectures.
How it works
Single photons (boson sampling) or squeezed light (Gaussian boson sampling) enter an interferometer; photon-number detectors record which outputs fire; the probabilities relate to matrix permanents or hafnians.
Typical use cases
- Demonstrations of quantum advantage.
- Proposed uses in graph problems and molecular vibronic spectra, without verified advantage.
Resource estimates
No resource estimate with stated assumptions was verified for this family in this release.
Demonstrations
- 2022: Gaussian boson sampling on 216 squeezed modes with events of up to 219 photons and a mean of 125; 36 microseconds per sample against an estimate of more than 9,000 years with exact classical methods. (L. S. Madsen et al. 2022)
Hardware platforms that fit
- Photonic qubits: Native to photonic processors: Borealis performed Gaussian boson sampling on 216 squeezed modes (Madsen et al. 2022).
What you need to run it
- Classical simulation
- Small instances on a laptop with Perceval or The Walrus; the classical cost grows exponentially with the number of photons.
- Noisy hardware (NISQ)
- A photonic processor with low-loss interferometers, bright single-photon or squeezed-light sources and photon-number-resolving detectors; loss is the main limitation.
- Fault-tolerant machine
- Not applicable for this family.
- Annealer or analogue simulator
- Not applicable for this family.
Calculate the memory of a simulation
Where to run it in Europe
Photonic qubits
- Lucy (France; Inaugurated, per the EuroHPC JU): Photonic; digital quantum computer. Access: EuroHPC JU call for quantum access in pilot mode. Deployment milestones Lucy
- France Hybrid HPC Quantum Initiative (HQI) platform (France; In operation, per the source): Hybrid HPC–quantum platform coupled to the Joliot-Curie supercomputer: Ruby (analogue neutral-atom system controlling 100 rubidium atoms), Lucy (12-photon photonic QPU) and Qaptiva QPU emulation. Access: GENCI eDARI resource allocation requests. Deployment milestones France Hybrid HPC Quantum Initiative (HQI) platform
The full infrastructure catalogue · The infrastructure deployment tracker
Software
European tools in the software directory
Other open-source frameworks
- Strawberry Fields (Xanadu (Canada); non-European)
- The Walrus (Xanadu (Canada); non-European)
A listing is not an endorsement; check each tool for the features you need.
Limitations and open questions
- Advantage claims compare with specific classical methods; approximate classical simulators keep improving.
- The task itself has no confirmed practical application yet.
In the Quantum Algorithm Zoo
No matching Zoo entry was found on 23 October 2026; the Zoo lists algorithms with a proven or conjectured speedup, not this family.
Index: the Quantum Algorithm Zoo by Stephen P. Jordan, last updated 2026-09-10, checked 2026-10-23. The portal links to it and copies no description from it. Browse the full Quantum Algorithm Zoo (external site)
Named in European procurements
- Used in: EuroHPC procurement EuroQCS-France (now Lucy) (Required in the benchmark suite (scored under the award criteria))
As the tender documents state; how a benchmark is weighted against others is described in each procurement.
Sources
- S. Aaronson, A. Arkhipov (2010). The Computational Complexity of Linear Optics. arXiv:1011.3245 (2010). Read: abstract page, retrieved 2026-10-23.
- C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, I. Jex (2017). Gaussian Boson Sampling. Phys. Rev. Lett. 119, 170501 (2017); arXiv:1612.01199. Read: abstract page, retrieved 2026-10-23.
- L. S. Madsen et al. (2022). Quantum computational advantage with a programmable photonic processor. Nature 606, 75 (2022), open access (CC BY 4.0) in PubMed Central. Read: abstract page, retrieved 2026-10-23.