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:2106.01445

Cracking the Quantum Advantage threshold for Gaussian Boson Sampling

A. S. Popova, A. N. Rubtsov

Published Jun 2, 2021• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2106.01445

Related papers

Cracking the Quantum Advantage Threshold for Gaussian Boson Sampling

A. S. Popova, Alexey N. Rubtsov

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.

Quantum 2.0 Conference and Exhibition•Jan 1, 2022•10 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

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

Gaussian Boson Sampling with Pseudo-Photon-Number-Resolving Detectors and Quantum Computational Advantage

Yu‐Hao Deng, Yi-Chao Gu, Hua-Liang Liu +26 more

We report new Gaussian boson sampling experiments with pseudo-photon-number-resolving detection, which register up to 255 photon-click events. We consider partial photon distinguishability and develop a more complete model for the characterization of the noisy Gaussian boson sampling. In the quantum computational advantage regime, we use Bayesian tests and correlation function analysis to validate the samples against all current classical spoofing mockups. Estimating with the best classical algorithms to date, generating a single ideal sample from the same distribution on the supercomputer Frontier would take $\ensuremath{\sim}600\text{ }\text{ }\mathrm{yr}$ using exact methods, whereas our quantum computer, Ji\ifmmode \check{u}\else \v{u}\fi{}zh\ifmmode \bar{a}\else \={a}\fi{}ng 3.0, takes only $1.27\text{ }\text{ }\mathrm{\ensuremath{\mu}}\mathrm{s}$ to produce a sample. Generating the hardest sample from the experiment using an exact algorithm would take $\mathrm{Frontier}\ensuremath{\sim}3.1\ifmmode\times\else\texttimes\fi{}{10}^{10}\text{ }\text{ }\mathrm{yr}$.

arXiv:2304.12240•Physical Review Letters•Oct 10, 2023•155 citations

Gaussian boson sampling with click-counting detectors

Gabriele Bressanini, Hyukjoon Kwon, M. S. Kim

Gaussian boson sampling constitutes a prime candidate for an experimental demonstration of quantum advantage within reach with current technological capabilities. The original proposal employs photon-number-resolving detectors, however, these are not widely available. Nevertheless, inexpensive threshold detectors can be combined into a single click-counting detector to achieve approximate photon-number resolution. We investigate the problem of sampling from a general multimode Gaussian state using click-counting detectors and show that the probability of obtaining a given outcome is related to a matrix function which is dubbed as the Kensingtonian. We show how the Kensingtonian relates to the Torontonian and the Hafnian, thus bridging the gap between known Gaussian boson sampling variants. We then prove that, under standard complexity-theoretical conjectures, the model cannot be simulated efficiently. Published by the American Physical Society 2024

arXiv:2305.00853•Physical Review A•Feb 12, 2024•2 citations

Gaussian boson sampling with partial distinguishability

Junheng Shi, Tim Byrnes

Gaussian boson sampling (GBS) allows for a way to demonstrate quantum supremacy with the relatively modest experimental resources of squeezed light sources, linear optics, and photon detection. In a realistic experimental setting, numerous effects can modify the complexity of the sampling, in particular loss, partial distinguishability of the photons, and the use of threshold detectors rather than photon counting detectors. In this paper, we investigate GBS with partial distinguishability using an approach based on virtual modes and indistinguishability efficiency. We develop a model using these concepts and derive the probabilities of measuring a specific output pattern from partially distinguishable and lossy GBS for both types of detectors. In the case of threshold detectors, the probability as calculated by the Torontonian is a special case under our framework. By analyzing the expressions of these probabilities we propose an efficient auxiliary classical simulation algorithm which can be used to calculate the probabilities. Our model and the auxiliary algorithm provide foundations for an approximation method for the probability calculation and simulation algorithms not only compatible with existing state-of-the-art simulation algorithms for ideal GBS but also reduce their complexities exponentially depending on the indistinguishability. Using the approximation method and the simulation algorithms we show how the boundary of quantum supremacy in GBS can be pushed further by partial distinguishability.

arXiv:2105.09583•May 20, 2021•3 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.
We report new Gaussian boson sampling experiments with pseudo-photon-number-resolving detection, which register up to 255 photon-click events. We consider partial photon distinguishability and develop a more complete model for the characterization of the noisy Gaussian boson sampling. In the quantum computational advantage regime, we use Bayesian tests and correlation function analysis to validate the samples against all current classical spoofing mockups. Estimating with the best classical algorithms to date, generating a single ideal sample from the same distribution on the supercomputer Frontier would take $\ensuremath{\sim}600\text{ }\text{ }\mathrm{yr}$ using exact methods, whereas our quantum computer, Ji\ifmmode \check{u}\else \v{u}\fi{}zh\ifmmode \bar{a}\else \={a}\fi{}ng 3.0, takes only $1.27\text{ }\text{ }\mathrm{\ensuremath{\mu}}\mathrm{s}$ to produce a sample. Generating the hardest sample from the experiment using an exact algorithm would take $\mathrm{Frontier}\ensuremath{\sim}3.1\ifmmode\times\else\texttimes\fi{}{10}^{10}\text{ }\text{ }\mathrm{yr}$.
Gaussian boson sampling constitutes a prime candidate for an experimental demonstration of quantum advantage within reach with current technological capabilities. The original proposal employs photon-number-resolving detectors, however, these are not widely available. Nevertheless, inexpensive threshold detectors can be combined into a single click-counting detector to achieve approximate photon-number resolution. We investigate the problem of sampling from a general multimode Gaussian state using click-counting detectors and show that the probability of obtaining a given outcome is related to a matrix function which is dubbed as the Kensingtonian. We show how the Kensingtonian relates to the Torontonian and the Hafnian, thus bridging the gap between known Gaussian boson sampling variants. We then prove that, under standard complexity-theoretical conjectures, the model cannot be simulated efficiently. Published by the American Physical Society 2024
Gaussian boson sampling (GBS) allows for a way to demonstrate quantum supremacy with the relatively modest experimental resources of squeezed light sources, linear optics, and photon detection. In a realistic experimental setting, numerous effects can modify the complexity of the sampling, in particular loss, partial distinguishability of the photons, and the use of threshold detectors rather than photon counting detectors. In this paper, we investigate GBS with partial distinguishability using an approach based on virtual modes and indistinguishability efficiency. We develop a model using these concepts and derive the probabilities of measuring a specific output pattern from partially distinguishable and lossy GBS for both types of detectors. In the case of threshold detectors, the probability as calculated by the Torontonian is a special case under our framework. By analyzing the expressions of these probabilities we propose an efficient auxiliary classical simulation algorithm which can be used to calculate the probabilities. Our model and the auxiliary algorithm provide foundations for an approximation method for the probability calculation and simulation algorithms not only compatible with existing state-of-the-art simulation algorithms for ideal GBS but also reduce their complexities exponentially depending on the indistinguishability. Using the approximation method and the simulation algorithms we show how the boundary of quantum supremacy in GBS can be pushed further by partial distinguishability.