# Measurement-Based Quantum Computation

# Measurement-Based Quantum Computation

- Tzu-Chieh WeiTzu-Chieh WeiC.N. Yang Institute for Theoretical Physics, Stony Brook University

### Summary

Measurement-based quantum computation is a framework of quantum computation, where entanglement is used as a resource and local measurements on qubits are used to drive the computation. It originates from the one-way quantum computer of Raussendorf and Briegel, who introduced the so-called cluster state as the underlying entangled resource state and showed that any quantum circuit could be executed by performing only local measurement on individual qubits. The randomness in the measurement outcomes can be dealt with by adapting future measurement axes so that computation is deterministic. Subsequent works have expanded the discussions of the measurement-based quantum computation to various subjects, including the quantification of entanglement for such a measurement-based scheme, the search for other resource states beyond cluster states and computational phases of matter. In addition, the measurement-based framework also provides useful connections to the emergence of time ordering, computational complexity and classical spin models, blind quantum computation, and so on, and has given an alternative, resource-efficient approach to implement the original linear-optic quantum computation of Knill, Laflamme, and Milburn. Cluster states and a few other resource states have been created experimentally in various physical systems, and the measurement-based approach offers a potential alternative to the standard circuit approach to realize a practical quantum computer.

### Keywords

### Subjects

- Quantum Information

### Introduction

Quantum computation has the potential to perform specific computational tasks more efficiently and hence faster than current classical computers (Nielsen & Chuang, 2002). In the 2010s, some small-scale quantum computers, with sizes ranging from a few to about 70 quantum bits (qubits), were built and put into action. The technology has become increasingly mature, and it is likely that quantum computers will soon perform computational tasks beyond what current classical computers can efficiently simulate (Arute et al., 2019).

A natural framework for quantum computation is the standard circuit model, where an array of qubits are appropriately initialized, such as in the logical 0 state, and depending on the algorithmic task, a sequence of quantum gates (typically one-qubit and two-qubit) are applied to the array of qubits; finally, readout is done by measuring individual qubits in the logical 0/1 basis—the so-called computational basis. In addition to the circuit model, the adiabatic quantum computational model does not use gates, but rather, time-dependent, smoothly or adiabatically varied Hamiltonians (Averin, 1998; Farhi et al., 2000; Kadowaki & Nishimori, 1998). Both rely on the unitary property of either quantum gates or Hamiltonian evolution.

In contrast, measurement-based quantum computation, which originated from the work of Raussendorf and Briegel on the one-way quantum computer (Raussendorf & Briegel, 2001) utilizes local measurement to drive computation. Measurement is often regarded as a mechanism that destroys coherence in quantum states. The key feature to understand how measurement can achieve unitary operation is entanglement. The broader measurement-based framework is currently being explored as an alternative approach to realize a quantum computer.

### Part One: Quantum Computation and Measurement-Based Approaches

#### Early Development in Quantum Computation

The earliest notion of quantum computation goes back to the 1980s, with initial writings on the topic including an article that described a microscopic model of the classical Turing machine using quantum mechanics (Benioff, 1980) and a Russian-titled book, *Vychislimoe i Nevychislimoe* [Computable and Noncomputable], that suggested the idea of quantum computation (Manin, 1980). In a keynote address entitled “Simulating Physics With Computers” at the 1981 MIT Physics of Computation Conference, Nobel Prize-winning Richard Feynman pointed out that it was not possible to simulate a quantum system efficiently with classical computers (Feynman, 1982). Therefore it was natural to consider simulating a quantum system with another quantum system that is well-controlled or, in other words, with a quantum-mechanical computer (Feynman, 1985). The most prominent work that suggests the potential quantum advantage is the paper by Shor, who showed a quantum computer could, in principle, factorize a large integer number almost exponentially faster than any currently existing classical method (Shor, 1994). To get a sense of the time complexity, if it takes 1 second to factor a 30-digit number for both classical and quantum computers, then it takes about three years for the classical computer to factorize a 100-digit number, but about 40 seconds for a quantum computer. To factorize a 300-digit number will take about a third of the age of the universe for a classical computer but only about 10 minutes for a quantum computer. At present such a powerful quantum computer does not exist. However, the potential capability prompted great interest in both theoretical and experimental quantum computation and information science. The progress of quantum technology in the past few decades shows promising advances toward these goals.

#### Rules of Quantum Mechanics and the Circuit Model of Quantum Computation

To understand how quantum computation works, it is essential to understand the governing rules stemming from quantum mechanics. Three of them are particularly important: (a) superposition, (b) evolution, and (c) measurement. (For an explanation of these rules, see e.g., Susskind & Friedman, 2014.) Superposition appears in classical waves, and in quantum mechanics, it allows quantum states, like vectors, to add or interfere. In fact, by representing quantum states as vectors (such as single-qubit states indicated by arrows in the “Bloch” sphere; see figure 1[a]), how they evolve in time is governed by Schroedinger’s equation, whose effect is to apply a suitable unitary matrix to the vector representing the quantum state. A quantum gate is built from the action of evolution. For example, the goal of the so-called NOT gate is to flip the arrow pointing to the north pole to the south pole in the Bloch sphere and vice versa (see figure 1[b]). To so do, the evolution may begin with the north pole and follow the path of a meridian to the south pole. Another example is the so-called Hadamard gate, which consists of two steps (see figure 1[b]): (a) rotation around the y-axis by -90^{○}, followed by (b) rotation around the z-axis by 180^{○}. The effect is to rotate $|0\u3009$ to $(\left|0\u3009+\right|1\u3009)/\sqrt{2}$, and $|1\u3009$ to $\left(\left|0\u3009-\right|1\u3009\right)/\sqrt{2}$. By using a sequence of three Euler rotations, an arbitrary one-qubit state $\alpha \left|0\u3009+\beta \right|1\u3009$ can be arrived at from $|0\u3009$, where $\text{\alpha}$ and $\text{\beta}$ are two complex numbers that satisfy ${\left|\alpha \right|}^{2}+{\left|\beta \right|}^{2}=1$.

The evolution under Schroedinger’s equation is deterministic; in contrast, measurement of a quantum state generally yields random outcomes, and the distribution of outcomes also depends on the basis or the axis of the measurement. The rule of measurement in quantum mechanics states that the act of measuring an observable $O$ projects the system to an eigenstate of $O$, and the observed value is the associated eigenvalue. In the case of one qubit, the observable $O$ defines an axis cutting through the center of the Bloch sphere, and the two intersecting poles are the two possible outcomes. Unless the arrow representing the quantum state aligns exactly with one of the poles, the measurement outcome appears randomly and the outcome corresponding to either pole can appear. The probability distribution governing the random outcomes obeys the so-called Born rule, given by the modulus square of the coefficient of that eigenstate in the quantum state to be measured, and depends on the relative orientation of the state vector with the measurement axis.

The usual measurement result of $0$ and $1$ is represented as the axis connecting the north and south poles on the Bloch sphere. But measurement along the x-axis that intersects the equator gives rise to two possible outcomes corresponding to $|+\u3009=(\left|0\u3009+\right|1\u3009)/\sqrt{2}$ and $|-\u3009=(\left|0\u3009-\right|1\u3009)/\sqrt{2}$. Practically, such a measurement can be achieved by carrying out the typical energy eigenbasis $(\text{Z})$ measurement in the $0$ and $1$ basis after the Hadamard rotation to induce the basis change (from $\text{X}$ to $\text{Z}$ or vice versa).

A quantum computer has many qubits, and there are an exponential number, ${2}^{N}$, of basis states for $N$ qubits, ranging from $|0\dots 0\u3009$ to $|1\dots 1\u3009$. Description of such a vector and its change in time requires an exponential number of complex numbers, which is intuitively why quantum computers are difficult to simulate by classical computers.

Even with just two qubits, a natural consequence of quantum mechanics yields an exotic feature called entanglement, which, for example, appears in a quantum state of $(\left|00\u3009+\right|11\u3009)/\sqrt{2}$, and which can be achieved by preparing the two qubits in $|00\u3009$ initially, applying the Hadamard gate to the first qubit (which rotates it from the north pole to a point on the equator: $|+\u3009=(\left|0\u3009+\right|1\u3009)/\sqrt{2}$), and then acting on them by a two-qubit CNOT gate (which flips the second bit only if the first is 1), just like the first two gates shown in figure 2. The sequence takes $|00\u3009$ to $(\left|0\u3009+\right|1\u3009)|0\u3009/\sqrt{2}$ and then to $(\left|00\u3009+\right|11\u3009)/\sqrt{2}$.

A quantum computer, in a nutshell, implements a large unitary matrix $U$ on a vector of ${2}^{N}$ components representing $N$ quantum bits. A mathematical result (DiVincenzo, 1995) shows that any such unitary matrix $U$ can be decomposed into a sequence of one- and two-qubit gates, where one-qubit gates are simply performing local rotations and two-qubit gates are generating entanglement. The CNOT gate is the only two-qubit gate that is needed (Barenco et al., 1995); other entangling gates, such as a Controlled-Z gate may also be used instead. Such one- and two-qubit gates form the universal set of gates (DiVincenzo, 1995); such a notion of universality already exists in classical computation, with the set of AND, OR, and NOT gates being universal. From this picture of quantum computation, entanglement is created by quantum gates and subsequently reduced or destroyed by measurement. In measurement-based quantum computation, the universal set of gates needs to be implemented by measurement.

#### Measurement-Based Quantum Computation

Besides the circuit model, there are other frameworks of quantum computation, such as adiabatic quantum computation, which are still based on the unitary evolution of a quantum system. Topological quantum computation utilizes the properties of the so-called anyons, which under exchange of pairs of anyons (i.e., braiding) can induce unitary transformation that can be used for quantum gates. The subject of interest here is measurement-based quantum computation (MBQC), which uses measurement to achieve emulation of unitary circuits. It originated from the pioneering work of Raussendorf and Briegel on the one-way quantum computer (Raussendorf & Briegel, 2001). Subsequent works resulted in some variants. The variants that will be discussed include the teleportation-based, state transfer–based, and correlation-space approaches, which provide useful perspectives to appreciate the original one-way model and further development of the measurement-based quantum computation.

##### One-Way Quantum Computer and Cluster States

#### Table 1. Definitions of Some Terminology

Graph states: |
Qubits reside on the vertices of a graph. The graph state can be defined by a procedure—all qubits are initialized in the $|+\u3009$ states and Controlled-Z gates are applied pairwise to a pair of qubits that share an edge. The resultant state is a graph state. See fig. 2. |

Cluster states: |
A cluster state is a graph state when the underlying graph is a regular graph, such as a one-dimensional lattice or a two-dimensional square lattice. See fig. 2. |

Matrix product states: |
A matrix product state is a quantum state whose coefficients in some expansion of basis states can be given via a product of matrices. This is usually used to describe one-dimensional quantum states. |

Projected-entangled-pair states: |
A projected-entangled-pair state is a quantum state that can be described by a projection of local virtual qubits or qudits to local physical degrees of freedom, and the virtual qubits are initially entangled pairwise with a neighboring virtual qubit. Matrix product states are special cases. See fig. 7. |

Tensor-network states: |
A tensor-network state is a quantum state whose coefficients in some expansion of basis states can be given via a contraction of a tensor network. A tensor network is a collection of tensors located, e.g., at vertices of a graph. Edges connecting two vertices correspond to contraction, i.e., summing over identical indices. The local tensors are related to projections in the projected-entangled-pair states. They are in fact equivalent descriptions. Matrix product states are special cases. See fig. 7. |

Bell-state measurement: |
This is also called Bell-basis measurement or simply Bell measurement. It corresponds to a measurement on two qubits, and the effect of the measurement is to project the two qubits to any of the four Bell states. See fig. 4. |

In around 2000, Raussendorf and Briegel showed that quantum computation was possible by merely performing individual single-qubit measurements, which they called the one-way quantum computer (Raussendorf & Briegel, 2001). The key necessary ingredient is the high persistent entanglement residing in the cluster state that Raussendorf and Briegel exploited (Briegel & Raussendorf, 2001). A cluster state can be described as follows (see Table 1). Qubits are sitting on the vertices of a graph, and the edges describe an Ising-like interaction (Ising, 1925) between two adjacent spins. The only nontrivial effect is to induce a sign change in the state $|11\u3009$, so that $|11\u3009$ becomes $-|11\u3009$ after the interaction. This is also called a Controlled-Phase or Controlled-Z (CZ) gate. If initially all the qubits are in $|+\u3009$ state, the system after pairwise action of Controlled-Z gates will end up in a graph state (see Table 1). The cluster state is a special graph state on a regular lattice, such as the square lattice (see figures 2[c] and [d]).

Single-qubit measurement can only decrease the amount of entanglement, and hence the computation via measuring qubit by qubit in the cluster is “one-way.” Any quantum circuit in the standard circuit model can be translated to a measurement pattern on all the qubits of the cluster state. Execution of the measurement pattern with possible adaptation then drives computation and at the same time, the entanglement as a *resource* (for computation) is being “consumed.”

In more detail, in a two-dimensional square array of qubits initially in the cluster state, structures can be “carved out” to form a backbone of computation by measuring unwanted qubits in the z-axis. Such a backbone mimics the structure of a quantum circuit. For a segment of five linear sites, any rotation in the Bloch sphere can be achieved by using a combination of three Euler $\left(\text{\alpha},\text{\beta},\text{\gamma}\right)$ shown in figure 3(a). The symbols in the circles represent the angles of the measurement axes as measured from the positive x-axis on the x–y plane. Given that measurement gives random outcomes, to make the computation stay on track, subsequent measurement axes may need to be adapted—for example, by flipping the angle with a minus sign. This adaptation is the feedforward that is needed to make the desired unitary gates deterministic (Raussendorf et al., 2003). To complete the universal gate set, a two-qubit entangling gate such as the Controlled-NOT gate is needed. One example to realize this is illustrated in a structure of “I” shape junctions (see figure 3[b]). It is interesting to note that the adaptation of measurement axes is not necessary to implement the CNOT gate, in contrast to arbitrary one-qubit gates. There are other variants of these “LEGO” pieces for quantum gates (Raussendorf & Briegel, 2001; Raussendorf et al., 2003). By placing these pieces on a 2D grid, any quantum circuits can be realized by local measurement. Hence, the 2D cluster state can be regarded as a universal resource for quantum computation.

The above explanation of the one-way quantum computer relies on the mapping of a quantum circuit to a measurement pattern in the cluster state. In fact, it is not necessary to use the circuit-simulation picture; instead an “intrinsic” one-way computer based on the consideration of measurement, time ordering, and deterministic computation can be used (Raussendorf & Briegel, 2002; Raussendorf et al., 2016).

#### Other Approaches of Measurement-Based Quantum Computation

Since the invention of the one-way quantum computer by Raussendorf and Briegel, there have been attempts to understand this novel approach of quantum computation by using different perspectives, including teleportation, state transfer, and tensor network.

##### Teleportation-Based Measurement Scheme for Quantum Computation

The teleportation-based construction of quantum gates was proposed by Nielsen and Chuang (Nielsen & Chuang, 1997) and by Gottesman and Chuang (Gottesman & Chuang, 1999). The basic setup of teleportation is illustrated in figure 4(a), where an unknown qubit state $|\psi \u3009$ can be transferred to a third qubit by using an entangled pair $(\left|00\u3009+\right|11\u3009)/\sqrt{2}$, one of the four Bell states, shared between a second and a third qubit and then joint measurement on the first two qubits. A correcting operation that depends on the measurement outcomes completes the teleportation and recovers the unknown state. By using such a teleportation-based approach (Bennett et al., 1993; Gottesman & Chuang, 1999; Nielsen & Chuang, 1997), Nielsen showed that it is possible to perform universal quantum computation using only measurements (needed to create entanglement that will be used to mediate gate operations) and quantum memory (needed to store quantum information and entanglement) (Nielsen, 2003), without the need of a prior entangled resource state. The key intuition is that by allowing measurement on two or more qubits, entanglement can be created. Nielsen generalized the quantum teleportation protocol by using a locally rotated Bell state (by $U$), and showed that a quantum state could be teleported so that the output state is acted by a random Pauli operator $\text{\sigma}$ (associated with the usual teleportation) and additionally the desired gate $U$ (see figure 4[b]). The random Pauli operator arises due to unpredictable measurement outcomes and can be probabilistically canceled by repeatedly performing the above “teleportation” procedure, as in figure 4(a), until the product of these Pauli operators cancels one another and becomes identity. By using a four-qubit state that was defined by rotating two pairs of Bell states by a two-qubit gate $U$, two-qubit gates can be achieved (see figure 4[c]). Such a four-qubit state can be created by a four-qubit measurement and it can be used to induce a two-qubit gate such as the CNOT gate in Nielsen’s scheme. The upshot is that universal quantum computation can be done by a combination of two- and four-qubit measurement.

Nielsen’s teleportation-based measurement scheme for quantum computation does not rely on an initial entangled state such as a cluster state. All the qubits can be set to a fixed $|0\u3009$ state in the beginning. The Bell states that are needed for teleportation are created by measurement. The measurement needs to involve two qubits simultaneously, unlike the measurements in the one-way quantum computer that only involve individual qubits. In such a teleportation-based scheme, implementation of a one-qubit gate requires two-qubit measurement and that of a two-qubit gate seemingly requires four-qubit measurement. From a different viewpoint, the multi-qubit measurement allows the creation of the needed entanglement. Conceptually, Nielsen’s result may be regarded as a simple corollary from the one-way model of Raussendorf and Briegel (Raussendorf & Briegel, 2001). The ability to perform arbitrary 4-qubit measurements means that a cluster state on the honeycomb lattice can be created by measuring its so-called stabilizer operators, which define the cluster-state model. The execution of subsequent computation can then be done by one-qubit measurements as in the one-way model.

The requirement of a four-qubit measurement in Nielsen’s scheme for the CNOT gate may not be feasible. Fenner and Zhang later reduced the required measurement to three qubits (Fenner & Zhang, 2001), and subsequently, Leung reduced it further to two qubits (Leung, 2001, 2004). Using only two-qubit measurements for universal quantum computation is already optimal in terms of the number of qubits that need to be measured simultaneously.

Later, Aliferis and Leung (2004) showed that the teleportation-based approach is equivalent to the one-way approach by demonstrating local mapping between them in the set of universal gates. Subsequently, Childs, Leung, and Nielsen (Childs et al., 2005) used the approach of the one-bit teleportation (Zhou et al., 2000) to unify the two models (see figure 5).

##### State Transfer–Based Measurement Scheme for Quantum Computation

Instead of teleportation, Perdrix proposed a state-transfer approach for measurement-based quantum computation (Perdrix, 2005), where only single-qubit and two-qubit observables are used. All observables he used have two outcomes, 0 or 1 (or equivalently +1 and -1). The basic state-transfer scheme is shown in figure 6(a), where each box depicts an observable that represents a two-outcome measurement that projects onto the +1 and -1 subspace of the observable’s eigenstates. Unlike teleportation, it uses only two qubits to transfer a one-qubit state. It was shown that arbitrary one-qubit gates can be implemented by rotating the observables in the state transfer and that the CNOT gate can be implemented by combining two such state transfers with only one auxiliary qubit (see figures 6[b] and [c]). Jorrand and Perdrix used this state-transfer perspective to relate the one-way and teleportation-based approaches in the context of a one-dimensional cluster state (Jorrand & Perdrix, 2005).

Given that universality can be achieved by two-qubit measurements in both the state-transfer picture and the teleportation picture, it seems natural to ask which two-qubit measurements are easier to implement: those of Leung (Leung, 2001) or those of Perdrix (Perdrix, 2005). The answer may depend on physical systems and how the measurements can be implemented.

Beyond the state-transfer picture of computation, it is worth noting that Perdrix and Jorrand also presented a measurement-based approach to construct quantum Turing machines (Perdrix & Jorrand, 2004). The classical Turing machine is a fundamental model of computation that inspires many developments, and its generalization to the quantum regime can also be useful and may lead to further development.

##### Valence-Bond or Correlation-Space Picture

Verstraete and Cirac used the picture of valence-bond states (Verstraete & Cirac, 2004b) to understand the one-way computer. The cluster state that Briegel and Raussendorf introduced has an interpretation in terms of a tensor network of valence bonds, or what Verstraete and Cirac referred to as projected entangled-pairs states. There are four virtual qubits at each site, except at the boundary, and two neighboring virtual qubits form a maximally entangled pair or a kind of valence bond, $CZ|++\u3009=(\left|00\u3009+\left|01\u3009+\right|10\u3009-\right|11\u3009)/2=\left(\left|0\u3009+\u3009+\right|1-\u3009\right)/\sqrt{2}$ (see figure 7[a]). Because each physical site is also a qubit, there is a mapping from the onsite four virtual qubits to one physical qubit via $\left|0000\u3009\to \right|0\u3009$ and $\left|1111\u3009\to \right|1\u3009$, that is, a repetition code. A general projected-entangled-pair state can have more general local mapping beyond the repetition code. As depicted in figures 7(b) and (c), the computation takes place at the virtual qubits and uses teleportation similar but not identical to what was done elsewhere (i.e., in Gottesman & Chuang, 1999, and Nielsen, 2003). This approach later instigated the development of the correlation-space MBQC by Gross and Eisert (2007). The correlation-space MBQC exploits the tensor-network structure of the states, such as the one-dimensional matrix product states (Perez-Garcia et al., 2007) as well as the two-dimensional projected-entangled-pair states (Verstraete & Cirac, 2004a, 2004b; see Table 1). It should be pointed out that projected-entangled-pair states and tensor-network states are used almost synonymously in the literature.

For example, Affleck, Kennedy, Lieb, and Tasaki (AKLT) constructed a one-dimensional spin chain (Affleck et al., 1987) whose ground state can be written in terms of the matrix product states, with local matrices corresponding to “+1,” “0,”, “-1” being ${A}_{+1}=\sqrt{2}\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right),{A}_{0}=\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right),{A}_{-1}=-\sqrt{2}\left(\begin{array}{cc}0& 0\\ 1& 0\end{array}\right)$, respectively. These matrices represent the respective action on the virtual qubits when a physical spin is measured in the “+1,” “0,” and “-1” basis. The quantum state of the whole chain can be expressed in terms of the *matrix product representation*: $\left|{\psi}_{AKLT}\u3009={\displaystyle \sum}_{s}\text{Tr}\left({A}_{{s}_{1}}{A}_{{s}_{2}}\dots {A}_{{s}_{N}}\right)\right|{s}_{2},{s}_{2}\cdots {s}_{N}\u3009$. More sophisticated gate actions can be obtained by measuring the physical spin in a general basis; for example, if the measurement projects the physical spin to $\left(\text{|}+1\u3009-|-1\u3009|\right)/\sqrt{2}$, then the gate is proportional to ${A}_{+1}-{A}_{-1}=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)={\sigma}_{x}$, a NOT gate. Extending this example to arbitrary measurement axes leads to a general set of gates that can be implemented by measuring this AKLT state locally. Two dimensions are more complicated, but careful analysis on interesting known states or modification of their local tensors leads to useful gate constructions (Gross et al., 2007).

After the discussions of the original one-way computer and other variants of measurement-based quantum computation, it is appropriate to point out that in the literature, measurement-based quantum computation, one-way quantum computation, and cluster-state quantum computation are often used synonymously. The subtle difference may lie in what resource states are used and whether measurement is performed on individual qubits or multiple qubits jointly.

#### Entanglement in the Circuit Model and the Measurement-Based Models

In measurement-based quantum computation, entanglement is the essential resource. In the circuit model, large entanglement may be created during the computation. However, it should be mentioned that in the circuit model, it is possible to realize universal quantum computation with little entanglement, as shown by Van den Nest (Van den Nest, 2013). The idea is that any circuit $U$ that performs a computation can always be modified by appending an ancillary qubit that is initialized in a state $\sqrt{1-\epsilon}\left|0\u3009+\sqrt{\epsilon}\right|1\u3009$ and the original action of $U$ is applied when this ancillary qubit is in the state $|1\u3009$. Thus, the state of the whole system, after such a controlled action, becomes a superposition of (a) the ancillary qubit being $|0\u3009$ and no computation being executed and (b) the ancillary qubit being $|1\u3009$ and the computation $U$ being executed. Because $\epsilon $ is small, the state of the quantum computer is dominated by case (a) and has little entanglement at any stage of computation. However, the probability that the desired computation has been executed is also small, which is proportional to $\epsilon $. In contrast, the one-way quantum computer requires the substantial presence of initial entanglement in the resource state.

### Part Two: Further Developments of MBQC and Connections to Other Subjects

#### Resource States Beyond Cluster States

Cluster states are recognized as a resource for measurement-based quantum computation, in particular in the one-way quantum computer and the correlation-space approach. This was originally shown for the square-lattice cluster state. In fact, cluster states can be defined on any graph, usually referred to as graph states. An immediate question after the work of Raussendorf and Briegel was whether cluster states defined on other 2D lattices were also universal in the sense that they could also be used for universal quantum computation by measuring individual spins. This was first addressed by Van den Nest and colleagues (Van den Nest et al., 2006), who showed that cluster states on other regular lattices such as the triangular, hexagonal, and kagome lattices are also universal. This can be intuitively understood by the picture of measurement “LEGO” pieces for universal gates (see the section “One-Way Quantum Computer and Cluster States”). Another approach to proving the universality is to demonstrate that these cluster states can be interconverted (to a smaller size) by performing single-qubit measurements on a subset of qubits, as done by Van den Nest and colleagues.

A natural next question is whether the universality holds when the lattice is not perfectly regular or, more generally, the qubits reside on vertices of planar random graphs. Browne and colleagues first addressed this, showing that the universality of the faulty square-lattice cluster state depends on the connectivity of the lattice, or more explicitly, the so-called site percolation threshold (Browne et al., 2008). Such a view of percolation was later shown to hold generally for graph states on planar random graphs (Wei et al., 2012).

Several obvious questions arise. Are there other types of resource states? Can these resource states emerge as ground states of short-ranged Hamiltonians, preferably with a gap? Can thermal states provide useful computation? What is the entanglement requirement of resource states? Can MBQC be fault-tolerant, just like the circuit model employing quantum error-correction codes? Can universal quantum computation become a property of a phase of matter? Is MBQC a practical approach to build a quantum computer? The second part of this review discusses answers to these questions as well as other topics of MBQC.

#### MBQC Is Programmable

Nielsen and Chuang showed that it is not possible to build a general-purpose quantum computer to perform an arbitrary quantum computation unless the gate array is operated probabilistically (Nielsen & Chuang, 1997). Their result is based on the circuit model and teleportation. The framework of the MBQC actually allows for a general-purpose quantum computer. In terms of the cluster state, the gate can be applied deterministically provided feedforward is permitted and the size of the cluster state is sufficiently large. The resultant quantum state before the final readout is correct up to Pauli corrections, but the classical outcomes can be corrected. Therefore, it can be argued that such a general-purpose measurement-based quantum computation does allow for arbitrary quantum computation and is hence programmable.

#### Entanglement Requirement of One-Way and Correlation-Space MBQC

Systems of limited entanglement can be efficiently simulated by classical computers (Vidal, 2003). From this perspective, entanglement in the universal resource states should grow with their system size, as shown by Van den Nest and colleagues, and is consistent with the entanglement in various universal cluster states (Van den Nest et al., 2006). Van den Nest and colleagues further applied an entanglement quantifier called Schmidt rank, which is the least number of components in a product form (with respect to a bi-partitioning A:B) that a quantum state can be decomposed to (i.e., the number $x$ in the decomposition $|{\Psi}_{AB}\u3009={\Sigma}_{\text{i}=1}^{x}|{\psi}_{i}\u3009{}_{A}\otimes |{\phi}_{i}\u3009{}_{B}$). They showed that when the Schmidt rank of a quantum state, maximized over all bi-partitions, is only logarithmic in the system size, then the efficient classical simulations of MBQC using the quantum state is possible (Van den Nest et al., 2007). This is a no-go result for universal quantum computation with limited entanglement. Thus, it is natural to ask how much entanglement in the resource state is needed for universal MBQC. It is expected to scale with the number of qubits. However, the following result is unexpected.

##### Too Much Entanglement Is Useless

Gross, Flammia, and Eisert (Gross et al., 2009) found that random states generically have a high amount of entanglement, and if the entanglement of a quantum state is too high, then using it for MBQC cannot offer any speed-up for computation and is no better than random coin tossing. A similar conclusion that random states drawn uniformly from the state space (or in a more technical term, from the Haar measure) are useless for MBQC was reached by Bremner, Mora, and Winter (Bremner et al., 2009). Both results suggest that quantum states that are a universal resource for QC are actually rare and that as commented by Bacon, “entanglement, like most good things in life, must be consumed in moderation” (Bacon, 2009). In fact, by using computational complexity theory, Morimae showed that it is generically a difficult problem to find resource states for measurement-based quantum computation (Morimae, 2017).

#### Fault Tolerance of MBQC

In order to guarantee that quantum computation can proceed as long as is needed, error correction and fault tolerance are necessary. In the circuit model, transversal error-correction codes are used to encode a logical qubit by several physical qubits, so that an error can be suppressed at the encoded logical level if the error rate at the physical level is sufficiently low (Gottesman, 1997; Lidar & Brun, 2013). Error correction in other models of quantum computation, such as the adiabatic quantum computation, is still not yet settled. The issue of fault tolerance in the one-way quantum computer was first addressed by Raussendorf in his PhD thesis (Raussendorf, 2003). One can essentially use the 2D cluster state to simulate 1D fault-tolerant circuits. In a similar way, Nielsen proposed to use the teleportation-based approach to simulate quantum circuits with error correction. He argued that a similar threshold theorem should hold here.

Later, Nielsen and Dawson addressed the issue of fault tolerance in the one-way quantum computation with cluster states (Nielsen & Dawson, 2005). They employed the techniques in the conventional circuit model and developed methods to translate the noise and error considerations into the one-way quantum computer model. They proved that it is indeed possible that the computation is fault-tolerant, provided the error rate is below a certain threshold. However, they did not give a numerical estimate of the threshold value.

Raussendorf et al. (2006, 2007) exploited a three-dimensional cluster state so that each two-dimensional slice is used to simulate the surface code, a popular error-correcting code (S. B. Bravyi & Kitaev, 1998; Fowler et al., 2009; Kitaev, 2003). However, the surface code alone cannot achieve all universal gates; additional gates that are needed to complete the universality can be inserted by the so-called magic-state distillation (Bravyi & Kitaev, 2005). The 3D cluster state can be imagined to be measured layer by layer. Specific measurement patterns mimic the braiding of anyons of topological quantum computation to create gates allowed in the surface code, and others are used to inject the magic state. They showed that the error threshold in this topologically simulated fashion reached as high as 0.75% versus other estimates of order 0.01% or lower (Nielsen & Chuang, 2002). The higher the threshold, the higher the tolerance of errors. Such a topological protection of the MBQC also gives rise to a high threshold in the so-called surface-code quantum computation (Fowler et al., 2012; Raussendorf & Harrington, 2007), intensively pursued in the circuit-model-based quantum computers using a two-dimensional architecture.

More recently, Brown and Roberts developed a general framework that translates a fault-tolerant procedure for stabilizer codes to a measurement-based protocol (Brown & Roberts, 2020) by treating the resource state and single-qubit measurement pattern in the MBQC as a gauge fixing, which is an advanced technique in the subsystem error-correction codes.

#### Resource States as Ground States of Short-Ranged Interacting Hamiltonians

Cluster states can be created by unitary evolution induced by Ising-type spin–spin interaction. This was demonstrated in cold atoms (Mandel et al., 2003). However, it may not be easy to achieve such active coupling for other types of resource states. An alternative method—if the resource state is the unique ground state of a short-ranged interacting Hamiltonian with a finite spectral gap—is by cooling the system to low-enough temperature. Unfortunately, cluster states are not unique ground states of any two-body interacting Hamiltonians (Nielsen, 2006). The cluster state on the square lattice is the unique ground state of a five-body interacting Hamiltonian with a non-zero spectral gap. Interaction involving more than two spins is generally difficult to engineer. (If the condition of being exact ground states is relaxed, then the cluster state in certain encoding forms can be an approximate ground state of a two-body interacting Hamiltonian [Bartlett & Rudolph, 2006].) A linear-optical simulation of the cooling of a cluster-state Hamiltonian has actually been performed for a three-site chain, whose Hamiltonian involves only the three spins. Ideally the range of interaction should involve just the nearest neighbors. If such a Hamiltonian can be engineered (which, in itself, is also not a trivial task), then simply “cooling” the system to low-enough temperature can prepare the system to be close to the perfect universal resource ground state. An obvious question is where such states and their Hamiltonian can be found.

The first provable universal resource state with a nearest-neighbor interacting parent Hamiltonian with a non-zero spectral gap is the so-called tri-cluster state defined on the hexagonal lattice, invented by Chen and colleagues (Chen et al., 2009). This is a quantum state with a local Hilbert space of dimension six, which contains the cluster state in three different bases, hence the name tri-cluster state. Despite this having more than two levels, the tri-cluster state can be further converted to a cluster state of qubit local Hilbert space (i.e., of two levels) by the so-called quantum state reduction (Chen et al., 2010).

#### Tensor-Network States and Correlation-Space MBQC

The correlation-space measurement-based quantum computation taps into tensor-network states for the enabling resource (Gross & Eisert, 2007; Gross et al., 2007; Verstraete & Cirac, 2004b). It explains how the cluster state used in the one-way quantum computer can be understood with local tensors. It offers a simple explanation of local gates and also generalizes resource states by modifying local tensors. However, it should be pointed out that the computation is undertaken in the Hilbert space of virtual qubits, in contrast to the one-way quantum computer where the computation is done in the Hilbert space of physical qubits. Some example states investigated in the correlation-space picture include the AKLT state and modified toric code states (Gross et al., 2007).

#### Affleck-Kennedy-Lieb-Tasaki States for Universal MBQC

One family of states that has gained much attention for the MBQC is the one constructed by Affleck, Kennedy, Lieb, and Tasaki (referred to as AKLT) (Affleck et al., 1987, 1988). The particular 1D AKLT model gives strong evidence of Haldane’s conjecture (Haldane, 1983) that isotropic quantum spin chains of integer spin have a unique ground state with a finite spectral gap. This is the opposite of half-integer spin chains, where the ground state is either degenerate or the system does not possess a finite spectral gap (Lieb et al., 1961). The AKLT construction by valence-bond states naturally generalizes to higher dimensions and arbitrary graphs. It was shown that these AKLT states are unique ground states of certain isotropic two-body interacting Hamiltonians. The local Hilbert-space dimension and the explicit form of the Hamiltonian depend on the local structure of a lattice.

The 1D AKLT state of local Hilbert-space dimension 3 (i.e., qutrits) was first explored by Gross and Eisert in the measurement-based quantum computation (Gross & Eisert, 2007; Gross et al., 2007) using the correlation-space picture. Brennen and Miyake (Brennen & Miyake, 2008) later realized that, to execute one-qubit operation in the edge state of the spin-1 AKLT chain, the coupling of the edge spin with the bulk must be turned off and a subsequent local measurement performed on it. In fact, this works with any spin chain in the so-called Haldane’s phase that is symmetry protected (Miyake, 2010).

To go beyond one dimension, Cai and colleagues considered stacked layers of 1D AKLT chains with decoration; namely, in each layer there are spins of local dimension 4 residing on the backbone of a chain, and spins of local dimension 2 are connected to each site of the backbone. They transformed such a layer structure of 1D chains into a 2D AKLT-like state. They showed that this state is universal for MBQC (Cai et al., 2010). Later it was shown by Wei and colleagues (Wei et al., 2011) and independently by Miyake (Miyake, 2011) that the original 2D spin-3/2 AKLT state on the hexagonal lattice is actually universal for MBQC. Such a result was also generalized beyond the hexagonal lattice (Wei, 2013; Wei et al., 2014), including the universality of the spin-2 AKLT state on the square lattice (Wei & Raussendorf, 2015).

One approach to show that AKLT states are universal for MBQC is to convert the AKLT state to a cluster state, which is itself universal, via local measurement. In the case of the spin-3/2 AKLT states, a four-level system must be mapped locally to a two-level system. This can be achieved by a generalized measurement at all sites. Similar to the projective measurement, the outcome of the generalized measurement on the AKLT spins is also random and has three different outcomes labeled by x, y, or z. It was shown that for any outcome of the generalized measurement on all sites, the AKLT state is transformed into an encoded graph state. Encoding simply means that a logical qubit is extended to connected sites of the same type of outcome (x, y, or z) (see figures 8[b] and [e]). The graph is modified from the hexagonal lattice: Each domain that contains connected sites of the same outcome form a vertex, whereas the interdomain edges need to be treated in a modulo-2 manner—an even number of edges will be converted to no edge between two domains, but an odd number of edges will be converted to a single edge that connects two domains (see figure 8). Invoking the results of universality for random planar graphs, if their connectivity as defined by percolation is sufficiently high, then the graph states are as good as regular cluster states for MBQC. This connectivity was checked and confirmed by numerical percolation simulations (Wei et al., 2011).

Another approach to proving the universality is to demonstrate that universal gates can be simulated. Miyake used the same generalized measurement and defined the notion of a computational backbone (Miyake, 2011), where one- and two-qubit gates were constructed in the correlation-space picture. He argued that a macroscopic size of the backbone exists with a sufficiently high probability on the hexagonal lattice, and thus, the AKLT state is universal for MBQC.

Higher spins present specific technical difficulties. However, Wei and Raussendorf managed to show that the spin-2 AKLT state on the square lattice is universal (Wei & Raussendorf, 2015, p. 2). Whether AKLT states with higher spins than 2 are universal for MBQC remains open.

The issue of the non-zero gap above the ground state in the spin-3/2 model on the hexagonal lattice has been a longstanding question. AKLT showed that the spatial correlation function in the ground state decays exponentially, but the existence of the gap could not be proved (Affleck et al., 1987). In newer work, two groups independently used numerically assisted approaches to show that the AKLT model indeed possesses a non-zero spectral gap (Lemm et al., 2020; Pomata & Wei, 2020), even in the limit that the system size becomes infinite. Therefore, the AKLT models provide example Hamiltonians that are short-ranged, gapped, and have a unique ground state that is universal for measurement-based quantum computation. This property may be helpful when creation of the ground-resource states is performed by cooling the temperature of the physical system.

#### Symmetry-Protected Topological States and Quantum Computational Phases of Matter

The lack of a systematic approach to characterize universal resource states has led researchers to consider certain phases of matter, and in particular, the symmetry-protected topological phases. Else and colleagues (Else et al., 2012) found that teleportation of the one-qubit state is possible in the correlation space anywhere within a symmetric phase of ${Z}_{2}\times {Z}_{2}$, but general gates can only be achieved at very special points in the phase of matter. The ${Z}_{2}$ symmetry group consists of only two elements, such as the identity element and a rotation around the x-axis by 180 degrees; ${Z}_{2}\times {Z}_{2}$ is a symmetry group that is a product of two such ${Z}_{2}$ symmetry groups (that commute with each other). Example states in the nontrivial ${Z}_{2}\times {Z}_{2}$ phase include the 1D cluster state and the 1D AKLT state. The ability to implement teleportation in a quantum wire with ${Z}_{2}\times {Z}_{2}$ symmetry (as in the work of Else et al., 2012) was later extended to other symmetry groups, including non-Abelian ones (Prakash & Wei, 2015). More relevantly, Miller and Miyake generalized the idea of renormalization (Bartlett et al., 2010) and used it to show that the 1D symmetry-protected topological phase by ${S}_{4}$ symmetry (which is the permutation group of four objects) can give rise to the implementation of arbitrary one-qubit gates (Miller & Miyake, 2015). Subsequently, Stephen and colleagues extended this more generally (Stephen et al., 2017). This is the strongest connection of symmetry-protected topological phases to quantum computation. However, a one-dimensional state of matter only offers limited computation, such as one-qubit gates. In order to obtain universal quantum computation, higher dimensions are needed.

Doherty and Bartlett considered teleportation to be a necessary condition and devised an order parameter to detect it in a cluster Hamiltonian with an external field (Doherty & Bartlett, 2009). They found that such characterization coincided with the conventional phase diagram of the model. However, the ability to teleport does not necessarily imply the ability to implement universal gates.

Going beyond one dimension, Poulsen Nautrup and Wei considered the fixed-point wavefunctions of 2D symmetry-protected topological phases constructed by Chen and colleagues using the mathematics of cohomology and showed that they could be used to perform universal measurement-based quantum computation (Poulsen Nautrup & Wei, 2015). Independently, Miller and Miyake considered a different symmetry-protected topological state (with ${Z}_{2}\times {Z}_{2}\times {Z}_{2}$ symmetry) on the “union-jack” lattice based on a Control-Control-Z gate construction by Yoshida (Yoshida, 2016) and showed that this state could also be used for universal measurement-based quantum computation (Miller & Miyake, 2016). This universality was later generalized to the symmetry of ${Z}_{d}\times {Z}_{d}\times {Z}_{d}$ (Chen et al., 2017). One interesting feature in the work of Miller and Miyake is that universality can already be achieved by measuring Pauli operators, namely along the x-, y- and z-axis of the Bloch sphere, which is not the case in the cluster state. In Wei (Wei, 2018), the construction by Miller and Miyake was shown to be equivalent to a different but widely known topological state constructed by Levin and Gu (Levin & Gu, 2012), whose model was a paradigmatic one for two-dimensional symmetry-protected topological phases. However, these studies only apply to specific representative wavefunctions of the symmetry-projected topological phases. An attempt was made by Wei and Huang that extended the universality to an extended region around some of these fixed-point states (Wei & Huang, 2017), but whether an entire phase could be reached was not known at that time.

It is possible to obtain universal resource from an entire phase of matter in two dimensions. The particular phase is called the cluster phase (Raussendorf et al., 2019), which contains the cluster state as a specific example. It has been studied on various 2D lattices (Daniel et al., 2020; Devakul & Williamson, 2018), and it was understood that the essential symmetry that provides such computational power belongs to the so-called subsystem symmetry, including a symmetry element that acts on spins located spatially in a fractal pattern. These results point to a possible general notion of quantum computational phases of matter. In fact, a different perspective of quantum computational phases of matter has been explored in the context of intrinsic topological phases where braiding of anyonic excitations leads to a myriad of quantum gates (Nayak et al., 2008).

#### Thermal States for Measurement-Based Quantum Computation

The cluster state in the one-way quantum computer can be regarded as the ground state of a cluster Hamiltonian, which is related to a simple paramagnetic Hamiltonian via transformation using Controlled-Z gates (Briegel & Raussendorf, 2001). The ground state is the property of a system at zero temperature, but in real life, the system will always sit at a finite temperature. Thus, it is natural to consider one-way computation at finite temperatures. Fujii and colleagues compared the cluster Hamiltonian and a related interacting cluster Hamiltonian that is transformed to an Ising-interacting Hamiltonian and investigated the finite-temperature effect on the computational capability (Fujii et al., 2013). The latter model possesses a thermal phase transition, whereas there is no transition in the original cluster-state model. Fujii and colleagues found that the long-range order in their model enhances the robustness of quantum computation against thermal excitations. In going beyond cluster models, Li and colleagues constructed two models in two- and three-dimensions in which the thermal states are useful for universal MBQC and the interactions do not need to be turned off during computation (Li et al., 2011). The three-dimensional model was subsequently modified by Fujii and Morimae to one that possesses uniform spin-3/2 entities on all sites. They showed that from the thermal state, a relatively clean cluster state of high connectivity could be distilled (Fujii & Morimae, 2012). Other constructions were proposed (Wei et al., 2014) that also discussed the thermal transition of quantum computational power. Consideration of thermal states and the finite-temperature effect for measurement-based quantum computation will become relevant in the effort of building a realistic measurement-based quantum computer.

#### MBQC and Classical Computation

The aim of measurement-based quantum computation is to achieve the capability of universal quantum computation. It not only relies on simple classical computation but may also yield insight on the latter. Van den Nest and Briegel established a connection between the MBQC and the field of mathematical logic (Van den Nest & Briegel, 2008). In particular, if a graph state yields a speed-up of the quantum computation with respect to its classical counterpart, then the underlying graph is associated with an undecidable logic theory, where the undecidability is similar to Gödel’s incompleteness results.

From a different perspective, Anders and Browne studied how the correlations exploited in MBQC enabled computational power (Anders & Browne, 2009; see figure 9). Cluster states possess certain kinds of entanglement and correlations, and the classical computer interacting with such correlations (as revealed by measurement) only needs to execute binary addition in order to achieve universal quantum computation. Thus, a meaningful question is: With the limited power of a classical computer, how do the correlations give rise to computational power? For certain tensor-network states, to achieve universal quantum computation, the classical computer needs operations beyond binary addition. Said conversely, a limitation to perform only binary addition (i.e., parity) for the classical computer interacting with the correlations from the tensor-network states may not achieve universal quantum computation. This also leads to the concept of measurement-based classical computation: What kind of correlations can boost the computational power of a classical parity computer? Anders and Browne showed that correlations in any bipartite quantum state cannot help to realize the classical NAND gate deterministically. In contrast, the three-qubit GHZ can do that, thereby boosting the classical computer to a classical universal one. These considerations also reveal a connection between the violation of local realistic models and the computational power of entangled states. Such violation is a manifestation of the so-called *contextuality* in the foundations of quantum mechanics (Kochen & Specker, 1967). Naively, one might expect that the measurement of observables simply reveals their pre-existing values and hence is not *contextual*. However, this view is at odds with quantum mechanics.

In addition to its role in quantum foundations, contextuality has been shown to supply the “magic” to quantum computation (Bermejo-Vega et al., 2017; Howard et al., 2014). It is known that quantum computation with a limited gate set, such as the Pauli gates, Hadamard, phase and CNOT gates (in the family of Clifford gates), can be efficiently simulated by a classical computer. A non-Clifford gate is needed to boost the power of a quantum computer. The consequence of a state being contextual is that a magic state can be distilled out of it and enables implementation of non-Clifford gates, making a quantum computer universal. Clifford gates are those that transform a product of Pauli operators to another product form, and quantum computation using only Clifford gates can be efficiently simulated by a classical computer by tracking how Pauli operators transform into one another; therefore, such a computer cannot achieve universal quantum computation (Gottesman, 1999). An example of a non-Clifford gate is a rotation around the z-axis by ${45}^{\circ}$, also known as the T gate. Adding this T gate to the set of Clifford gates unleashes the power of universal quantum computation.

Given that contextuality is intimately related to measurement, Raussendorf (2013) expanded the study of contextuality in MBQC and showed that such a qubit quantum-computational model with classical binary-addition capability is contextual if it can compute a nonlinear Boolean function with a high probability—meaning such a computational model cannot be explained by a realistic local hidden-variable model. In particular, this shows that such MBQC executing the quantum algorithm for the discrete log problem is contextual; the super-polynomial speed-up over the best-known classical algorithm seems to be supplied by contextuality. Such a result was recently generalized to the qudit (with $d$ levels instead of two) scenario that shows strong non-locality is necessary for MBQC evaluating high-degree polynomial functions, with the classical control computer having only linear processing capability (Frembs et al., 2018).

#### Time Ordering in MBQC

In the one-way quantum computer of Raussendorf and Briegel (Raussendorf & Briegel, 2001), measurement axes of some qubits may depend on the measurement outcomes of previously measured qubits. This results in partial time ordering among qubits in terms of measurement (Raussendorf et al., 2003). This can also be formulated in terms of the flow of quantum information (Danos & Kashefi, 2006), as illustrated in figure 10, which has led to a flow condition that gives rise to deterministic computation on graph states (de Beaudrap, 2008a, 2008b). Measurement calculus has also been developed for the one-way quantum computer (Danos et al., 2007). These prior works have led to the reduction and parallelization of a certain class of polynomial-depth circuits to logarithmic ones (Broadbent & Kashefi, 2009). The notion of flow has also been generalized so as to deal with the situation where there is no flow on an entanglement graph, but instead a generalized flow exists, as well as to optimize implementation of the unitary gates (Browne et al., 2007). Generalizing this to stabilizer states beyond graph states, temporal relations and measurement settings were classified in terms of bases of the so-called check matrix that characterizes these states. This also gave rise to the result that classical processing relations for deterministic computation can constrain the resource state and measurement setting (Raussendorf et al., 2016).

#### MBQC and Classical Spin Models

In statistical mechanics, knowledge of the partition function of a system gives rise to its equilibrium properties (Baxter, 2016; McCoy, 2010). Van den Nest, Dür, and Briegel found that the partition function of the well-known classical Ising model in statistical mechanics (Baxter, 2016; McCoy, 2010) can be written as the overlap between a resource state $|\psi \u3009$ and a product state (Van den Nest et al., 2007). The resource state $|\psi \u3009$ is a graph state that encodes the interaction pattern of the model, and the product state encodes coupling and local field strengths, which can be complex in general. Such an overlap represents a branch in the measurement-based quantum computation. If it is easy to compute the corresponding partition functions for all model parameters, then the quantum computation can be efficiently simulated by classical means, and thus the corresponding resource state is not universal (Van den Nest et al., 2007). Moreover, the 2D Ising model is regarded as complete in that the partition function of the q-state Potts models in statistical mechanics (Baxter, 2016; McCoy, 2010) can be reduced to an instance of the partition function of the Ising model with generally complex parameters. The connection to MBQC is made via the branch in the computation (specified by the product state) using a 2D cluster state for both the Ising and q-state Potts models in statistical mechanics (Van den Nest et al., 2008). Using measurement-based quantum computation to study classical spin models seems to be an interesting research direction. Considerations along this line of thought have led to the fruitful finding that all the physics of every classical spin model is reproduced by certain “universal models” in their low-energy sector and that the two-dimensional Ising model with fields is universal (De las Cuevas & Cubitt, 2016).

#### Blind Quantum Computation

In the one-way computer, once the resource state and the measurement patterns are fixed, the specific quantum circuit is determined. Imagine a server that takes the instruction of measurement axes and reports the outcomes to a client that intends to run some quantum computation. Is it possible that the client can instruct the server, but the latter cannot find out what quantum circuit has been executed? Broadbent et al. (2009) devised so-called blind quantum computation using measurement-based quantum computation to achieve this. However, this requires the client to prepare the initial product state of the entire array of qubits in the form $\left|0+{e}^{i\theta}\right|1\u3009$, where the phase $\theta $ is a multiple of $\text{\pi}/4$. Then the client sends all qubits to the server, which then places them on a brickwork lattice (see figure 11) and applies the Controlled-Z gates pairwise according to the brickwork structure. Subsequent communication between them is entirely classical. They communicate back and forth via the client informing the measurement axes of a column of qubits to be measured, and the server returns the measurement outcomes. The computation terminates when all qubits have been measured. Broadbent and colleagues showed that by randomly initializing the qubits and randomly flipping the measurement axes, the client could hide the computation from the server. A small-scale experimental demonstration of blind quantum computation has been carried out by Barz and colleagues (Barz et al., 2012). There have been many works following up on the idea of blind quantum computation; see the review by Fitzsimons (Fitzsimons, 2017) and the references therein.

#### Issues of Measurement Axes and Observables

Already in the work of blind quantum computation (Broadbent et al., 2009), measurement of observables in the x–y plane is sufficient, as there is no need to carve the required entanglement structure from some other initial cluster or graph states. Mantri and colleagues consider open-ended rectangular lattices and show that for cluster states on these lattices, measurement in the x–y plane is also sufficient (Mantri et al., 2017). In a ${Z}_{2}$ symmetry-protected topological state, which belongs to the hypergraph states, Miller and Miyake showed that only Pauli X, Y, and Z measurements are sufficient (Miller & Miyake, 2016). Subsequently, Takeuchi and colleagues constructed a specific hypergraph state such that only Pauli X and Z measurements are sufficient (Takeuchi et al., 2019). It is believed that further reduction of measurement is unlikely to be possible, but Pauli measurements are relatively easy to implement. However, hypergraph states may not be trivial to generate.

#### Linear-Optical Quantum Computation

The perspective of MBQC also revived the proposal by Knill, Laflamme, and Milburn that showed it is possible to use linear-optical elements assisted with single-photon sources and detectors for universal quantum computation in the standard circuit model (Knill et al., 2001). Despite the scheme being possible in principle, the required resources involved are daunting (Li et al., 2015). It is by using cluster states of the one-way quantum computation (Browne & Rudolph, 2005; Nielsen, 2004) that the interest in linear-optical quantum computation was revived, as the resource requirement was dramatically reduced (see figure 12). Some small cluster states were realized by merging down-conversion entangled photon pairs (Lu et al., 2007; Walther et al., 2005). There have been further works that propose methods to create 2D cluster states (Economou et al., 2010; Gimeno-Segovia et al., 2019; Lindner & Rudolph, 2009), and there has been some experimental effort toward realizing key proposed ingredients (Schwartz et al., 2016).

In addition to using discrete basis states such as polarization or time bins, another related development is to use continuous variables of light (i.e., the continuous degrees of freedom in its electric field). Menicucci and colleagues proposed schemes to generate continuous-variable cluster states (Menicucci, 2014; Menicucci et al., 2007), later showing that it is possible to use them for fault-tolerant measurement-based quantum computation (Menicucci, 2014). There have been experimental achievements in realizing large-scale cluster states of a large number of optical modes (Chen et al., 2014; Larsen et al., 2019; Yokoyama et al., 2013; Yoshikawa et al., 2016). However, it is still a challenge to perform local optical-mode measurement for universal quantum computation.

#### Graph States and Measurement-Based Approach for Quantum Communication

Bell states can be used to teleport an unknown quantum state, but in order to teleport over a long distance, such a long-distance entanglement needs to be established. If there is an array of Bell pairs distributed across two distant nodes, then so-called entanglement swapping can serve this purpose. As shown in figure 13(a), with one Bell pair shared between A and B and another shared between B and C, party B performs a Bell-basis measurement (see Table 1) and forwards the outcome to C; the initial shared A–B entanglement can be teleported to form entanglement between A and C. This is entanglement swapping (Pan et al., 1998). By applying this to an array of entangled pairs, as shown in figure 13(b), a long-distance entanglement can be established (Sangouard et al., 2011). This is the basic setup of the so-called “quantum repeaters” (Duan et al., 2001). In fact, the measurement-based approach has provided a useful framework to consider ideas from entanglement purification, noisy channels, fault tolerance, and transmission of big quantum data together (Pirker et al., 2018; Wallnöfer & Dür, 2017; Zwerger et al., 2012, 2013, 2014, 2016, 2018). Some of the proposed methods have been realized experimentally (Chrzanowski et al., 2014), including amplification of degraded entanglement and extraction of secure keys in an otherwise insecure regime.

In using entangled photons there is, however, a limitation due to the finite failure probability of photonic Bell measurement (see Table 1), which is $1/2$ without using additional resource (Calsamiglia, 2002). This means that successful long-range entanglement only happens at an exponentially small rate. Azuma, Tamaki, and Lo proposed to use cluster states or graph states to solve this issue (Azuma et al., 2015). The graph of the graph states used in this quantum communication scheme consists of inner nodes that form a complete graph and outer nodes (also called leaf nodes) that are connected to the inner nodes. In figure 13(c), two such graph states are shown, which replace the two Bell pairs in figure 13(a). Because of multiple leaves, multiple attempts of Bell measurement can be made and the success probability that A and B become entangled can be boosted from $1/2$ to $1-1/{2}^{n}$, where $n$ is the number of leaves. This scheme, in principle, allows quantum communication without using quantum memories to temporarily store the states of photons. However, the challenge is to create such a graph state; one natural approach is to use the fusion schemes in figure 12.

#### Experimental Progress

Arguably, the first experimental realization of a cluster state was achieved by the group of Bloch using cold atoms trapped in an optical lattice (with two selected hyperfine states as a qubit) (Mandel et al., 2003). They used a “cold controlled collision” method (Jaksch et al., 1999) already envisaged in the original work of the cluster state by Briegel and Raussendorf (Briegel & Raussendorf, 2001), which shifted atoms by a lattice site depending on their hyperfine spin state so as to induce a phase shift for certain combinations of nearby spin states. However, at that time, individual addressing such as single-atom measurement and gate operation were not possible and implementation of the one-way computer was still very challenging. Progress on the imaging and addressing of individual atoms makes the realization of the one-way computation in trapped cold atoms probably not far-fetched (Bakr et al., 2009; Edge et al., 2015; Sherson et al., 2010; Simon et al., 2011; Weitenberg et al., 2011). In addition to previous use of bosonic cold atoms, a scheme for cluster-state generation with trapped fermionic atoms using interplay of the spin-orbit coupling and superexchange interaction has also been proposed, which may potentially have longer coherence time (Mamaev et al., 2019).

Instead of the cold collision, a Rydberg state can be exploited to induce a phase shift for two atoms in a particular hyperfine state that is driven resonantly to this Rydberg state. This is due to the interaction of the extended electron clouds of the two atoms in a Rydberg state and is usually referred to as the Rydberg blockade (Jaksch et al., 2000; Lukin et al., 2001; Weiss & Saffman, 2017). Rydberg blockade and entanglement generation between two neutral atoms via the Rydberg blockade have been demonstrated experimentally (Urban et al., 2009; Wilk et al., 2010; Zhang et al., 2010). This has also led to implementation of a Controlled-Z gate and it can potentially be used to directly create a cluster state of an array of atoms (Briegel & Raussendorf, 2001).

Small-size cluster and graph states have also been realized experimentally by probabilistically merging pairs of entangled photons (Lu et al., 2007; Walther et al., 2005); a small graph-state error-correction code was implemented (Bell et al., 2014). Deterministic schemes for their generation have also been proposed using solid-state and quantum-dot emitters (Economou et al., 2010; Gimeno-Segovia et al., 2019; Lindner & Rudolph, 2009). Important ingredients underlying these schemes have also been realized experimentally (Schwartz et al., 2016). In addition to the discrete polarization degrees of freedom of light, the so-called continuous-variable states of light have been employed to create large-scale cluster states in optical modes (Chen et al., 2014; Larsen et al., 2019; Yokoyama et al., 2013; Yoshikawa et al., 2016). One challenge for that system to implement computation is the measurement of individual modes and the fast feedforward to adapt subsequent mode measurements.

Cluster and graph states have also been generated in other physical systems, such as in trapped ions, where some error-correction codes were created (Lanyon et al., 2013), and in superconducting qubits, where some experiments were performed via the cloud-based publicly available quantum computers of IBM (Mooney et al., 2019; Wang et al., 2018).

Generation of resource states beyond cluster states seems to be harder. Nevertheless, certain one-dimensional tensor-network states used in the correlation-space approach have also been realized (Gao et al., 2011), including a short chain of the AKLT state (Kaltenbaek et al., 2010).

There are other theoretical proposals to produce cluster states and implement measurement-based quantum computation on various physical systems (Cho & Lee, 2005; Guo et al., 2007; Koch-Janusz et al., 2015; Kuznetsova et al., 2012; Lim et al., 2005, 2006; Lin et al., 2008; Tanamoto et al., 2006, 2009; Weinstein et al., 2005). It may be possible that the measurement-based approach will result in practical quantum computers in the not-so-distant future, comparable to those based on the standard circuit model.

### Conclusion

Measurement-based quantum computation offers both an intellectual framework for quantum information processing and a blueprint for potentially building up a quantum computer. For example, the entanglement requirement for computation was explored, and partial time ordering and symmetry were also studied for deterministic computation. Furthermore, how correlations could be used as a resource for classical computation also links to the foundations of quantum mechanics. Universal blind quantum computation was an unexpected application of measurement-based quantum computation, which could be useful in future, secure cloud-based quantum computation. In fact, application of the measurement-based approach to quantum communication is already feasible. From the perspective of condensed matter, the existence of an entire phase of matter capable of universal quantum computation makes the notion of the quantum computational phase of matter an interesting new interdisciplinary direction to explore. The establishment of fault tolerance in the MBQC and a high threshold value show that it is a viable alternative to the circuit model using error-correction codes in terms of fighting against noise and error. Many physical systems have been studied to realize the MBQC, and proof-of-principle experimental demonstrations have been made, such as in photonic, continuous-variable, trapped atoms and ions, and superconducting systems. However, each system has its own challenges lying ahead that need to be overcome before a realistic one-way quantum computer can be constructed.

#### Further Reading

- Briegel, H. J. (2009). Cluster states. In D. Greenberger, K. Hentschel, & F. Weinert (Eds.),
*Compendium of quantum physics—Concepts, experiments, history and philosophy*(pp. 96–105). Springer. - Briegel, H. J., Browne, D. E., Dür, W., Raussendorf, R., & Van den Nest, M. (2009). Measurement-based quantum computation.
*Nature Physics*,*5*, 19–26. - Browne, D. E., & Briegel, H. J. (2019). One-way quantum computation. In D. Bruß & G. Leuchs (Eds.),
*Quantum information: From foundations to quantum technology applications*. Wiley. - Jozsa, R. (2006). An introduction to measurement based quantum computation. In D. G. Angelakis, M. Christandl, A. Ekert, A. Kay, & S. Kulik (Eds.),
*NATO science series, III: Computer and systems sciences—Quantum information processing: From theory to experiment*(Vol. 199, pp. 137–158). IOS Press. - Kwek, L. C., Wei, Z., & Zeng, B. (2012). Measurement-based quantum computing with valence-bond-solids.
*International Journal of Modern Physics B*,*26*(02), 1230002. - Raussendorf, R., & Wei, T.-C. (2012). Quantum computation by local measurement.
*Annual Review of Condensed Matter Physics*,*3*, 239–261.

#### References

- Affleck, I., Kennedy, T., Lieb, E. H., & Tasaki, H. (1987). Rigorous results on valence-bond ground states in antiferromagnets.
*Physical Review Letters*,*59*, 799–802. - Affleck, I., Kennedy, T., Lieb, E. H., & Tasaki, H. (1988). Valence bond ground states in isotropic quantum antiferromagnets. In B. Nachtergaele, J. P. Solovej, & J. Yngvason (Eds.),
*Condensed matter physics and exactly soluble models*(pp. 253–304). Springer. - Aliferis, P., & Leung, D. W. (2004). Computation by measurements: A unifying picture.
*Physical Review A*,*70*(6), 062314. - Anders, J., & Browne, D. E. (2009). Computational power of correlations.
*Physical Review Letters*,*102*(5), 050502. - Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J. C., Barends, R., Biswas, R., Boixo, S., Brandao, F. G., Buell, D. A., Burkett, B., Chen, Y., Chen, Z., Chiaro, B., Collins, R., Courtney, W., Dunsworth, A., Farhi, E., Foxen, B., Fowler, A., . . . Martinis, J. M. (2019). Quantum supremacy using a programmable superconducting processor.
*Nature*,*574*, 505–510. - Averin, D. (1998). Adiabatic quantum computation with Cooper pairs.
*Solid State Communications*,*105*, 659–664. - Azuma, K., Tamaki, K., & Lo, H.-K. (2015). All-photonic quantum repeaters.
*Nature Communications*,*6*, 6787. - Bacon, D. (2009). Too entangled to quantum compute one-way.
*Physics*,*2*, 38. - Bakr, W. S., Gillen, J. I., Peng, A., Fölling, S., & Greiner, M. (2009). A quantum gas microscope for detecting single atoms in a Hubbard-regime optical lattice.
*Nature*,*462*, 74–77. - Barenco, A., Bennett, C., Cleve, R., DiVincenzo, D., & Margolus, N. (1995). Elementary gates for quantum computation.
*Physical Review A*,*52*, 3457. - Bartlett, S. D., Brennen, G. K., Miyake, A., & Renes, J. M. (2010). Quantum computational renormalization in the Haldane phase.
*Physical Review Letters*,*105*(11), 110502. - Bartlett, S. D., & Rudolph, T. (2006). Simple nearest-neighbor two-body Hamiltonian system for which the ground state is a universal resource for quantum computation.
*Physical Review A*,*74*(4), 040302. - Barz, S., Kashefi, E., Broadbent, A., Fitzsimons, J. F., Zeilinger, A., & Walther, P. (2012). Demonstration of blind quantum computing.
*Science*,*335*, 303–308. - Baxter, R. J. (2016).
*Exactly solved models in statistical mechanics*. Elsevier. - Bell, B., Herrera-Martí, D., Tame, M., Markham, D., Wadsworth, W., & Rarity, J. (2014). Experimental demonstration of a graph state quantum error-correction code.
*Nature Communications*,*5*, 3658. - Benioff, P. (1980). The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines.
*Journal of Statistical Physics*,*22*, 563–591. - Bennett, C. H., Brassard, G., Crépeau, C., Jozsa, R., Peres, A., & Wootters, W. K. (1993). Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels.
*Physical Review Letters*,*70*, 1895–1899. - Bermejo-Vega, J., Delfosse, N., Browne, D. E., Okay, C., & Raussendorf, R. (2017). Contextuality as a resource for models of quantum computation with qubits.
*Physical Review Letters*,*119*(12), 120505. - Bravyi, S. B., & Kitaev, A. Y. (1998). Quantum codes on a lattice with boundary. [ArXiv:9811052 [quant-ph]].
- Bravyi, S., & Kitaev, A. (2005). Universal quantum computation with ideal Clifford gates and noisy ancillas.
*Physical Review A*,*71*(2), 022316. - Bremner, M. J., Mora, C., & Winter, A. (2009). Are random pure states useful for quantum computation?
*Physical Review Letters*,*102*(19), 190502. - Brennen, G. K., & Miyake, A. (2008). Measurement-based quantum computer in the gapped ground state of a two-body Hamiltonian.
*Physical Review Letters*,*101*(1), 010502. - Briegel, H. J., & Raussendorf, R. (2001). Persistent entanglement in arrays of interacting particles.
*Physical Review Letters*,*86*(5), 910. - Broadbent, A., Fitzsimons, J., & Kashefi, E. (2009). Universal blind quantum computation. In
*Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science*(pp. 517–526). IEEE. - Broadbent, A., & Kashefi, E. (2009). Parallelizing quantum circuits.
*Theoretical Computer Science*,*410*, 2489–2510. - Brown, B. J., & Roberts, S. (2020). Universal fault-tolerant measurement-based quantum computation.
*Physical Review Research*,*2*(3), 033305. - Browne, D. E., & Rudolph, T. (2005). Resource-efficient linear optical quantum computation.
*Physical Review Letters*,*95*(1), 010501. - Browne, D. E., Elliott, M. B., Flammia, S. T., Merkel, S. T., Miyake, A., & Short, A. J. (2008). Phase transition of computational power in the resource states for one-way quantum computation.
*New Journal of Physics*,*10*, 023010. - Browne, D. E., Kashefi, E., Mhalla, M., & Perdrix, S. (2007). Generalized flow and determinism in measurement-based quantum computation.
*New Journal of Physics*,*9*, 250. - Cai, J., Miyake, A., Dür, W., & Briegel, H. J. (2010). Universal quantum computer from a quantum magnet.
*Physical Review A*,*82*(5), 052309. - Calsamiglia, J. (2002). Generalized measurements by linear elements.
*Physical Review A*,*65*(3), 030301. - Chen, M., Menicucci, N. C., & Pfister, O. (2014). Experimental realization of multipartite entanglement of 60 modes of a quantum optical frequency comb.
*Physical Review Letters*,*112*(12), 120505. - Chen, X., Duan, R., Ji, Z., & Zeng, B. (2010). Quantum state reduction for universal measurement based computation.
*Physical Review Letters*,*105*(2), 020502. - Chen, X., Gu, Z.-C., Liu, Z.-X., & Wen, X.-G. (2012). Symmetry-protected topological orders in interacting bosonic systems.
*Science*,*338*, 1604–1606. - Chen, X., Zeng, B., Gu, Z.-C., Yoshida, B., & Chuang, I. L. (2009). Gapped two-body Hamiltonian whose unique ground state is universal for one-way quantum computation.
*Physical Review Letters*,*102*(22), 220501. - Chen, Y., Prakash, A., & Wei, T.-C. (2017). Universal quantum computing using $($\backslash$mathbb ${$Z$}$ _d)^3$ symmetry-protected topologically ordered states.
*Physical Review A*,*97*(2), 022305 [ArXiv:1711.00094]. - Childs, A. M., Leung, D. W., & Nielsen, M. A. (2005). Unified derivations of measurement-based schemes for quantum computation.
*Physical Review A*,*71*(3), 032318. - Cho, J., & Lee, H.-W. (2005). Generation of atomic cluster states through the cavity input-output process.
*Physical Review Letters*,*95*(16), 160501. - Chrzanowski, H. M., Walk, N., Assad, S. M., Janousek, J., Hosseini, S., Ralph, T. C., Symul, T., & Lam, P. K. (2014). Measurement-based noiseless linear amplification for quantum communication.
*Nature Photonics*,*8*, 333–338. - Daniel, A. K., Alexander, R. N., & Miyake, A. (2020). Computational universality of symmetry-protected topologically ordered cluster phases on 2D Archimedean lattices.
*Quantum*,*4*, 228. - Danos, V., & Kashefi, E. (2006). Determinism in the one-way model.
*Physical Review A*,*74*(5), 052310. - Danos, V., Kashefi, E., & Panangaden, P. (2007). The measurement calculus.
*Journal of the ACM*,*54*(2), Article 8. - de Beaudrap, N. (2008a). An extremal result for geometries in the one-way measurement model.
*Quantum Information & Computation*,*8*, 430–437. - de Beaudrap, N. (2008b). Finding flows in the one-way measurement model.
*Physical Review A*,*77*(2), 022328. - De las Cuevas, G., & Cubitt, T. S. (2016). Simple universal models capture all classical spin physics.
*Science*,*351*, 1180–1183. - Devakul, T., & Williamson, D. J. (2018). Universal quantum computation using fractal symmetry-protected cluster phases.
*Physical Review A*,*98*(2), 022332. - DiVincenzo, D. P. (1995). Two-bit gates are universal for quantum computation.
*Physical Review A*,*51*(2), 1015. - Doherty, A. C., & Bartlett, S. D. (2009). Identifying phases of quantum many-body systems that are universal for quantum computation.
*Physical Review Letters*,*103*(2), 020506. - Duan, L.-M., Lukin, M. D., Cirac, J. I., & Zoller, P. (2001). Long-distance quantum communication with atomic ensembles and linear optics.
*Nature*,*414*, 413–418. - Economou, S. E., Lindner, N., & Rudolph, T. (2010). Optically generated 2-dimensional photonic cluster state from coupled quantum dots.
*Physical Review Letters*,*105*(9), 093601. - Edge, G. J., Anderson, R., Jervis, D., McKay, D. C., Day, R., Trotzky, S., & Thywissen, J. H. (2015). Imaging and addressing of individual fermionic atoms in an optical lattice.
*Physical Review A*,*92*(6), 063406. - Else, D. V., Schwarz, I., Bartlett, S. D., & Doherty, A. C. (2012). Symmetry-protected phases for measurement-based quantum computation.
*Physical Review Letters*,*108*(24), 240505. - Farhi, E., Goldstone, J., Gutmann, S., & Sipser, M. (2000). Quantum computation by adiabatic evolution. [ArXiv:0001106 [quant-ph]].
- Fenner, S. A., & Zhang, Y. (2001). Universal quantum computation with two-and three-qubit projective measurements. [ArXiv:0111077 [quant-ph]].
- Feynman, R. P. (1982). Simulating physics with computers.
*International Journal of Theoretical Physics*,*21*, 467–488. - Feynman, R. P. (1985). Quantum mechanical computers.
*Optics News*,*11*(2), 11–20. - Fitzsimons, J. F. (2017). Private quantum computation: An introduction to blind quantum computing and related protocols.
*npj Quantum Information*,*3*, 23. - Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012). Surface codes: Towards practical large-scale quantum computation.
*Physical Review A*,*86*(3), 032324. - Fowler, A. G., Stephens, A. M., & Groszkowski, P. (2009). High-threshold universal quantum computation on the surface code.
*Physical Review A*,*80*(5), 052312. - Frembs, M., Roberts, S., & Bartlett, S. D. (2018). Contextuality as a resource for measurement-based quantum computation beyond qubits.
*New Journal of Physics*,*20*, 103011. - Fujii, K., & Morimae, T. (2012). Topologically protected measurement-based quantum computation on the thermal state of a nearest-neighbor two-body Hamiltonian with spin-3/2 particles.
*Physical Review A*,*85*(1), 010304. - Fujii, K., Nakata, Y., Ohzeki, M., & Murao, M. (2013). Measurement-based quantum computation on symmetry breaking thermal states.
*Physical Review Letters*,*110*(12), 120502. - Gao, W.-B., Yao, X.-C., Cai, J.-M., Lu, H., Xu, P., Yang, T., Lu, C.-Y., Chen, Y.-A., Chen, Z.-B., & Pan, J.-W. (2011). Experimental measurement-based quantum computing beyond the cluster-state model.
*Nature Photonics*,*5*, 117–123. - Gimeno-Segovia, M., Rudolph, T., & Economou, S. E. (2019). Deterministic generation of large-scale entangled photonic cluster state from interacting solid state emitters.
*Physical Review Letters*,*123*(7), 070501. - Gottesman, D. (1997).
*Stabilizer codes and quantum error correction*[Doctoral dissertation, California Institute of Technology, United States] [ArXiv:9705052 [quant-ph]]. - Gottesman, D. (1999). The Heisenberg representation of quantum computers. In S. Corney, R. Delbourgo, & P. Jarvis (Eds.),
*Group 22: Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics*. International Press. - Gottesman, D., & Chuang, I. L. (1999). Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations.
*Nature*,*402*, 390. - Gross, D., & Eisert, J. (2007). Novel schemes for measurement-based quantum computation.
*Physical Review Letters*,*98*(22), 220503. - Gross, D., Eisert, J., Schuch, N., & Perez-Garcia, D. (2007). Measurement-based quantum computation beyond the one-way model.
*Physical Review A*,*76*(5), 052315. - Gross, D., Flammia, S. T., & Eisert, J. (2009). Most quantum states are too entangled to be useful as computational resources.
*Physical Review Letters*,*102*(19), 190501. - Gu, Z.-C., & Wen, X.-G. (2009). Tensor-entanglement-filtering renormalization approach and symmetry-protected topological order.
*Physical Review B*,*80*(15), 155131. - Guo, G.-P., Zhang, H., Tu, T., & Guo, G.-C. (2007). One-step preparation of cluster states in quantum-dot molecules.
*Physical Review A*,*75*(5), 050301. - Haldane, F. D. M. (1983). Nonlinear field theory of large-spin Heisenberg antiferromagnets: Semiclassically quantized solitons of the one-dimensional easy-axis Néel state.
*Physical Review Letters*,*50*, 1153–1156. - Howard, M., Wallman, J., Veitch, V., & Emerson, J. (2014). Contextuality supplies the “magic” for quantum computation.
*Nature*,*510*, 351–355. - Ising, E. (1925). Contribution to the theory of ferromagnetism.
*Zeitschrift für Physik*,*31*(1), 253–258. - Jaksch, D., Briegel, H.-J., Cirac, J., Gardiner, C., & Zoller, P. (1999). Entanglement of atoms via cold controlled collisions.
*Physical Review Letters*,*82*(9), 1975. - Jaksch, D., Cirac, J., Zoller, P., Rolston, S., Côté, R., & Lukin, M. (2000). Fast quantum gates for neutral atoms.
*Physical Review Letters*,*85*(10), 2208. - Jorrand, P., & Perdrix, S. (2005). Unifying quantum computation with projective measurements only and one-way quantum computation.
*Quantum Informatics 2004*,*5833*, 44–51. - Kadowaki, T., & Nishimori, H. (1998). Quantum annealing in the transverse Ising model.
*Physical Review E*,*58*(5), 5355. - Kaltenbaek, R., Lavoie, J., Zeng, B., Bartlett, S. D., & Resch, K. J. (2010). Optical one-way quantum computing with a simulated valence-bond solid.
*Nature Physics*,*6*, 850–854. - Kieling, K., Rudolph, T., & Eisert, J. (2007). Percolation, renormalization, and quantum computing with nondeterministic gates.
*Physical Review Letters*,*99*(13), 130501. - Kitaev, A. Y. (2003). Fault-tolerant quantum computation by anyons.
*Annals of Physics*,*303*, 2–30. - Knill, E., Laflamme, R., & Milburn, G. J. (2001). A scheme for efficient quantum computation with linear optics.
*Nature*,*409*, 46–52. - Kochen, S., & Specker, E. P. (1967). The problem of hidden variables in quantum mechanics.
*Journal of Mathematics and Mechanics*,*17*, 59–87. - Koch-Janusz, M., Khomskii, D., & Sela, E. (2015). Affleck-Kennedy-Lieb-Tasaki state on a honeycomb lattice from t 2 g orbitals.
*Physical Review Letters*,*114*(24), 247204. - Kuznetsova, E., Bragdon, T., Côté, R., & Yelin, S. (2012). Cluster-state generation using van der Waals and dipole-dipole interactions in optical lattices.
*Physical Review A*,*85*(1), 012328. - Kwiat, P. G., Mattle, K., Weinfurter, H., Zeilinger, A., Sergienko, A. V., & Shih, Y. (1995). New high-intensity source of polarization-entangled photon pairs.
*Physical Review Letters*,*75*(24), 4337. - Lanyon, B., Jurcevic, P., Zwerger, M., Hempel, C., Martinez, E., Dür, W., Briegel, H., Blatt, R., & Roos, C. F. (2013). Measurement-based quantum computation with trapped ions.
*Physical Review Letters*,*111*(21), 210501. - Larsen, M. V., Guo, X., Breum, C. R., Neergaard-Nielsen, J. S., & Andersen, U. L. (2019). Deterministic generation of a two-dimensional cluster state.
*Science*,*366*, 369–372. - Lemm, M., Sandvik, A. W., & Wang, L. (2020). Existence of a spectral gap in the Affleck-Kennedy-Lieb-Tasaki model on the hexagonal lattice.
*Physical Review Letters*,*124*(7), 177204. - Leung, D. W. (2001). Two-qubit projective measurements are universal for quantum computation. [ArXiv:0111122 [quant-ph]].
- Leung, D. W. (2004). Quantum computation by measurements.
*International Journal of Quantum Information*,*2*, 33–43. - Levin, M., & Gu, Z.-C. (2012). Braiding statistics approach to symmetry-protected topological phases.
*Physical Review B*,*86*(11), 115109. - Li, Y., Browne, D. E., Kwek, L. C., Raussendorf, R., & Wei, T.-C. (2011). Thermal states as universal resources for quantum computation with always-on interactions.
*Physical Review Letters*,*107*(6), 060501. - Li, Y., Humphreys, P. C., Mendoza, G. J., & Benjamin, S. C. (2015). Resource costs for fault-tolerant linear optical quantum computing.
*Physical Review X*,*5*(4), 041007. - Lidar, D. A., & Brun, T. A. (2013).
*Quantum error correction*. Cambridge University Press. - Lieb, E., Schultz, T., & Mattis, D. (1961). Two soluble models of an antiferromagnetic chain.
*Annals of Physics*,*16*, 407–466. - Lim, Y. L., Barrett, S. D., Beige, A., Kok, P., & Kwek, L. C. (2006). Repeat-until-success quantum computing using stationary and flying qubits.
*Physical Review A*,*73*(1), 012304. - Lim, Y. L., Beige, A., & Kwek, L. C. (2005). Repeat-until-success linear optics distributed quantum computing.
*Physical Review Letters*,*95*(3), 030505. - Lin, Z.-R., Guo, G.-P., Tu, T., Zhu, F.-Y., & Guo, G.-C. (2008). Generation of quantum-dot cluster states with a superconducting transmission line resonator.
*Physical Review Letters*,*101*(23), 230501. - Lindner, N. H., & Rudolph, T. (2009). Proposal for pulsed on-demand sources of photonic cluster state strings.
*Physical Review Letters*,*103*(11), 113602. - Lu, C.-Y., Zhou, X.-Q., Gühne, O., Gao, W.-B., Zhang, J., Yuan, Z.-S., Goebel, A., Yang, T., & Pan, J.-W. (2007). Experimental entanglement of six photons in graph states.
*Nature Physics*,*3*, 91–95. - Lukin, M. D., Fleischhauer, M., Cote, R., Duan, L., Jaksch, D., Cirac, J. I., & Zoller, P. (2001). Dipole blockade and quantum information processing in mesoscopic atomic ensembles.
*Physical Review Letters*,*87*(3), 037901. - Mamaev, M., Blatt, R., Ye, J., & Rey, A. M. (2019). Cluster state generation with spin-orbit coupled fermionic atoms in optical lattices.
*Physical Review Letters*,*122*(16), 160402. - Mandel, O., Greiner, M., Widera, A., Rom, T., Hänsch, T. W., & Bloch, I. (2003). Controlled collisions for multi-particle entanglement of optically trapped atoms.
*Nature*,*425*, 937–940. - Manin, Y. I. (1980).
*Vychislimoe i nevychislimoe*[Computable and Noncomputable] (in Russian). Sovetskoe Radio. - Mantri, A., Demarie, T. F., & Fitzsimons, J. F. (2017). Universality of quantum computation with cluster states and (X, Y)-plane measurements.
*Scientific Reports*,*7*, 42861. - McCoy, B. M. (2010).
*Advanced statistical mechanics*(Vol. 146). Oxford University Press. - Menicucci, N. C. (2014). Fault-tolerant measurement-based quantum computing with continuous-variable cluster states.
*Physical Review Letters*,*112*(12), 120504. - Menicucci, N. C., Flammia, S. T., Zaidi, H., & Pfister, O. (2007). Ultracompact generation of continuous-variable cluster states.
*Physical Review A*,*76*(1), 010302. - Miller, J., & Miyake, A. (2015). Resource quality of a symmetry-protected topologically ordered phase for quantum computation.
*Physical Review Letters*,*114*(12), 120506. - Miller, J., & Miyake, A. (2016). Hierarchy of universal entanglement in 2D measurement-based quantum computation.
*npj Quantum Information*,*2*, 16036. - Miyake, A. (2010). Quantum computation on the edge of a symmetry-protected topological order.
*Physical Review Letters*,*105*(4), 040501. - Miyake, A. (2011). Quantum computational capability of a 2D valence bond solid phase.
*Annals of Physics*,*326*, 1656–1671. - Mooney, G. J., Hill, C. D., & Hollenberg, L. C. (2019). Entanglement in a 20-qubit superconducting quantum computer.
*Scientific Reports*,*9*, 13465. - Morimae, T. (2017). Finding resource states of measurement-based quantum computing is harder than quantum computing.
*Physical Review A*,*96*(5), 052308. - Nayak, C., Simon, S. H., Stern, A., Freedman, M., & Sarma, S. D. (2008). Non-Abelian anyons and topological quantum computation.
*Reviews of Modern Physics*,*80*, 1083. - Nielsen, M. A. (2003). Quantum computation by measurement and quantum memory.
*Physics Letters A*,*308*(2–3), 96–100. - Nielsen, M. A. (2004). Optical quantum computation using cluster states.
*Physical Review Letters*,*93*(4), 040503. - Nielsen, M. A. (2006). Cluster-state quantum computation.
*Reports on Mathematical Physics*,*57*(1), 147–161. - Nielsen, M. A., & Chuang, I. (2002).
*Quantum computation and quantum information*. American Association of Physics Teachers. - Nielsen, M. A., & Chuang, I. L. (1997). Programmable quantum gate arrays.
*Physical Review Letters*,*79*, 321–324. - Nielsen, M. A., & Dawson, C. M. (2005). Fault-tolerant quantum computation with cluster states.
*Physical Review A*,*71*(4), 042323. - Pan, J.-W., Bouwmeester, D., Weinfurter, H., & Zeilinger, A. (1998). Experimental entanglement swapping: Entangling photons that never interacted.
*Physical Review Letters*,*80*, 3891–3894. - Perdrix, S. (2005). State transfer instead of teleportation in measurement-based quantum computation.
*International Journal of Quantum Information*,*3*(01), 219–223. - Perdrix, S., & Jorrand, P. (2004). Measurement-based quantum Turing machines and their universality. [ArXiv:0404146 [quant-ph]].
- Perez-Garcia, D., Verstraete, F., Wolf, M., & Cirac, J. (2007). Matrix product state representations.
*Quantum Information and Computation*,*7*, 401. - Pirker, A., Wallnöfer, J., & Dür, W. (2018). Modular architectures for quantum networks.
*New Journal of Physics*,*20*, 053054. - Pollmann, F., Berg, E., Turner, A. M., & Oshikawa, M. (2012). Symmetry protection of topological phases in one-dimensional quantum spin systems.
*Physical Review B*,*85*(7), 075125. - Pomata, N., & Wei, T.-C. (2020). Demonstrating the Affleck-Kennedy-Lieb-Tasaki spectral gap on 2D degree-3 lattices.
*Physical Review Letters*,*124*(7), 177203. - Poulsen Nautrup, H., & Wei, T.-C. (2015). Symmetry-protected topologically ordered states for universal quantum computation.
*Physical Review A*,*92*(5), 052309. - Prakash, A., & Wei, T.-C. (2015). Ground states of one-dimensional symmetry-protected topological phases and their utility as resource states for quantum computation.
*Physical Review A*,*92*(2), 022310. - Raussendorf, R. (2003).
*Measurement-based quantum computation with cluster states*[Doctoral dissertation, Ludwig-Maximilians-University, Munich, Germany]. LMU Elektronische Hochschulschriften. - Raussendorf, R. (2013). Contextuality in measurement-based quantum computation.
*Physical Review A*,*88*(2), 022322. - Raussendorf, R., & Briegel, H. (2002). Computational model underlying the one-way quantum computer.
*Quantum Information and Computation*,*6*, 433. - Raussendorf, R., & Briegel, H. J. (2001). A one-way quantum computer.
*Physical Review Letters*,*86*(22), 5188. - Raussendorf, R., Browne, D. E., & Briegel, H. J. (2003). Measurement-based quantum computation on cluster states.
*Physical Review A*,*68*(2), 022312. - Raussendorf, R., & Harrington, J. (2007). Fault-tolerant quantum computation with high threshold in two dimensions.
*Physical Review Letters*,*98*(19), 190504. - Raussendorf, R., Harrington, J., & Goyal, K. (2006). A fault-tolerant one-way quantum computer.
*Annals of Physics*,*321*, 2242–2270. - Raussendorf, R., Harrington, J., & Goyal, K. (2007). Topological fault-tolerance in cluster state quantum computation.
*New Journal of Physics*,*9*, 199. - Raussendorf, R., Okay, C., Wang, D.-S., Stephen, D. T., & Poulsen Nautrup, H. (2019). Computationally universal phase of quantum matter.
*Physical Review Letters*,*122*(9), 090501. - Raussendorf, R., Sarvepalli, P., Wei, T.-C., & Haghnegahdar, P. (2016). Symmetry constraints on temporal order in measurement-based quantum computation.
*Information and Computation*,*250*, 115–138. - Sangouard, N., Simon, C., De Riedmatten, H., & Gisin, N. (2011). Quantum repeaters based on atomic ensembles and linear optics.
*Reviews of Modern Physics*,*83*, 33. - Schwartz, I., Cogan, D., Schmidgall, E. R., Don, Y., Gantz, L., Kenneth, O., Lindner, N. H., & Gershoni, D. (2016). Deterministic generation of a cluster state of entangled photons.
*Science*,*354*, 434–437. - Sherson, J. F., Weitenberg, C., Endres, M., Cheneau, M., Bloch, I., & Kuhr, S. (2010). Single-atom-resolved fluorescence imaging of an atomic Mott insulator.
*Nature*,*467*, 68–72. - Shor, P. W. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. In
*Proceedings 35th Annual Symposium on Foundations of Computer Science*(pp. 124–134). IEEE. - Simon, J., Bakr, W. S., Ma, R., Tai, M. E., Preiss, P. M., & Greiner, M. (2011). Quantum simulation of antiferromagnetic spin chains in an optical lattice.
*Nature*,*472*, 307–312. - Stephen, D. T., Wang, D.-S., Prakash, A., Wei, T.-C., & Raussendorf, R. (2017). Computational power of symmetry-protected topological phases.
*Physical Review Letters*,*119*(1), 010504. - Susskind, L., & Friedman, A. (2014).
*Quantum mechanics: The theoretical minimum*. Basic Books. - Takeuchi, Y., Morimae, T., & Hayashi, M. (2019). Quantum computational universality of hypergraph states with Pauli-X and Z basis measurements.
*Scientific Reports*,*9*, 13585. - Tanamoto, T., Liu, Y., Fujita, S., Hu, X., & Nori, F. (2006). Producing cluster states in charge qubits and flux qubits.
*Physical Review Letters*,*97*(23), 230501. - Tanamoto, T., Liu, Y., Hu, X., & Nori, F. (2009). Efficient quantum circuits for one-way quantum computing.
*Physical Review Letters*,*102*(10), 100501. - Urban, E., Johnson, T. A., Henage, T., Isenhower, L., Yavuz, D., Walker, T., & Saffman, M. (2009). Observation of Rydberg blockade between two atoms.
*Nature Physics*,*5*, 110–114. - Van den Nest, M. (2013). Universal quantum computation with little entanglement.
*Physical Review Letters*,*110*(6), 060504. - Van den Nest, M., & Briegel, H. J. (2008). Measurement-based quantum computation and undecidable logic.
*Foundations of Physics*,*38*, 448–457. - Van den Nest, M., Dür, W., & Briegel, H. J. (2007). Classical spin models and the quantum-stabilizer formalism.
*Physical Review Letters*,*98*(11), 117207. - Van den Nest, M., Dür, W., & Briegel, H. J. (2008). Completeness of the classical 2D Ising model and universal quantum computation.
*Physical Review Letters*,*100*(11), 110501. - Van den Nest, M., Dür, W., Vidal, G., & Briegel, H. J. (2007). Classical simulation versus universality in measurement-based quantum computation.
*Physical Review A*,*75*(1), 012337. - Van den Nest, M., Miyake, A., Dür, W., & Briegel, H. J. (2006). Universal resources for measurement-based quantum computation.
*Physical Review Letters*,*97*(15), 150504. - Verstraete, F., & Cirac, J. I. (2004a). Renormalization algorithms for quantum-many body systems in two and higher dimensions. [ArXiv:0407066 [cond-mat]].
- Verstraete, F., & Cirac, J. I. (2004b). Valence-bond states for quantum computation.
*Physical Review A*,*70*(6), 060302(R). - Vidal, G. (2003). Efficient classical simulation of slightly entangled quantum computations.
*Physical Review Letters*,*91*(14), 147902. - Wallnöfer, J., & Dür, W. (2017). Measurement-based quantum communication with resource states generated by entanglement purification.
*Physical Review A*,*95*(1), 012303. - Walther, P., Resch, K. J., Rudolph, T., Schenck, E., Weinfurter, H., Vedral, V., Aspelmeyer, M., & Zeilinger, A. (2005). Experimental one-way quantum computing.
*Nature*,*434*, 169–176. - Wang, Y., Li, Y., Yin, Z., & Zeng, B. (2018). 16-qubit IBM universal quantum computer can be fully entangled.
*npj Quantum Information*,*4*, 46. - Wei, T.-C. (2013). Quantum computational universality of Affleck-Kennedy-Lieb-Tasaki states beyond the honeycomb lattice.
*Physical Review A*,*88*(6), 062307. - Wei, T.-C. (2018). Quantum spin models for measurement-based quantum computation.
*Advances in Physics: X*,*3*(1), 1461026. - Wei, T.-C., Affleck, I., & Raussendorf, R. (2011). Affleck-Kennedy-Lieb-Tasaki state on a honeycomb lattice is a universal quantum computational resource.
*Physical Review Letters*,*106*(7), 070501. - Wei, T.-C., Affleck, I., & Raussendorf, R. (2012). Two-dimensional Affleck-Kennedy-Lieb-Tasaki state on the honeycomb lattice is a universal resource for quantum computation.
*Physical Review A*,*86*(3), 032328. - Wei, T.-C., Haghnegahdar, P., & Raussendorf, R. (2014). Hybrid valence-bond states for universal quantum computation.
*Physical Review A*,*90*(4), 042333. - Wei, T.-C., & Huang, C.-Y. (2017). Universal measurement-based quantum computation in two-dimensional symmetry-protected topological phases.
*Physical Review A*,*96*(3), 032317. - Wei, T.-C., Li, Y., & Kwek, L. C. (2014). Transitions in the quantum computational power.
*Physical Review A*,*89*(5), 052315. - Wei, T.-C., & Raussendorf, R. (2015). Universal measurement-based quantum computation with spin-2 Affleck-Kennedy-Lieb-Tasaki states.
*Physical Review A*,*92*(1), 012310. - Weinstein, Y. S., Hellberg, C. S., & Levy, J. (2005). Quantum-dot cluster-state computing with encoded qubits.
*Physical Review A*,*72*(2), 020304. - Weiss, D. S., & Saffman, M. (2017). Quantum computing with neutral atoms.
*Physics Today*,*70*(7), 44. - Weitenberg, C., Endres, M., Sherson, J. F., Cheneau, M., Schauß, P., Fukuhara, T., Bloch, I., & Kuhr, S. (2011). Single-spin addressing in an atomic Mott insulator.
*Nature*,*471*, 319–324. - Wilk, T., Gaëtan, A., Evellin, C., Wolters, J., Miroshnychenko, Y., Grangier, P., & Browaeys, A. (2010). Entanglement of two individual neutral atoms using Rydberg blockade.
*Physical Review Letters*,*104*(1), 010502. - Yokoyama, S., Ukai, R., Armstrong, S. C., Sornphiphatphong, C., Kaji, T., Suzuki, S., Yoshikawa, J., Yonezawa, H., Menicucci, N. C., & Furusawa, A. (2013). Ultra-large-scale continuous-variable cluster states multiplexed in the time domain.
*Nature Photonics*,*7*, 982. - Yoshida, B. (2016). Topological phases with generalized global symmetries.
*Physical Review B*,*93*(15), 155131. - Yoshikawa, J., Yokoyama, S., Kaji, T., Sornphiphatphong, C., Shiozawa, Y., Makino, K., & Furusawa, A. (2016). Invited article: Generation of one-million-mode continuous-variable cluster state by unlimited time-domain multiplexing.
*APL Photonics*,*1*(6), 060801. - Zhang, X., Isenhower, L., Gill, A., Walker, T., & Saffman, M. (2010). Deterministic entanglement of two neutral atoms via Rydberg blockade.
*Physical Review A*,*82*(3), 030306. - Zhou, X., Leung, D. W., & Chuang, I. L. (2000). Methodology for quantum logic gate construction.
*Physical Review A*,*62*(5), 052316. - Zwerger, M., Briegel, H., & Dür, W. (2013). Universal and optimal error thresholds for measurement-based entanglement purification.
*Physical Review Letters*,*110*(26), 260503. - Zwerger, M., Briegel, H., & Dür, W. (2014). Robustness of hashing protocols for entanglement purification.
*Physical Review A*,*90*(1), 012314. - Zwerger, M., Briegel, H., & Dür, W. (2016). Measurement-based quantum communication.
*Applied Physics B*,*122*(3), 50. - Zwerger, M., Dür, W., & Briegel, H. (2012). Measurement-based quantum repeaters.
*Physical Review A*,*85*(6), 062326. - Zwerger, M., Pirker, A., Dunjko, V., Briegel, H. J., & Dür, W. (2018). Long-range big quantum-data transmission.
*Physical Review Letters*,*120*(3), 030503.