VOLUME 86, NUMBER 22 PHYSICAL REVIEW LETTERS 28 MAY 2001

A One-Way Quantum Computer

Robert Raussendorf and Hans J. Briegel
Theoretische Physik, Ludwig-Maximilians-Universität München, Germany
(Received 25 October 2000)
We present a scheme of quantum computation that consists entirely of one-qubit measurements on a
particular class of entangled states, the cluster states. The measurements are used to imprint a quantum
logic circuit on the state, thereby destroying its entanglement at the same time. Cluster states are thus
one-way quantum computers and the measurements form the program.

DOI: 10.1103/PhysRevLett.86.5188 PACS numbers: 03.67.Lx, 03.65.Ud

A quantum computer promises efficient processing of the state of a cluster 共C 兲 of neighboring qubits, which is
certain computational tasks that are intractable with clas- thereby created provides in advance all entanglement that
sical computer technology [1]. While basic principles of a is involved in the subsequent quantum computation. It has
quantum computer have been demonstrated in the labora- been shown [6] that the cluster state jF典C is characterized
tory [2], scalability of these systems to a large number of by a set of eigenvalue equations
qubits [3], essential for practical applications such as the O
sx共a兲 sz共a 兲 jF典C 苷 6jF典C ,
0

Shor algorithm, represents a formidable challenge. Most (1)

a0 [ngbh共a兲
of the current experiments are designed to implement se-
quences of highly controlled interactions between selected where ngbh共a兲 specifies the sites of all qubits that inter-
particles (qubits), thereby following models of a quan- act with the qubit at site a [ C . The eigenvalues are de-
termined by the distribution of the qubits on the lattice.
tum computer as a (sequential) network of quantum logic
The equations (1) are central for the proposed computation
gates [4,5].
scheme. As an example, a measurement on an individual
Here we propose a different model of a scalable quan-
qubit of a cluster has a random outcome. On the other
tum computer. In our model, the entire resource for the
hand, Eqs. (1) imply that any two qubits at sites a, a0 [ C
quantum computation is provided initially in the form of
a specific entangled state (a so-called cluster state [6]) of can be projected into a Bell state by measuring a subset of
a large number of qubits. Information is then written onto the other qubits in the cluster. This property will be used to
the cluster, processed, and read out from the cluster by define quantum channels that allow us to propagate quan-
one-particle measurements only. The entangled state of tum information through a cluster.
the cluster thereby serves as a universal “substrate” for any We show that a cluster state jF典C can be used as a sub-
quantum computation. Cluster states can be created effi- strate on which any quantum circuit can be imprinted by
ciently in any system with a quantum Ising-type interaction one-qubit measurements. In Fig. 1 this scheme is illus-
(at very low temperatures) between two-state particles in trated. For simplicity, we assume that in a certain region
a lattice configuration. of the lattice each site is occupied by a qubit. This re-
We consider two- and three-dimensional arrays of quirement is not essential as will be explained below [see
qubits that interact via an Ising-type next-neighbor in- (d)]. In the first step of the computation, a subset of
teraction [6] described by a Hamiltonian Hint 苷 g共t兲 3 qubits is measured in the basis of sz which effectively
P 共a兲 共a0 兲 P removes them. In Fig. 1 these qubits are denoted by “ Ø.”
⬵ 2 14 g共t兲 具a,a0 典 sz共a兲 sz共a 兲 [7] whose
11sz 12sz 0
具a,a 典
0
2 2
strength g共t兲 can be controlled externally. A possible information flow
realization of such a system is discussed below. A qubit at
site a can be in two states j0典a ⬅ j0典z,a or j1典a ⬅ j1典z,a ,
the eigenstates of the Pauli phase flip operator sz共a兲
关sz共a兲 ji典a 苷 共21兲i ji典a 兴. These two states form the compu-
tational basis. Each qubit can equally be in an arbitrary
superposition state aj0典 1 bj1典, jaj2 1 jbj2 苷 1. For
our purpose, we initially prepare quantum gate
p all qubits in the su-
perposition j1典 苷 共j0典 1 j1典兲兾 2, an eigenstate of the
Pauli spin flip operator sx 关sx j6典 苷 6j6典兴. Hint is
then switched on for RTan appropriately chosen finite time
interval T , where 0 dt g共t兲 苷 p, by which a unitary FIG. 1. Quantum computation by measuring two-state parti-
cles on a lattice. Before the measurements the qubits are in the
transformation S is realized. Since Hint acts uniformly on cluster state jF典C of (1). Circles Ø symbolize measurements of
the lattice, entire clusters of neighboring particles become sz , vertical arrows are measurements of sx , while tilted arrows
entangled in one single step. The quantum state jF典C , refer to measurements in the x-y plane.

5188 0031-9007兾01兾86(22)兾5188(4)$15.00 © 2001 The American Physical Society

VOLUME 86, NUMBER 22 PHYSICAL REVIEW LETTERS 28 MAY 2001

The state jF典C is thereby projected into a tensor prod- surements (basis 兵j1典j 苷 j0典x,j , j2典j 苷 j1典x,j 其) at qubit
uct jm典C nN ≠ jF̃典N consisting of the state jm典C nN of sites j 苷 1, . . . , n 2 1 with measurement outcomes sj [
all measured particles (subset C nN ) on one side and an 兵0, 1其. The resulting state is js1 典x,1 ≠ · · · ≠ jsn21 典x,n21 ≠
entangled state jF̃典N of yet unmeasured particles (subset jcout 典n . The output state jcout 典 is related to the input state
N , C ), on the other side. These unmeasured particles jcin 典 by a unitary transformation US [ 兵1, sx , sz , sx sz 其
define a “network” N corresponding to the shaded struc- which depends on the outcomes of the sx measurements
ture in Fig. 1. The state jF̃典N of the network is related at sites 1 to n 2 1. A similar argument can be given for an
to a cluster state jF典N on N by a local unitary transfor- even number of qubits. The effect of US can be accounted
mation which depends on the set of measurement results for at the end of a computation as shown below [see (d)].
m. More specifically, jF̃典N satisfies Eqs. (1)— with C It is noteworthy that not all classical information gained
replaced by the subcluster N — except for a possible dif- by the sx measurements needs to be stored to identify the
ference in the sign factors, which are determined by the transformation US . Instead, US is determined by the val-
measurement results m. ues of only two classical bits which are updated with every
To process quantum information with this network, it measurement.
suffices to measure its particles in a certain order and in a (b) An arbitrary rotation UR [ SU共2兲 can be achieved
certain basis. Quantum information is thereby propagated in a chain of five qubits. Consider a rotation in its
horizontally through the cluster by measuring the qubits Euler representation UR 共j, h, z 兲 苷 Ux 共z 兲Uz 共h兲Ux 共j兲,
s s
on the wire while qubits on vertical connections are used where Ux 共a兲 苷 exp共2ia 2x 兲,Uz 共a兲 苷 exp共2ia 2z 兲. Ini-
to realize two-bit quantum gates. The basis in which a tially, the first qubit is in some state jcin 典, which
certain qubit is measured depends in general on the results is to be rotated, and the other qubits are in j1典;
of preceding measurements. The processing is finished i.e., their common state reads jC典1,...,5 苷 jcin 典1 ≠
once all qubits except the last one on each wire have been j1典2 ≠ j1典3 ≠ j1典4 ≠ j1典5 . After the five qubits are
measured. At this point, the results of previous measure- entangled by S they are in the state SjC典1,...,5 苷
ments determine in which basis these “output” qubits need 1兾2jcin 典1 j0典2 j2典3 j0典4 j2典5 2 1兾2jcin 典1 j0典2 j1典3 j1典4 j1典5 2
to be measured for the final readout. We note that, in the ⴱ ⴱ
1兾2jcin 典1 j1典2 j1典3 j0典4 j2典5 1 1兾2jcin 典1 j1典2 j2典3 j1典4 j1典5 ,
entire process, only one-qubit measurements are required. ⴱ
where jcin 典 苷 sz jcin 典. Now, the state jcin 典 can be rotated
The amount of entanglement therefore decreases with ev- by measuring qubits 1 to 4, while it is teleported to site 5 at
ery measurement [8] and all entanglement involved in the the same time. The qubits 1, . . . , 4 are measured in appro-
process is provided by the initial resource, the cluster state. j0典 1eiaj j1典 j0典 2eiaj j1典
This is different from the scheme of Ref. [11], which uses priately chosen bases Bj 共aj 兲 苷 兵 j p2 j , j p2 j 其
Bell measurements (capable of producing entanglement) whereby the measurement outcomes sj [ 兵0, 1其 for j 苷
to realize quantum gates. 1, . . . , 4 are obtained. Here, sj 苷 0 means that qubit j is
In the following, we show that any quantum logic circuit projected into the first state of Bj 共aj 兲. The resulting
can be implemented on a cluster state. The purpose of this state is js1 典a1 ,1 ≠ js2 典a2 ,2 ≠ js3 典a3 ,3 ≠ js4 典a4 ,4 ≠ jcout 典5
is twofold. First, it serves as an illustration of how to im- with jcout 典 苷 Ujcin 典. For the choice a1 苷 0 (measur-
plement a particular quantum circuit in practice. Second, ing sx of qubit 1) the rotation U has the form U 苷
in showing that any quantum circuit can be implemented sxs2 1s4 szs1 1s3 UR 关共21兲s1 11 a2 , 共21兲s2 a3 , 共21兲s1 1s3 a4 兴. In
on a sufficiently large cluster we demonstrate the univer- summary, the procedure to implement an arbitrary
sality of the proposed scheme. For pedagogical reasons we rotation UR 共j, h, z 兲, specified by its Euler angles
first explain a scheme with one essential modification with j, h, z is (i) measure qubit 1 in B1 共0兲; (ii) measure
respect to the proposed scheme: before the entanglement qubit 2 in B2 共 共21兲s1 11 j兲兲; (iii) measure qubit 3 in
operation S, certain qubits are selected as input qubits and B3 共 共21兲s2 h兲兲; (iv) measure qubit 4 in B4 共 共21兲s1 1s3 z 兲 .
the input information is written onto them, while the re- In this way the rotation UR0 is realized: UR0 共j, h, z 兲 苷
maining qubits are prepared in j1典. This step weakens the sxs2 1s4 szs1 1s3 UR 共j, h, z 兲. The extra rotation US 苷
scheme since it affects the character of the cluster state as sxs2 1s4 szs1 1s3 can be accounted for at the end of the com-
a genuine resource. It can, however, be avoided [see (e)]. putation, as is described below in (d).
Points (a) to (c) are concerned with the basic elements of a (c) To perform the gate CNOT共c, tin ! tout 兲 苷
共t !t 兲
quantum circuit, quantum gates, and wires, point (d) with j0典cc 具0j ≠ 1共tin !tout 兲 1 j1典cc 具1j ≠ sx in out between a con-
the composition of gates to circuits. trol qubit c and a target qubit t, four qubits, arranged
(a) Information propagation in a wire for qubits. A qubit as depicted Fig. 2a, are required. During the action
can be teleported from one site of a cluster to any other of the gate, the target qubit t is transferred from tin
site. In particular, consider a chain of an odd number of to tout . The following procedure has to be imple-
qubits 1 to n prepared in the state jcin 典1 ≠ j1典2 ≠ · · · ≠ mented. Let qubit 4 be the control qubit. First, the state
j1典n and subsequently entangled by S. The state that was ji1 典z,1 ≠ ji4 典z,4 ≠ j1典2 ≠ j1典3 is prepared and then the
originally encoded in qubit 1, jcin 典, is now delocalized entanglement operation S is performed. Second, sx of
and can be transferred to site n by performing sx mea- qubits 1 and 2 is measured. The measurement results

5189
VOLUME 86, NUMBER 22 PHYSICAL REVIEW LETTERS 28 MAY 2001

(a) (b) O ; (3) entangle the qubits on N2 ; (4) measure all qubits
target in target out
1 2 3
in N2 nR. Steps 3 and 4 implement the circuit 2 on N2 .
target out
The measurements on N1 nO commute with the entangle-
target in
4
ment operation restricted to N2 , since they act on differ-
control
ent subsets of particles. Therefore the two strategies are
mathematically equivalent and yield the same results. It
control in control out
is therefore consistent to entangle in a single step at the
FIG. 2. Realization of a CNOT gate by one-particle measure- beginning and perform all measurements afterwards.
ments. See text. Two further points should be addressed in connection
with circuits. First, the randomness of the measurement
sj [ 兵0, 1其 correspond to projections of the qubits j into results does not jeopardize the function of the circuit.
jsj 典x,j , j 苷 1, 2. The quantum state created by this proce- Depending on the measurement results, extra rotations
共34兲 sx and sz act on the output qubit of every implemented
dure is js1 典x,1 ≠ js2 典x,2 ≠ US ji4 典z,4 ≠ ji1 1 i4 mod2典z,3 , 0
共34兲 s 11 s s1 gate. 0 By use of the0 relations UR 共j, h, z 兲szs sxs 苷
where US 苷 sz共3兲 sx共3兲 sz共4兲 . The input state is thus
1 2 st
szs sxs UR 共0共21兲s0 j, 共21兲s h, 共21兲s z 兲 , 0and0 CNOT 0
共c, t兲sz共t兲
acted upon by the CNOT and successive sx and sz rota- sc s s st sc 1st 共t兲sc 1st 共c兲sc
共34兲 sz共c兲 sx共t兲 t sx共c兲 c 苷 sz共t兲 sz共c兲 sx sx CNOT共c, t兲,
tions US , depending on the measurement results s1 , s2 . these extra rotations can be pulled through the network to
These unwanted extra rotations can again be accounted act upon the output state. There they can be accounted
for as described in (d). For practical purposes it is more for by adjusting the measurement basis for the final
convenient if the control qubit is, as the target qubit, readout. The above relations imply that for a rotation
transferred to another site during the action of the gate. UR 共j, h, z 兲— different from the CNOT gate — the accu-
When a CNOT is combined with other gates to form a mulated extra rotations US at the input side of UR need to
quantum circuit it will be used in the form shown in be determined before the measurement bases that realize
Fig. 2b. UR can be specified. This introduces a partial temporal
To explain the working principle of the CNOT gate we, ordering of the measurements on the whole cluster.
for simplicity, refer to the minimal implementation with Second, quantum circuits can also be implemented on
four qubits. The minimal CNOT can be viewed as a wire irregular clusters. In that case, qubits may be missing
from qubit 1 to qubit 3 with an additional qubit, No. 4, which are required for the standard implementation of the
attached. From the eigenvalue equations (1) it can now be circuit. This can be compensated by a large flexibility in
derived that, if qubit 4 is in an eigenstate ji4 典z,4 of sz , then shape of the gates and wires. The components can be bent
the value of i4 [ 兵0, 1其 determines whether a unit wire or and stretched to fit to the cluster structure as long as the
共3兲
a spin flip sx (modulo the same correction US for both topology of the circuit implementation does not change.
values of i4 ) is being implemented. In other words, once Irregular clusters are found in lattices with a finite site
sx of qubits 1 and 2 have been measured, the value i4 of occupation probability 0 , p , 1. In such a situation,
qubit 4 controls whether the target qubit is flipped or not. the possibility of universal quantum computation is
(d) Quantum circuits. The gates described — the CNOT closely linked to the phenomenon of percolation. For p
and arbitrary one-qubit rotations — form a universal set above a certain critical value pc , which depends on the
[5]. In the implementation of a quantum circuit on a clus- dimension of the lattice, an infinitely extended cluster
ter state the site of every output qubit of a gate overlaps exists that may be used as the carrier of the quantum
with the site of an input qubit of a subsequent gate. Be- circuit. In two dimensions, for example, exactly one
cause of this, the entire entanglement operation can be such cluster C exists. Suppose this cluster is divided
performed at the beginning. To see this, compare the into two subclusters C1 and C2 by a one-dimensional cut
following two strategies. Given a quantum circuit im- O 苷 C1 > C2 . It can be shown, e.g., by using Russo’s
plemented on a network N of qubits which is divided formula [12] from percolation theory that, for any cut O ,
into two consecutive circuits, circuit 1 is implemented on jO j 苷 `. Therefore there is no upper bound, in principle,
network N1 and circuit 2 is implemented on network to the “capacity” of the cluster, i.e., to the number of
N2 , and N 苷 N1 < N2 . There is an overlap O 苷 qubits that can be processed across such a cut.
N1 > N2 which contains the sites of the output qubits (e) Full scheme. It is important to note that the step
of circuit 1 (these are identical to the sites of the input of writing the input information onto the qubits before
qubits of circuit 2). The sites of the readout qubits form a the cluster is entangled was introduced only for peda-
set R , N2 . Strategy (i) consists of the following steps: gogical reasons. For illustration of this point consider
(1) write input and entangle all qubits on N ; (2) mea- a chain of five qubits in the state Sj1典1 ≠ j1典2 ≠ · · · ≠
sure qubits [ N nR to implement the circuit. Strategy j1典5 . Clearly, there is no local information on any of the
(ii) consists of (1) write input and entangle the qubits on qubits. However, by measuring qubits 1 to 4 along suitable
N1 , (2) measure the qubits in N1 nO . This implements directions, qubit 5 can be projected into any desired state
the circuit on N1 and writes the intermediate output to (modulo US ). What is used here is the knowledge that the

5190
VOLUME 86, NUMBER 22 PHYSICAL REVIEW LETTERS 28 MAY 2001

resource has been prepared with qubit 1 in the state j1典1 In conclusion, we have described a new scheme of
before the entanglement operation. By the four measure- quantum computation that consists entirely of one-qubit
ments, this qubit is then rotated as described in (b). In measurements on a particular class of entangled states,
order to use qubit 5 for further processing, the five-qubit the cluster states. The measurements are used to imprint a
chain considered here should, of course, be part of a larger quantum circuit on the state, thereby destroying its entan-
cluster such that particle 5 is still entangled with the re- glement at the same time. Cluster states are thus one-way
maining network, after particles 1 to 4 have been mea- quantum computers and the measurements form the
sured. The method of preparing the input state remains the program.
same, in this case, as explained in (d). In a similar man- We thank D. E. Browne, D. P. DiVincenzo, A. Schenzle,
ner any desired input state can be prepared if the rotations and H. Wagner for helpful discussions. This work was
are replaced by a circuit preceding the proper circuit for supported by the Deutsche Forschungsgemeinschaft.
computation. In summary, no input information needs to
be written to the qubits before they are entangled. Cluster
states are thus a genuine resource for quantum computa-
tion via measurements only.
For a cluster of a given finite size, the number of compu- [1] C. H. Bennett and D. P. DiVincenzo, Nature (London) 404,
tational steps may be too large to fit on the cluster. In this 247 (2000).
case, the computation can be split into consecutive parts, [2] See Ref. [1] for a recent review.
for each of which there is sufficient space on the cluster. [3] J. I. Cirac and P. Zoller, Nature (London) 404, 579 (2000).
The modified procedure consists then of repeatedly (re)en- [4] D. Deutsch, Proc. R. Soc. London 425, 73 (1989).
tangling the cluster and imprinting the actual part of the [5] A. Barenco et al., Phys. Rev. A 52, 3457 (1995).
[6] H.-J. Briegel and R. Raussendorf, Phys. Rev. Lett. 86, 910
circuit — by measuring all of the lattice qubits except
(2001).
the ones carrying the intermediate quantum output — until [7] The second Hamiltonian is of the standard Ising form. The
the whole calculation is performed. This procedure has symbol “⬵” means that the states generated from a given
also the virtue that qubits involved in the later part of a initial state, under the action of these Hamiltonians, are
calculation need not be protected from decoherence for a identical up to a local rotation on certain qubits. We use
long time while the calculation is still being performed at the first Hamiltonian to make the computational scheme
a remote place of the cluster. Standard error-correction more transparent. The conclusions drawn in the paper are,
techniques [13,14] may then be used on each part of the however, the same for both Hamiltonians.
circuit to stabilize the computation against decoherence. [8] By the “amount of entanglement” contained in the re-
A possible implementation of such a quantum computer source, we mean any measure that satisfies the criteria of
uses neutral atoms stored in periodic micropotentials an entanglement monotone [9]. For cluster states, the en-
tanglement can be calculated, e.g., in terms of the Schmidt
[15–18] where Ising-type interactions can be realized
measure of Ref. [10].
by controlled collisions between atoms in neighboring [9] G. Vidal, J. Mod. Opt. 47, 355 (2000).
potential wells [16,18]. This system combines small [10] J. Eisert and H.-J. Briegel, quant-ph/0007081.
decoherence rates with a high scalability. The question [11] D. Gottesman and I. L. Chuang, Nature (London) 402, 390
of scalability is linked to the percolation phenomenon, (1999).
as mentioned earlier. For a site occupation probability [12] See, e.g., G. Grimmett, Percolation (Springer-Verlag, New
above the percolation threshold, there exists a cluster York, 1989).
which is bounded in size only by the trap dimensions. [13] A. Calderbank and P. W. Shor, Phys. Rev. A 54, 1098
For optical lattices in three dimensions, single-atom site (1996).
occupation with a filling factor of 0.44 has been reported [14] A. Steane, Phys. Rev. Lett. 77, 793 (1996).
[19] which is significantly above the percolation threshold [15] G. K. Brennen et al., Phys. Rev. Lett. 82, 1060 (1999).
[16] D. Jaksch et al., Phys. Rev. Lett. 82, 1975 (1999).
of 0.31 [20]. As in other proposed implementations for
[17] T. Calarco et al., Phys. Rev. A 61, 022304 (2000).
quantum computing, the addressability of single qubits [18] H.-J. Briegel et al., J. Mod. Opt. 47, 415 (2000).
in the lattice is, however, still a problem. (For recent [19] M. T. DePue et al., Phys. Rev. Lett. 82, 2262 (1999).
progress, see Ref. [21]). Recently, it has also been shown [20] J. M. Ziman, Models of Disorder (Cambridge University
that implementations based on arrays of capacitively cou- Press, Cambridge, United Kingdom, 1979).
pled quantum dots may be used to realize an Ising-type [21] R. Scheunemann et al., Phys. Rev. A 62, 051801(R) (2000).
interaction [22]. [22] T. Tanamoto, quant-ph/0009030.

5191