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• 88 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•0 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•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•0 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•47 citations

Robust quantum computational advantage with programmable 3050-photon Gaussian boson sampling

Hua-Liang Liu, Su, Hao, Si-Qiu Gong +34 more

The creation of large-scale, high-fidelity quantum computers is not only a fundamental scientific endeavour in itself, but also provides increasingly robust proofs of quantum computational advantage (QCA) in the presence of unavoidable noise and the dynamic competition with classical algorithm improvements. To overcome the biggest challenge of photon-based QCA experiments, photon loss, we report new Gaussian boson sampling (GBS) experiments with 1024 high-efficiency squeezed states injected into a hybrid spatial-temporal encoded, 8176-mode, programmable photonic quantum processor, Jiuzhang 4.0, which produces up to 3050 photon detection events. Our experimental results outperform all classical spoofing algorithms, particularly the matrix product state (MPS) method, which was recently proposed to utilise photon loss to reduce the classical simulation complexity of GBS. Using the state-of-the-art MPS algorithm on the most powerful supercomputer EI Capitan, it would take > $10^{42}$ years to construct the required tensor network for simulation, while our Jiuzhang 4.0 quantum computer takes 25.6 $μ$s to produce a sample. This work establishes a new frontier of QCA and paves the way to fault-tolerant photonic quantum computing hardware.

arXiv:2508.09092•Aug 12, 2025•6 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.
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.
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.
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.
The creation of large-scale, high-fidelity quantum computers is not only a fundamental scientific endeavour in itself, but also provides increasingly robust proofs of quantum computational advantage (QCA) in the presence of unavoidable noise and the dynamic competition with classical algorithm improvements. To overcome the biggest challenge of photon-based QCA experiments, photon loss, we report new Gaussian boson sampling (GBS) experiments with 1024 high-efficiency squeezed states injected into a hybrid spatial-temporal encoded, 8176-mode, programmable photonic quantum processor, Jiuzhang 4.0, which produces up to 3050 photon detection events. Our experimental results outperform all classical spoofing algorithms, particularly the matrix product state (MPS) method, which was recently proposed to utilise photon loss to reduce the classical simulation complexity of GBS. Using the state-of-the-art MPS algorithm on the most powerful supercomputer EI Capitan, it would take > 104210^{42}1042 years to construct the required tensor network for simulation, while our Jiuzhang 4.0 quantum computer takes 25.6 μμμs to produce a sample. This work establishes a new frontier of QCA and paves the way to fault-tolerant photonic quantum computing hardware.