Emerged as a leading approach14.

A major di ffi culty for optical quantum information

Processing (QIP) is in realizing two-qubit entangling logic

Gates. The canonical example is the controlled-NOT gate

(CNOT), which fl ips the state of a target qubit con-

Ditional on a control qubit being in the logical state

“1”—the quantum analogue of the XOR gate. Figure

2a outlines why this operation is di ffi cult: The two opti-

Cal paths that encode the target qubit are combined at

a 50% re fl ecting beamsplitter (BS). The output modes

Of this BS are then combined at a second BS to form a

Mach-Zehnder interferometer. The logical operation of

This interferometer by itself is to do nothing: classical

Interference of the single photon in the interferometer re-

Sults in the target photon exiting in the same state it

entered in, i.e. |0i→|0i;|1i→|1i. If, however, the

π phase shift is applied inside the interferometer (such

that |0i+|1i↔|0i−|1i) the target qubit undergoes a

bit- fl ip or NOT operation: |0i↔|1i. A CNOT must

Implement this phase shift if the control photon is in the

“1” path. No known or foreseen nonlinear optical mate-

Rial has a non-linearity strong enough to implement this

Conditional phase shift (although progress has been made

with single atoms in high- fi nesse optical cavities11,15, as

Discussed below, and electromagnetically induced trans-

Parency has been considered16).

In 2001 a surprising breakthrough showed that scalable

Quantum computing is possible using only single photon

Sources and detectors, and linear optical networks17—

I.e. without the need for an optical nonlinearity. This

scheme uses additional auxiliary (or ‘ancilla’) photons

That are not part of the computation, but enable a CNOT

Gate to work. A cartoon of a non-deterministic (proba-

Bilistic with success signal) CNOT is shown in Fig. 2b.

The control and target qubits, together with two auxil-

iary photons, enter a (here unspeci fi ed) optical network

Of BSs (essentially a multi-path nested interferometer),

Where the four photons’ paths are combined, and quan-

tum interference can occur (Fig. 2c). At the output of

This network, the control and target photons emerge, hav-

Ing had the CNOT logic operation applied to their state,

Conditional on a single photon being detected at both

Detectors. This detection event occurs with probability

P < 1; the rest of the time another detection pattern is

Recorded. The success probability of this nondetermin-

Istic CNOT can be boosted to near-unity by harnessing

Quantum teleportation9,18—a process whereby the un-

Known state of a qubit can be transferred to another

Qubit. The idea is to teleport the control and target

Qubits onto the output of a non-deterministic gate that

Has already been measured to have worked19.

Although this ‘KLM’ scheme17 was ‘in-principle’ possi-

Ble, initially the large resource overhead arising from the

nondeterministic interactions and the di ffi culty of con-

Trolling photons moving at the speed of light made it

3

!"

#"

!"

#"

$%&#'" (")"*"

&"

$"

a!

a!

Control!

Target!

Single!

Photon!

Single!

Photon!

Single Photon!

Detection!

Single Photon!

Detection!

Linear Optical

Network!

Linear optical network!

+,"

!"

$"

*"

*"

""&"""

%"

FIG. 2: An optical controlled-NOT gate. a, Schematic of a

Possible realization of an optical CNOT gate. b, Schematic of

The KLM scheme. c, Quantum interference of photons: two

Photons arriving simultaneously at a beamsplitter both leave

In the same output mode with certainty because quantum

Interference of the probability amplitudes to detect a photon

At A and at B destructively interfere. d, A Mach-Zehnder

interferometer. The sensitivity with which the phase φ can be

Measured is related to the gradient of the interference fringe.

Practically daunting. This situation has changed over

The past several years14: Experimental proof-of-principle

Demonstrations of two-20–23 and three-qubit gates24 were

Followed by demonstrations of simple-error-correcting

Codes25–27 and small-scale quantum algorithms28,29. New

Theoretical schemes, which dramatically reduced the con-

Siderable resource overhead30–33 by applying the previ-

Ously abstract ideas of cluster state (or measurement-

based) quantum computing34, were soon followed by ex-

Perimental demonstrations35,36.

Even with these advances, the resource overhead