A key quantum algorithm may not beat classical computers on graphs

Konrad Anand of the University of Oxford, Zongchen Chen of the Georgia Institute of Technology, and colleagues report in the journal Quantum that a key distribution used in Gaussian Boson Sampling (GBS) can be classically simulated in polynomial time. This finding challenges expectations of exponential speedup from quantum algorithms when applied to graph-based problems, a prominent area for demonstrating quantum computational advantage. The researchers also demonstrated polynomial-time classical simulation for a second distribution related to Boson sampling, indicating a broader limitation than previously understood for graphical applications of GBS.

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

Graphical applications of Gaussian boson sampling (GBS) do not offer a quantum speedup, according to new work published in Quantum, volume 10, page 2268 (2026). This simulation capability directly impacts the viability of GBS for solving graph-related problems, a prominent area of investigation for the algorithm. The work builds on previous research into the computational complexity of linear optics and the development of efficient sampling methods for Boson sampling distributions, referencing the 2013 work by Scott Aaronson and Alex Arkhipov.

The team’s approach circumvents the expected exponential scaling of computational resources required to simulate quantum systems, a hurdle that has long been a central challenge in verifying quantum advantage. Previously, researchers like Hamilton, Sansoni, Barkhofen, Silberhorn, and Jex detailed studies of Gaussian boson sampling, while Zhong, Wang, Deng, and colleagues reported quantum computational advantage using photons.

The demonstrated classical simulation relies on algorithmic techniques that efficiently approximate the probability distributions generated by GBS on graphs, effectively mimicking the quantum process without requiring a quantum computer. However, their main graph applications can be simulated classically in polynomial time. The study’s methodology involved developing a classical algorithm that efficiently samples from the output distribution of GBS on graphs. This algorithm uses mathematical properties of the graph structure to reduce the computational complexity of the simulation, enabling it to run in polynomial time with respect to the number of nodes in the graph.

More like this

Quantum PhysicsNew X-ray technique maps dopants in quantum silicon without damage

Quantum AlgorithmsAqarios joins HyQInt project to link simulation to quantum optimizers

Quantum PhysicsNew asymmetry measure stays within the Gaussian quantum manifold

PhysicsUniversity of Waterloo summer research links quantum effects to neurons