Classical boson sampling algorithms with superior performance to near-term experiments

Alex Neville, Chris Sparrow, Raphael Clifford, Eric Johnston, Patrick Birchall, Ashley Montanaro, Anthony Laing*

*Corresponding author for this work

Research output: Contribution to journalArticle (Academic Journal)peer-review

128 Citations (Scopus)
561 Downloads (Pure)


It is predicted that quantum computers will dramatically outperform their conventional counterparts. However, large-scale universal quantum computers are yet to be built. Boson sampling is a rudimentary quantum algorithm tailored to the platform of linear optics, which has sparked interest as a rapid way to demonstrate such quantum supremacy. Photon statistics are governed by intractable matrix functions, which suggests that sampling from the distribution obtained by injecting photons into a linear optical network could be solved more quickly by a photonic experiment than by a classical computer. The apparently low resource requirements for large boson sampling experiments have raised expectations of a near-term demonstration of quantum supremacy by boson sampling. Here we present classical boson sampling algorithms and theoretical analyses of prospects for scaling boson sampling experiments, showing that near-term quantum supremacy via boson sampling is unlikely. Our classical algorithm, based on Metropolised independence sampling, allowed the boson sampling problem to be solved for 30 photons with standard computing hardware. Compared to current experiments, a demonstration of quantum supremacy over a successful implementation of these classical methods on a supercomputer would require the number of photons and experimental components to increase by orders of magnitude, while tackling exponentially scaling photon loss.

Original languageEnglish
Pages (from-to)1153-1157
Number of pages5
JournalNature Physics
Issue number12
Early online date2 Oct 2017
Publication statusPublished - 1 Dec 2017

Structured keywords

  • QITG
  • Bristol Quantum Information Institute
  • QETLabs


Dive into the research topics of 'Classical boson sampling algorithms with superior performance to near-term experiments'. Together they form a unique fingerprint.

Cite this