CoChat
Sign Up
Cited by 88Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum many-body systems

The boundary for quantum advantage in Gaussian boson sampling

Open access
Bulmer, Jacob F. F., Bell, Bryn A., Chadwick, Rachel S., Jones, Alex E., Moise, Diana, Rigazzi, Alessandro, Thorbecke, Jan, Haus, Utz-Uwe +4 more·2022·Science Advances
DOI 10.1126/sciadv.abl9236PMC PMC8791606
Open this paper in CoChat — free account

Abstract

Identifying the boundary beyond which quantum machines provide a computational advantage over their classical counterparts is a crucial step in charting their usefulness. Gaussian boson sampling (GBS), in which photons are measured from a highly entangled Gaussian state, is a leading approach in pursuing quantum advantage. State-of-the-art GBS experiments that run in minutes would require 600 million years to simulate using the best preexisting classical algorithms. Here, we present faster classical GBS simulation methods, including speed and accuracy improvements to the calculation of loop hafnians. We test these on a ∼100,000-core supercomputer to emulate GBS experiments with up to 100 modes and up to 92 photons. This reduces the simulation time for state-of-the-art GBS experiments to several months, a nine–orders of magnitude improvement over previous estimates. Last, we introduce a distribution that is efficient to sample from classically and that passes a variety of GBS validation methods.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1126/sciadv.abl9236

Cites

5 of 5 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The best-known algorithm to simulate GBS scales with the total number of modes and the time it takes to calculate a probability amplitude of a pure-state GBS instance.

    “The best-known algorithm to simulate GBS30,34 scales with the total number of modes and the time it takes to calculate a probability amplitude of a pure-state GBS instance.”

    From Quantum computational advantage with a programmable photonic processor (2022) · cites this paper as [30]

  • On average, it would take more than 9,000 years for the best available algorithms and supercomputers to produce, using exact methods, a single sample from the programmed distribution.

    “On average, it would take more than 9,000 years for the best available algorithms and supercomputers to produce, using exact methods, a single sample from the programmed distribution”

    From Quantum computational advantage with a programmable photonic processor (2022) · cites this paper as [30]

    The Results (Benchmarking; page not provided) estimate seconds per sample for the paper’s simulated GBS systems, potentially milliseconds on Fugaku. The Discussion (page not provided) mentions programmability as a possible feature of future experiments, but our copy does not identify the claimed programmed distribution or give a 9,000-year estimate for an exact sample from it. Searched for the 9,000-year estimate and programmed distribution. (LLM, conf=0.78)

    Experimental — accuracy not yet measured

  • Borealis uses 216 independent quantum systems to achieve quantum computational advantage, placing it well beyond the capabilities of current state-of-the-art classical simulation algorithms.

    “Borealis uses 216 independent quantum systems to achieve quantum computational advantage, placing it well beyond the capabilities of current state-of-the-art classical simulation algorithms30.”

    From Quantum computational advantage with a programmable photonic processor (2022) · cites this paper as [30]

    The Introduction discusses a different experiment, Jiŭzhāng, with 100 optical modes. Searches for Borealis and 216 independent quantum systems found no passage in our copy addressing Borealis’s system count or its claimed advantage over classical simulation algorithms. (LLM, conf=0.76)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 32

  1. [1]S. Aaronson, A. Arkhipov, The computational complexity of linear optics, in Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing (ACM, 2011), pp. 333–342.
  2. [2]A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O’Brien, T. C. Ralph, Boson sampling from a Gaussian state. Phys. Rev. Lett. 113, 100502 (2014). 25238340
  3. [3]C. S. Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, I. Jex, Gaussian boson sampling. Phys. Rev. Lett. 119, 170501 (2017). 29219463
  4. [5]N. Quesada, Franck-Condon factors by counting perfect matchings of graphs with loops. J. Chem. Phys. 150, 164113 (2019). 31042916
  5. [8]D. Grier, D. J. Brod, J. M. Arrazola, M. B. de Andre Alonso, N. Quesada, The complexity of bipartite Gaussian boson sampling. arXiv: 2110.06964 [quant-ph] (13 October 2021). · arXiv
  6. [9]N. Quesada, R. S. Chadwick, B. A. Bell, J. M. Arrazola, T. Vincent, H. Qi, R. García-Patrón, Quadratic speedup for simulating Gaussian boson sampling. arXiv: 2010.15595 [quant-ph] (29 October 2020). · arXiv
  7. [11]N. Quesada, J. M. Arrazola, Exact simulation of Gaussian boson sampling in polynomial space and exponential time. Phys. Rev. Res. 2, 023005 (2020).
  8. [12]B. Wu, B. Cheng, F. Jia, J. Zhang, M.-H. Yung, X. Sun, Speedup in classical simulation of Gaussian boson sampling. Sci. Bull. 65, 832– 841 (2020). 36659202
  9. [13]B. Gupt, J. M. Arrazola, N. Quesada, T. R. Bromley, Classical benchmarking of Gaussian Boson Sampling on the Titan supercomputer. Quantum Inf. Process 19, 249 (2020).
  10. [14]A. Serafini, Quantum Continuous Variables (CRC Press, 2017).
  11. [15]H. J. Ryser, Combinatorial Mathematics (Mathematical Association of America, 1963), vol. 14.
  12. [16]V. S. Shchesnovich, Asymptotic evaluation of bosonic probability amplitudes in linear unitary networks in the case of large number of bosons. Int. J. Quantum Inf. 11, 1350045 (2013).
  13. [17]M. Tichy, “Entanglement and interference of identical particles,” thesis, Albert-Ludwigs-Universität Freiburg, Freiburg (2011).
  14. [18]S. Chin, J. Huh, Generalized concurrence in boson sampling. Sci. Rep. 8, 6101 (2018). 29666423 PMC5904218
  15. [22]K. Balasubramanian, “Combinatorics and diagonals of matrices,” thesis, Indian Statistical Institute, Calcutta (1980).
  16. [25]O. F. Thomas, W. McCutcheon, D. P. S. McCutcheon, A general framework for multimode Gaussian quantum optics and photo-detection: Application to Hong–Ou–Mandel interference with filtered heralded single photon sources. APL Photonics 6, 040801 (2021).
  17. [27]J. S. Liu, Monte Carlo Strategies in Scientific Computing (Springer Publishing Company Incorporated, 2008).
  18. [28]L. Devroye, Nonuniform random variate generation, in Handbooks in Operations Research and Management Science, S. G. Henderson, B. L. Nelson, Eds. (Elsevier, 2006), vol. 13, pp. 83–122.
  19. [31]B. Villalonga, M. Y. Niu, L. Li, H. Neven, J. C. Platt, V. N. Smelyanskiy, S. Boixo, Efficient approximation of experimental Gaussian boson sampling. arXiv: 2109.11525 [quant-ph] (23 September 2021). · arXiv
  20. [32]J. J. Renema, A. Menssen, W. R. Clements, G. Triginer, W. S. Kolthammer, I. A. Walmsley, Efficient classical algorithm for boson sampling with partially distinguishable photons. Phys. Rev. Lett. 120, 220502 (2018). 29906153
  21. [33]A. E. Moylett, R. García-Patrón, J. J. Renema, P. S. Turner, Classically simulating near-term partially-distinguishable and lossy boson sampling. Quantum Sci. Technol. 5, 015001 (2020).
  22. [34]R. García-Patrón, J. J. Renema, V. Shchesnovich, Simulating boson sampling in lossy architectures. Quantum 3, 169 (2019).
  23. [35]D. J. Brod, M. Oszmaniec, Classical simulation of linear optics subject to nonuniform losses. Quantum 4, 267 (2020).
  24. [36]J. Shi, T. Byrnes, Gaussian boson sampling with partial distinguishability. arXiv: 2105.09583 [quant-ph] (20 May 2021). · arXiv
  25. [37]N. Quesada, L. G. Helt, J. Izaac, J. M. Arrazola, R. Shahrokhshahi, C. R. Myers, K. K. Sabapathy, Simulating realistic non-Gaussian state preparation. Phys. Rev. A 100, 022341 (2019).
  26. [40]J. E. Gentle, Computational Statistics (Springer, 2009), vol. 308.
  27. [41]P. Clifford, R. Clifford, The classical complexity of boson sampling, in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM, 2018), pp. 146–155.
  28. [43]B. Gupt, J. Izaac, N. Quesada, The Walrus: A library for the calculation of hafnians, Hermite polynomials and Gaussian boson sampling. J. Open Source Softw. 4, 1705 (2019).
  29. [44]S. K. Lam, A. Pitrou, S. Seibert, Numba: A llvmbased python jit compiler, in Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC (Association for Computing Machinery, 2015), pp. 1–6.
  30. [46]L. Latmiral, N. Spagnolo, F. Sciarrino, Towards quantum supremacy with lossy scattershot boson sampling. New J. Phys. 18, 113008 (2016).
  31. [47]P. Clifford, R. Clifford, Faster classical Boson Sampling. arXiv: 2005.04214 [quant-ph] (7 May 2020). · arXiv
  32. [49]D. S. Phillips, M. Walschaers, J. J. Renema, I. A. Walmsley, N. Treps, J. Sperling, Benchmarking of Gaussian boson sampling using two-point correlators. Phys. Rev. A 99, 023836 (2019).

Cited by

Sorted by citations

Authors
Bulmer, J. F. F., Bell, B. A., Chadwick, R. S., Jones, A. E., Moise, D., Rigazzi, A., Thorbecke, J., Haus, U.-U., Van Vaerenbergh, T., Patel, R. B., Walmsley, I. A., & Laing, A.
Affiliations
  • University of Bristol (GB)
  • Imperial College London (GB)
  • Hewlett Packard Enterprise, Zurich, Switzerland.
  • Hewlett-Packard (Netherlands) (NL)
  • HPE HPC/AI EMEA Research Lab, Wallisellen, Switzerland.
  • Hewlett Packard Labs, HPE Belgium, Diegem, Belgium.
  • University of Oxford (GB)
Corresponding author
  • Bulmer, Jacob F. F.
  • Bell, Bryn A.
  • Laing, Anthony
ORCID
Venue
Science Advances
Publisher
American Association for the Advancement of Science (AAAS)
Published
2022-01-28
Volume
8
Issue
4
Pages
eabl9236-eabl9236
ISSN
2375-2548 (ISSN-L)
DOI
10.1126/sciadv.abl9236
PMC
PMC8791606
OpenAlex
W3193169079
Cited by
88
References
5
Citations by year
2026: 10 · 2025: 18 · 2024: 19 · 2023: 23 · 2022: 15 · 2021: 3
FWCI
6.17
Type
journal article
Language
en
Open access
Licence
cc-by
Locations
  • Science Advances (publishedVersion, cc-by)
  • PubMed Central (publishedVersion, cc-by)
  • PubMed (publishedVersion)
  • Explore Bristol Research (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • Bristol Research (University of Bristol) (submittedVersion, cc-by)
  • Griffith Research Online (submittedVersion, cc-by)
  • arXiv (Cornell University) (cc-by)
Funders
  • Met Office
  • Engineering and Physical Sciences Research Council (EP/T001062/1, EP/T022078/1, T001062, EP/N003470/1)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
Keywords
Gaussian boson sampling, quantum advantage, classical simulation of quantum circuits, supercomputer simulation, photon number distribution

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review