Quantum Algorithms

Gaussian Boson Sampling

A photonic sampling model using squeezed light instead of single photons, easier to scale and tied to matrix hafnians.

Squeezed light as input

Standard boson sampling requires many identical single photons produced simultaneously, which is experimentally demanding. Gaussian boson sampling (GBS) replaces single photons with squeezed states of light, a Gaussian resource that can be generated deterministically. The squeezed modes pass through a linear interferometer and are measured with photon-number-resolving detectors.

Hafnians

Kronos motion — pid vs model

Where standard boson sampling probabilities involve matrix permanents, GBS probabilities involve the hafnian of a matrix built from the interferometer and the squeezing. The hafnian counts perfect matchings of a graph and, like the permanent, is #P-hard to compute. This preserves the classical hardness that makes the model a candidate for demonstrating quantum advantage.

Advantages over single-photon sampling

Squeezed states are produced deterministically, improving scalability.
Higher effective photon rates enable larger instances.
The hafnian connection links GBS to graph problems and molecular vibronic spectra.

Applications beyond advantage

Unlike pure advantage demonstrations, GBS has proposed applications. Because hafnians count perfect matchings, GBS can heuristically sample dense subgraphs and estimate graph similarity, and it maps naturally onto certain molecular vibronic spectrum calculations. These are heuristic uses whose practical value over classical methods is still being assessed, not proven speedups.

Experimental status

Photonic platforms have reported GBS with tens to over a hundred detected photons across many modes, with output distributions argued to be classically intractable to sample. As with all sampling-based claims, verification at scale is difficult and improved classical spoofing and simulation algorithms continue to test the boundary. GBS and superconducting random circuit sampling are the two main experimental pillars of near-term quantum advantage claims.