KLM Protocol

Photons are the closest thing nature offers to a free flying qubit: they barely decohere, they move at the speed of light, and a handful of beam splitters and phase shifters steer them with exquisite precision. Yet those same passive elements are also their curse. Every linear-optical component implements a transformation that is bilinear in the mode operators — it rotates one creation operator into a sum of creation operators and nothing more — so two photons sharing a beam splitter never truly collide. There is no conditional phase, no entangling gate, no photon–photon force to build logic on. Before 2001 the field's working assumption was that optical quantum computing therefore required a strong material nonlinearity, a Kerr medium giving one photon a phase that depends on whether a second photon is present, and every candidate material had a nonlinearity far too weak and too lossy to use. Knill, Laflamme and Milburn dissolved the problem rather than solving it. Their observation is that a photon detector is already a nonlinear, non-unitary device, and that conditioning what you do next on what a detector reports — feedforward — can imprint an effective nonlinearity on the photons you kept. You entangle your computational photons with disposable ancilla photons using ordinary linear optics, you measure the ancillas, and a particular detection pattern heralds that the surviving photons have undergone a transformation no passive network could have produced. The catch is that the right pattern only appears some of the time, so the gate is probabilistic — but its success is announced, never silent. KLM then stack three ideas — the nonlinear sign-shift gate, Gottesman–Chuang gate teleportation, and an error-correctable bosonic encoding — to drive the success probability toward one using only a polynomial number of ancillas. The upshot is a constructive proof that bare linear optics, single photons, and detectors satisfy every DiVincenzo criterion for scalable universal quantum computation. It founded linear-optical quantum computing and seeded the cluster-state and fusion-based architectures that lead the photonic field today.

Key takeaways

The KLM protocol (Knill, Laflamme, Milburn, 2001) proves that universal, scalable quantum computing needs only single-photon sources, passive linear optics, photon-number-resolving detectors, and classical feedforward — no direct photon–photon interaction.
Linear optics alone is Gaussian and cannot deterministically entangle photons; KLM manufactures an effective nonlinearity by measuring ancilla photons, yielding a heralded, probabilistic two-qubit gate.
The workhorse is the nonlinear sign-shift (NS) gate, which flips the sign of the two-photon amplitude and succeeds with probability 1/4; two NS gates in a Mach–Zehnder build a controlled-Z that fires with probability 1/16.
Gate teleportation through a pre-tested $|t_n\rangle$ resource lifts the per-gate success probability to $n/(n+1)$ using $n$ ancilla photons, approaching certainty at polynomial cost.
KLM satisfies the DiVincenzo criteria with photons despite their non-interacting nature, launching linear-optical quantum computing and the measurement-based schemes descended from it.
The raw overhead is enormous, so modern photonic machines replace bare KLM with cluster-state and fusion-based architectures — but all inherit its one idea.
Key idea: measurement is nonlinear — entangle computational photons with ancillas through linear optics, projectively measure the ancillas, and a heralding pattern imprints an effective photon–photon interaction on the survivors, turning a deterministically-impossible gate into a probabilistic-but-heralded one that teleportation and bosonic encoding then boost toward determinism.

The core insight

Measurement is nonlinear. By entangling computational photons with ancilla photons through purely linear optics and then projectively measuring the ancillas, one heralds an effective photon–photon interaction on the surviving modes — converting a deterministically-impossible entangling gate into a probabilistic-but-heralded one, which is then boosted toward determinism by teleportation and bosonic encoding.

Where this lives today

No one builds a photonic quantum computer out of raw KLM — the overhead in Example 1 and Example 2 makes that plain — but every leading photonic architecture is its intellectual child. The dominant descendants are cluster-state and fusion-based quantum computing: KLM's probabilistic gates are used offline to stitch small entangled photon clusters into a large resource state, after which the computation runs deterministically by adaptive single-qubit measurements, so the probabilistic failures never touch the running algorithm. Companies such as PsiQuantum and Xanadu are engineering exactly this at scale, pouring effort into the three ingredients KLM exposed as the bottleneck: near-deterministic single-photon (and squeezed-light) sources, near-unit-efficiency photon-number-resolving detectors like superconducting transition-edge sensors, and low-loss integrated waveguide circuits with fast feedforward. The same measurement-plus-feedforward logic reappears far beyond optics — in magic-state injection for fault-tolerant gates, in measurement-based computing on matter qubits, and in linear-optical Bell-state measurements at the heart of quantum repeaters and the future quantum internet. And KLM's numbers remain the field's yardstick: quoting the 1/16 controlled-Z yield and the $n/(n+1)$ boosting law is still how photonic engineers estimate photon budgets, source rates, and the detector efficiencies needed to cross the fault-tolerance threshold. Boson sampling, the influential near-term test of quantum advantage, is in a real sense KLM stripped of its ancillas and feedforward — the same linear-optical interference, run open-loop.

The physical picture

Picture a beam splitter as a fixed gear-train that turns field modes into one another but never lets two photons touch. To force an interaction you smuggle in extra witness photons, run everything through the gears so the witnesses become entangled with your data, and then look at where the witnesses come out. Finding them in one specific arrangement collapses the data photons into a state that could only have arisen from an interaction — you have hired the detector to do the nonlinearity the glass refused to do. The seed of the whole trick is the Hong–Ou–Mandel effect: two identical photons entering a balanced beam splitter always leave together, an interference that is intrinsically two-photon and therefore sensitive to photon number in exactly the way a nonlinearity is. The first figure shows the smallest self-contained example — the nonlinear sign-shift gate — where a heralded detection flips the sign of just the two-photon amplitude.

Figure

The nonlinear sign-shift gate: a signal mode carrying zero-, one- and two-photon amplitudes mixes with two ancilla modes on three beam splitters set at 22.5°, 40.06° and 22.5°; detecting exactly one photon in the top ancilla and none in the bottom heralds success with probability 1/4 and flips the sign of the two-photon amplitude alone

Because every elementary gate is probabilistic, running KLM naively is like playing a casino where you can at least see your losing hands. The genius is to bet only on cheap, re-runnable things. Gate teleportation lets you build the entangling resource offline, test it, and teleport your precious data qubit through it only once it has passed — so failures consume disposable ancillas, never data. And a bosonic encoding spreads one logical qubit across $n$ photons so that a failed teleportation collapses only a correctable slice of it. Each added photon buys success probability $n/(n+1)$ per teleportation, the explicit polynomial road from "works sometimes" to "works almost always." The second figure plots that boosting law: the per-gate success probability climbing from 1/2 at $n=1$ toward 1, hitting 0.99 by the time $n=99$ .

Figure

The teleportation boosting law P_n = n/(n+1): a single ancilla gives 1/2, three give 3/4, fifteen give 15/16, and reaching 0.99 needs n = 99 ancilla photons — failure probability 1/(n+1) falls only polynomially, which is why bare KLM is expensive but still scalable

The core equations

A logical qubit in KLM is one photon that can sit in either of two modes — the dual-rail encoding. Nothing about the photon itself carries the bit; the which-mode degree of freedom does. This makes every single-qubit gate a passive interferometer and quarantines all the difficulty into the two-qubit gate.

|0_L\rangle = |1\rangle_a\,|0\rangle_b,\qquad |1_L\rangle = |0\rangle_a\,|1\rangle_b \qquad (1)

where: $a,b$ — the two optical modes (spatial paths or polarizations) that together carry one logical qubit; $|n\rangle$ — the Fock state with $n$ photons in the indicated mode. Reading it: the photon is always present; the logical value is where it is. A beam splitter acts on the mode operators, not on the logical amplitudes directly. Its entire effect is the linear rotation below — a single creation operator maps to a linear combination of creation operators, and that linearity is precisely what forbids a deterministic entangling gate.

\hat U_{BS}\begin{pmatrix}\hat a^\dagger\\ \hat b^\dagger\end{pmatrix}\hat U_{BS}^\dagger = \begin{pmatrix}\cos\theta & \sin\theta\\ -\sin\theta & \cos\theta\end{pmatrix}\begin{pmatrix}\hat a^\dagger\\ \hat b^\dagger\end{pmatrix} \qquad (2)

where: $\hat a^\dagger,\hat b^\dagger$ — creation operators for the two input modes; $\theta$ — the mixing angle, with reflectivity $R=\sin^2\theta$ . Reading it: the map sends $\hat a^\dagger\mapsto\cos\theta\,\hat a^\dagger+\sin\theta\,\hat b^\dagger$ , a rotation in operator space with no product terms — the transformation is Gaussian. The single non-Gaussian primitive KLM needs is the nonlinear sign-shift gate. It acts on one mode's photon-number amplitudes and does something no passive network can: it flips the sign of the two-photon component while leaving the vacuum and one-photon components untouched.

\mathrm{NS}\big(\alpha|0\rangle+\beta|1\rangle+\gamma|2\rangle\big)=\alpha|0\rangle+\beta|1\rangle-\gamma|2\rangle \qquad (3)

where: $\alpha,\beta,\gamma$ — the amplitudes of the zero-, one-, and two-photon components of the mode; $-\gamma$ — the heralded sign flip applied to the two-photon amplitude alone. Reading it: the NS gate is a $\pi$ phase on the $|2\rangle$ rung of the ladder and nothing else. The NS gate is not unitary on demand. It is realized as a projection: signal and ancilla pass through a linear network, the ancillas are measured, and only a chosen detection pattern is kept. That conditioning is the effective nonlinearity.

|\psi_{\text{out}}\rangle \propto \hat\Pi_{\text{herald}}\;\hat U_{\text{linear}}\;|\psi_{\text{in}}\rangle\,|\text{anc}\rangle \qquad (4)

where: $\hat U_{\text{linear}}$ — the passive beam-splitter-and-phase network coupling signal and ancilla modes; $\hat\Pi_{\text{herald}}$ — the projector onto the heralding ancilla detection pattern; $|\text{anc}\rangle$ — the prepared ancilla state (for the NS gate, $|1\rangle|0\rangle$ ). Reading it: the non-unitary $\hat\Pi$ is what lifts the dynamics out of the Gaussian class. Two NS gates placed in the arms of a Mach–Zehnder interferometer combine into a controlled-Z between two dual-rail qubits — the entangling gate the whole protocol is built to deliver.

\mathrm{CZ}:\;|x\rangle|y\rangle \mapsto (-1)^{xy}\,|x\rangle|y\rangle,\qquad P_{\text{success}}=\tfrac{1}{16} \qquad (5)

where: $x,y\in\{0,1\}$ — the logical values of the two dual-rail qubits; $(-1)^{xy}$ — the conditional sign, acquired only when both qubits are $|1\rangle$ . Reading it: each NS fires with probability 1/4 and the two are independent, so the CZ fires with probability $(1/4)^2=1/16$ . To beat the dismal 1/16, KLM teleport the data qubit through a larger entangled resource. The resource $|t_n\rangle$ is an $(n{+}1)$ -term superposition that encodes the qubit across $n$ photons so that the teleporting Bell measurement almost always succeeds.

|t_n\rangle = \sum_{j=0}^{n}\,|1\rangle^{\otimes j}\,|0\rangle^{\otimes(n-j)}\;|0\rangle^{\otimes j}\,|1\rangle^{\otimes(n-j)} \qquad (6)

where: $n$ — the number of photons in the boosting resource; $j$ — the index labelling the $n+1$ terms of the entangled superposition. Reading it: spreading the qubit over $n$ photons gives $n+1$ distinguishable measurement outcomes, of which only one is unrecoverable. The resulting per-gate success probability is the central scaling law of KLM: it rises toward one as the resource grows, at a cost only polynomial in $n$ .

P_n = \frac{n}{n+1},\qquad 1-P_n=\frac{1}{n+1} \qquad (7)

where: $P_n$ — the probability the gate-teleportation step succeeds with an $n$ -photon resource; the residual $1/(n+1)$ — the heralded, correctable failure. Reading it: doubling the photon count roughly halves the failure rate, so any fixed target below 1 is reached with finite resources. All of this rests on one piece of two-photon physics — Hong–Ou–Mandel interference, the number-dependent bunching that a heralding measurement converts into a conditional phase.

|\psi_{\text{HOM}}\rangle = \frac{1}{\sqrt2}\big(|2\rangle_c|0\rangle_d - |0\rangle_c|2\rangle_d\big) \qquad (8)

where: $c,d$ — the two output modes of a balanced beam splitter fed one photon in each input; the absent $|1\rangle_c|1\rangle_d$ term — the vanishing coincidence, i.e. the two photons always exit together. Reading it: the coincidence amplitude destructively interferes, leaving only two-photon states — the raw material a detector turns into nonlinearity.

Derivation ABuilding the nonlinear sign-shift gate from three beam splitters

The goal is to exhibit an explicit passive network that realizes the NS map — sending $\alpha|0\rangle+\beta|1\rangle+\gamma|2\rangle$ to $\tfrac12(\alpha|0\rangle+\beta|1\rangle-\gamma|2\rangle)$ upon a fixed heralding outcome — and to pin down where the success probability 1/4 comes from and why it is independent of the input amplitudes. We work with the signal mode plus two ancilla modes prepared in $|1\rangle$ and $|0\rangle$ , send all three through a three-beam-splitter network, and keep only the runs in which the detectors report exactly one photon in the first ancilla and none in the second.

Step 1. Fix the network. The original KLM construction uses three beam splitters whose angles are $\theta_1=\theta_3=22.5^\circ$ and a central element with $\cos 2\theta_2 = 3-2\sqrt2$ , i.e. $\theta_2\approx40.06^\circ$ , together with fixed phase shifts. These specific values are chosen so that, after post-selecting on the $(1,0)$ ancilla pattern, the retained signal amplitudes for $|0\rangle$ , $|1\rangle$ , $|2\rangle$ are scaled by exactly $\tfrac12$ , $\tfrac12$ , and $-\tfrac12$ . Why: the phase on $|2\rangle$ relative to $|0\rangle$ and $|1\rangle$ is an interference effect that only comes out to $\pi$ for this fine-tuned splitting — a generic network would give some useless phase.

Step 2. Track the number states. Under the network the signal number state $|n\rangle$ tensored with the ancilla $|1,0\rangle$ evolves into $c_n|n\rangle|1,0\rangle$ plus terms with other ancilla patterns that we discard. The retained coefficients are $c_0=c_1=\tfrac12$ and $c_2=-\tfrac12$ . Why: because the map is linear, the surviving signal state is a fixed linear combination whose coefficients depend only on the network, not on the input amplitudes $\alpha,\beta,\gamma$ .

Step 3. Read off the heralded state. Since every retained amplitude is multiplied by the same $\tfrac12$ except for the sign on $|2\rangle$ , the post-selected signal is $\tfrac12(\alpha|0\rangle+\beta|1\rangle-\gamma|2\rangle)$ — the NS map, up to an overall $\tfrac12$ that is absorbed on renormalization. Why: an equal attenuation of all components is just a scale factor; only the relative sign carries physical content, and that sign is the whole point of the gate.

Step 4. Compute the yield. The success probability is $P_{NS}=\sum_n |c_n|^2|a_n|^2$ with $|c_n|^2=\tfrac14$ for every retained $n$ , so $P_{NS}=\tfrac14\sum_n|a_n|^2=\tfrac14$ for any normalized input. Why: because the attenuation is amplitude-independent, the gate is faithful — it never distorts the state it does deliver, and its 1/4 yield is a property of the network alone. *The key numerical check: the stated angles $\theta_1=\theta_3=22.5^\circ$ and $\cos2\theta_2=3-2\sqrt2$ yield exactly $c_0=c_1=\tfrac12$ , $c_2=-\tfrac12$ , and hence $P_{NS}=\tfrac14$ .*

Go deeper · Derivation B · 1 minWhy two NS gates give a controlled-Z that fires one time in sixteen

Derivation BWhy two NS gates give a controlled-Z that fires one time in sixteen

The goal is to see how the amplitude-only NS gate becomes a genuine two-qubit entangling gate, and to trace the controlled-Z success probability 1/16 to its origin as the product of two independent 1/4 events. The setup is two dual-rail qubits sharing a Mach–Zehnder interferometer: the two inner rails — the modes that are occupied when a qubit reads $|1_L\rangle$ — are interfered on a balanced beam splitter, an NS gate sits in each interferometer arm, and a second balanced beam splitter closes the loop.

Step 1. Route the inner rails together. Only when both qubits are in $|1_L\rangle$ do two photons enter the first balanced beam splitter, and Hong–Ou–Mandel interference then puts a genuine two-photon amplitude $|2\rangle$ into the arms. For the $|00\rangle$ , $|01\rangle$ , $|10\rangle$ inputs at most one photon is present, so no $|2\rangle$ component ever appears. Why: the conditional phase must act only on $|11\rangle$ , so we need a photonic signature — the $|2\rangle$ state — that is present for that input and absent for the others.

Step 2. Apply NS in each arm. The NS gates flip the sign of the $|2\rangle$ amplitude, which exists only for the $|11\rangle$ branch. After the closing beam splitter undoes the first, the net effect is a minus sign on $|11\rangle$ and identity on the rest — exactly $\mathrm{CZ}=\mathrm{diag}(1,1,1,-1)$ . Why: a sign that appears only when two photons meet is precisely the conditional phase $(-1)^{xy}$ ; the interferometer converts "sign on $|2\rangle$ " into "sign on $|1_L\rangle|1_L\rangle$ ."

Step 3. Multiply the yields. Each NS gate succeeds with probability 1/4 and the two act on independent modes, so the controlled-Z is heralded with probability $P=P_{NS}^2=(\tfrac14)^2=\tfrac{1}{16}$ . Why: the two heralding measurements are statistically independent, so their success probabilities multiply — there is no interference between the two ancilla systems that could rescue the rate. *The gate matrix is $\mathrm{diag}(1,1,1,-1)$ on the four dual-rail inputs, and the success rate is $(1/4)^2=1/16$ .*

Go deeper · Derivation C · 1 minTeleportation boosting and the n over n plus one success law

Derivation CTeleportation boosting and the n over n plus one success law

The goal is to explain how a gate that fires only 1 time in 16 becomes near-deterministic, and to derive the scaling $P_n=n/(n+1)$ that governs the cost. The engine is Gottesman–Chuang gate teleportation: rather than risk the fragile entangling gate on the data qubit, apply it offline to a disposable entangled resource, test that it worked, and only then teleport the data through the certified resource. What remains fallible is the teleporting Bell measurement, which in the photonic encoding cannot always be completed — but its failures are heralded and correctable.

Step 1. Move failure off the data. Apply the probabilistic entangling gate to half of a Bell-like resource state, offline. If it fails, throw the resource away and remake it; the data qubit is never touched. Why: failures now cost only ancillas, so the exponential blow-up of "retry the whole circuit on failure" is replaced by cheap offline retries.

Step 2. Encode across $n$ photons. Use the resource $|t_n\rangle=\sum_{j=0}^{n}|1\rangle^{j}|0\rangle^{n-j}|0\rangle^{j}|1\rangle^{n-j}$ , which distributes the logical qubit over $n$ photons and yields $n+1$ distinguishable total-photon-number outcomes in the Bell measurement. Why: a richer resource gives the incomplete linear-optical Bell measurement more room, so that all but one measurement outcome herald a known correctable teleportation.

Step 3. Count the outcomes. Of the $n+1$ possible detected photon numbers, $n$ herald a teleportation that can be completed with a known Pauli correction and exactly one is unrecoverable, so $P_n = n/(n+1)$ and the failure probability is $1/(n+1)$ . Why: the failure is a single boundary outcome, so its weight shrinks like $1/(n+1)$ as the resource grows — a clean, countable bookkeeping.

Step 4. Take the limit. As $n\to\infty$ , $P_n\to1$ : the gate becomes deterministic, and because the failure is heralded it can be handed to a quantum error-correcting code, giving fault-tolerant near-deterministic logic at cost polynomial in $n$ . Why: a heralded, polynomially-rare error is exactly what error correction is designed to absorb, closing the loop from "probabilistic" to "scalable." *The outcome count is $n$ recoverable out of $n+1$ total, giving $P_n=n/(n+1)$ and $P_n\to1$ as $n\to\infty$ .*

Limiting cases

How the protocol behaves at its extremes clarifies exactly what KLM delivers and what it does not.

Case	Result	Meaning
Single elementary CZ gate	$P_{\text{success}}=\tfrac{1}{16}$	Two NS gates at 1/4 each, combined in the Mach–Zehnder — the bare, unamplified entangling yield.
Teleportation boosting, $n$ ancillas	$P_n=\dfrac{n}{n+1}$	Gate teleportation through $\|t_n\rangle$ succeeds with probability $n/(n+1)$ , at polynomial cost.
Deterministic limit	$n\to\infty\;\Rightarrow\;P_n\to1$	Universal deterministic linear optics is recovered only asymptotically; any finite scheme is near-deterministic with bounded, correctable failure.
No ancillas, unitary only	$U\in\mathrm{Sp}(2m,\mathbb{R})$ (Gaussian)	Passive linear optics without measurement generates only mode-mixing Gaussian unitaries — provably non-universal for qubit logic, which is why ancillas and detection are essential.

Common trapThe controlled-Z always fires when you send the photons through

It does not. KLM gates are non-deterministic and heralded, not unitary on demand. Each elementary controlled-Z attempt succeeds with probability only 1/16, and you must observe the heralding detection pattern before you are allowed to trust the output. The saving grace is that failure is announced, not silent — a wrong ancilla pattern tells you the gate did not fire, so you either reattempt it or, better, correct it through gate teleportation. Treating the gate as deterministic is the single most common misreading of KLM and it is exactly why the naive protocol carries astronomical overhead. A second, subtler trap: the NS gate is defined only on the $\{|0\rangle,|1\rangle,|2\rangle\}$ photon-number subspace — feed it three or more photons in one mode and the carefully tuned interference no longer gives the clean sign flip.

Worked examples

1 · Photon budget for one raw controlled-Z (fully worked)

A bare KLM controlled-Z fires with probability $P=1/16$ , and each failed attempt is heralded so it can be retried. How many attempts should you expect before the first success, and how many attempts guarantee at least a 99% chance that the gate has fired at least once?

Step 1. Expected attempts to first success. Retries are independent Bernoulli trials with success probability $P=1/16$ , so the number of attempts is geometric with mean $1/P$ . That gives $\langle N\rangle = 1/P = \mathbf{16}$ attempts on average for a single raw controlled-Z.

Step 2. Probability of at least one success in $k$ attempts. The failure probability per attempt is $1-P=15/16$ , so the chance that all $k$ attempts fail is $(15/16)^k$ and the chance of at least one success is $1-(15/16)^k$ .

Step 3. Solve for the 99% target. Set $(15/16)^k = 0.01$ and take logs: $k = \ln(0.01)/\ln(15/16) = (-4.6052)/(-0.06454) = 71.3$ , so you need $k=\mathbf{72}$ attempts to be 99% sure the gate has fired at least once.

Step 4. Read the lesson. Even to fire one gate once with high confidence you burn dozens of attempts, and a useful algorithm chains thousands of gates in series where a single un-heralded failure would corrupt the data. This 16-attempts-per-gate, 72-for-99%-confidence blow-up is precisely why KLM needs teleportation boosting rather than brute-force retrying.

2 · Sizing the teleportation resource (fully worked)

Using the boosting law $P_n=n/(n+1)$ , how many ancilla photons $n$ does one gate teleportation need to reach a per-gate success probability of 0.99? Of 0.999? What does the trend imply?

Step 1. Invert the law. Set $n/(n+1)=P$ and solve: $n = P/(1-P)$ .

Step 2. Evaluate for 0.99. $n = 0.99/(1-0.99) = 0.99/0.01 = \mathbf{99}$ photons — matching the red point on the boosting figure.

Step 3. Evaluate for 0.999. $n = 0.999/0.001 = \mathbf{999}$ photons: each extra "nine" of reliability costs roughly a factor of ten more photons, since $n\approx 1/(1-P)$ for $P$ near 1.

Step 4. Interpret. The failure probability $1/(n+1)$ falls only polynomially (in fact linearly) in the resource size, so pushing toward determinism is expensive but never exponential — the resource stays polynomial, which is exactly the sense in which KLM is "efficient." Reaching 99% costs 99 photons and 99.9% costs 999; the scaling is polynomial, the practical constants brutal — which is why cluster-state descendants exist.

3 · Checking the NS gate on a balanced input

Feed the NS gate the balanced signal $|\psi\rangle=\tfrac{1}{\sqrt3}\big(|0\rangle+|1\rangle+|2\rangle\big)$ . What is the heralded output state, and what is the success probability?

Step 1. Apply the map. NS flips the sign of the $|2\rangle$ amplitude only, so the (renormalized) heralded output is $|\psi_{\text{out}}\rangle = \tfrac{1}{\sqrt3}\big(|0\rangle+|1\rangle-|2\rangle\big)$ — still a valid unit vector, since flipping a sign preserves the norm.

Step 2. Compute the yield. With $|a_n|^2 = 1/3$ for $n=0,1,2$ and the network attenuation $|c_n|^2=1/4$ for each, $P_{NS}=\sum_n |c_n|^2|a_n|^2 = 3\times\tfrac14\times\tfrac13 = \mathbf{1/4}$ .

Step 3. Confirm the key property. The yield came out to 1/4 independent of the equal-weight choice — the same value you would get for any normalized input — confirming the gate is faithful. Output $\tfrac{1}{\sqrt3}(|0\rangle+|1\rangle-|2\rangle)$ , success probability 1/4, amplitude-independent.

Physics of the portrait

The KLM protocol is one of those rare results that changed what an entire community believed was possible. It is named for three theorists at Los Alamos who, in a single 2001 paper, converted "linear optics is non-universal" from folklore into a precisely bounded — and surmountable — statement.

Origins · 1 minKnill, Laflamme and Milburn and how this was discovered

Knill, Laflamme and Milburn

scheme published in Nature, 2001 · linear-optical quantum computing

Emanuel Knill, Raymond Laflamme and Gerard Milburn published "A scheme for efficient quantum computation with linear optics" in Nature in January 2001, and with it founded a field. Knill and Laflamme were already central figures in quantum error correction — the Knill–Laflamme conditions for a correctable code bear their names, and both were architects of fault-tolerance theory — while Milburn was a leading quantum optician who understood photonic measurement to its roots. Their collaboration fused those two worlds. The prevailing view, going back to arguments that passive optics generates only Gaussian transformations, was that scalable optical quantum computing demanded a strong single-photon Kerr nonlinearity that no material could supply without ruinous loss. KLM's insight was that the nonlinearity did not have to live in a material at all: photodetection is already nonlinear, and feedforward can transplant its effect onto the photons that survive a heralding measurement. From that seed they built the nonlinear sign-shift gate, showed two of them make a controlled-Z, and — most importantly — proved that gate teleportation and an error-correctable bosonic code drive the success probability to one with only polynomial overhead. The paper is celebrated less for any single gadget than for its structure: a constructive, efficient proof that photons meet the DiVincenzo criteria. Within a few years Nielsen, Browne and Rudolph had recast the same probabilistic gates as a recipe for growing cluster states, cutting the overhead enormously and launching the measurement-based photonic architectures that dominate the field today.

History

1987

— Hong, Ou and Mandel observe two-photon bunching interference at a beam splitter

1999

— Gottesman and Chuang show gate teleportation makes a universality primitive out of measurement

2001

— Knill, Laflamme and Milburn publish the linear-optics scheme in Nature 409, 46

2005

— Nielsen and, separately, Browne and Rudolph recast KLM as cluster-state generation, slashing overhead

2021

— Fusion-based and cluster-state photonic processors, direct descendants of KLM, reach industrial scale

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, §7.4 (optical implementations) · Kok, Munro, Nemoto, Ralph, Dowling & Milburn, "Linear optical quantum computing with photonic qubits," Rev. Mod. Phys. 79, 135 (2007) — the definitive review · Knill, Laflamme & Milburn, "A scheme for efficient quantum computation with linear optics," Nature 409, 46 (2001) — the original · Preskill, Lecture Notes on Quantum Computation, Ch. 9 · Gottesman & Chuang, "Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations," Nature 402, 390 (1999). The key numerical values are: NS gate yield $1/4$ (from network amplitudes $c_0=c_1=\tfrac12$ , $c_2=-\tfrac12$ ); controlled-Z yield $1/16$ ; boosting law $P_n=n/(n+1)$ ; 16 mean attempts per raw CZ, 72 attempts for 99% confidence; $n=99$ photons for $P=0.99$ , $n=999$ for $P=0.999$ .

Prerequisites. Photonic Qubits · Linear-Optical Quantum Computing · DiVincenzo Criteria. Leads to. Linear-Optical Quantum Computing · Photonic Qubits.

Ask the tutor: ask me to trace a photon through the NS gate, work out any KLM photon budget, or show how gate teleportation boosts 1/16 up toward one.

Why is measurement "nonlinear" when the optics is linear?

A beam splitter maps creation operators linearly into creation operators, so it can only produce Gaussian transformations — mode rotations that conserve photon number and never introduce a conditional phase. Photodetection is a completely different kind of operation: it is a projection, non-unitary and outside the Gaussian class. When you measure the ancilla photons and keep only a particular outcome, you apply a projector to the joint state, and projecting an entangled state can leave the surviving photons in a configuration no passive network could have produced. That is the sense in which "measurement is nonlinear": the effective map on the data photons, conditioned on the herald, is exactly the non-Gaussian gate the glass alone could never implement.

What is the nonlinear sign-shift gate and why is it the key ingredient?

The NS gate acts on a single optical mode's photon-number amplitudes, sending $\alpha|0\rangle+\beta|1\rangle+\gamma|2\rangle$ to $\alpha|0\rangle+\beta|1\rangle-\gamma|2\rangle$ — a $\pi$ phase on the two-photon rung and nothing else. That specific, photon-number-dependent phase is the smallest genuinely non-Gaussian operation you need: everything universal in KLM is assembled from it. Two NS gates inside a Mach–Zehnder interferometer turn "sign on $|2\rangle$ " into "sign on $|1_L\rangle|1_L\rangle$ ," which is the controlled-Z. The NS gate is realized by a fixed three-beam-splitter network with a one-photon ancilla, heralded by detecting one photon in one ancilla mode and none in the other, and it succeeds with probability 1/4.

Where does the 1/16 controlled-Z probability come from?

The controlled-Z is built from two nonlinear sign-shift gates, one in each arm of a Mach–Zehnder interferometer. Each NS gate is itself heralded — it only fires when its ancilla detectors report the right pattern — and that happens with probability 1/4. The two NS gates act on independent ancilla systems, so their successes are statistically independent and the probabilities multiply: $\tfrac14\times\tfrac14=\tfrac{1}{16}$ . There is no clever interference between the two ancilla measurements that could rescue the rate, so 1/16 is the honest, unavoidable yield of a bare KLM entangling gate — and the reason the protocol needs teleportation boosting.

How does teleportation turn a 1-in-16 gate into a near-certain one?

The trick is to never risk the entangling gate on your data. Instead you apply it offline to a disposable entangled resource state; if it fails, you throw the resource away and remake it, so failures cost only ancillas. Once you have a resource that passed the test, you teleport your data qubit through it, and the gate comes along for free. The only remaining failure is the teleporting Bell measurement, which in linear optics is incomplete — but by spreading the qubit over $n$ photons in the resource $|t_n\rangle$ , you make all but one of the $n+1$ measurement outcomes correctable. The success probability is then $n/(n+1)$ , which you can push as close to 1 as you like.

Does KLM violate the theorem that linear optics is non-universal?

No — it respects it precisely and then steps outside its assumptions. The no-go statement is about passive, unitary linear optics with no measurement: such networks generate only Gaussian transformations and cannot do universal qubit logic. KLM does not challenge that. What it adds are two ingredients the theorem never covered: ancilla photons and projective photodetection with feedforward. Those are non-Gaussian and non-unitary, and they supply exactly the effective nonlinearity universality requires. So the lesson is not that the no-go theorem was wrong, but that its scope was narrower than people assumed — "linear optics" in practice includes the detectors, and detectors change everything.

Why does anyone still care about KLM if real machines don't use it?

Because KLM is the proof of concept the whole field is built on, and its ideas are everywhere even where its literal circuit is not. Cluster-state and fusion-based photonic computers replace bare KLM to cut overhead, but they still rely on probabilistic, heralded, linear-optical entangling operations — that is pure KLM logic, just applied offline to build a resource state instead of online to run the algorithm. The 1/16 and $n/(n+1)$ numbers remain the benchmarks engineers quote to size photon budgets and detector requirements. And the central principle — synthesize an interaction you cannot build by measuring something and feeding the result forward — reappears in magic-state injection, quantum repeaters, and measurement-based computing far beyond optics.