Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2108.01622 · Science Advances

The boundary for quantum advantage in Gaussian boson sampling

Jacob F. F. Bulmer, Bryn A. Bell, Rachel S. Chadwick, Alex E. Jones, Diana Maria Moise, Alessandro Rigazzi, Jan W. Thorbecke, Utz‐Uwe Haus, Thomas Van Vaerenbergh, Raj B. Patel, Ian A. Walmsley, Anthony Laing

Published Jan 26, 2022• 109 citations
arXivHTMLPDF

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.

DOI
10.1126/sciadv.abl9236

Related papers

Quantum advantage with light

Han-Sen Zhong, Hui Wang, Yu-Hao Deng +21 more

We realize quantum computational advantage in a Gaussian Boson Sampling (GBS) experiment. We inject 25 two mode squeezed states into a 100-mode ultralow-loss interferometer with full connectivity and random matrix. We rule out thermal states, distinguishable photons, and uniform distribution hypotheses. This GBS machine can sample 14 orders of magnitude faster than classical supercomputer.

Quantum Computing, Communication, and Simulation•Mar 4, 2021•0 citations

Gaussian boson sampling: Benchmarking quantum advantage

Ned Goodman, Alexander S. Dellios, Margaret D. Reid +1 more

Quantum computers solve intractable problems which classically require an exponentially long time to compute. With the development of large-scale experiments that claim quantum advantage, a vital issue has now emerged. What are the errors, and how do they affect the complexity of the problem solved? Large-scale Gaussian boson sampling (GBS) experiments give an example in which random numbers are generated. Despite classical hardness, these have computable benchmarks for checking data validity. While there are other quantum computing architectures, Gaussian boson sampling is uniquely testable at all scales. Several large, pioneering quantum computing (QC) experiments have been carried out to investigate quantum advantage. Here, we introduce a highly scalable but classical algorithm that can solve GBS approximately. Our numerical simulation of the output count data is closer to the exact solution than current experiments up to 1152 modes. This algorithm outperforms all previous classical, approximate algorithms and scales efficiently to larger experiments. Our results show that effects beyond losses can cause the errors that allow classical simulability. This work will lead to more precise algorithms and is a step towards understanding how QC quantum advantage is affected by the underlying physics.

quant-pharXiv:2604.12330•Apr 15, 2026•1 citation

A fast and frugal Gaussian Boson Sampling emulator

Tom Dodd, Javier Martínez-Cifuentes, Oliver Thomson Brown +2 more

If classical algorithms have been successful in reproducing the estimation of expectation values of observables of some quantum circuits using off-the-shelf computing resources, matching the performance of the most advanced quantum devices on sampling problems usually requires extreme cost in terms of memory and computing operations, making them accessible to only a handful of supercomputers around the world. In this work, we demonstrate for the first time a classical simulation outperforming Gaussian boson sampling experiments of one hundred modes on established benchmark tests using a single CPU or GPU. Being embarrassingly parallelizable, a small number of CPUs or GPUs allows us to match previous sampling rates that required more than one hundred GPUs. We believe algorithmic and implementation improvements will generalize our tools to photo-counting, single-photon inputs, and pseudo-photon-number-resolving scenarios beyond one thousand modes. Finally, most of the innovations in our tools remain valid for generic probability distributions over binary variables, rendering it potentially applicable to the simulation of qubit-based sampling problems and creating classical surrogates for classical-quantum algorithms.

quant-pharXiv:2511.14923•Science Advances•Nov 20, 2025•9 citations

Speeding up the classical simulation of Gaussian boson sampling with limited connectivity

Tian-Yu Yang, Xiang‐Bin Wang

Abstract Gaussian boson sampling (GBS) plays a crucially important role in demonstrating quantum advantage. As a major imperfection, the limited connectivity of the linear optical network weakens the quantum advantage result in recent experiments. In this work, we introduce an enhanced classical algorithm for simulating GBS processes with limited connectivity. It computes the loop Hafnian of an $$n \times n$$ n×n symmetric matrix with bandwidthwin $$O(nw2^w)$$ O(nw2w) time. It is better than the previous fastest algorithm which runs in $$O(nw^2 2^w)$$ O(nw22w) time. This classical algorithm is helpful on clarifying how limited connectivity affects the computational complexity of GBS and tightening the boundary for achieving quantum advantage in the GBS problem.

arXiv:2311.05355•Scientific Reports•Apr 1, 2024•3 citations

Quadratic Speed-Up for Simulating Gaussian Boson Sampling

Nicolás Quesada, Rachel S. Chadwick, Bryn A. Bell +4 more

We introduce an algorithm for the classical simulation of Gaussian boson sampling that is quadratically faster than previously known methods.The complexity of the algorithm is exponential in the number of photon pairs detected, not the number of photons, and is directly proportional to the time required to calculate a probability amplitude for a pure Gaussian state.The main innovation is to use auxiliary conditioning variables to reduce the problem of sampling to the computation of the pure-state probability amplitudes, for which the most computationally expensive step is the calculation of a loop hafnian.We implement and benchmark an improved loop-hafnian algorithm and show that it can be used to compute pure-state probabilities, the dominant step in the sampling algorithm, of events involving up to 50 photons in a single workstation, i.e., without the need of a supercomputer.

arXiv:2010.15595•PRX Quantum•Jan 11, 2022•57 citations

Quantum computational advantage via high-dimensional Gaussian boson sampling

Abhinav Deshpande, Arthur Mehta, Trevor J. Vincent +10 more

Photonics is a promising platform for demonstrating a quantum computational advantage (QCA) by outperforming the most powerful classical supercomputers on a well-defined computational task. Despite this promise, existing proposals and demonstrations face challenges. Experimentally, current implementations of Gaussian boson sampling (GBS) lack programmability or have prohibitive loss rates. Theoretically, there is a comparative lack of rigorous evidence for the classical hardness of GBS. In this work, we make progress in improving both the theoretical evidence and experimental prospects. We provide evidence for the hardness of GBS, comparable to the strongest theoretical proposals for QCA. We also propose a QCA architecture we call high-dimensional GBS, which is programmable and can be implemented with low loss using few optical components. We show that particular algorithms for simulating GBS are outperformed by high-dimensional GBS experiments at modest system sizes. This work thus opens the path to demonstrating QCA with programmable photonic processors.

arXiv:2102.12474•Science Advances•Jan 5, 2022•139 citations
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.
Quantum computers solve intractable problems which classically require an exponentially long time to compute. With the development of large-scale experiments that claim quantum advantage, a vital issue has now emerged. What are the errors, and how do they affect the complexity of the problem solved? Large-scale Gaussian boson sampling (GBS) experiments give an example in which random numbers are generated. Despite classical hardness, these have computable benchmarks for checking data validity. While there are other quantum computing architectures, Gaussian boson sampling is uniquely testable at all scales. Several large, pioneering quantum computing (QC) experiments have been carried out to investigate quantum advantage. Here, we introduce a highly scalable but classical algorithm that can solve GBS approximately. Our numerical simulation of the output count data is closer to the exact solution than current experiments up to 1152 modes. This algorithm outperforms all previous classical, approximate algorithms and scales efficiently to larger experiments. Our results show that effects beyond losses can cause the errors that allow classical simulability. This work will lead to more precise algorithms and is a step towards understanding how QC quantum advantage is affected by the underlying physics.
If classical algorithms have been successful in reproducing the estimation of expectation values of observables of some quantum circuits using off-the-shelf computing resources, matching the performance of the most advanced quantum devices on sampling problems usually requires extreme cost in terms of memory and computing operations, making them accessible to only a handful of supercomputers around the world. In this work, we demonstrate for the first time a classical simulation outperforming Gaussian boson sampling experiments of one hundred modes on established benchmark tests using a single CPU or GPU. Being embarrassingly parallelizable, a small number of CPUs or GPUs allows us to match previous sampling rates that required more than one hundred GPUs. We believe algorithmic and implementation improvements will generalize our tools to photo-counting, single-photon inputs, and pseudo-photon-number-resolving scenarios beyond one thousand modes. Finally, most of the innovations in our tools remain valid for generic probability distributions over binary variables, rendering it potentially applicable to the simulation of qubit-based sampling problems and creating classical surrogates for classical-quantum algorithms.
Abstract Gaussian boson sampling (GBS) plays a crucially important role in demonstrating quantum advantage. As a major imperfection, the limited connectivity of the linear optical network weakens the quantum advantage result in recent experiments. In this work, we introduce an enhanced classical algorithm for simulating GBS processes with limited connectivity. It computes the loop Hafnian of an n×nn \times nn×n n×n symmetric matrix with bandwidthwin O(nw2w)O(nw2^w)O(nw2w) O(nw2w) time. It is better than the previous fastest algorithm which runs in O(nw22w)O(nw^2 2^w)O(nw22w) O(nw22w) time. This classical algorithm is helpful on clarifying how limited connectivity affects the computational complexity of GBS and tightening the boundary for achieving quantum advantage in the GBS problem.
We introduce an algorithm for the classical simulation of Gaussian boson sampling that is quadratically faster than previously known methods.The complexity of the algorithm is exponential in the number of photon pairs detected, not the number of photons, and is directly proportional to the time required to calculate a probability amplitude for a pure Gaussian state.The main innovation is to use auxiliary conditioning variables to reduce the problem of sampling to the computation of the pure-state probability amplitudes, for which the most computationally expensive step is the calculation of a loop hafnian.We implement and benchmark an improved loop-hafnian algorithm and show that it can be used to compute pure-state probabilities, the dominant step in the sampling algorithm, of events involving up to 50 photons in a single workstation, i.e., without the need of a supercomputer.
Photonics is a promising platform for demonstrating a quantum computational advantage (QCA) by outperforming the most powerful classical supercomputers on a well-defined computational task. Despite this promise, existing proposals and demonstrations face challenges. Experimentally, current implementations of Gaussian boson sampling (GBS) lack programmability or have prohibitive loss rates. Theoretically, there is a comparative lack of rigorous evidence for the classical hardness of GBS. In this work, we make progress in improving both the theoretical evidence and experimental prospects. We provide evidence for the hardness of GBS, comparable to the strongest theoretical proposals for QCA. We also propose a QCA architecture we call high-dimensional GBS, which is programmable and can be implemented with low loss using few optical components. We show that particular algorithms for simulating GBS are outperformed by high-dimensional GBS experiments at modest system sizes. This work thus opens the path to demonstrating QCA with programmable photonic processors.