Fault-tolerant quantum computation with cluster states

The one-way quantum computing model introduced by Raussendorf and Briegel [Phys. Rev. Lett. 86, 5188 (2001)] shows that it is possible to quantum compute using only a fixed entangled resource known as a cluster state, and adaptive single-qubit measurements. This model is the basis for several practical proposals for quantum computation, including a promising proposal for optical quantum computation based on cluster states [M. A. Nielsen, Phys. Rev. Lett. (to be published), quant-ph/0402005]. A significant open question is whether such proposals are scalable in the presence of physically realistic noise. In this paper we prove two threshold theorems which show that scalable fault-tolerant quantum computation may be achieved in implementations based on cluster states, provided the noise in the implementations is below some constant threshold value. Our first threshold theorem applies to a class of implementations in which entangling gates are applied deterministically, but with a small amount of noise. We expect this threshold to be applicable in a wide variety of physical systems. Our second threshold theorem is specifically adapted to proposals such as the optical cluster-state proposal, in which nondeterministic entangling gates are used. A critical technical component of our proofs is two powerful theorems which relate the properties of noisy unitary operations restricted to act on a subspace of state space to extensions of those operations acting on the entire state space. We expect these theorems to have a variety of applications in other areas of quantum-information science.

Figure 1

A simple cluster state. Note that each circle represents a single qubit in the cluster.

Figure 2

A two-qubit quantum circuit. Without loss of generality we may assume the computation starts with each qubit in the $\mid +⟩\equiv (\mid 0⟩+\mid 1⟩)∕\sqrt{2}$ state, since single-qubit gates can be prepended to the circuit if we wish to start in some other state. The two-qubit gate is a CPHASE gate. The boxes are single-qubit gates of the form $H{Z}_{\alpha }$, where $H$ and $Z_{\alpha }$ are as defined in Sec. 2B. Note that by composing three of these gates we can obtain an arbitrary single-qubit gate. Thus gates of the form $H{Z}_{\alpha }$, together with CPHASE gates, are universal for quantum computation.

Figure 3

The cluster state of Fig. 1, marked to indicate how it is used to simulate the different elements in the circuit of Fig. 2. Note that the labeled qubits all have labels of the form “${}^{n}U$,” where $n$ is a positive integer, and $U$ is a unitary operation. The label $n$ indicates the time order; qubits with the same label can be measured in either order, or simultaneously. $U$ indicates that the qubit is measured by performing the unitary $U$ and then measuring in the computational basis. Equivalently, a single-qubit measurement in the basis $\{U^{†}\mid 0⟩,U^{†}\mid 1⟩\}$ is performed. Note that except for the first measurements, all measurements have $U$ of the form $H{Z}_{\pm \alpha }$; the ± indicates that the value of the sign depends upon the outcomes of earlier measurements. The output from the computation is at the unlabeled qubits, which are not measured.

Figure 4

Use of ancillas in cluster-state computations. Figure (a) shows an ancilla which is prepared then discarded. The cluster-state computation used to simulate this is shown in (b).

Figure 5

The starting point for mapping noise in the quantum circuit model to corresponding noise in the cluster state model. We begin with a simple quantum circuit in the canonical form of Sec. 2B, and translate this circuit into a cluster-state computation. The explicit implementation of the cluster-state computation is described by the literal circuit.

Figure 6

A circuit with the same output as that of Fig. 5c. The new two-qubit gates that have been inserted are SWAP gates.

Figure 7

A circuit with the same output as Fig. 6, but with the classical controls explicitly drawn in. Note that $x$ is the top bit, while $z$ is the lower bit. The new circuit notation involving the $H{Z}_{{\alpha }_1}$ and $H{Z}_{{\alpha }_2}$ operations indicates how the classical variable $x$ is used to control the measurement basis. A value of $x=0$ means that $H{Z}_{\alpha }$ is applied, while a value of $x=1$ means that $H{Z}_{-\alpha }$ is applied. Note that in the case of $H{Z}_{{\alpha }_1}$, we always have $x=0$, and so $H{Z}_{{\alpha }_1}$ is applied, as expected.

Figure 8

The classical error update circuit, following Eqs. (21, 22).

Figure 9

A definition to make other circuits more compact.

Figure 10

The output of Fig. 5c is the same as the output of this imperfect circuit.

Figure 11

The output of Fig. 10 is unchanged if these perfect gates are prepended at the beginning of the computation.

Figure 12

The effective output of Fig. 10 is unchanged if these perfect gates are appended at the end of the computation.

Figure 13

We insert these perfect gates between each pair of blocks in Fig. 10.

Figure 14

The output of this imperfect circuit is the same as the output of the noisy cluster-state computation in Fig. 5c.

Figure 15

The definition of the operation $B_{\alpha }$ used as the basis for the repeating blocks in Fig. 14.

Figure 16

The output of the circuit on the left is identical to the output of the circuit on the right. For this identity we assume that all operations in both circuits are done perfectly—there is no noise.

Figure 17

The definition of the operation $Q{B}_{\alpha }$.

Figure 18

The definition of the quantum error update operation, QEU.

Figure 19

The output at $Q$ in this imperfect circuit is identical to the output of the imperfect circuit of Fig. 14, and thus is equivalent to the output of the noisy cluster-state computation of Fig. 5c.

Figure 20

The circuit identity of proposition 5. This is a perfect circuit identity, i.e., all elements in both circuits are assumed to be performed without any noise.

Figure 21

The definition of the operation ${\tilde{U}}_j$. The environment $E$ is shown at the bottom, where the wire with a slash through it indicates an arbitrary quantum system.

Figure 22

This noisy circuit is equivalent to the noisy one-buffered cluster-state computation of Fig. 5c.

Figure 23

An illustrative two-qubit quantum circuit ${\mathcal{F}}_{\mathcal{Q}}$ using canonical fault-tolerant gates.

Figure 24

A noisy two-qubit cluster-state computation.

Figure 25

The output of this imperfect circuit is equivalent to the output of the noisy two-qubit cluster-state computation in Fig. 24. The operations $Q{B}_{{\alpha }_j},Q{B}_{{\beta }_j}$ are as defined in the previous subsection, while $QC$ is defined in Fig. 26.

Figure 26

The definition of the imperfect operation $QC$ appearing in Fig. 25. We have prepended and appended the same fictitious elements used in the single-qubit case in Figs. 11, 12. The gate ${\mathrm{QEU}}^{\prime }$ is the two-qubit extension of the error update, and is shown in detail in Fig. 27. The only noisy operations are the Hadamard gates, and the CPHASE gate between the first and the fifth qubits.

Figure 27

The definition of the two-qubit quantum error update operation analogous to that of Fig. 18.

Figure 28

The circuit identity of proposition 6. This is a perfect circuit identity, i.e., all elements in both circuits are assumed to be performed without any noise.

Figure 29

The microcluster used in the dangling node implementation of cluster-state computation. There are $k$ dangling nodes, in general; in this example, $k=3$.

Figure 30

Figure 30a shows the cluster state which results after successfully adjoining a microcluster to the initial microcluster in Fig. 29, deleting the extra nodes, and applying appropriate local operations. Figure 30b shows the cluster which results after $k-1$ failed joining attempts.

Figure 31

The simpler two-qubit microcluster adjoined to the cluster state at the very end of a single-qubit cluster-state computation, in place of the microcluster in Fig. 29.

Figure 32

This microcluster is used in the dangling node implementation of multiqubit cluster-state quantum computations.

Figure 33

An example cluster-state computation. We have omitted explicit description of the measurements performed, since it is the formation of the cluster that we wish to concentrate on, rather than the details of the measurements.

Figure 34

The cluster after success and failure to adjoin the microcluster of Fig. 32.

Figure 35

The literal circuit for a two-at-a-time implementation of a single-qubit cluster-state computation, with the noisy quantum memory steps explicitly indicated by crosses. For simplicity we have combined the single-qubit rotations and computational basis measurements into a single-qubit measurement in some other basis, not explicitly specified.

Figure 36

The output of this circuit is equivalent to the output of the literal circuit for the two-at-a-time implementation in Fig. 35.

Figure 37

The literal circuit for a dangling node implementation of a single-qubit cluster-state computation. We have chosen to use an implementation with $k=3$ dangling nodes; the circuit for other values of $k$ follows similar lines.

Figure 38

The operation ADD satisfies the approximate circuit identity illustrated here. This identity becomes more exact as $k$ is increased, and the level of noise in the physical operations used to do the operation is decreased.

Figure 39

The output of this imperfect circuit is the same as the output of the noisy cluster-state computation. The state ∣anc⟩ is an ancilla prepared (noisily) offline; it contains microclusters, the ancillas used in the KLM CPHASE, and qubits used to simulate the classical control and feedforward in the dangling node implementation. Note that the ancilla line is marked by a slash to indicate that it involves many systems, not just a single qubit.

Figure 40

We may insert some fictitious perfect gates between the operations in Fig. 39, without changing the output.

Figure 41

The output of this imperfect circuit is the same as the output of the noisy dangling node cluster-state computation.

Figure 42

The definition of the gate $G$ used in Fig. 41. This figure also defines subsystem labels $Q$ and $A$.

Figure 43

The definition of the gate $V$.

Figure 44

The output of this noisy circuit is the same as the output of the noisy cluster-state computation.

Figure 45

Identity 1 of Appendix B.

Figure 46

Identity 2 of Appendix B.

Figure 47

Identity 3 of Appendix B.

Figure 48

Identity 4 of Appendix B.

Figure 49

Circuit identity of Proposition 5.