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:1908.08068 · Physical Review Research

Exact simulation of Gaussian boson sampling in polynomial space and exponential time

Nicolás Quesada, Juan Miguel Arrazola

Published Apr 3, 2020• 55 citations
arXivHTMLPDF

Abstract

This work introduces a classical algorithm that can simulate the output of a Gaussian Boson Sampling device in time exponential in the number of photons detected and in only polynomial space in the number of modes/photons. The algorithm takes advantage of the fact that the marginal Wigner functions of Gaussian states can be easily calculated.

DOI
10.1103/physrevresearch.2.023005

Related papers

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

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

On classical simulation algorithms for noisy Boson Sampling

Changhun Oh, Liang Jiang, Bill Fefferman

We present a classical algorithm that approximately samples from the output distribution of certain noisy Boson Sampling experiments. This algorithm is inspired by a recent result of Aharonov, Gao, Landau, Liu and Vazirani and makes use of an observation originally due to Kalai and Kindler that the output probability of Boson Sampling experiments with a Gaussian noise model can be approximated by sparse low-degree polynomials. This observation alone does not suffice for classical sampling, because its marginal probabilities might not be approximated by sparse low-degree polynomials, and furthermore, the approximated probabilities might be negative. We solve this problem by employing the first quantization representation to give an algorithm for computing the marginal probabilities of these experiments. We prove that when the overall noise rate is constant, the algorithm runs in time quasi-polynomial in the number of input photons $N$ and accuracy. When the overall noise rate scales as $1-x_1^γ$ for constant $x_1$ and $γ=Ω(\log N)$, the running time becomes polynomial. Furthermore, we study noisy Boson Sampling with practically relevant noise models such as partial distinguishability and photon loss. We show that the same technique does not immediately apply in these settings, leaving open the possibility of a scalable demonstration of noisy quantum advantage for these noise models in certain parameter regimes.

arXiv:2301.11532•Jan 27, 2023•3 citations

Efficient approximation of experimental Gaussian boson sampling

Benjamin Villalonga, Murphy Yuezhen Niu, Li Li +4 more

Two recent landmark experiments have performed Gaussian boson sampling (GBS) with a non-programmable linear interferometer and threshold detectors on up to 144 output modes (see Refs.~\onlinecite{zhong_quantum_2020,zhong2021phase}). Here we give classical sampling algorithms with better total variation distance and Kullback-Leibler divergence than these experiments and a computational cost quadratic in the number of modes. Our method samples from a distribution that approximates the single-mode and two-mode ideal marginals of the given Gaussian boson sampler, which are calculated efficiently. One implementation sets the parameters of a Boltzmann machine from the calculated marginals using a mean field solution. This is a 2nd order approximation, with the uniform and thermal approximations corresponding to the 0th and 1st order, respectively. The $k$th order approximation reproduces Ursell functions (also known as connected correlations) up to order $k$ with a cost exponential in $k$ and high precision, while the experiment exhibits higher order Ursell functions with lower precision. This methodology, like other polynomial approximations introduced previously, does not apply to random circuit sampling because the $k$th order approximation would simply result in the uniform distribution, in contrast to GBS.

arXiv:2109.11525•Sep 23, 2021•16 citations

Classical Algorithms for Function Computation in Gaussian Boson Sampling

Ruoting Dou, Hao Zhan, Shengjun Wu +2 more

Gaussian boson sampling (GBS) seeks quantum advantage by sampling photon-number patterns generated with squeezed inputs and passive linear optics. Many proposed GBS applications instead target function computation by applying functions to mode-resolved photon-number outcomes---a natural form of experimental postprocessing that produces classical outputs. Sampling hardness alone, however, does not determine the complexity of these tasks. By analyzing the irreducible decomposition of fixed-photon-number operator spaces, we prove that the expectation value of every such function in the average case over passive linear-optical networks can be classically evaluated for inputs with finite squeezing strength. We also provide a classical algorithm that estimates this value to inverse-polynomial additive error. The result provides new theoretical tools for analyzing linear-optical quantum systems, helps clarify the origin of current GBS hardness evidence, and inspires new applications of GBS with genuine quantum advantages.

quant-pharXiv:2609.38882•Oct 1, 2026•0 citations

Classical Modeling of a Lossy Gaussian Bosonic Sampler

Mikhail V. Umanskii, Alexey N. Rubtsov

Gaussian boson sampling (GBS) is considered a candidate problem for demonstrating quantum advantage. We propose an algorithm for the approximate classical simulation of a lossy GBS instance. The algorithm relies on the Taylor series expansion, and increasing the number of terms of the expansion that are used in the calculation yields greater accuracy. The complexity of the algorithm is polynomial in the number of modes given the number of terms is fixed. We describe conditions for the input state squeezing parameter and loss level that provide the best efficiency for this algorithm (by efficient, we mean that the Taylor series converges quickly). In recent experiments that claim to have demonstrated quantum advantage, these conditions are satisfied; thus, this algorithm can be used to classically simulate these experiments.

Entropy•Jun 5, 2024•0 citations
This work introduces a classical algorithm that can simulate the output of a Gaussian Boson Sampling device in time exponential in the number of photons detected and in only polynomial space in the number of modes/photons. The algorithm takes advantage of the fact that the marginal Wigner functions of Gaussian states can be easily calculated.
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.
We present a classical algorithm that approximately samples from the output distribution of certain noisy Boson Sampling experiments. This algorithm is inspired by a recent result of Aharonov, Gao, Landau, Liu and Vazirani and makes use of an observation originally due to Kalai and Kindler that the output probability of Boson Sampling experiments with a Gaussian noise model can be approximated by sparse low-degree polynomials. This observation alone does not suffice for classical sampling, because its marginal probabilities might not be approximated by sparse low-degree polynomials, and furthermore, the approximated probabilities might be negative. We solve this problem by employing the first quantization representation to give an algorithm for computing the marginal probabilities of these experiments. We prove that when the overall noise rate is constant, the algorithm runs in time quasi-polynomial in the number of input photons NNN and accuracy. When the overall noise rate scales as 1−x1γ1-x_1^γ1−x1γ​ for constant x1x_1x1​ and γ=Ω(log⁡N)γ=Ω(\log N)γ=Ω(logN), the running time becomes polynomial. Furthermore, we study noisy Boson Sampling with practically relevant noise models such as partial distinguishability and photon loss. We show that the same technique does not immediately apply in these settings, leaving open the possibility of a scalable demonstration of noisy quantum advantage for these noise models in certain parameter regimes.
Two recent landmark experiments have performed Gaussian boson sampling (GBS) with a non-programmable linear interferometer and threshold detectors on up to 144 output modes (see Refs.~\onlinecite{zhong_quantum_2020,zhong2021phase}). Here we give classical sampling algorithms with better total variation distance and Kullback-Leibler divergence than these experiments and a computational cost quadratic in the number of modes. Our method samples from a distribution that approximates the single-mode and two-mode ideal marginals of the given Gaussian boson sampler, which are calculated efficiently. One implementation sets the parameters of a Boltzmann machine from the calculated marginals using a mean field solution. This is a 2nd order approximation, with the uniform and thermal approximations corresponding to the 0th and 1st order, respectively. The kkkth order approximation reproduces Ursell functions (also known as connected correlations) up to order kkk with a cost exponential in kkk and high precision, while the experiment exhibits higher order Ursell functions with lower precision. This methodology, like other polynomial approximations introduced previously, does not apply to random circuit sampling because the kkkth order approximation would simply result in the uniform distribution, in contrast to GBS.
Gaussian boson sampling (GBS) seeks quantum advantage by sampling photon-number patterns generated with squeezed inputs and passive linear optics. Many proposed GBS applications instead target function computation by applying functions to mode-resolved photon-number outcomes---a natural form of experimental postprocessing that produces classical outputs. Sampling hardness alone, however, does not determine the complexity of these tasks. By analyzing the irreducible decomposition of fixed-photon-number operator spaces, we prove that the expectation value of every such function in the average case over passive linear-optical networks can be classically evaluated for inputs with finite squeezing strength. We also provide a classical algorithm that estimates this value to inverse-polynomial additive error. The result provides new theoretical tools for analyzing linear-optical quantum systems, helps clarify the origin of current GBS hardness evidence, and inspires new applications of GBS with genuine quantum advantages.
Gaussian boson sampling (GBS) is considered a candidate problem for demonstrating quantum advantage. We propose an algorithm for the approximate classical simulation of a lossy GBS instance. The algorithm relies on the Taylor series expansion, and increasing the number of terms of the expansion that are used in the calculation yields greater accuracy. The complexity of the algorithm is polynomial in the number of modes given the number of terms is fixed. We describe conditions for the input state squeezing parameter and loss level that provide the best efficiency for this algorithm (by efficient, we mean that the Taylor series converges quickly). In recent experiments that claim to have demonstrated quantum advantage, these conditions are satisfied; thus, this algorithm can be used to classically simulate these experiments.