Boson sampling is a deliberately restricted quantum-computation model. It does not implement arbitrary quantum algorithms. Instead, indistinguishable photons pass through a passive linear-optical interferometer, and the computer’s output is a random photon-count pattern whose probabilities are governed by matrix permanents.
The model matters because its hardware is conceptually simple—single photons, beam splitters, phase shifters and photodetectors—while the resulting probability distribution is connected to a classically difficult algebraic quantity. Aaronson and Arkhipov showed that an efficient classical sampler for the ideal distribution would have surprising consequences in complexity theory, and argued approximate sampling is also hard under additional conjectures. [1]
This guide develops the transition-amplitude formula, explains why the permanent appears instead of the determinant, works through Hong–Ou–Mandel cancellation as a two-photon permanent, and separates proven mathematics from conjecture-dependent quantum-advantage claims.
Prepare indistinguishable bosons → apply a linear-optical unitary → count output occupation → evaluate amplitudes by permanents → sample from the resulting distribution.
1. The physical model
Take m optical modes. Prepare n single photons in selected input modes, often one photon per occupied mode with n≤m.
A passive interferometer implements an m×m unitary matrix U using beam splitters and phase shifters.
At the output, number-resolving detectors measure the occupation pattern
t=(t₁,t₂,…,t_m)
with Σtj=n when there is no loss.
The computational task is to draw samples from the exact or approximate output distribution generated by this experiment.
2. Linear optics acts linearly on creation operators
Let ai† create one photon in input mode i and bj† create one photon in output mode j.
A passive interferometer transforms creation operators as
a_i† → Σ_j U_{ji} b_j†.
Because U is unitary, canonical bosonic commutation relations are preserved and total photon number is conserved.
The transformation is simple at the operator level. Complexity emerges when many identical photons make all path assignments interfere coherently.
3. Why identical bosons add amplitudes over permutations
Suppose n photons enter distinct input modes i₁,…,in and we ask for one photon in each of distinct output modes j₁,…,jn.
There are n! assignments pairing the input photons with output modes.
Because the photons are indistinguishable bosons, these assignments are not distinguishable alternatives whose probabilities should be added. Their quantum amplitudes are added first.
For permutation σ∈Sn, one assignment contributes
∏_{k=1}^n U_{j_k,i_{σ(k)}}.
Summing all permutations gives the permanent.
4. Matrix permanent
For an n×n matrix A,
Per(A)=Σ_{σ∈S_n}∏_{k=1}^n A_{k,σ(k)}.
This looks almost identical to a determinant:
det(A)=Σ_σ sgn(σ)∏_k A_{k,σ(k)}.
The permanent has no alternating permutation sign. That missing sign is exactly what makes it natural for symmetric bosonic amplitudes.
5. Fermions would produce determinants
Exchanging two identical fermions changes the wavefunction sign. Their multiparticle amplitudes are antisymmetrised and determinants appear naturally.
Exchanging identical bosons does not introduce the minus sign. Their amplitudes are symmetrised, producing permanents.
The permanent/determinant distinction is therefore not arbitrary linear algebra. It encodes particle-exchange statistics.
6. Transition amplitude with collisions
Let the input occupation be s=(s₁,…,sm) and output occupation t=(t₁,…,tm) with equal total photon number n.
Construct an n×n matrix Us,t by repeating input columns according to s and output rows according to t.
The Fock transition amplitude is
⟨t|Û|s⟩=Per(U_{s,t}) / √(∏_i s_i! ∏_j t_j!).
The probability is the squared magnitude of this amplitude.
The factorials are essential when two or more photons occupy the same mode because Fock states contain √(n!) normalisation factors.
7. Worked two-photon beam splitter: coincidence amplitude
Use the balanced beam-splitter matrix
U=(1/√2)[[1,1],[1,-1]].
Input |1,1⟩ asks for one photon in each input mode. The coincidence output |1,1⟩ uses U itself.
The permanent is
Per(U)=U₁₁U₂₂+U₁₂U₂₁=(-1/2)+(1/2)=0.
Therefore the coincidence probability is zero.
This is the Hong–Ou–Mandel cancellation from Guide 39 written as one 2×2 permanent.
8. Worked bunching amplitude
Now ask for output |2,0⟩. Repeat the first output row twice:
U_{s,t}=(1/√2)[[1,1],[1,1]].
Its permanent is
1/2+1/2=1.
The denominator contains √(2!) from the two output photons, so the amplitude is 1/√2 and the probability is 1/2.
The other bunching outcome |0,2⟩ also has probability 1/2. The probabilities sum to one.
9. Three-photon permanent
For a 3×3 submatrix A,
Per(A)=A11A22A33+A11A23A32+A12A21A33+A12A23A31+A13A21A32+A13A22A31.
There are 3!=6 terms. For n photons the direct definition contains n! products.
Ryser’s classical algorithm evaluates an n×n permanent in roughly O(n2ⁿ) arithmetic operations, much faster than n! enumeration but still exponential in n.
10. Permanent computation is #P-hard
Valiant proved that computing the permanent of a 0–1 matrix exactly is #P-complete. [2]
This is a major contrast with determinants, which are computable in polynomial time by Gaussian elimination or related methods.
Boson sampling exploits the appearance of permanents in amplitudes, but “permanent is hard” alone is not enough to prove that sampling from the complete optical distribution is classically hard. Complexity reductions must connect a hypothetical sampler to permanent estimation under specific approximation assumptions.
11. Exact boson-sampling hardness evidence
Aaronson and Arkhipov showed that if a polynomial-time classical algorithm could exactly sample from the boson-sampling distribution under their model, then unlikely complexity-class consequences would follow, including a collapse of the polynomial hierarchy under standard complexity assumptions.
This is conditional evidence, not an unconditional proof that no efficient classical sampler exists.
The distinction mirrors Guide 28: complexity theory often supports quantum advantage through implications and conjectures rather than resolved separations such as P≠BQP.
12. Approximate sampling is the experimentally relevant problem
No experiment samples an exact mathematical distribution. Loss, source impurity, distinguishability and detector error perturb the probabilities.
Therefore the key theoretical question is whether a classical computer can efficiently sample from a distribution close to ideal boson sampling in total variation distance.
Aaronson and Arkhipov’s approximate-hardness argument relies on additional unproven conjectures about permanents of Gaussian random matrices and anti-concentration. [1]
Those conjectures must be named when making a rigorous advantage claim.
13. Total variation distance
For discrete distributions P and Q, total variation distance is
D_TV(P,Q)=(1/2)Σ_x |P(x)−Q(x)|.
It equals the largest possible difference in probability that P and Q assign to the same event.
An approximate sampler guarantees a sample distribution Q whose DTV from target P is below a specified ε.
14. Collision-free versus collision events
A collision-free output has at most one photon per mode. A collision event has some tj≥2.
The original complexity arguments often focus on regimes where m is sufficiently larger than n² so collisions are relatively rare, simplifying the connection to Gaussian submatrices.
Modern photonic experiments can operate in collision-rich regimes as well, but the statistical and complexity analysis changes accordingly.
15. Birthday-paradox intuition
If n particles were placed independently and uniformly into m modes, collisions would become likely when n is comparable with √m.
Bosonic interference changes the exact distribution, but the same scale motivates choosing m much larger than n² when one wants a sparse collision-free regime.
Mode count is therefore an algorithmic parameter, not just empty optical hardware.
16. Photon distinguishability weakens permanent interference
The permanent formula assumes photons are indistinguishable in all unmeasured degrees of freedom.
If photon wavepackets carry distinguishable spectral, temporal or polarisation labels, different path assignments are only partially coherent.
Transition probabilities then involve weighted sums of permutation terms determined by the photons’ internal-state Gram matrix rather than one simple permanent squared.
Hong–Ou–Mandel visibility provides a pairwise diagnostic, but large-n indistinguishability is a genuinely many-body calibration problem.
17. Loss changes the sample space
In ideal boson sampling, total detected photon number equals n. Real photons can be lost in sources, interferometers or detectors.
Postselecting only no-loss events can restore an idealised n-photon sample but may make the accepted rate exponentially small if per-photon transmission is poor.
Lossy boson-sampling models keep events with fewer detected photons and ask whether hardness survives at realistic loss rates. The answer depends on how loss scales with n.
18. Worked survival-rate estimate
Suppose each of n=30 photons survives source, circuit and detection with independent probability η=0.8.
The probability all 30 survive is
0.8^30≈0.001238.
Only about 0.124% of trials retain all photons.
If the source repetition rate is 1 MHz and every trial otherwise succeeds, the raw all-survival ceiling is only about 1238 samples/s before source-generation probability and processing dead time are included.
19. Verification is difficult because exact probabilities are difficult
To verify that a device samples from the correct distribution, one might try to compute many target probabilities and compare frequencies.
But those probabilities contain the very permanents believed to be hard to compute at large n.
Experimental validation therefore uses indirect statistical tests, smaller classically tractable instances, cross-entropy-like estimators, likelihood ratios against specific spoofing models and hardware calibration.
Passing one validation test does not prove closeness against every possible adversarial classical distribution.
20. Boson sampling is not universal quantum computation
The standard model uses a fixed passive interferometer followed by nonadaptive photon counting. It does not implement arbitrary gates on arbitrary logical qubits.
Its value is narrower: it isolates a sampling task for which quantum interference naturally computes amplitudes associated with classically difficult combinatorics.
A device can therefore demonstrate a meaningful sampling advantage without being a general-purpose quantum computer.
21. Gaussian boson sampling
Gaussian boson sampling changes the input resource. Instead of n deterministic single photons, one commonly injects squeezed Gaussian states into a linear interferometer and performs photon counting.
Output probabilities are connected to matrix hafnians rather than ordinary permanents in the zero-displacement setting, with loop hafnians appearing when displacement is included.
The hafnian sums over perfect pairings rather than permutations, matching the pair-creation structure of squeezed vacuum.
Gaussian boson sampling is therefore related to, but mathematically distinct from, Aaronson–Arkhipov single-photon boson sampling.
22. Hafnian definition
For a symmetric 2n×2n matrix A with zero diagonal, the hafnian is
Haf(A)=Σ_matchings ∏_{(i,j) in matching} A_ij.
The sum runs over all perfect pairings of the 2n indices.
This contrasts with the permanent, which sums over all bijections between two index sets. Different photonic source structure therefore selects a different combinatorial matrix function.
23. Threshold detectors versus number-resolving detectors
An ideal boson-sampling outcome records exact occupation number in every mode. A threshold detector only says click/no-click.
If collisions are negligible, threshold detection approximates number resolution because every occupied mode likely contains one photon.
In collision-rich Gaussian boson sampling, exact number resolution carries much more information and the theoretical output formula depends on which detector model is used.
24. Common misconception: a photonic chip explicitly calculates a permanent and prints it
The device samples photon occupations. Permanents appear in the amplitudes governing those probabilities. Extracting one permanent numerically from samples can itself require many repetitions and statistical inference.
25. Common misconception: #P-hard permanents prove unconditional quantum advantage
Permanent hardness is one ingredient. Sampling-hardness conclusions additionally rely on complexity reductions, approximation notions and, for the strongest approximate claims, conjectures such as average-case permanent hardness and anti-concentration.
26. Common misconception: more photons always make a stronger demonstration
More photons increase ideal computational difficulty but also amplify loss, distinguishability error, multiphoton-source contamination and verification difficulty. Useful scale is a joint hardware-and-complexity question.
27. Worked synthesis problem
Two indistinguishable photons enter a balanced beam splitter, one per input mode.
Step 1: Interferometer matrix.
U=(1/√2)[[1,1],[1,-1]].
Step 2: Coincidence permanent.
Per(U)=0.
Therefore P(1,1)=0.
Step 3: Bunched output. For t=(2,0), repeat row one. The permanent is 1 and the Fock normalisation denominator is √2, so P(2,0)=1/2.
Step 4: Other port. P(0,2)=1/2.
Step 5: Complexity lesson. At n=2 the permanent is trivial to calculate. Boson-sampling complexity comes from scaling this symmetrised path interference to many photons and modes while retaining low loss and high indistinguishability.
28. Practice set
- What hardware primitives define standard boson sampling?
- How does passive linear optics transform creation operators?
- Why are amplitudes summed over permutations?
- Define the permanent.
- What is the difference between permanent and determinant?
- Write the general Fock transition amplitude including factorial normalisation.
- Why does the balanced-beam-splitter |1,1⟩ coincidence permanent vanish?
- What classical complexity class is exact 0–1 permanent computation complete for?
- Why does that fact alone not prove sampling hardness?
- What does total variation distance measure?
- What experimental imperfection breaks ideal permanent interference most directly?
- What matrix function appears in zero-displacement Gaussian boson sampling?
Answers
- Indistinguishable photon sources, a passive linear-optical interferometer and photon-counting detectors.
a_i†→Σ_jU_ji b_j†.- Indistinguishable bosons make different input-output assignments coherent alternatives.
Σ_σ∏_kA_{kσ(k)}.- The determinant multiplies each permutation term by its sign; the permanent does not.
Per(U_{s,t})/√(∏s_i!∏t_j!).- The two permutation amplitudes are +1/2 and −1/2 and cancel.
- #P.
- A sampling algorithm need not explicitly output individual permanents; a reduction is needed to connect efficient sampling to unlikely complexity consequences.
- The maximum event-probability discrepancy between two distributions, equivalently half their L1 distance.
- Photon distinguishability, along with loss and source/detector imperfections.
- The hafnian.
Sources and further study
[1] Scott Aaronson and Alex Arkhipov, The Computational Complexity of Linear Optics. The foundational boson-sampling complexity paper and source of the approximate-hardness conjectures.
[2] Leslie G. Valiant, The Complexity of Computing the Permanent, Theoretical Computer Science 8, 189–201 (1979). The foundational #P-completeness result for the permanent.
[3] C. K. Hong, Z. Y. Ou and L. Mandel, Measurement of subpicosecond time intervals between two photons by interference. The two-photon bunching experiment whose balanced-beam-splitter cancellation is the smallest permanent-interference example.
[4] Craig S. Hamilton and colleagues, Gaussian Boson Sampling. The squeezed-state variant whose photon-count probabilities are governed by hafnians.
Batch 11 series navigation
- Guide 41: GKP Oscillator Codes, Lattice States, Modular Quadratures and Displacement Errors
- Guide 42: Cat Codes, Bosonic Quantum Error Correction, Photon Loss and Parity
- Guide 43: Continuous-Variable Cluster States, Graph Nullifiers and Measurement-Based Quantum Computation
- Guide 44: Boson Sampling, Matrix Permanents, Linear Optics and Photonic Quantum Advantage
- Return to the BTT Mathematics Learning Hub
Educational note: boson-sampling advantage claims depend on the precise sampling task, approximation metric, noise/loss model and complexity assumptions. A larger photonic experiment does not by itself establish a complexity-theoretic separation.