Boson Sampling

Give a quantum device the barest possible resources — a handful of single photons, a fixed maze of half-silvered mirrors, and detectors that count photons — and ask it to do one thing: report where the photons came out. No adaptive measurements, no entangling gates beyond what glass and mirrors supply, no error correction. This is Boson Sampling, proposed by Scott Aaronson and Alex Arkhipov in 2011, the cleanest thought experiment we have for "can a quantum machine do something a classical one provably cannot?" The device runs nothing you would call an algorithm; it merely samples from the distribution of photon-detection patterns. Yet reproducing that distribution classically appears intractable. The reason is a single mathematical object. A linear-optical network on $m$ modes is an $m\times m$ unitary $U$ on the single-photon amplitudes, and when $n$ indistinguishable photons enter, the amplitude to find them in a given output arrangement is the permanent of an $n\times n$ submatrix of $U$ — the determinant's innocent twin with all the minus signs deleted. Deleting them is catastrophic: the permanent is $\#\mathsf{P}$ -complete (Valiant, 1979), as hard as counting the solutions of any NP problem. Bosonic interference evaluates these permanents "for free" in the amplitudes of nature, while any classical simulation must grapple with them one exponential at a time. Aaronson and Arkhipov turned this coincidence into an argument: an efficient classical sampler — even one only close to the true distribution — would let a modest classical machine estimate the permanent of a Gaussian random matrix, collapsing the polynomial hierarchy, a catastrophe almost no complexity theorist believes. The claim rests on two plausible conjectures, not a proof, and its experimental incarnation — Gaussian Boson Sampling with squeezed light — is a live contest between photonic hardware and ever-cleverer spoofing algorithms.

Key takeaways

Boson Sampling samples the output pattern of $n$ indistinguishable photons sent through a Haar-random $m$ -mode linear-optical network and counted — nothing more.
Each output amplitude is a matrix permanent of an $n\times n$ submatrix of $U$ ; the probability is $|\mathrm{Perm}(U_S)|^2$ up to occupation factorials.
The permanent is $\#\mathsf{P}$ -hard, so no efficient classical sampling algorithm is known — the engine of the whole hardness argument.
Aaronson and Arkhipov (2011) proved an efficient classical sampler, even approximate, would collapse the polynomial hierarchy, under the Permanent-of-Gaussians and Anti-Concentration conjectures (the clean regime is dilute, $m \gtrsim n^2$ ).
Boson Sampling is deliberately weak — not universal, adaptive, or fault-tolerant — and its scalable cousin Gaussian Boson Sampling (squeezed light, hafnians) drives today's experiments.
Key idea: indistinguishable bosons passing through a passive linear-optical unitary $U$ produce output amplitudes equal to permanents of submatrices of $U$ ; because the permanent is $\#\mathsf{P}$ -hard, classically sampling the output distribution is conjectured to be infeasible, giving evidence for quantum advantage without universality or error correction.

Where this lives today

The idea is now a hardware race. Photonic groups have pushed Gaussian Boson Sampling into regimes claimed beyond classical reach: the USTC "Jiuzhang" experiment (Zhong et al., 2020) detected up to 76 photons across a 100-mode interferometer, and Xanadu's programmable "Borealis" (2022) implemented GBS over 216 squeezed modes. But each claim quotes a classical-runtime estimate that is a moving target, not a theorem, because the other half is classical: tensor-network and loss-exploiting spoofing algorithms (Clifford–Clifford samplers; the noise analyses of Oh, García-Patrón, Bulmer) repeatedly narrow the gap. The open scientific question is where the frontier lies: how much loss $\eta$ , distinguishability, and finite squeezing a device tolerates before its output becomes efficiently classically samplable. Boson Sampling thus survives less as a settled demonstration than as the sharpest probe of the noise threshold for quantum advantage — and, via GBS, as a proposed heuristic for molecular vibronic spectra and graph problems.

The physical picture

Picture each photon as a token dropped into a maze of half-silvered mirrors. If the tokens were distinguishable, each would follow its own probabilistic path, the output counts would be a classical convolution, and a laptop could simulate it in seconds. Indistinguishability breaks this: when $n$ identical photons head for the same detectors, the amplitudes for every assignment of photons to detectors add coherently, and that sum over all $n!$ assignments is exactly a matrix permanent — a $\#\mathsf{P}$ -hard object nature evaluates in the time it takes light to cross the chip. The two-photon seed is the Hong–Ou–Mandel effect: two identical photons entering a balanced beam splitter never come out separately, the coincidence amplitude being a $2\times2$ permanent that vanishes. Scale it to $n$ photons in $m$ modes and that vanishing permanent becomes a large random permanent no classical algorithm can sample efficiently.

Figure

A single-photon Boson Sampler: n = 3 indistinguishable photons enter an m = 5 mode interferometer U, a mesh of beam splitters and phase shifters, and photon-counting detectors read an output pattern S. The detection probability is the modulus-squared permanent of a 3×3 submatrix of U divided by the occupation factorials. The smallest instance, two photons on a 50:50 beam splitter, already shows the effect: the coincidence amplitude carries 1 + i² = 0, so both photons always leave together

Why insist on many more modes than photons, $m\gtrsim n^2$ ? With detectors spread thin, a random output almost never puts two photons in the same mode — a birthday-paradox argument. In this collision-free regime occupations are $0$ or $1$ and $U_S$ has entries that are asymptotically i.i.d. complex Gaussians — precisely the object, the permanent of a Gaussian random matrix, for which the hardness conjecture is stated. The complexity argument is then a proof by contradiction at a distance: an efficient classical sampler would let a probabilistic machine with an oracle high in the polynomial hierarchy estimate one of these hard permanents, collapsing the hierarchy. The second figure shows why the classical route is hopeless even for one amplitude.

Figure

The classical wall. The determinant of an n×n matrix costs O(n³) operations, but the fastest known exact permanent algorithm, Ryser's inclusion–exclusion formula, costs O(n·2ⁿ). At n = 30 that is 3.2×10¹⁰ operations versus 27 000; at n = 50 it is 5.6×10¹⁶ versus 125 000 — the entire difference between fermions, which are classically simulable, and bosons, which are not

The core equations

A beam splitter or phase shifter acts linearly on the mode creation operators, and any network of them realizes a single $m\times m$ unitary $U$ on the mode space — the entire dynamics.

a_i^\dagger \;\longmapsto\; \sum_{j=1}^{m} U_{ji}\, b_j^\dagger \qquad (1)

where: $a_i^\dagger$ — creation operator for input mode $i$ ; $b_j^\dagger$ — for output mode $j$ ; $U_{ji}$ — the $(j,i)$ entry of the interferometer unitary; $m$ — number of modes. Reading it: one photon in input mode $i$ emerges spread over all output modes with weights $U_{\cdot i}$ — a single-particle change of basis lifted to operators. The standard input places one photon in each of the first $n$ modes, and the amplitude to any output pattern is a permanent of the corresponding submatrix — the load-bearing identity.

\langle S | \varphi(U) | T \rangle \;=\; \frac{\mathrm{Perm}(U_{S,T})}{\sqrt{\,s_1!\cdots s_m!\; t_1!\cdots t_m!\,}} \qquad (2)

where: $\varphi(U)$ — the unitary on Fock space induced by $U$ ; $T,S$ — input and output occupation patterns with $\sum_j t_j=\sum_j s_j=n$ ; $U_{S,T}$ — the $n\times n$ matrix built from $U$ by repeating row $j$ $s_j$ times and column $i$ $t_i$ times. Reading it: the amplitude is a permanent because indistinguishable photons sum coherently over all $n!$ routings — the permanent's definition. Squaring the amplitude for the single-photon input gives the sampling probability; in the collision-free regime the factorials are all $1$ and it is a bare squared permanent.

P(S) \;=\; \frac{\big|\mathrm{Perm}(U_S)\big|^2}{s_1!\,s_2!\cdots s_m!} \qquad (3)

where: $P(S)$ — probability of detecting pattern $S$ ; $U_S$ — the $n\times n$ matrix from the first $n$ columns of $U$ and the $S$ -rows. Reading it: the output distribution is a table of squared permanents, one per pattern, and Boson Sampling draws $S$ from it. The permanent is the determinant with every sign set to $+1$ — but that change removes the cancellation that makes the determinant easy, lifting the object into $\#\mathsf{P}$ .

\mathrm{Perm}(A) = \sum_{\sigma \in S_n} \prod_{i=1}^{n} A_{i,\sigma(i)}, \qquad \det(A) = \sum_{\sigma \in S_n} \mathrm{sgn}(\sigma)\prod_{i=1}^{n} A_{i,\sigma(i)} \qquad (4)

where: $S_n$ — the symmetric group of $n!$ permutations; $\mathrm{sgn}(\sigma)$ — the sign of $\sigma$ , present for the determinant and absent for the permanent. Reading it: the signs let Gaussian elimination compute the determinant in $O(n^3)$ ; the permanent has no such trick and is $\#\mathsf{P}$ -complete for $0/1$ matrices (Valiant, 1979). The clean hardness statement lives in the dilute regime; a birthday bound tells us when.

\Pr\big[\text{no collision}\big] \;\geq\; 1 - O\!\Big(\frac{n^2}{m}\Big) \qquad (5)

where: "no collision" — the event that all $n$ photons land in distinct output modes; $m$ — number of modes. Reading it: $m \gtrsim n^2$ keeps this bounded below, so typical outputs are collision-free and $U_S$ is a near-Gaussian $n\times n$ submatrix — the hardness conjecture's setting. The consequence is a conditional collapse: an efficient classical sampler places a $\#\mathsf{P}$ -hard estimation task low in the hierarchy.

\text{estimating } |\mathrm{Perm}(\mathcal{N})|^2 \text{ is } \#\mathsf{P}\text{-hard} \;\Longrightarrow\; \mathsf{P}^{\#\mathsf{P}} \subseteq \mathsf{BPP}^{\mathsf{NP}} \subseteq \Sigma_3^{\mathsf{P}} \qquad (6)

where: $\mathcal{N}$ — an $n\times n$ matrix of i.i.d. complex Gaussians; $\mathsf{P}^{\#\mathsf{P}}$ — polynomial time with a counting oracle; $\mathsf{BPP}^{\mathsf{NP}}$ — randomized poly-time with an NP oracle, at the third level $\Sigma_3^{\mathsf{P}}$ . Reading it: since $\mathsf{PH}\subseteq\mathsf{P}^{\#\mathsf{P}}$ (Toda), this collapses the hierarchy to its third level — treated as absurd. Finally, the experimentally dominant variant replaces single photons with squeezed light, turning the object into a hafnian.

P_{\mathrm{GBS}}(S) \;\propto\; \frac{\big|\,\mathrm{Haf}(A_S)\,\big|^2}{s_1!\cdots s_m!}, \qquad \mathrm{Haf}(A) = \sum_{M\in\mathrm{PMP}} \prod_{(i,j)\in M} A_{ij} \qquad (7)

where: $\mathrm{Haf}$ — the hafnian, a sum over perfect matchings $M$ (the set $\mathrm{PMP}$ ); $A_S$ — a submatrix of the kernel built from the squeezing and $U$ . Reading it: the hafnian counts pairings not permutations, reduces to the permanent on a bipartite block, and is likewise $\#\mathsf{P}$ -hard — GBS keeps the intractability while scaling more easily.

Derivation AHow bosonic interference makes the amplitude a permanent

The goal is to show, from the linear map on creation operators and bosonic commutation alone, that the amplitude of equation (2) is forced to be a permanent — so the $\#\mathsf{P}$ -hard object is an identity in the algebra of indistinguishable photons, not an analogy. We expand the product of output operators and collect the terms surviving projection onto an output pattern.

Step 1. Apply the induced Fock-space map to the input. Using equation (1) on each factor, $\varphi(U)\,a_1^\dagger\cdots a_n^\dagger|0\rangle = \prod_{i=1}^{n}\big(\sum_{j} U_{ji}\, b_j^\dagger\big)|0\rangle$ . Why: the network acts on each photon independently, so the input becomes a product of $n$ identical operator sums.

Step 2. Expand into a sum over routings, $\sum_{j_1,\dots,j_n} U_{j_1 1}\cdots U_{j_n n}\, b_{j_1}^\dagger\cdots b_{j_n}^\dagger |0\rangle$ , each term assigning an output mode $j_i$ to photon $i$ . Why: the sum runs over all $m^n$ routings, and terms differing only by relabelling identical photons collapse together.

Step 3. Project onto an output pattern $S$ with photons in modes $k_1,\dots,k_n$ . Because $b^\dagger$ 's commute, all $n!$ orderings of the same output multiset contribute the same product of $U$ -entries and their coefficients add. Why: that coherent sum $\sum_{\sigma}\prod_i U_{k_{\sigma(i)}, i}$ is precisely the permanent of the selected submatrix.

Step 4. Normalize. Repeated modes generate $\sqrt{s_1!\cdots s_m!}$ from $\langle 0|b^{s}b^{\dagger s}|0\rangle=s!$ , giving $\langle S|\varphi(U)|T\rangle=\mathrm{Perm}(U_{S,T})/\sqrt{s_1!\cdots\, t_1!\cdots}$ . Why: the factorials are the only residue of collisions; in the dilute regime they are $1$ and the amplitude is a bare permanent. *For the single-photon input and collision-free output this reproduces $P(S)=|\mathrm{Perm}(U_S)|^2$ of equation (3); the algebra is the standard first-quantized permanent lemma of Caianiello and Scheel.*

Go deeper · Derivation B · 1 minThe Hong–Ou–Mandel dip as a two-by-two permanent

Derivation BThe Hong–Ou–Mandel dip as a two-by-two permanent

The goal is to compute the smallest nontrivial Boson Sampling instance — two indistinguishable photons on one balanced beam splitter — and watch the coincidence amplitude vanish as a $2\times2$ permanent, exhibiting in miniature the interference that scales up to intractable permanents. We inject one photon into each port of a 50:50 splitter and read off the output term by term.

Step 1. Fix the beam-splitter map $a_1^\dagger \mapsto \tfrac{1}{\sqrt2}(b_1^\dagger + i\,b_2^\dagger)$ , $a_2^\dagger \mapsto \tfrac{1}{\sqrt2}(i\,b_1^\dagger + b_2^\dagger)$ , so $U=\tfrac{1}{\sqrt2}\begin{pmatrix}1 & i\\ i & 1\end{pmatrix}$ . Why: the factors of $i$ on the reflected paths are what unitarity demands of a lossless symmetric splitter.

Step 2. Apply it to $a_1^\dagger a_2^\dagger|0\rangle = \tfrac12(b_1^\dagger + i b_2^\dagger)(i b_1^\dagger + b_2^\dagger)|0\rangle$ , which multiplies out to $\tfrac12\big(i\,b_1^{\dagger 2} + b_1^\dagger b_2^\dagger + i^2 b_2^\dagger b_1^\dagger + i\, b_2^{\dagger 2}\big)|0\rangle$ . Why: this is Step 1 of the general derivation for $n=2$ , before collecting terms.

Step 3. Collect the coincidence term. Using $b_1^\dagger b_2^\dagger = b_2^\dagger b_1^\dagger$ , the two $|1,1\rangle$ contributions combine as $\tfrac12(1 + i^2)\,b_1^\dagger b_2^\dagger|0\rangle = 0$ . Why: $1+i^2$ is $\mathrm{Perm}\begin{pmatrix}1&i\\ i&1\end{pmatrix}$ up to the $\tfrac12$ normalization — both photons occupy both input columns.

Step 4. Read off $|\psi_\mathrm{out}\rangle = \tfrac{i}{\sqrt2}\big(|2,0\rangle + |0,2\rangle\big)$ , so $P(1,1)=0$ while $P(2,0)=P(0,2)=\tfrac12$ . Why: the photons bunch with certainty — the exact cancellation that becomes a hard permanent when the matrix grows to $n\times n$ . *The result checks out: $\tfrac12\,\mathrm{Perm}\begin{pmatrix}1&i\\ i&1\end{pmatrix}=\tfrac12(1+i^2)=0$ , reproducing the HOM dip, with the bunched outputs $|2,0\rangle,|0,2\rangle$ each carrying probability $\tfrac12$ .*

Go deeper · Derivation C · 1 minWhy an efficient classical sampler would collapse the polynomial hierarchy

Derivation CWhy an efficient classical sampler would collapse the polynomial hierarchy

The goal is to trace the Aaronson–Arkhipov chain that turns a hypothetical efficient classical sampler into a collapse of the polynomial hierarchy, making explicit where each conjecture enters and why the conclusion is a reductio. We assume a classical sampler, apply Stockmeyer's approximate-counting theorem, connect the probability to a Gaussian permanent, and invoke Toda's theorem.

Step 1. Suppose a classical sampler whose probabilities $\{q_S\}$ match $\{P(S)\}$ . Stockmeyer's theorem estimates any efficiently samplable distribution's individual probabilities to within a multiplicative factor using an $\mathsf{FBPP}^{\mathsf{NP}}$ machine. Why: sampling access plus an NP oracle already yields good multiplicative estimates — no stronger resource is assumed.

Step 2. Identify that probability as a Gaussian permanent: $P(S)=|\mathrm{Perm}(U_S)|^2/(\text{norm})$ , and by Haar-to-Gaussian truncation $U_S$ is close in total variation to a complex-Gaussian $\mathcal{N}$ . Why: here the Permanent-of-Gaussians Conjecture enters — estimating $|\mathrm{Perm}(\mathcal{N})|^2$ is asserted $\#\mathsf{P}$ -hard.

Step 3. Handle approximate samplers, which are only close in total variation: the Anti-Concentration Conjecture keeps $|\mathrm{Perm}(\mathcal{N})|^2$ unconcentrated, so a random $S$ still carries the hard permanent. Why: without it an approximate sampler could hide all its error on exactly the informative outcomes.

Step 4. Close with Toda. A $\#\mathsf{P}$ -hard quantity would be estimable in $\mathsf{BPP}^{\mathsf{NP}}$ , so $\mathsf{P}^{\#\mathsf{P}}\subseteq\mathsf{BPP}^{\mathsf{NP}}\subseteq\Sigma_3^{\mathsf{P}}$ ; since $\mathsf{PH}\subseteq\mathsf{P}^{\#\mathsf{P}}$ (Toda), the hierarchy collapses. Why: a collapse of $\mathsf{PH}$ is believed false, so the efficient sampler is believed not to exist. *The argument above reproduces Theorem 1 of Aaronson–Arkhipov (2013): it is conditional on the two conjectures and $\mathsf{PH}$ being infinite, and asserts hardness of the sampling task, not any single probability.*

Limiting cases

Boson Sampling slides between trivially classical and conjecturally hard as the photon number, mode number, and physical imperfections change:

Case	Result	Meaning
Single photon ( $n=1$ )	$P(\text{mode }j)=\lvert U_{j1}\rvert^2$	Just the squared moduli of a column of $U$ — trivially computable, no advantage.
Distinguishable photons	$P \propto \mathrm{Perm}\big(\lvert U_S\rvert^2\big)$	Phase coherence lost; a permanent of a nonnegative matrix, approximable in randomized polynomial time (Jerrum–Sinclair–Vigoda), so classically simulable.
Dilute / collision-free	$m\gtrsim n^2,\quad P(S)=\dfrac{\lvert\mathrm{Perm}(U_S)\rvert^2}{s_1!\cdots s_m!}$	The hardness regime: $s_j\in\{0,1\}$ , $U_S$ near-Gaussian, permanent argument clean.
Heavy loss / distinguishability	$\eta\to0$ or $x\to0$	Tensor-network and truncated-photon algorithms reproduce the statistics — advantage evaporates.

Common trapBoson Sampling is a universal quantum computer, and its classical intractability has been proven

Both halves are wrong. A Boson Sampler is a single, fixed, non-adaptive linear-optical network followed by measurement; it cannot run Shor's algorithm, has no error correction, and its only output is a sample from one hard distribution — universality would need adaptive measurements and feedforward, or photonic cluster states. And the hardness is not proven: it is conditional on the two conjectures and on the polynomial hierarchy being infinite, so Boson Sampling is evidence for intractability, not a theorem. Two further traps: the hardness concerns the whole sampling distribution, not any single output probability; and the clean argument needs the dilute regime $m\gtrsim n^2$ , because with too few modes the "collision" outputs dominate.

Worked examples

1 · Three photons through a Fourier interferometer (fully worked)

Send one photon into each of three modes, $T=(1,1,1)$ , through the $3\times3$ discrete-Fourier interferometer $U=F/\sqrt3$ with $F_{jk}=\omega^{(j-1)(k-1)}$ , $\omega=e^{2\pi i/3}$ . Find the probability of the "straight-through" output $S=(1,1,1)$ , and compare it with distinguishable photons.

Step 1. Since $T=S=(1,1,1)$ , the submatrix is all of $U$ , so $P(1,1,1)=|\mathrm{Perm}(U)|^2$ . The permanent of $F$ over the six column permutations gives products $\{\omega^2,\omega,\omega,\omega^2,\omega^2,\omega\}$ , summing to $3(\omega+\omega^2)$ .

Step 2. Use $1+\omega+\omega^2=0$ , so $\omega+\omega^2=-1$ and $\mathrm{Perm}(F)=\mathbf{-3}$ . Rescaling by $U=F/\sqrt3$ multiplies by $(1/\sqrt3)^3$ , giving $\mathrm{Perm}(U)=-3/(3\sqrt3)=-1/\sqrt3$ .

Step 3. Square it: $P(1,1,1)=\mathbf{1/3}\approx0.333$ . For distinguishable photons, $P_\mathrm{dist}=\mathrm{Perm}(|U|^2)$ with every $|U_{jk}|^2=1/3$ , so $P_\mathrm{dist}=(1/3)^3\,\mathrm{Perm}(J_3)=(1/27)\cdot 3!=\mathbf{2/9}\approx0.222$ .

Step 4. Indistinguishable photons bunch: interference raises the straight-through probability from $2/9$ to $3/9$ , a purely quantum enhancement. This instance is easy by hand, but the same permanent at $n=50$ is what no classical machine can sample. Result: bosonic P(1,1,1) = 1/3, distinguishable = 2/9 — interference enhances bunching by 50%.

2 · The cost of an exact classical simulation

Estimate the classical effort to evaluate one output amplitude for $n=30$ and $n=50$ photons in the collision-free regime, and contrast with the sampling task.

Step 1. Collision-free needs $m\gtrsim n^2$ , so $n=30$ wants $m\gtrsim 900$ modes and $n=50$ wants $m\gtrsim 2500$ ; each amplitude is a bare $n\times n$ permanent. Ryser's inclusion–exclusion formula, the fastest known exact route, runs in $O(n\,2^n)$ .

Step 2. For $n=30$ that is $30\cdot2^{30}\approx\mathbf{3.2\times10^{10}}$ operations (seconds on a workstation); for $n=50$ it is $50\cdot2^{50}\approx\mathbf{5.6\times10^{16}}$ — supercomputer-scale for a single evaluation. The determinant of the same matrix costs only $n^3$ : $2.7\times10^4$ and $1.25\times10^5$ operations.

Step 3. Sampling is worse still: the number of collision-free outcomes is $\binom{m}{n}$ , already $\sim10^{57}$ for $m=900,n=30$ , and no classical method produces correctly distributed samples without effectively evaluating these permanents. Result: one n=50 permanent ≈ 5.6×10¹⁶ ops vs 1.25×10⁵ for the determinant; sampling ranges over ~10⁵⁷ outcomes, no efficient classical algorithm known.

Physics of the portrait

Boson Sampling was born inside theoretical computer science, its portrait a complexity theorist who asked what the simplest optics could prove.

Origins · 1 minScott Aaronson and how this was discovered

Scott Aaronson

born 1981 · computational complexity and the Boson Sampling proposal

Scott Aaronson is an American theoretical computer scientist, now at the University of Texas at Austin, whose work sits at the border of quantum computing and computational complexity, including the meaning of "quantum supremacy." In 2011, with his student Alex Arkhipov at MIT, he introduced Boson Sampling in "The Computational Complexity of Linear Optics." The move was to abandon universality entirely: rather than build a full quantum computer, take the most impoverished quantum-optical device imaginable — single photons, a fixed passive interferometer, photon counters — and show that even this cannot be simulated classically unless the polynomial hierarchy collapses. That linear-optical amplitudes are matrix permanents was known since Caianiello in the 1950s; Valiant's 1979 proof of $\#\mathsf{P}$ -completeness supplied the hardness. Aaronson and Arkhipov's contribution was the reduction from approximate sampling to permanent estimation, with the two conjectures that make it robust to noise. The proposal reframed the quantum-advantage program — not "compute something useful faster" but "sample from a distribution no classical machine can" — and launched the photonic experiments that a decade later claimed exactly that.

History

1963

— Ryser publishes the inclusion–exclusion formula, still the fastest known exact permanent algorithm

1979

— Valiant proves that computing the matrix permanent is #P-complete

1987

— Hong, Ou and Mandel observe the two-photon coincidence dip

2011

— Aaronson and Arkhipov propose Boson Sampling and the approximate-sampling hardness argument

2020

— the Jiuzhang experiment claims photonic quantum advantage via Gaussian Boson Sampling

Going further

Texts. Aaronson & Arkhipov, "The Computational Complexity of Linear Optics," Theory of Computing 9 (2013) 143 · Valiant, "The complexity of computing the permanent," Theor. Comput. Sci. 8 (1979) 189 · Nielsen & Chuang, Quantum Computation and Quantum Information (10th anniv. ed.), Ch. 4 and 6 · Preskill, Lecture Notes for Physics 219 (complexity and quantum advantage) · Kitaev, Shen & Vyalyi, Classical and Quantum Computation ( $\#\mathsf{P}$ , Toda) · Watrous, The Theory of Quantum Information · Hamilton et al., "Gaussian Boson Sampling," Phys. Rev. Lett. 119 (2017) 170501 · Zhong et al., "Quantum computational advantage using photons," Science 370 (2020) 1460. Key results collected here: the permanent amplitude rule follows from bosonic commutation; the HOM cancellation gives $\tfrac12\,\mathrm{Perm}\begin{pmatrix}1&i\\ i&1\end{pmatrix}=0$ with bunched output $|2,0\rangle,|0,2\rangle$ ; the Fourier permanent is $\mathrm{Perm}(F_3)=-3$ , yielding bosonic $P=1/3$ vs distinguishable $2/9$ ; $\#\mathsf{P}$ -completeness of the permanent is due to Valiant (1979) and Toda's theorem gives $\mathsf{PH}\subseteq\mathsf{P}^{\#\mathsf{P}}$ ; Ryser's algorithm runs in $O(n\,2^n)$ vs the determinant's $O(n^3)$ , giving $\approx3.2\times10^{10}$ and $\approx5.6\times10^{16}$ operations at $n=30$ and $n=50$ respectively. The Jiuzhang and Borealis scales are from Zhong et al. (2020) and the Xanadu Borealis paper (2022); no classical-runtime advantage figure is asserted as settled, only the conditional-hardness statements and the $m\gtrsim n^2$ regime.

Prerequisites. Quantum Harmonic Oscillator and Fock States · Linear Optics and the Unitary on Modes · Computational Complexity Classes · Matrix Permanent and Determinant. Leads to. Random Circuit Sampling · Measurement-Based Quantum Computation · Cluster States and Graph States.

Ask the tutor: Want to watch a $3\times3$ interferometer's whole output distribution built permanent by permanent, and see exactly where distinguishable and lossy photons fall back into classical reach? Ask and we will sample it together.

Why is the permanent so much harder than the determinant if the formulas look identical?

The two differ by one ingredient: the determinant weights each permutation by its sign, the permanent by $+1$ . Those signs make Gaussian elimination work, giving $O(n^3)$ cost; delete them and no cancellation survives, so the permanent is a raw count over $n!$ terms. Valiant proved in 1979 that computing it (even for $0/1$ matrices) is $\#\mathsf{P}$ -complete, as hard as counting a Boolean formula's satisfying assignments — one symbol separating polynomial from believed-exponential time.

Does a Boson Sampling experiment actually compute a permanent?

Not in the sense of printing its value. The device samples output patterns whose probabilities are governed by permanents, but it never reports any permanent. Computing a single amplitude is $\#\mathsf{P}$ -hard, yet nature samples the whole distribution effortlessly because interference sums the routings physically. The hardness claim is about reproducing that sampling classically — a demonstration of intractable sampling, not a permanent calculator.

What are the two conjectures, and why not just prove hardness outright?

The Permanent-of-Gaussians Conjecture says approximating $|\mathrm{Perm}(\mathcal{N})|^2$ for an i.i.d. complex-Gaussian matrix $\mathcal{N}$ is $\#\mathsf{P}$ -hard; the Anti-Concentration Conjecture says these permanents are not too concentrated near zero, so a random output still carries the hard quantity. Both are needed because the realistic target is an approximate sampler, and exact worst-case permanent hardness (a theorem) does not survive that approximation. Proving them would upgrade Boson Sampling to an unconditional separation, but average-case permanent hardness remains open.

Why does the model need so many more modes than photons?

Because the clean permanent argument assumes at most one photon per output mode. With $n$ photons over $m$ modes, the chance two land together is roughly $n^2/m$ by a birthday count, so $m\gtrsim n^2$ keeps collisions rare. In this dilute regime $U_S$ is a genuine $n\times n$ submatrix whose entries are asymptotically i.i.d. complex Gaussians — exactly the setting the hardness conjecture is phrased for. Pack photons into too few modes and collision outputs dominate, the factorials stop being $1$ , and the Gaussian-permanent connection breaks.

Why is Gaussian Boson Sampling preferred experimentally?

GBS replaces single-photon Fock inputs with squeezed vacuum, making the whole state Gaussian and shifting the governing object from the permanent to the hafnian — a sum over perfect matchings rather than permutations, which reduces to the permanent on a bipartite block and is likewise $\#\mathsf{P}$ -hard. The practical payoff is large: single indistinguishable photons are generated probabilistically and hard to synchronize at scale, whereas squeezed light is deterministic — which is why every large "photonic advantage" claim (Jiuzhang, Borealis) is a GBS experiment.

Has photonic quantum advantage via Boson Sampling actually been achieved?

It has been claimed and is genuinely contested. Experiments like Jiuzhang (76 detected photons, 2020) and Borealis (216 modes, 2022) produced samples with quoted classical-simulation costs of thousands of years, but those estimates keep falling as spoofing and tensor-network algorithms improve by exploiting the imperfections — loss, distinguishability, finite squeezing — that real devices suffer. No advantage claim is unconditionally settled; the frontier between the quantum-hard and classically-simulable regimes is exactly where the research lives. Boson Sampling remains the sharpest testbed for that boundary, not a closed demonstration.