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

Lecture notes in computer science

Simulating Sparse and Shallow Gaussian Boson Sampling

Zoltán Kolarovszki, Ágoston Kaposi, Tamás Kozsik, Zoltán Zimborás

Published Jan 1, 2023• 3 citations
Publisher
DOI
10.1007/978-3-031-36030-5_17

Related papers

Classical simulations of Gaussian boson sampling

Rachel S. Chadwick

•Jan 1, 2022•0 citations

Speedup in classical simulation of Gaussian boson sampling

Bujiao Wu, Bin Cheng, Fei Jia +3 more

arXiv:1908.10070•中国科学通报:英文版•Feb 19, 2020•18 citations

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

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

Efficient sampling from shallow Gaussian quantum-optical circuits with local interactions

Haoyu Qi, Diego Cifuentes, Kamil Brádler +3 more

Gaussian boson sampling is a candidate model for demonstrating quantum computational advantage in photonic systems. Here, the authors narrow down the range of possible architectures for such a demonstration, by introducing a classical algorithm that can simulate optical systems with shallow-depth circuits and local gates in polynomial time.

arXiv:2009.11824•Physical Review A•May 6, 2022•15 citations

On computational complexity and average-case hardness of shallow-depth boson sampling

Byeongseon Go, Changhun Oh, Hyunseok Jeong

Boson Sampling, a computational task believed to be classically hard to simulate, is expected to hold promise for demonstrating quantum computational advantage using near-term quantum devices. However, noise in experimental implementations poses a significant challenge, potentially rendering Boson Sampling classically simulable and compromising its classical intractability. Numerous studies have proposed classical algorithms that can efficiently simulate Boson Sampling under various noise models, particularly as noise rates increase with circuit depth. To address this challenge, we investigate the viability of achieving quantum computational advantage through Boson Sampling implemented with shallow-depth linear optical circuits. In particular, as the average-case hardness of estimating output probabilities of Boson Sampling is a crucial ingredient in demonstrating its classical intractability, we make progress on establishing the average-case hardness of Boson Sampling confined to logarithmic-depth regimes. We also obtain the average-case hardness for logarithmic-depth Fock-state Boson Sampling subject to lossy environments and for the logarithmic-depth Gaussian Boson Sampling. By providing complexity-theoretical backgrounds for the classical simulation hardness of logarithmic-depth Boson Sampling, we expect that our findings will mark a crucial step towards a more noise-tolerant demonstration of quantum advantage with shallow-depth Boson Sampling.

arXiv:2405.01786•Quantum•Mar 13, 2026•6 citations
Boson Sampling, a computational task believed to be classically hard to simulate, is expected to hold promise for demonstrating quantum computational advantage using near-term quantum devices. However, noise in experimental implementations poses a significant challenge, potentially rendering Boson Sampling classically simulable and compromising its classical intractability. Numerous studies have proposed classical algorithms that can efficiently simulate Boson Sampling under various noise models, particularly as noise rates increase with circuit depth. To address this challenge, we investigate the viability of achieving quantum computational advantage through Boson Sampling implemented with shallow-depth linear optical circuits. In particular, as the average-case hardness of estimating output probabilities of Boson Sampling is a crucial ingredient in demonstrating its classical intractability, we make progress on establishing the average-case hardness of Boson Sampling confined to logarithmic-depth regimes. We also obtain the average-case hardness for logarithmic-depth Fock-state Boson Sampling subject to lossy environments and for the logarithmic-depth Gaussian Boson Sampling. By providing complexity-theoretical backgrounds for the classical simulation hardness of logarithmic-depth Boson Sampling, we expect that our findings will mark a crucial step towards a more noise-tolerant demonstration of quantum advantage with shallow-depth Boson Sampling.