U (0,0) = , U (1,1) = ,

0 ’1

01

(20.70)

01 01

(0,1) (1,0)

U ,U ,

= =

’1 0

10

then it is easy to verify that

U (1,1) ¦+ = ¦’ , U (0,1) ¦+ = Ψ+ , U (1,0) ¦+ = Ψ’ . (20.71)

After the programmer supplies the two bits needed to choose the operator U f ”

i.e. the one that gives the same output as the classical computer”the output of the

computation is obtained by performing a Bell state measurement. If the result is |Ψ+ ,

then f = (0, 1), etc. The important point is that it is only necessary to run the quantum

algorithm once to get both values f (0) and f (1). Thus quantum parallelism gives the

same result as classical parallelism, but the work of the two classical computers is done

by one quantum computer.

Quantum logic gates—

B

The description of the simple quantum computer given in the last section ¬ts con-

veniently with the discussion of quantum dense coding in Section 20.4.1, but it does

not have the form commonly used in the quantum computing literature. The usual

procedure is to express the operator Ualg as the product of a standard set of unitary

operators, called quantum logic gates, that typically act on one or two qubits out

of the N qubits in the register. Since the output of each gate serves as input to the

next, the collection of gates can be visualized as a quantum circuit.

Classical computers employ operations on single bits and pairs of bits, and it has

been shown that the most general computation can be performed by means of a single

kind of two-bit gate combined with a collection of single-bit gates. An analogous result

holds for quantum computers, so we only need to consider a single kind of two-qubit

gate.

A one-qubit logic gate is completely speci¬ed by its action on the basis vectors |0

and |1 ; for example, the X gate is de¬ned by X |0 = |1 , and X |1 = |0 . This is

analogous to the classical NOT gate that interchanges 0 (false) and 1 (true). There

¿¿

Quantum computing

are also useful one-qubit gates that do not have classical analogues, such as the Z

gate: Z |0 = |0 , Z |1 = ’ |1 , and the Hadamard gate:

1 1

H |0 = √ {|0 + |1 } , H |1 = √ {|0 ’ |1 } .

2 2

These gates can all be expressed as 2 — 2 matrices, and”as seen in Exercises 20.15

and 20.16”they are also related to rotations on the Poincar´ sphere.

e

An important two-qubit gate is the controlled-NOT (C-NOT) gate, de¬ned by

CNOT |a, b = |a, b • a (a, b = 0, 1) , (20.72)

where • represents addition modulo 2. The ¬rst and second qubits in the two-qubit

state |a, b = |a |b are conventionally called the control qubit and the target qubit

respectively.

Thus the C-NOT gate has the following e¬ects. (1) The control qubit is left un-

changed. (2) The target qubit is ¬‚ipped if the control qubit is 1, and left alone if the

control qubit is 0. A convenient graphical notation for these standard gates is shown

in Fig 20.7.

Another useful two-qubit gate is the controlled-sign or controlled-phase gate

de¬ned by

ab

CS |a, b = (’1) |a, b (a, b = 0, 1) . (20.73)

This operation does nothing unless both the control and target qubits are |1 , in which

case it multiplies the two-qubit state by ’1.

C Quantum circuits—

In Section 20.5.1-A we ¬‚outed the convention that the register always begins in a

standard state, e.g. |Λin = |0, 0 . It is easy to verify that |¦+ = CNOT H |0, 0 , i.e.

the initial state used in the previous discussion is built up from the standard state by

applying a Hadamard gate followed by a controlled-NOT gate.

Inspection of eqn (20.70) shows that the operator U (0,1) leading to the outcome

|Ψ+ is an X gate, so the result f = (0, 1) is achieved by the unitary transformation

|Ψ+ = U (0,1) |¦+ = XCNOT H |0, 0 . The corresponding quantum circuit diagram,

shown in Fig. 20.8, is to be read from left to right. Other examples are considered in

Exercise 20.17.

Fig. 20.7 Graphical representations of quantum logic gates: (a) a generic one-qubit gate,

and (b) a controlled-NOT gate, with control qubit |a and target qubit |b .

¿ Quantum information

Fig. 20.8 Quantum circuit diagram for

the program implemented by the sequence:

Hadamard gate, controlled-NOT gate, and X

gate.

Quantum computing experiments—

20.5.2

Experimental realizations of the idealized devices discussed above must overcome a

number of very serious di¬culties. To begin with, the qubits must be controllable

to one part in 104 by means of analog pulses (Berggren, 2004). This is an especially

acute problem if the qubits are carried by photons. The dissipative interaction of the

qubits with the environment poses a still more daunting obstacle, since the resulting

decoherence will destroy the entangled state.

Decoherence can be reduced by clever design, but it is impossible to eliminate it

altogether. This fact has necessitated the introduction of error-correction protocols,

¬rst by Shor (1995), and later by Bennett et al. (1996) and Knill and La¬‚amme (1997).

A common feature of these schemes is the use of a large number of ancillary qubits to

guarantee the accuracy of the computation.

The necessity of error correction is a strong contributor to estimates that something

like 106 qubits would be needed for a computation of practical interest (Berggren,

2004). Experiments performed to date only involve a few qubits, but scalability, i.e.

the potential for extending a scheme to a very large number of qubits, is a primary

concern.

The ¬rst experimental demonstrations of quantum computing (Chuang et al., 1998;

Vandersypen et al., 2001) used the method of bulk quantum computation (Knill et al.,

1998), in which a large number of qubits”provided by spin-1/2 nuclei in molecules”

are manipulated in parallel by nuclear magnetic resonance (NMR) techniques. This

approach is adequate for proof-of-principle demonstrations but cannot be used for

register sizes much greater than ten.

In order to achieve scalability, subsequent proposals have concentrated on vari-

ous solid-state systems, e.g. nuclear spins of donor atoms in Si (Kane, 1998), elec-

tron spins in quantum dots (Loss and DiVincenzo, 1998; Petta et al., 2005), qubits

formed by counter-circulating persistent currents in Josephson junction circuits (Mooij

et al., 1999), electron-spin-resonance transistors (Vrijen et al., 2000), and electron spins

bound to deep donor states in Si (Stoneham et al., 2003).

The physical system of greatest interest for us”the photon”is conspicuously ab-

sent from this list of candidates for quantum computers. The reason is that a two-qubit

logic gate, such as the C-NOT gate discussed in Section 20.5.1-B, can only produce an

entangled state”in our terminology a dynamically entangled state”of two photons

by means of photon“photon coupling, i.e. an optical nonlinearity.

As suggested by Milburn (1989), one way to do this would be to induce a cross-

Kerr coupling”see Section 13.4.3”between two optical modes. Unfortunately, the

materials provided by nature have χ(3) s that are orders-of-magnitude too small to

accomplish the desired e¬ects. Increasing the length of the nonlinear region does not

¿

Quantum computing

help, because the accompanying linear absorption will defeat the purpose of the device.

Another possibility is to trap an atom in a very small, high ¬nesse cavity, but this

approach has not yet been successful. This situation led to the general feeling that

large-scale quantum computing by optical means is not a practical possibility.

Two-photon logic gates with linear optics—

20.5.3

The consensus view that optical methods are not suitable for quantum computing

was challenged by the work of Knill, La¬‚amme, and Milburn (KLM) (Knill et al.,

2001), who showed that quantum algorithms could be implemented by combining

single-photon sources, photon detectors, and passive linear optical elements.

Their scheme eliminated the need for strong optical nonlinearities in the manipula-

tion of photonic qubits. This is a complex and rapidly evolving subject, so we will only

sketch the ¬rst step in its development. More details can be found in recent review

articles, e.g. Ralph (2006).

One possible design”adapted from the work of Hofmann and Takeuchi (2002)”for

a two-photon logic gate utilizing only linear optics and photon detection is shown in

Fig. 20.9.

This is a four channel/eight port device; the four input ports are the Control-

in port, the Target-in port, and the unused ports of beam splitters 1 and 3, that

Control-in

Vac-1

Loss-1 D

L

Target-in

D L

L D

Control-out

L

Vac-2

D

Loss-2

Target-out

Fig. 20.9 Schematic for a nondeterministic control-NOT gate. The polarizing beam splitters

transmit v-polarized light and re¬‚ect h-polarized light at 90—¦ . The half-wave plate (hwp) at

the control input is aligned at ‘ = 0, while the hwps at the target input and output ports

are aligned at ‘ = ’22.5—¦ , where ‘ is the angle between the h-polarization and the fast axis;

see Exercise 20.8. The beam splitters are asymmetric.

¿ Quantum information

communicate with the vacuum channels Vac-1 and Vac-2. The beam splitters are

asymmetric, with scattering laws of the general form

√

√

a1 = 1 ’ Ra1 ’ Ra2 ,

√ √ (20.74)

Ra1 + 1 ’ Ra2 ,

a2 =

worked out in Exercise 8.1. All three beam splitters are assumed to have the same

re¬‚ectivity R, and the sign factors = ±1 are chosen to accomplish the design objec-

tives. The half-wave plate at the control input is a Z gate, and the half-wave plates at

the target ports are Hadamard gates.

The use of passive optical elements ensures that photon number is conserved, so for

two incident photons”one in the control channel and one in the target channel”we

can be sure that exactly two photons will be emitted. However, the mixing occurring at

the beam splitters implies that the output state will be a superposition of all possible

two-photon states in the output channels: Control-out, Target-out, Loss-1, and Loss-2.

The central beam splitter is particularly important in this regard, since photons

are incident from both sides. As we have seen in Section 10.2.1, this is precisely the

situation required for the strictly quantum interference e¬ects associated with di¬erent

Feynman paths having the same end point.

The key to the operation of this gate is postselection, i.e. discarding all outcomes

that do not satisfy a chosen criterion. In the present case, the ¬rst part of the criterion

is that detectors in the Control-out and Target-out channels should eventually register

a coincidence count. The states that can contribute to such a coincidence event are su-

perpositions of the coincidence basis states {|hC , hT , |hC , vT , |vC , hT , |vC , vT }.

Satisfying the condition (20.72) for a control-NOT gate further requires that ex-

actly one member of the coincidence basis occurs in the output state for each of the four

possible input states. A rather lengthy calculation, outlined in Exercise 20.18, shows

that this goal can only be reached for the value R = 1/3 and asymmetry parameters

satisfying 2 = ’ 3 = 1 .

With these values, the operation of the gate is given by

1 1

CNOT |hC , hT = |hC , hT + · · · , CNOT |hC , vT = |hC , vT + · · · ,

3 3 (20.75)

1 1

CNOT |vC , hT = |vC , vT + · · · , CNOT |vC , vT = |vC , hT + · · · ,

3 3

where ˜· · · ™ contains the terms that are not in the subspace spanned by the coincidence

basis. The target photon polarization is unchanged if the control photon is h-polarized

but ¬‚ipped (h ” v), when the control photon is v-polarized. With the identi¬cation

h ” 0 and v ” 1, this is the photonic version of eqn (20.72).

A simple modi¬cation of the design in Fig. 20.9 yields the gate action

1 1

CS |hC , hT = |hC , hT + · · · , CS |hC , vT = |hC , vT + · · · ,

3 3 (20.76)

1 1

CS |vC , hT = |vC , hT + · · · , CS |vC , vT = ’ |vC , vT + · · · ,

3 3

which satis¬es the de¬nition (20.73) of a controlled-sign gate.

¿

Quantum computing

The postselection criterion picks out the appropriate outcomes, but the probability

2

for successful operation is (1/3) = 1/9. Eight times out of nine, the two photons are

emitted into the wrong channels, e.g. one photon into Loss-2 and one into Control-1,

or two photons into Control-out, etc. The success or failure of the gate is heralded”

i.e. the outcome is known”by the presence or absence of a coincidence between the

Control-out and Target-out channels. Additional checks could be made by detecting

photons emitted into the loss channels, or by discriminating between one- or two-

photon events in the control and target channels.

This gate has been experimentally realized (O™Brien et al., 2003) by using down-

conversion to produce the input photons and quantum state tomography to verify

that the output states agreed with the theoretical model. In this approach, the neces-

sity for dynamically coupling the two photons has been avoided by incorporating the

coincidence measurement as part of the action of the device.

Linear optical quantum computing—

20.5.4

The quantum logic gate discussed above does provide a nontrivial two-qubit operation,

but it fails the scalability test. A device containing many such gates, each with a success

probability of 1/9, would almost never work. In their general scheme, KLM answered

this objection by making use of the ideas involved in quantum teleportation.

The use of quantum teleportation to carry out general quantum computations was

¬rst suggested by Gottesman and Chuang (1999), and KLM showed that a so-called

teleportation gate could be realized with a high probability of success, given a

su¬ciently complex entangled state.

The KLM approach avoids the failure mode associated with a vanishingly small

success probability, but the resources required are too large for practical scalability.

For example, the number of Bell pairs”i.e. pairs of photons described by a Bell

state”needed to implement a single controlled-sign gate with success probability of

95% is of the order 10 000 (Ralph, 2006).

This resource cost can be greatly reduced by using parity-state encoding (Hayes

et al., 2004). Single-qubit parity states are the alternative basis states,

√

|± = (|0 ± |1 ) / 2 , (20.77)

that satisfy X |± = ± |± . In parity-state encoding, the logical 0 and 1 are represented

by n-qubit states:

1

|0 (n) = √ —n |+ j + —n |’ j ,

j=1 j=1

2

(20.78)

1

(n)

= √ —j=1 |+ j ’ —j=1 |’ j .

|1 n n

2

A clever application of this encoding scheme reduces the overhead cost to the order of

100 Bell pairs per gate.

An alternative scheme”which actually amounts to a fundamentally di¬erent model

for quantum computing”grew out of a theoretical proposal by Raussendorf and Briegel

(2001). In the standard model sketched in Section 20.5.1, an algorithm is represented

as a sequence of unitary operators that are physically realized by quantum logic gates.

¿ Quantum information

The logic gates produce a sequence of entangled states that ends in the desired ¬nal

state, which is measured to produce the computational result.

In the new model, the entanglement resource is prepared beforehand, in the form

of a highly entangled, multi-qubit, initial state. The nature of this state is most easily

understood by visualizing the qubits as spin-1/2 particles attached to the sites of a

lattice and interacting through nearest-neighbor coupling. A cluster is a collection

of occupied lattice points such that each pair of sites is connected by jumps across

nearest-neighbor links. Each qubit is initially prepared in the parity state |+ and a

cluster state is generated by pair-wise entanglement of the initial qubits.

As an example, consider a one-dimensional lattice with three occupied sites, 1, 2,

3, so that the initial state is |+ 1 |+ 2 |+ 3 . The corresponding cluster state can be

generated by successive application of controlled-sign gates as follows:

(1,2) (2,3)

|¦lin3 = CS |+ CS |+ |+ , (20.79)

1 2 3

(i,j)

where CS acts on two-qubit states |a i |b j . Carrying out the gate operations, with

the aid of the de¬nitions (20.73) and (20.77), leads to the explicit expression

1

|¦lin3 = √ [|+ |0 |+ + |’ |1 |’ 3 ] (20.80)

1 2 3 1 2

2

for the cluster state. The cluster states needed for nontrivial calculations generally

involve clusters on two-dimensional lattices and many more qubits.

The cluster state provides the essential substrate for the computation, but the al-

gorithm itself is de¬ned by combining two further elements: (1) a sequence of local

measurements (von Neumann measurements on individual qubits); and (2) classi-

cal feedforward. The latter term means that the result of one measurement in the

sequence can be used to determine the choice of the measurement basis used in a

subsequent measurement.

These two elements can replace any of the operations considered in Section 20.5.1.

For example, any unitary operation on a single qubit can be simulated by means of a

four-qubit cluster state and three measurements. In general, one-qubit measurements

are used to imprint the initial data onto the cluster state, and then process it to yield

the ¬nal result.

The use of irreversible measurements as an integral part of the algorithm, rather

than just the ¬nal readout step, has led to the name one-way quantum computing

for this approach. For a su¬ciently large cluster state, it has been shown that these

elements are su¬cient to implement a universal quantum computer. The di¬erent

structures of reversible and one-way computing make comparisons a bit di¬cult, but

the current estimate is that one-way computing requires roughly 60 Bell pairs per

two-qubit gate operation.

Highly entangled states of many atoms have been experimentally produced by

precise control of the interactions between neutral atoms bound by dipole forces to

the sites of an optical lattice (Mandel et al., 2003), but we are more interested in

optical realizations of cluster states. Walther et al. (2005) demonstrated a one-way

version of a simple example of Grover™s search algorithm.

¿

Exercises

In their experiment, a four-photon cluster state was directly produced by down-

conversion techniques. Four-qubit cluster states have also been produced by entangling

EPR pairs with a controlled-sign gate (Kiesel et al., 2005), and by a technique called

type-I qubit fusion (Zhang et al., 2006), which combines Bell states by mixing at a

beam splitter and postselection. One-way quantum computing may, therefore, be a

promising application of quantum optics to quantum computing.

20.6 Exercises

20.1 Variable retarder plate

Design a variable retarder plate by joining two identical, thin, right-angle prisms along

their hypotenuses. Sketch the appropriate arrangement and carry out the following.

(1) Assuming that the light passes through the central part of the retarder, show how

the optical path length can be adjusted by sliding the prisms along their common

hypotenuse.

(2) Express the optical path length in terms of the index of refraction and the geo-

metrical parameters of the device. Assign numerical values for a practical design.

(3) Calculate the optical path lengths required to obtain the phase shifts θ = ’π/2

and θ = π/2.

20.2 Modi¬ed beam splitter

Consider the modi¬ed beam splitter pictured in Fig. 20.1.

(1) Derive eqn (20.5) for the scattering matrix.

(2) For general values of θ and θ , use the scattering matrix to express the output

quadratures X1 , Y1 , X2 , Y2 in terms of the input quadratures X1 , Y1 , X2 , Y2 .

Calculate the variances of the output quadratures. Explain why the values θ =

’π/2 and θ = π/2 are particularly useful.

(3) If no variable retarder plates are available, i.e. θ = θ = 0, how can the operation

of the SQLG be changed to achieve the same noiseless splitting of the input signal

X1 .

20.3 Bell states

Consider the Bell states de¬ned in eqn (20.15).

(1) Show that the Bell states are mutually orthogonal and all normalized to unity.

(2) Explain”ideally without any further algebra”why the Bell states form a basis

for Ha — Hb .

20.4 No-cloning theorem for photons

Consider cloning the one-photon states |γ = “† |0 and |ζ = Z † |0 , where

ζks a† .

Z† = ks

s

¼ Quantum information

(1) Derive the commutator

Z, “† = —

ζks γks ≡ (ζ, γ) .

ks

(2) Adapt the general proof for the no-cloning theorem to show that the cloning

assumption (20.25), and the corresponding assumption for |ζ , cannot be satis¬ed

for all choices of the operators “† and Z † .

20.5 Cloning a known state

For the device in Section 20.2.1 that clones a known state, assume the model interaction

Hint = gσ’ a† + a† + HC, between the two-level atom and the ¬eld. For the initial

kh kv

state |1kh , use ¬rst-order, time-dependent perturbation theory to calculate the change

in the initial state vector and thus derive eqn (20.26).

Buˇek“Hillery QCM—

20.6 z

Use the explicit expressions (20.31) and (20.32) to evaluate the reduced qubit density

operators ρab , ρa , and ρb . Use the results to calculate the ¬delities for the clones a and

b.

Photon cloning machine—

20.7