Boson Sampling

Imagine shooting individual photons — particles of light — one by one into a network of beam splitters and mirrors. Each beam splitter partly reflects and partly transmits its incoming light. When two photons meet at a beam splitter, something purely quantum happens: they refuse to behave as independent particles. Instead they bunch together, anti-bunch, or interfere in patterns governed by the laws of quantum mechanics.

At the output ports you observe which photons land where. The probability of any particular outcome is linked to a quantity called the permanent of a matrix — a sum over all permutations that looks like a determinant but without the minus signs. Computing permanents is one of the hardest tasks in all of combinatorics.

In 2011, Scott Aaronson and Alex Arkhipov proposed boson sampling as a deliberately minimal quantum experiment: it does not try to be a universal quantum computer. It just routes bosons (here, photons) through a linear-optical network and samples from the resulting distribution. The striking conjecture is that no classical computer can efficiently simulate this sampling, making even small experiments potential demonstrations of quantum advantage beyond anything classical hardware can match.

Boson sampling thus sits at a fascinating crossroads: it is experimentally accessible with today's photonic hardware, yet its output is believed to be classically intractable — a window into the power of quantum mechanics without needing full fault-tolerant qubits.

Below is a tiny boson sampling experiment: 3 photons entering 3 input ports of a linear-optical network. The network is described by a 3×3 unitary matrix (you can randomize it). The simulator computes the exact output probability for every way 3 photons can be distributed across 3 output ports using the permanent of the relevant submatrix.

<p class="hint">{{hint}}</p>
<div class="matrix-area">
  <div class="mat-label">{{mat_label}}</div>
  <div id="matrix-display" class="matrix-grid"></div>
</div>
<div class="btns">
  <button id="randomize" type="button">{{btn_randomize}}</button>
  <button id="hadamard" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="chart-label">{{chart_label}}</div>
<div id="chart" class="chart"></div>
<div class="status" id="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .75rem; line-height: 1.45; }
.matrix-area { margin-bottom: .6rem; }
.mat-label { font-size: .8rem; color: #666; margin-bottom: .3rem; }
.matrix-grid { display: grid; grid-template-columns: repeat(3, 54px); gap: 3px; width: max-content; }
.mat-cell { background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 5px;
            text-align: center; padding: 4px 2px; font: 600 12px ui-monospace, monospace;
            color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .75rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.chart-label { font-size: .8rem; color: #666; margin-bottom: .3rem; }
.chart { display: flex; flex-direction: column; gap: 4px; }
.bar-row { display: flex; align-items: center; gap: 6px; }
.bar-key { font: 600 11px ui-monospace, monospace; color: #1d3557; width: 80px; flex-shrink: 0; text-align: right; }
.bar-track { flex: 1; background: #e8eef3; border-radius: 4px; height: 20px; overflow: hidden; }
.bar-fill { background: #1d3557; height: 100%; border-radius: 4px; transition: width .3s; }
.bar-pct { font: 600 11px ui-monospace, monospace; color: #555; width: 44px; flex-shrink: 0; }
.status { font-size: .85rem; color: #444; margin-top: .5rem; min-height: 1.2em; }

// Code not found

Notice how changing the matrix changes the output distribution dramatically. The permanent calculation here is trivial for 3 photons — but for 50 photons it would require summing over 50! ≈ 3 × $10^{64}$ permutations. That exponential blowup is exactly why classical computers cannot efficiently simulate large boson sampling experiments.

Why is boson sampling believed to be hard for classical computers? The key is the matrix permanent.

• What is a permanent? For an n×n matrix M, its permanent is Σ (over all permutations σ) of the product M[i][σ(i)]. Unlike the determinant, no minus signs appear, so no Gaussian-elimination trick works. Computing the permanent exactly is #P-complete (Valiant, 1979) — as hard as counting the solutions to any NP problem.
• Why does it appear? When n indistinguishable photons enter n input ports and you ask for the probability that each output port receives exactly one photon, the amplitude is |Perm(U_S)|² / n! where U_S is the submatrix of the network's unitary matrix U selected by the input and output modes.
• The hardness argument (Aaronson–Arkhipov, 2011). If there were a classical algorithm that could efficiently sample from the boson sampling distribution (even approximately), then — under two widely-believed conjectures about the permanent — the polynomial hierarchy would collapse to the third level. That is considered extremely unlikely by complexity theorists, so the existence of such an algorithm is conjectured to be false.
• Status: open conjecture. The classical hardness of boson sampling is not a proven theorem — it rests on the conjectures that (1) estimating permanents of random Gaussian matrices is #P-hard even approximately, and (2) the output distribution of a random boson sampler cannot be spoofed efficiently. Disproving either conjecture would remove the complexity argument, but no one has succeeded in doing so.

This places boson sampling in a unique spot: unlike P vs NP, the hardness claim is about sampling rather than decision problems, and it is directly testable with quantum optics hardware. Related problems like counting #P underlie the same mathematical challenge.

Boson sampling started as a theoretical curiosity but has grown into a rich research programme:

• Quantum supremacy benchmarks: experiments by groups at USTC (China, 2020–2022) and elsewhere have run boson sampling variants with 50–100 photons, claiming outputs that classical supercomputers cannot reproduce in practical time.
• Molecular vibronic spectra: the same permanent formula governs the Franck–Condon factors that describe how molecules absorb light and vibrate. A boson sampler can in principle simulate vibronic spectra of molecules — a direct application to quantum chemistry.
• Graph problems via the hafnian: a variant called Gaussian boson sampling computes the hafnian (a relative of the permanent for symmetric matrices), which counts perfect matchings in graphs. This links photonic hardware to combinatorial optimization.
• Randomness certification: the unpredictability of boson sampling outputs can serve as a source of certified quantum randomness, useful in cryptography.
• Foundational tests: boson sampling experiments probe Hong–Ou–Mandel interference (the photon bunching effect) at scale, testing whether quantum mechanics continues to hold in complex multi-photon regimes.

The field is moving fast: each new experiment pushes the photon count higher and sharpens the question of whether classical simulators can ever catch up.

Boson sampling is a beautiful reminder that quantum mechanics is not just strange — it may be computationally powerful in ways classical physics cannot match. A handful of photons routed through a passive optical network can, in principle, produce a distribution whose simulation requires resources that scale exponentially on any classical machine.

The experiment does not need qubits, error correction, or a universal gate set. It needs only indistinguishable photons and well-calibrated beam splitters. And yet the output is connected to one of the hardest computational objects we know — the matrix permanent, a #P-complete quantity tied to counting, permutations, and the deep structure of counting problems.

Whether classical computers will ever find a shortcut to simulate large boson samplers remains an open question, but the burden of proof now lies with the classical side. As photonic hardware matures, boson sampling experiments will keep raising the bar — and keep asking whether quantum computers truly offer an exponential edge.