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

Quantum 2.0 Conference and Exhibition

Cracking the Quantum Advantage Threshold for Gaussian Boson Sampling

A. S. Popova, Alexey N. Rubtsov

Published Jan 1, 2022• 10 citations
Publisher

Abstract

Here we challenge the quantum advantage claimed for the Gaussian Boson Sampling experiment by introducing an approximate polynomial-time algorithm. Our fourth-order approximation gives an accuracy comparable with that of the experiment.
DOI
10.1364/quantum.2022.qw2a.15

Related papers

Cracking the Quantum Advantage threshold for Gaussian Boson Sampling

A. S. Popova, A. N. Rubtsov

Scientists in quantum technology aspire to quantum advantage: a computational result unattainable with classical computers. Gaussian boson sampling experiment has been already claimed to achieve this goal. In this setup squeezed light states interfere in a mid-sized linear optical network, where multi-photon collisions take place. The exact simulation of the counting statistics of $n$ threshold detectors is far beyond the possibilities of modern supercomputers once $n$ exceeds $100$. Here we challenge quantum advantage for a mid-sized Gaussian boson sampling setup and propose the approximate algorithm to obtain the probability of any specific measurement outcome. For an 70-mode device on a laptop, our approximation achieves accuracy competitive with the experimental one.

arXiv:2106.01445•Jun 2, 2021•3 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•0 citations

Simulating Gaussian boson sampling on graphs in polynomial time

Konrad Anand, Zongchen Chen, Mary Cryan +4 more

We show that a distribution related to Gaussian Boson Sampling (GBS) on graphs can be sampled classically in polynomial time. Graphical applications of GBS typically sample from this distribution, and thus quantum algorithms do not provide exponential speedup for these applications. We also show that another distribution related to Boson sampling can be sampled classically in polynomial time.

quant-pharXiv:2511.16558•Nov 21, 2025•0 citations

The boundary for quantum advantage in Gaussian boson sampling

Jacob F. F. Bulmer, Bryn A. Bell, Rachel S. Chadwick +9 more

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.

arXiv:2108.01622•Science Advances•Jan 26, 2022•88 citations

Efficient sampling from shallow Gaussian quantum-optical circuits with local interactions

Haoyu Qi, Diego Cifuentes, Kamil Brádler +3 more

Gaussian boson sampling is a candidate model for demonstrating quantum computational advantage in photonic systems. Here, the authors narrow down the range of possible architectures for such a demonstration, by introducing a classical algorithm that can simulate optical systems with shallow-depth circuits and local gates in polynomial time.

Physical Review A•May 6, 2022•12 citations

Estimating the Percentage of GBS Advantage in Gaussian Expectation Problems

Jørgen Ellegaard Andersen, Shan Shan

Gaussian Boson Sampling (GBS), which can be realized with a photonic quantum computing model, perform some special kind of sampling tasks. In [4], we introduced algorithms that use GBS samples to approximate Gaussian expectation problems. We found a non-empty open subset of the problem space where these algorithms achieve exponential speedup over the standard Monte Carlo (MC) method. This speedup is defined in terms of the guaranteed sample size to reach the same accuracy $ε$ and success probability $δ$ under the $(ε, δ)$ multiplicative error approximation scheme. In this paper, we enhance our original approach by optimizing the average photon number in the GBS distribution to match the specific Gaussian expectation problem. We provide updated estimates of the guaranteed sample size for these improved algorithms and quantify the proportion of problem space where they outperform MC. Numerical results indicate that the proportion of the problem space where our improved algorithms have an advantage is substantial, and the advantage gained is significant. Notably, for certain special cases, our methods consistently outperform MC across nearly 100\% of the problem space.

arXiv:2502.19362•Feb 26, 2025•0 citations
Scientists in quantum technology aspire to quantum advantage: a computational result unattainable with classical computers. Gaussian boson sampling experiment has been already claimed to achieve this goal. In this setup squeezed light states interfere in a mid-sized linear optical network, where multi-photon collisions take place. The exact simulation of the counting statistics of nnn threshold detectors is far beyond the possibilities of modern supercomputers once nnn exceeds 100100100. Here we challenge quantum advantage for a mid-sized Gaussian boson sampling setup and propose the approximate algorithm to obtain the probability of any specific measurement outcome. For an 70-mode device on a laptop, our approximation achieves accuracy competitive with the experimental one.
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.
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.
Gaussian Boson Sampling (GBS), which can be realized with a photonic quantum computing model, perform some special kind of sampling tasks. In [4], we introduced algorithms that use GBS samples to approximate Gaussian expectation problems. We found a non-empty open subset of the problem space where these algorithms achieve exponential speedup over the standard Monte Carlo (MC) method. This speedup is defined in terms of the guaranteed sample size to reach the same accuracy εεε and success probability δδδ under the (ε,δ)(ε, δ)(ε,δ) multiplicative error approximation scheme. In this paper, we enhance our original approach by optimizing the average photon number in the GBS distribution to match the specific Gaussian expectation problem. We provide updated estimates of the guaranteed sample size for these improved algorithms and quantify the proportion of problem space where they outperform MC. Numerical results indicate that the proportion of the problem space where our improved algorithms have an advantage is substantial, and the advantage gained is significant. Notably, for certain special cases, our methods consistently outperform MC across nearly 100\% of the problem space.