Simulating Gaussian boson sampling on graphs in polynomial time
Konrad Anand, Zongchen Chen, Mary Cryan, Graham Freifeld, Leslie Ann Goldberg, Heng Guo, Xinyuan Zhang
arXiv:2511.165589.2h-index: 42
Predicted impact top 34% in QUANT-PH · last 90 daysOriginality Incremental advance
AI Analysis
For researchers in quantum computing and graph theory, this work rules out exponential quantum advantage for a class of GBS-based graph problems.
The authors show that a distribution related to Gaussian Boson Sampling on graphs can be sampled classically in polynomial time, implying no exponential quantum speedup for graphical applications of GBS.
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.