Figure 1

A two-qubit quantum circuit. Without loss of generality we assume the computation starts in the $|+\rangle \equiv (|0\rangle +|1\rangle )/\sqrt{2}$ state. The single-qubit gates $U_{\alpha ,{\alpha }^{\prime }}\equiv X_{{\alpha }^{\prime }}{Z}_{\alpha }$ denote a rotation by $\alpha$ about the $\widehat{z}$ axis of the Bloch sphere, followed by a rotation by ${\alpha }^{\prime }$ about the $\widehat{x}$ axis. The two-qubit gate is a controlled-phase (cphase) gate, whose action in the computational basis is $|ab\rangle \to (-1{)}^{ab}|ab\rangle$. cphase and the gates $U_{\alpha ,{\alpha }^{\prime }}$ are together universal for quantum computation.Reuse & Permissions

Figure 2

The cluster state used to simulate the circuit in Fig. 1. Each circle represents a single qubit. The cluster state is constructed by preparing each qubit in the state $|+\rangle \equiv (|0\rangle +|1\rangle )/\sqrt{2}$, and then applying cphase between any two qubits joined by a line. Since the cphase gates commute with one another, it does not matter in what order they are applied.Reuse & Permissions

Figure 3

The circuit in Fig. 1 is simulated by measuring the individual qubits of the cluster in the time order denoted by the labels on the qubits, $1,2,3,\dots$. Qubits with the same label may be measured in either order, or simultaneously. The measurement basis is indicated via a single-qubit unitary operation to be applied before measuring in the computational basis. For example, the first qubit on the top line has $H{Z}_{{\alpha }_1}$ applied, before measuring in the computational basis. The prime notation, e.g., ${\alpha }_3^{\prime }$, indicates that the value of ${\alpha }_3^{\prime }$ is either $\pm {\alpha }_3$, with the sign determined by the outcome of previous measurements, as described in 5.Reuse & Permissions

Figure 4

Attempting to add a site connected by a single bond to the current cluster, using a $C{Z}_{4/9}$ gate. By performing the gate with sequential teleportations we ensure that the probability of success is $2/3$.Reuse & Permissions

Figure 5

Adding a site, $S$, to the cluster by attaching it to two qubits $A$ and $B$ already in the cluster.Reuse & Permissions

Figure 6

(a) We prepare microclusters nondeterministically and glue them together using parallel $C{Z}_{1/4}$ gates to give the cluster shown in (b). If gluing fails, we discard the qubits from the cluster. The extra dangling nodes enable multiple attempts at adjoining a microcluster; by increasing the number of dangling nodes we can increase the probability of successful gluing. For a cluster of size $s\left(n\right)$, using microclusters with $O\mathbf{(}\log [s\left(n\right)\left]\mathbf{\right)}$ dangling nodes gives a high probability of successfully preparing the entire cluster. The disadvantage is that preparing the microclusters nondeterministically incurs a poly­nomial overhead.Reuse & Permissions