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

Efficient approximation of experimental Gaussian boson sampling

Benjamin Villalonga, Murphy Yuezhen Niu, Li Li, Hartmut Neven, John C. Platt, Vadim Smelyanskiy, Sergio Boixo

Published Sep 23, 2021• 16 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2109.11525

Related papers

Training Gaussian boson sampling distributions

Leonardo Banchi, Nicolás Quesada, Juan Miguel Arrazola

Gaussian boson sampling (GBS) is a near-term platform for photonic quantum computing. Applications have been developed that rely on directly programming GBS devices, but the ability to train and optimize circuits has been a key missing ingredient for developing new algorithms. In this work, we derive analytical gradient formulas for the GBS distribution, which can be used for training devices using standard methods based on gradient descent. We introduce a parametrization of the distribution that allows the gradient to be estimated by sampling from the same device that is being optimized. In the case of training using a Kullback-Leibler divergence or log-likelihood cost function, we show that gradients can be computed classically, leading to fast training. We illustrate these results with numerical experiments in stochastic optimization and unsupervised learning. As a particular example, we introduce the variational Ising solver, a hybrid algorithm for training GBS devices to sample ground states of a classical Ising model with high probability.

arXiv:2004.04770•Physical Review A•Jul 15, 2020•33 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

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

Using Gaussian Boson Samplers to Approximate Gaussian Expectation Problems

Jørgen Ellegaard Andersen, Shan Shan

Gaussian Boson Sampling (GBS) have shown advantages over classical methods for performing some specific sampling tasks. To fully harness the computational power of GBS, there has been great interest in identifying their practical applications. In this study, we explore the use of GBS samples for computing a numerical approximation to the Gaussian expectation problem, that is to integrate a multivariate function against a Gaussian distribution. We propose two estimators using GBS samples, and show that they both can bring an exponential speedup over the plain Monte Carlo (MC) estimator. Precisely speaking, the exponential speedup is defined in terms of the guaranteed sample size for these estimators to reach the same level of accuracy $ε$ and the same success probability $δ$ in the $(ε, δ)$ multiplicative error approximation scheme. We prove that there is an open and nonempty subset of the Gaussian expectation problem space for such computational advantage.

arXiv:2502.19336•Feb 26, 2025•0 citations

Experimental Demonstration of Gaussian Boson Sampling with Displacement

Guillaume Thekkadath, S. Sempere-Llagostera, Bryn A. Bell +3 more

Gaussian boson sampling (GBS) is a quantum sampling task in which one has to draw samples from the photon-number distribution of a large-dimensional nonclassical squeezed state of light.In an effort to make this task intractable for a classical computer, experiments building GBS machines have mainly focused on increasing the dimensionality and squeezing strength of the nonclassical light.However, no experiment has yet demonstrated the ability to displace the squeezed state in phase space, which is generally required for practical applications of GBS.In this work, we build a GBS machine that achieves the displacement by injecting a laser beam alongside a two-mode squeezed vacuum state into a 15-mode interferometer.We focus on two new capabilities.Firstly, we use the displacement to reconstruct the multimode Gaussian state at the output of the interferometer.Our reconstruction technique is in situ and requires only three measurement settings regardless of the state dimension.Secondly, we study how the addition of classical laser light in our GBS machine affects the complexity of sampling its output photon statistics.We introduce and validate approximate semiclassical models that reduce the computational cost when a significant fraction of the detected light is classical.

arXiv:2202.00634•PRX Quantum•May 17, 2022•18 citations

Gaussian boson sampling validation via detector binning

Gabriele Bressanini, Benoît Seron, Leonardo Novo +2 more

Gaussian boson sampling (GBS), a computational problem conjectured to be hard to simulate on a classical machine, has been at the forefront of recent years' experimental and theoretical efforts to demonstrate quantum advantage. The classical intractability of the sampling task makes validating these experiments a challenging and essential undertaking. In this paper, we propose binned-detector probability distributions as a suitable quantity to statistically validate GBS experiments employing photon-number-resolving detectors. We show how to compute such distributions by leveraging their connection with their respective characteristic function. The latter may be efficiently and analytically computed for squeezed input states as well as for relevant classical hypothesis like squashed states. Our scheme encompasses other validation methods based on marginal distributions and correlation functions. Additionally, it can accommodate various sources of noise, such as losses and partial distinguishability, a feature that have received limited attention within the GBS framework so far. We also illustrate how binned-detector probability distributions behave when Haar-averaged over all possible interferometric networks, extending known results for Fock boson sampling.

arXiv:2310.18113•Oct 27, 2023•2 citations
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) is a near-term platform for photonic quantum computing. Applications have been developed that rely on directly programming GBS devices, but the ability to train and optimize circuits has been a key missing ingredient for developing new algorithms. In this work, we derive analytical gradient formulas for the GBS distribution, which can be used for training devices using standard methods based on gradient descent. We introduce a parametrization of the distribution that allows the gradient to be estimated by sampling from the same device that is being optimized. In the case of training using a Kullback-Leibler divergence or log-likelihood cost function, we show that gradients can be computed classically, leading to fast training. We illustrate these results with numerical experiments in stochastic optimization and unsupervised learning. As a particular example, we introduce the variational Ising solver, a hybrid algorithm for training GBS devices to sample ground states of a classical Ising model with high probability.
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.
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.
Gaussian Boson Sampling (GBS) have shown advantages over classical methods for performing some specific sampling tasks. To fully harness the computational power of GBS, there has been great interest in identifying their practical applications. In this study, we explore the use of GBS samples for computing a numerical approximation to the Gaussian expectation problem, that is to integrate a multivariate function against a Gaussian distribution. We propose two estimators using GBS samples, and show that they both can bring an exponential speedup over the plain Monte Carlo (MC) estimator. Precisely speaking, the exponential speedup is defined in terms of the guaranteed sample size for these estimators to reach the same level of accuracy εεε and the same success probability δδδ in the (ε,δ)(ε, δ)(ε,δ) multiplicative error approximation scheme. We prove that there is an open and nonempty subset of the Gaussian expectation problem space for such computational advantage.
Gaussian boson sampling (GBS) is a quantum sampling task in which one has to draw samples from the photon-number distribution of a large-dimensional nonclassical squeezed state of light.In an effort to make this task intractable for a classical computer, experiments building GBS machines have mainly focused on increasing the dimensionality and squeezing strength of the nonclassical light.However, no experiment has yet demonstrated the ability to displace the squeezed state in phase space, which is generally required for practical applications of GBS.In this work, we build a GBS machine that achieves the displacement by injecting a laser beam alongside a two-mode squeezed vacuum state into a 15-mode interferometer.We focus on two new capabilities.Firstly, we use the displacement to reconstruct the multimode Gaussian state at the output of the interferometer.Our reconstruction technique is in situ and requires only three measurement settings regardless of the state dimension.Secondly, we study how the addition of classical laser light in our GBS machine affects the complexity of sampling its output photon statistics.We introduce and validate approximate semiclassical models that reduce the computational cost when a significant fraction of the detected light is classical.
Gaussian boson sampling (GBS), a computational problem conjectured to be hard to simulate on a classical machine, has been at the forefront of recent years' experimental and theoretical efforts to demonstrate quantum advantage. The classical intractability of the sampling task makes validating these experiments a challenging and essential undertaking. In this paper, we propose binned-detector probability distributions as a suitable quantity to statistically validate GBS experiments employing photon-number-resolving detectors. We show how to compute such distributions by leveraging their connection with their respective characteristic function. The latter may be efficiently and analytically computed for squeezed input states as well as for relevant classical hypothesis like squashed states. Our scheme encompasses other validation methods based on marginal distributions and correlation functions. Additionally, it can accommodate various sources of noise, such as losses and partial distinguishability, a feature that have received limited attention within the GBS framework so far. We also illustrate how binned-detector probability distributions behave when Haar-averaged over all possible interferometric networks, extending known results for Fock boson sampling.