Simple Algorithm
Quantum Computing · Rydberg State · 30 min

Hong–Ou–Mandel & Boson Sampling

Two-photon interference and a route to quantum advantage.

Send two identical photons into the two input ports of a 50:50 beam splitter and they never leave by different ports: the two ways of getting one photon in each output cancel exactly. This two-photon interference is a ruler for indistinguishability, a swap test built into nature and, scaled up to many photons, a sampling problem believed to be beyond classical computers.

What you’ll learn

  • Derive the Hong–Ou–Mandel effect in second quantization, and the coincidence probability 12(1−∣⟨ψa∣ψb⟩∣2)\tfrac12(1 - \abs{\braket{\psi_a|\psi_b}}^2) for partially distinguishable photons.
  • Identify HOM interference with the swap test.
  • Prove that nn-photon amplitudes in an mm-mode linear interferometer are permanents of n×nn\times n submatrices, and contrast them with fermionic determinants.
  • State the Aaronson–Arkhipov hardness results for boson sampling, the conjectures they rest on, and how loss and distinguishability enable classical simulation.

Two photons, one beam splitter

Use creation operators: a†,b†a^\dagger, b^\dagger for the input modes and c†,d†c^\dagger, d^\dagger for the outputs. A lossless 50:50 beam splitter in the Hadamard convention maps a†↦12(c†+d†)a^\dagger \mapsto \tfrac{1}{\sqrt2}(c^\dagger + d^\dagger) and b†↦12(c†−d†)b^\dagger \mapsto \tfrac{1}{\sqrt2}(c^\dagger - d^\dagger). One photon enters each input.

DerivationThe Hong–Ou–Mandel effect
  1. ∣1,1⟩=a†b†∣vac⟩  ↦  12(c†+d†)(c†−d†)∣vac⟩\ket{1,1} = a^\dagger b^\dagger\ket{\mathrm{vac}} \;\mapsto\; \tfrac12\left(c^\dagger + d^\dagger\right)\left(c^\dagger - d^\dagger\right)\ket{\mathrm{vac}}

    Transform each creation operator.

  2. =12(c†2−c†d†+d†c†−d†2)∣vac⟩= \tfrac12\left(c^{\dagger 2} - c^\dagger d^\dagger + d^\dagger c^\dagger - d^{\dagger 2}\right)\ket{\mathrm{vac}}

    Expand.

  3. =12(c†2−d†2)∣vac⟩=12(∣2,0⟩−∣0,2⟩)= \tfrac12\left(c^{\dagger 2} - d^{\dagger 2}\right)\ket{\mathrm{vac}} = \tfrac{1}{\sqrt2}\big(\ket{2,0} - \ket{0,2}\big)

    Bosonic operators commute, c†d†=d†c†c^\dagger d^\dagger = d^\dagger c^\dagger, so the cross terms cancel; then c†2∣vac⟩=2∣2,0⟩c^{\dagger2}\ket{\mathrm{vac}} = \sqrt2\ket{2,0}.

  4. The coincidence term ∣1,1⟩\ket{1,1} is gone: both photons always leave together. In path language, "both transmitted" and "both reflected" lead to the same final state with amplitudes tt′tt' and rr′rr', and rr′=−tt′rr' = -tt' for every lossless 50:50 splitter.

DerivationPartially distinguishable photons
  1. ∣ψb⟩=γ∣ψa⟩+1−∣γ∣2 ∣ψ⊥⟩,γ=⟨ψa∣ψb⟩\ket{\psi_b} = \gamma\ket{\psi_a} + \sqrt{1 - \abs{\gamma}^2}\,\ket{\psi_\perp}, \qquad \gamma = \braket{\psi_a|\psi_b}

    Decompose photon bb's internal state (time, frequency, polarization) relative to photon aa's.

  2. The component along ∣ψa⟩\ket{\psi_a} is indistinguishable and bunches perfectly. The orthogonal component behaves like a distinguishable particle: each photon picks an output independently, giving one per port with probability 12\tfrac12.

  3. Pc=1−∣⟨ψa∣ψb⟩∣22P_{\mathrm{c}} = \frac{1 - \abs{\braket{\psi_a|\psi_b}}^2}{2}

    Scanning a time delay τ\tau between the photons traces out the HOM dip: Pc(τ)=12(1−∣∫ψa∗(t)ψb(t−τ) dt∣2)P_{\mathrm{c}}(\tau) = \tfrac12\big(1 - \abs{\textstyle\int\psi_a^*(t)\psi_b(t-\tau)\,dt}^2\big).

Predict before you look

Two single photons have mode overlap ∣⟨ψa∣ψb⟩∣2=0.9\abs{\braket{\psi_a|\psi_b}}^2 = 0.9. What is the coincidence probability at a 50:50 beam splitter, in percent?

Show the answer

5 %

Pc=12(1−0.9)=0.05P_{\mathrm{c}} = \tfrac12(1 - 0.9) = 0.05. The dip's depth, compared with the 50%50\% of distinguishable photons, is the standard way to certify that a single-photon source emits indistinguishable photons.

A swap test made of light

The formula Pc=12(1−∣⟨ψ∣ϕ⟩∣2)P_{\mathrm{c}} = \tfrac12(1 - \abs{\braket{\psi|\phi}}^2) is exactly the failure probability of the swap test (Buhrman, Cleve, Watrous & de Wolf, 2001): an ancilla in ∣+⟩\ket{+} controls a SWAP of two registers, then is measured in the XX basis. The beam splitter performs the same projection onto the symmetric and antisymmetric parts of the photons' internal state: only the antisymmetric part produces coincidences. (Garcia-Escartin and Chamorro-Posada, 2013, show the two are equivalent.)

The same mechanism powers linear-optics Bell measurements: of the four polarization Bell states only the antisymmetric ∣Ψ−⟩\ket{\Psi^-} gives coincidences behind a 50:50 splitter. Without ancilla photons, such a measurement can succeed at most half the time.

Check your understanding

Two identical fermions (say, electrons in a quantum Hall beam splitter) enter the two input ports of a 50:50 beam splitter. What do you observe?

  1. They always leave together, like photons
  2. They always leave by different ports
  3. Each leaves randomly and independently
  4. They are reflected back into the inputs
Show the answer

B. They always leave by different ports

For fermions c†d†=−d†c†c^\dagger d^\dagger = -d^\dagger c^\dagger and (c†)2=0(c^\dagger)^2 = 0, so the same expansion gives −c†d†∣vac⟩-c^\dagger d^\dagger\ket{\mathrm{vac}}: one particle per port with certainty. The coincidence amplitude is a determinant, det⁡H=−1\det H = -1, instead of the permanent Per H=0\mathrm{Per}\,H = 0.

Many photons: permanents

Now let nn single photons enter the first nn of mm modes of a linear interferometer, a unitary UU acting as ai†↦∑jUji bj†a_i^\dagger \mapsto \sum_j U_{ji}\, b_j^\dagger. Ask for the amplitude of a collision-free output pattern S={s1,…,sn}S = \{s_1, \dots, s_n\}, one photon in each mode of SS.

DerivationAmplitudes are permanents
  1. ∏i=1n(∑j=1mUji bj†)∣vac⟩=∑j1,…,jn(∏i=1nUjii) bj1†⋯bjn†∣vac⟩\prod_{i=1}^{n}\Big(\sum_{j=1}^{m}U_{ji}\,b_j^\dagger\Big)\ket{\mathrm{vac}} = \sum_{j_1,\dots,j_n}\Big(\prod_{i=1}^n U_{j_i i}\Big)\, b_{j_1}^\dagger\cdots b_{j_n}^\dagger\ket{\mathrm{vac}}

    Expand the product of transformed creation operators.

  2. ⟨S∣ U ∣1n0m−n⟩=∑σ∈Sn∏i=1nUsσ(i), i=Per(US)\braket{S|\,U\,|1^n0^{m-n}} = \sum_{\sigma\in S_n}\prod_{i=1}^n U_{s_{\sigma(i)},\,i} = \mathrm{Per}(U_S)

    The terms reaching SS are the n!n! assignments of photons to the modes of SS. Bosonic operators commute, so all assignments add with the same sign. USU_S is the n×nn\times n submatrix with rows SS and the first nn columns.

  3. ⟨S∣ U ∣1n0m−n⟩=Per(US)∏jsj!(with collisions)\braket{S|\,U\,|1^n0^{m-n}} = \frac{\mathrm{Per}(U_{S})}{\sqrt{\prod_j s_j!}}\quad\text{(with collisions)}

    With sjs_j photons in mode jj, row jj is repeated sjs_j times and the normalization of bj†sj∣vac⟩b_j^{\dagger s_j}\ket{\mathrm{vac}} contributes the factorials. For fermions the same computation produces det⁡(US)\det(U_S).

ParticlesProbability of pattern SSClassical cost
identical fermions∣det⁡US∣2\abs{\det U_S}^2polynomial (Gaussian elimination); free fermions are classically simulable
distinguishablePer(∣US∣∘2)\mathrm{Per}\big(\abs{U_S}^{\circ 2}\big), entrywise ∣Uij∣2\abs{U_{ij}}^2easy to sample (route each particle independently); nonnegative permanents have an FPRAS (Jerrum, Sinclair & Vigoda 2004)
identical bosons∣Per US∣2\abs{\mathrm{Per}\,U_S}^2#P-hard to compute in general; best exact methods O(2nn)\order{2^n n} (Ryser, Glynn)

Boson sampling

The best classical exact sampler (Clifford & Clifford, 2018) runs in time O(n2n+poly⁡(m,n))\order{n2^n + \poly(m,n)}, roughly the cost of computing a few n×nn\times n permanents. Three-photon demonstrations appeared in 2013 from four groups. Gaussian boson sampling, which uses squeezed light and has hafnians in place of permanents (Hamilton et al., 2017), was scaled to experiments with tens of detected photons that claimed quantum advantage (Zhong et al., 2020; Madsen et al., 2022).

Imperfections push the problem back toward classical tractability. Partial distinguishability suppresses high-order interference terms geometrically, which allows efficient approximate simulation (Renema et al., 2018). When loss grows with system size, so that only about n\sqrt n photons survive, efficient classical approximations exist as well (Oszmaniec & Brod, 2018). Each advantage claim has therefore been met by classical algorithms that exploit exactly these imperfections.

Key takeaways

  • HOM: for identical photons the two coincidence paths cancel (rr′=−tt′rr' = -tt'), so Pc=12(1−∣⟨ψa∣ψb⟩∣2)P_{\mathrm{c}} = \tfrac12\big(1 - \abs{\braket{\psi_a|\psi_b}}^2\big): an indistinguishability ruler and a swap test.
  • nn-photon amplitudes in an mm-mode interferometer are permanents Per(US)/∏jsj!\mathrm{Per}(U_S)/\sqrt{\prod_j s_j!}; fermions give determinants.
  • Permanents are #P-hard (Valiant) while determinants are easy: same-sign interference over n!n! assignments is the source of hardness.
  • Exact classical boson sampling would collapse PH; approximate hardness needs further conjectures, and loss and distinguishability open classical shortcuts.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Two photons in identical pure modes enter the two ports of a lossless 50:50 beam splitter. What is the coincidence probability?

  1. 12\tfrac12
  2. 14\tfrac14
  3. 00
  4. 11
Show the answer

C. 00

The amplitudes for "both transmitted" and "both reflected" are tt′tt' and rr′=−tt′rr' = -tt', and they cancel, so the output is 12(∣2,0⟩−∣0,2⟩)\tfrac{1}{\sqrt2}(\ket{2,0} - \ket{0,2}).

Question 2

The photons' mode overlap is ∣⟨ψa∣ψb⟩∣2=0.5\abs{\braket{\psi_a|\psi_b}}^2 = 0.5. What is the coincidence probability?

  1. 0.50.5
  2. 0.250.25
  3. 0.1250.125
  4. 00
Show the answer

B. 0.250.25

Pc=12(1−0.5)=0.25P_{\mathrm{c}} = \tfrac12(1 - 0.5) = 0.25: half of the pair amplitude is indistinguishable and bunches, the other half splits like independent particles.

Question 3

Why is a many-photon interferometer amplitude a permanent rather than a determinant?

  1. Because bosonic creation operators commute, so all n!n! assignments of photons to output modes add with the same sign
  2. Because photons are massless
  3. Because the interferometer is not unitary
  4. Because each photon interferes only with itself
Show the answer

A. Because bosonic creation operators commute, so all n!n! assignments of photons to output modes add with the same sign

Expanding ∏i(∑jUjibj†)\prod_i\big(\sum_j U_{ji}b_j^\dagger\big) and reordering commuting operators gives ∑σ∏iUsσ(i)i\sum_\sigma\prod_i U_{s_{\sigma(i)}i}, the permanent. Anticommuting fermionic operators insert sgn⁡σ\operatorname{sgn}\sigma and give the determinant.

Question 4

Which statement about boson sampling is a theorem rather than a conjecture?

  1. Approximate boson sampling to small total-variation distance is classically hard
  2. Estimating ∣Per X∣2\abs{\mathrm{Per}\,X}^2 for Gaussian XX is #P-hard on average
  3. Gaussian boson sampling experiments cannot be simulated classically at any size
  4. Exact classical boson sampling in polynomial time would collapse the polynomial hierarchy
Show the answer

D. Exact classical boson sampling in polynomial time would collapse the polynomial hierarchy

Aaronson and Arkhipov prove the exact-sampling collapse. Approximate hardness rests on the Permanent-of-Gaussians and anticoncentration conjectures, and noisy experiments face classical algorithms that exploit loss and distinguishability.

Further reading

  • C. K. Hong, Z. Y. Ou & L. Mandel, "Measurement of subpicosecond time intervals between two photons by interference", Phys. Rev. Lett. 59, 2044 (1987).
  • L. G. Valiant, "The complexity of computing the permanent", Theor. Comput. Sci. 8, 189 (1979).
  • S. Aaronson & A. Arkhipov, "The computational complexity of linear optics", Theory of Computing 9, 143 (2013); STOC 2011.
  • P. Clifford & R. Clifford, "The classical complexity of boson sampling", Proc. ACM-SIAM SODA (2018).
  • H.-S. Zhong et al., "Quantum computational advantage using photons", Science 370, 1460 (2020).