Measurement-Based Quantum Computing
Computing by measuring a cluster state.
What if a computation applied no gates at all? Prepare one fixed, highly entangled cluster state, then only measure single qubits, choosing each angle from earlier outcomes. Raussendorf and Briegel showed this "one-way" model is universal, and it now underlies photonic and fusion-based architectures.
What you’ll learn
- Define graph and cluster states, and prove that they are stabilized by .
- Derive the elementary step: measuring at angle teleports along a bond, and work out how byproducts force adaptive angles.
- Explain the universality of the 2D cluster state, the role of flow and gflow in determinism, and why Clifford parts need no adaptivity.
- Discuss what makes a resource state universal, and how MBQC enables fault tolerance, photonic fusion and blind computing.
Graph states
Preparing is a constant-depth Clifford circuit for bounded-degree graphs: edge-color the graph and apply one round of CZs per color (the square lattice needs 4). All the genuinely quantum work happens later, in the measurements.
Think first Write the stabilizers of the 3-qubit line . What happens if you apply to qubits 1 and 3?
, , . Conjugating by gives , , : the GHZ state. (If you did the Gottesman–Knill deep dive, you built this cluster state there.) Graph states are equivalent to one another, and to states like GHZ, under local Cliffords far more often than their pictures suggest.
One step of the one-way computer
Qubit 1 holds the input; qubit 2 is a fresh cluster qubit.
Measure qubit 1 in this basis on the equator of the Bloch sphere; outcome for and for .
Project qubit 1.
Using , and . Each outcome has probability .
The logical state hops from qubit 1 to qubit 2 (a one-bit teleportation), transformed by , up to a known Pauli byproduct . Measuring at angle therefore implements .
Pushing a byproduct through the next step, from and .
To apply to a state carrying an byproduct, implement instead, i.e. measure at rather than . The byproduct becomes ; a byproduct simply becomes . Outcomes thus feed forward into the bases of later measurements.
Since and : four measurements along a 5-qubit line implement an arbitrary single-qubit unitary, by Euler angles.
Universality, flow and the Clifford shortcut
On a 2D cluster, horizontal lines carry logical qubits through such single-qubit steps, and suitably measured vertical bonds between lines implement CZ gates between them. Unneeded cluster qubits are removed by measurements, which delete a vertex from the graph up to Pauli byproducts on its neighbors.
Measuring qubit 1 of a chain left an byproduct. The next step should implement . At what angle do you measure qubit 2?
- , as without a byproduct
- , then correct afterwards
Show the answer
B.
Measuring at implements , and . Measuring at therefore applies the intended , followed by a harmless byproduct that passes on as an .
Resources, fault tolerance and the frontier
| Resource state | Universal for MBQC? | Why |
|---|---|---|
| 1D cluster | No | A matrix-product state of bond dimension 2; it only transports one logical qubit and is efficiently simulable. |
| 2D cluster (square, hexagonal, triangular…) | Yes | Raussendorf–Briegel; universality holds for many 2D lattices (Van den Nest et al. 2006). |
| GHZ state | No | Bounded entanglement width; yet with parity-only side-processing it computes nonlinear Boolean functions (Anders & Browne 2009). |
| Typical Haar-random states | No | "Too entangled to be useful": outcomes are so random that classical coin flips do as well (Gross, Flammia & Eisert 2009; Bremner, Mora & Winter 2009). |
| 2D AKLT and certain SPT ground states | Yes, in many cases | Valence-bond and symmetry-protected phases can be universal resources (Wei, Affleck & Raussendorf 2011; Miyake 2011; Raussendorf et al. 2019). |
Fault tolerance. Raussendorf, Harrington and Goyal embedded the surface code in a 3D cluster state: measuring it layer by layer performs topologically protected computation, with an error threshold of order a percent. Photonics. Photons are hard to entangle deterministically but easy to measure, so photonic architectures stitch small entangled resource states together with probabilistic fusion measurements (fusion-based quantum computing, Bartolucci et al. 2023), letting the error-correcting structure absorb photon loss and fusion failures.
Blind computing. The computation is encoded in the measurement angles, so a client can hide it from the server: angles are masked with random offsets that are multiples of and random flips (Broadbent, Fitzsimons & Kashefi 2009).
Key takeaways
- Graph states are stabilized by and are prepared by constant-depth Clifford circuits.
- Measuring one qubit of a bond at angle teleports to its neighbor; byproducts force later angles to change sign.
- The 2D cluster state is universal; flow and gflow guarantee determinism, and all Pauli (Clifford) measurements can be done in the first round.
- Both too little and too much entanglement make a resource useless; MBQC underpins topological fault tolerance, fusion-based photonics and blind computing.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
For the star graph with center and leaves , which operator stabilizes ?
Show the answer
A.
, and all three leaves are neighbors of the center. The others are not in the stabilizer group: the -part of a product is , which fixes the exponents and hence the whole operator, and none of the other choices comes out.
Measuring qubit 1 of the bond at angle with outcome leaves qubit 2 in
- a mixed state, because the measurement destroyed the information
Show the answer
C.
The CZ bond and the equatorial measurement teleport , up to the byproduct that later steps account for.
Why can all Pauli measurements of an MBQC pattern be performed in the first round?
- Pauli measurements do not disturb the state
- They are only ever performed on output qubits
- Pauli measurements always give outcome
- Byproduct-induced sign flips leave their bases unchanged (up to relabeling outcomes), so they need no feed-forward
Show the answer
D. Byproduct-induced sign flips leave their bases unchanged (up to relabeling outcomes), so they need no feed-forward
Adaptivity means flipping ; for , or the basis, that is the same measurement with at most relabeled outcomes. Only non-Pauli angles must wait for earlier results.
Which resource state is universal for measurement-based quantum computing?
- A long 1D cluster state
- The 2D square-lattice cluster state
- A large GHZ state
- A typical Haar-random many-qubit state
Show the answer
B. The 2D square-lattice cluster state
The 2D cluster state is the canonical universal resource (Raussendorf–Briegel). 1D clusters and GHZ states have bounded entanglement width, and typical random states are too entangled to be useful.
Further reading
- R. Raussendorf & H. J. Briegel, "A one-way quantum computer", Phys. Rev. Lett. 86, 5188 (2001).
- R. Raussendorf, D. E. Browne & H. J. Briegel, "Measurement-based quantum computation on cluster states", Phys. Rev. A 68, 022312 (2003).
- H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf & M. Van den Nest, "Measurement-based quantum computation", Nature Physics 5, 19 (2009).
- D. E. Browne, E. Kashefi, M. Mhalla & S. Perdrix, "Generalized flow and determinism in measurement-based quantum computation", New J. Phys. 9, 250 (2007).
- A. Broadbent, J. Fitzsimons & E. Kashefi, "Universal blind quantum computation", Proc. FOCS (2009).