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.10070 · 中国科学通报:英文版

Speedup in classical simulation of Gaussian boson sampling

Bujiao Wu, Bin Cheng, Fei Jia, Jialin Zhang, Man‐Hong Yung, Xiaoming Sun

Published Feb 19, 2020• 18 citations
arXivHTMLPDF
DOI
10.1016/j.scib.2020.02.012

Related papers

Classical simulations of Gaussian boson sampling

Rachel S. Chadwick

•Jan 1, 2022•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•Quantum•Nov 21, 2025•1 citation

Classical algorithm for simulating experimental Gaussian boson sampling

Changhun Oh, Minzhao Liu, Yuri Alexeev +2 more

arXiv:2306.03709•Nature Physics•Jun 25, 2024•99 citations

Extended validations on photon number resolving detector based Gaussian boson sampling to evaluate noise levels

Yang Ji, Yongzheng Wu, Shi Wang +3 more

Abstract Gaussian boson sampling (GBS) is a variety of boson sampling overcoming the stable single-photon preparation difficulty of the later. However, like those in the original version, noises in GBS will also result in the deviation of output distributions and the reduction of classical simulation complexity. We extend the pattern recognition validation, together with the correlation validation as a comparison, on GBS using photon number resolving detectors, with noises of both photon loss and distinguishability, to quantificationally evaluate noise levels. As for the classical simulation with noises to be used during validations, it is actually a simulation of mixed states where noises have been proved to be possibly utilized to realize computation speedup. Furthermore, we use an output-binning strategy to realize validation speedup. Our work indicates that the pattern recognition protocol is useful for noise evaluations of GBS even when noises are sufficiently low.

arXiv:2510.06300•Physica Scripta•Sep 16, 2026•0 citations

Experimental Gaussian Boson sampling

Han-Sen Zhong, Li-Chao Peng, Yuan Li +15 more

arXiv:1905.00170•中国科学通报:英文版•Apr 1, 2019•78 citations

Gaussian-boson-sampling-enhanced dense subgraph finding shows limited advantage over efficient classical algorithms

Naomi R. Solomons, O. Thomas, Dara P. S. McCutcheon

Recent claims of achieving exponential quantum advantage have attracted attention to Gaussian boson sampling (GBS), a potential application of which is dense subgraph finding. We investigate the effects of sources of error including loss and spectral impurity on GBS applied to dense subgraph finding algorithms. We find that the effectiveness of these algorithms is remarkably robust to errors, to such an extent that there exist efficient classical algorithms that can simulate the underlying GBS. These results imply that the speedup of GBS-based algorithms for the dense subgraph problem over classical approaches is at most polynomial, though this could be achieved on a quantum device with dramatically less stringent requirements on loss and photon purity than general GBS.

arXiv:2301.13217•Jan 30, 2023•4 citations
Abstract Gaussian boson sampling (GBS) is a variety of boson sampling overcoming the stable single-photon preparation difficulty of the later. However, like those in the original version, noises in GBS will also result in the deviation of output distributions and the reduction of classical simulation complexity. We extend the pattern recognition validation, together with the correlation validation as a comparison, on GBS using photon number resolving detectors, with noises of both photon loss and distinguishability, to quantificationally evaluate noise levels. As for the classical simulation with noises to be used during validations, it is actually a simulation of mixed states where noises have been proved to be possibly utilized to realize computation speedup. Furthermore, we use an output-binning strategy to realize validation speedup. Our work indicates that the pattern recognition protocol is useful for noise evaluations of GBS even when noises are sufficiently low.
Recent claims of achieving exponential quantum advantage have attracted attention to Gaussian boson sampling (GBS), a potential application of which is dense subgraph finding. We investigate the effects of sources of error including loss and spectral impurity on GBS applied to dense subgraph finding algorithms. We find that the effectiveness of these algorithms is remarkably robust to errors, to such an extent that there exist efficient classical algorithms that can simulate the underlying GBS. These results imply that the speedup of GBS-based algorithms for the dense subgraph problem over classical approaches is at most polynomial, though this could be achieved on a quantum device with dramatically less stringent requirements on loss and photon purity than general GBS.