Boson Sampling
A restricted photonic model whose output distribution is classically hard to sample, offering evidence for quantum computational advantage.
The setup
Boson sampling sends n indistinguishable single photons into an m-mode linear optical network (a mesh of beam splitters and phase shifters) and measures how many photons emerge from each output mode. The network implements a unitary transformation on the modes. Because photons are bosons, their amplitudes interfere in a way governed by matrix permanents.
Permanents and hardness
The probability of a given output configuration is proportional to the squared modulus of the permanent of a submatrix of the network unitary. The permanent is like a determinant but without alternating signs, and computing it is #P-hard, believed far harder than any polynomial-time task. This links the output distribution of a simple optical experiment to a provably difficult counting problem.
Why it matters
- No universal quantum computer is needed: only linear optics, single photons, and photon-counting detectors.
- Sampling from the exact distribution efficiently would collapse parts of the classical complexity hierarchy, considered highly unlikely.
- It provided an early, physically accessible route to demonstrating quantum advantage.
What it is not
Boson sampling is not universal quantum computation: it cannot run arbitrary algorithms, has no error correction, and produces samples rather than answers to decision problems. Its purpose is narrow but sharp: to exhibit a task that quantum hardware performs and classical hardware plausibly cannot at scale. Verifying the output for large instances is itself hard, a subtlety in claiming advantage.
Realizations
Practical demonstrations use scattershot and Gaussian variants to raise photon rates; see Gaussian boson sampling. Photonic advantage experiments reported sampling from distributions estimated to be intractable for classical supercomputers, complementing the superconducting random circuit sampling approach. Both are sampling-based advantage claims rather than useful computations, and both have prompted improved classical algorithms that narrow the claimed gap.