-- Quantum Physics arXiv:2511.16558 (quant-ph) [Submitted on Nov 20, 2025 (v1), last revised Jun 25, 2026 (v2)]
Title: Polynomial Time Simulation of Gaussian Boson Sampling
Authors: Konrad Anand, Zongchen Chen, Mary Cryan, Graham Freifeld, Leslie Ann Goldberg, Heng Guo, Xinyuan Zhang
Abstract: 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.
Comments: 11 pages, 2 figures
Subjects: Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS)
Cite as: arXiv:2511.16558 [quant-ph] (or arXiv:2511.16558v2 [quant-ph] for this version)
Blogger's Review: This paper bridges the gap between quantum and classical computation, showing that Gaussian boson sampling can be simulated classically in polynomial time. This finding challenges the current understanding of quantum advantage and may lead to new balances between quantum and classical algorithms. Its implications on applications and theoretical significance should not be underestimated.