Simulating Gaussian boson sampling on graphs in polynomial time

Classical Polynomial‑Time Simulation of Graph‑Based Gaussian Boson Sampling

Gaussian boson sampling (GBS) has been promoted as a leading candidate for demonstrating quantum computational advantage, especially for graph‑theoretic problems such as finding dense subgraphs or detecting cliques. In a recent article published in Quantum (Vol 10, 2268, 2026) a team of computer‑science researchers from Oxford, Georgia Tech, and Edinburgh present a rigorous proof that the specific distributions underlying many GBS‑based graph applications can be sampled efficiently on a classical computer.

Why the Result Matters

The excitement around GBS stems from its ability to encode the adjacency matrix of a graph into the covariance matrix of a set of squeezed‑light modes. Measuring photon‑number outcomes then yields samples from a distribution whose probabilities are related to the hafnian of sub‑matrices—an operation believed to be #P‑hard. If a classical algorithm could reproduce those samples, the claimed quantum advantage for the associated graph problems would evaporate.

The authors show that for a broad class of graph‑derived distributions, the sampling problem reduces to estimating quantities that can be approximated using polynomial‑time Markov‑chain Monte Carlo techniques and known approximation algorithms for the permanent and hafnian. Their analysis builds on earlier work on classical boson‑sampling algorithms (e.g., Clifford & Clifford 2018, 2024) and recent advances in approximating permanents of non‑negative matrices (Jerrum & Sinclair 2004). By constructing an explicit algorithm and proving its runtime scales polynomially with the number of modes, they demonstrate that the quantum‑speedup argument does not hold for these graph applications.

Implications for Quantum Advantage Claims

• Graph problems lose their quantum edge – Tasks such as dense‑subgraph detection, planted‑clique identification, and perfect‑matching counting, which were previously touted as GBS‑friendly, now have known classical alternatives with comparable performance.
• Focus shifts to harder GBS regimes – Researchers may need to target distributions that are provably harder to approximate classically, perhaps by moving beyond unweighted graphs or by incorporating additional non‑Gaussian resources.
• Benchmarking standards must evolve – Future experimental demonstrations of quantum advantage will have to benchmark against the best known classical algorithms, including those derived from this work.

How the Classical Algorithm Works (High‑Level Overview)

1. Graph‑to‑Covariance Mapping – The input graph is encoded into a Gaussian state as usual.
2. Approximate Hafnian Evaluation – Using polynomial‑time approximation schemes for the hafnian of positive‑semidefinite matrices, the algorithm estimates the probabilities of photon‑number patterns.
3. Sampling via MCMC – A Markov chain is constructed whose stationary distribution matches the target GBS distribution; rapid mixing guarantees efficient sampling.
4. Error Bounds – The authors provide rigorous bounds on the total variation distance between the sampled distribution and the true GBS distribution, showing it can be made arbitrarily small with polynomial resources.

Practical Takeaways for Researchers

• Re‑evaluate GBS‑based proposals – Before committing experimental resources, verify whether the targeted graph problem falls within the class covered by the new classical algorithm.
• Explore non‑graph GBS applications – Problems that do not reduce to the studied distributions may still benefit from quantum photonic processors.
• Leverage the algorithm as a benchmark – Implement the classical sampler to set a baseline for any claimed quantum speed‑up in future photonic experiments.

---

The paper’s open‑access status and detailed proofs make it a valuable reference for both theorists and experimentalists seeking a realistic assessment of where quantum advantage truly lies in photonic computing.

---

For further reading, see the original article (doi: https://doi.org/10.22331/q-2026-11-10-2268) and its arXiv preprint (arXiv:2511.16558v3).