Boson Sampling

Boson sampling, introduced by Aaronson and Arkhipov, is the most physically transparent route to sampling-based quantum advantage. It needs no universal quantum computer — only single photons, passive linear optics, and photon detectors — yet sampling from its output is classically hard because the output amplitudes are permanents of complex matrices, a $\#\mathsf{P}$ -hard quantity. This lesson describes the setup and the hardness argument.

The physical setup

Send $n$ identical single photons into $n$ of the $m$ input modes (waveguides or beam paths) of a large passive linear-optical network — an interferometer built from beam splitters and phase shifters, with $m = \Theta(n^2)$ modes. The network implements an $m \times m$ unitary $U$ on the mode (creation-operator) space:

a_j^\dagger \ \longmapsto\ \sum_k U_{kj}\, a_k^\dagger .

At the output, detectors count photons per mode. We sample the output configuration $S = (s_1,\dots,s_m)$ with $\sum_k s_k = n$ . There is no entangling gate, no measurement-and-feedforward, no adaptivity — just photons through a fixed linear network. This is far less than universal quantum computation, which is exactly what makes the hardness result surprising and the experiment relatively accessible.

Why the permanent appears

For bosons, transition amplitudes add over indistinguishable paths with all-positive combinatorial weights, and the symmetric structure of multi-photon interference produces the permanent rather than the determinant. For the collision-free case (at most one photon per output mode), the amplitude to go from the input occupation to an output configuration $S$ is

\langle S | \varphi(U) | T \rangle = \mathrm{Per}(U_{S,T}),

where $U_{S,T}$ is the $n\times n$ submatrix of $U$ selected by the occupied input/output modes, and

\mathrm{Per}(A) = \sum_{\sigma \in \mathfrak{S}_n} \prod_{i=1}^{n} A_{i,\sigma(i)} .

The permanent looks like the determinant but without the alternating signs — and that small change is catastrophic for computation. Computing the permanent of a $0/1$ matrix is $\#\mathsf{P}$ -complete (Valiant's theorem); the determinant, by contrast, is computable in polynomial time by Gaussian elimination. The sign structure that makes the determinant easy is precisely what is absent for bosons.

The hardness argument

The reasoning mirrors the previous lesson's $\mathsf{PH}$ -collapse template, specialized to permanents:

Output probabilities are $|\mathrm{Per}(A)|^2$ for $A$ an $n\times n$ submatrix of the Haar-random interferometer unitary; for $m \gg n^2$ these submatrices are close to i.i.d. complex Gaussian matrices.
Computing the permanent exactly is $\#\mathsf{P}$ -hard (worst case, Valiant).
Average-case hardness and anticoncentration of $|\mathrm{Per}|^2$ over Gaussian matrices are conjectured (PGC + an anticoncentration conjecture).
Granting these, an efficient classical approximate sampler would let Stockmeyer's algorithm approximate a $\#\mathsf{P}$ -hard permanent inside $\mathsf{PH}$ , collapsing the polynomial hierarchy — assumed impossible.

So, under PGC and anticoncentration, no efficient classical algorithm samples from the boson-sampling distribution.

Variants and experiments

The pure linear-optics scheme demands deterministic single photons, which are hard to produce. The practical workhorse is Gaussian boson sampling (GBS), which injects squeezed-vacuum states instead of Fock states; its output probabilities are governed by the Hafnian (a permanent-like object that also counts perfect matchings), still $\#\mathsf{P}$ -hard. GBS underlies the photonic advantage demonstrations (e.g. the Jiuzhang experiments) reporting samples from $\sim 50$ – $100$ detected photons across hundreds of modes.

Caveats, shared with all sampling supremacy

Boson sampling inherits the same conditional status as random-circuit sampling: the hardness rests on unproven average-case conjectures (PGC, anticoncentration), and noise and photon loss degrade the distribution toward something classically simulable — classical spoofing algorithms exploiting loss and partial distinguishability have repeatedly contested experimental claims. Its scientific value is as a clean, hardware-light demonstration that the gap between quantum reality and classical simulation is real, tied to one of the most studied hard problems in counting complexity, the permanent.

Takeaways

Boson sampling shows that non-universal, passive linear optics already produces classically hard sampling, because indistinguishable-boson interference computes matrix permanents. The determinant-to-permanent distinction — one sign flip — is the entire reason, separating a $\mathsf{P}$ problem from a $\#\mathsf{P}$ -hard one and grounding photonic quantum advantage in counting complexity.