Simple Algorithm
Quantum Computing · Rydberg State · 30 min

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 Ka=Xa∏b∈N(a)ZbK_a = X_a\prod_{b\in N(a)}Z_b.
  • Derive the elementary step: measuring at angle θ\theta teleports XmJ(−θ)X^mJ(-\theta) 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 ∣G⟩\ket{G} 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 1−2−31-2-3. What happens if you apply HH to qubits 1 and 3?

K1=X1Z2K_1 = X_1Z_2, K2=Z1X2Z3K_2 = Z_1X_2Z_3, K3=Z2X3K_3 = Z_2X_3. Conjugating by H1H3H_1H_3 gives Z1Z2Z_1Z_2, X1X2X3X_1X_2X_3, Z2Z3Z_2Z_3: 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

DerivationTeleporting a gate through one bond
  1. ∣ψ⟩1∣+⟩2 → CZ12  a∣0⟩∣+⟩+b∣1⟩∣−⟩,∣ψ⟩=a∣0⟩+b∣1⟩\ket\psi_1\ket{+}_2\ \xrightarrow{\ \mathrm{CZ}_{12}\ }\ a\ket0\ket+ + b\ket1\ket-,\qquad\ket\psi = a\ket0+b\ket1

    Qubit 1 holds the input; qubit 2 is a fresh cluster qubit.

  2. ∣±θ⟩=12(∣0⟩±eiθ∣1⟩)\ket{\pm_\theta} = \tfrac{1}{\sqrt2}\big(\ket0\pm e^{i\theta}\ket1\big)

    Measure qubit 1 in this basis on the equator of the Bloch sphere; outcome m=0m=0 for ++ and m=1m=1 for −-.

  3. (⟨±θ∣⊗I)(a∣0⟩∣+⟩+b∣1⟩∣−⟩)=12(a∣+⟩±e−iθb∣−⟩)\big(\bra{\pm_\theta}\otimes\id\big)\big(a\ket0\ket+ + b\ket1\ket-\big) = \tfrac{1}{\sqrt2}\big(a\ket+\pm e^{-i\theta}b\ket-\big)

    Project qubit 1.

  4. =12 H(a∣0⟩±e−iθb∣1⟩)=12 Xm J(−θ)∣ψ⟩,J(α):=HP(α)= \tfrac{1}{\sqrt2}\,H\big(a\ket0\pm e^{-i\theta}b\ket1\big) = \tfrac{1}{\sqrt2}\,X^{m}\,J(-\theta)\ket\psi,\qquad J(\alpha) := HP(\alpha)

    Using a∣+⟩±c∣−⟩=H(a∣0⟩±c∣1⟩)a\ket+\pm c\ket- = H(a\ket0\pm c\ket1), HZ=XHHZ=XH and P(α)=diag⁡(1,eiα)P(\alpha)=\diag(1,e^{i\alpha}). Each outcome has probability 12\tfrac12.

  5. The logical state hops from qubit 1 to qubit 2 (a one-bit teleportation), transformed by J(−θ)J(-\theta), up to a known Pauli byproduct XmX^m. Measuring at angle −α-\alpha therefore implements J(α)J(\alpha).

DerivationByproducts and adaptive angles
  1. J(α) X=eiα Z J(−α),J(α) Z=X J(α)J(\alpha)\,X = e^{i\alpha}\,Z\,J(-\alpha),\qquad J(\alpha)\,Z = X\,J(\alpha)

    Pushing a byproduct through the next step, from P(α)X=eiαXP(−α)P(\alpha)X = e^{i\alpha}XP(-\alpha) and HX=ZHHX = ZH.

  2. J(−α) X∣ϕ⟩=e−iα Z J(α)∣ϕ⟩J(-\alpha)\,X\ket\phi = e^{-i\alpha}\,Z\,J(\alpha)\ket\phi

    To apply J(α)J(\alpha) to a state carrying an XX byproduct, implement J(−α)J(-\alpha) instead, i.e. measure at +α+\alpha rather than −α-\alpha. The byproduct becomes ZZ; a ZZ byproduct simply becomes XX. Outcomes thus feed forward into the bases of later measurements.

  3. J(0) J(α) J(β) J(γ)∝Rz(α) Rx(β) Rz(γ)J(0)\,J(\alpha)\,J(\beta)\,J(\gamma)\propto R_z(\alpha)\,R_x(\beta)\,R_z(\gamma)

    Since P(φ)∝Rz(φ)P(\varphi)\propto R_z(\varphi) and HP(φ)H∝Rx(φ)HP(\varphi)H\propto R_x(\varphi): 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 ZZ measurements, which delete a vertex from the graph up to Pauli byproducts on its neighbors.

Check your understanding

Measuring qubit 1 of a chain left an XX byproduct. The next step should implement J(π/4)J(\pi/4). At what angle do you measure qubit 2?

  1. −π/4-\pi/4, as without a byproduct
  2. +π/4+\pi/4
  3. −π/4+π-\pi/4+\pi
  4. 00, then correct afterwards
Show the answer

B. +π/4+\pi/4

Measuring at θ\theta implements J(−θ)J(-\theta), and J(−θ)X=e−iθZJ(θ)J(-\theta)X = e^{-i\theta}ZJ(\theta). Measuring at +π/4+\pi/4 therefore applies the intended J(π/4)J(\pi/4), followed by a harmless ZZ byproduct that passes on as an XX.

Resources, fault tolerance and the frontier

Resource stateUniversal for MBQC?Why
1D clusterNoA matrix-product state of bond dimension 2; it only transports one logical qubit and is efficiently simulable.
2D cluster (square, hexagonal, triangular…)YesRaussendorf–Briegel; universality holds for many 2D lattices (Van den Nest et al. 2006).
GHZ stateNoBounded entanglement width; yet with parity-only side-processing it computes nonlinear Boolean functions (Anders & Browne 2009).
Typical Haar-random statesNo"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 statesYes, in many casesValence-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 π/4\pi/4 and random π\pi flips (Broadbent, Fitzsimons & Kashefi 2009).

Key takeaways

  • Graph states ∏CZ∣+⟩⊗V\prod\mathrm{CZ}\ket{+}^{\otimes V} are stabilized by Ka=Xa∏b∈N(a)ZbK_a = X_a\prod_{b\in N(a)}Z_b and are prepared by constant-depth Clifford circuits.
  • Measuring one qubit of a bond at angle θ\theta teleports XmJ(−θ)X^mJ(-\theta) 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.

Question 1

For the star graph with center cc and leaves 1,2,31,2,3, which operator stabilizes ∣G⟩\ket{G}?

  1. XcZ1Z2Z3X_cZ_1Z_2Z_3
  2. XcX1X2X3X_cX_1X_2X_3
  3. Z1Z2Z3Z_1Z_2Z_3
  4. ZcZ1Z_cZ_1
Show the answer

A. XcZ1Z2Z3X_cZ_1Z_2Z_3

Kc=Xc∏b∈N(c)ZbK_c = X_c\prod_{b\in N(c)}Z_b, and all three leaves are neighbors of the center. The others are not in the stabilizer group: the XX-part of a product ∏aKaea\prod_aK_a^{e_a} is ∏aXaea\prod_aX_a^{e_a}, which fixes the exponents and hence the whole operator, and none of the other choices comes out.

Question 2

Measuring qubit 1 of the bond 1−21-2 at angle θ\theta with outcome mm leaves qubit 2 in

  1. P(θ)∣ψ⟩P(\theta)\ket\psi
  2. Zm∣ψ⟩Z^m\ket\psi
  3. Xm HP(−θ)∣ψ⟩X^m\,HP(-\theta)\ket\psi
  4. a mixed state, because the measurement destroyed the information
Show the answer

C. Xm HP(−θ)∣ψ⟩X^m\,HP(-\theta)\ket\psi

The CZ bond and the equatorial measurement teleport J(−θ)=HP(−θ)J(-\theta) = HP(-\theta), up to the byproduct XmX^m that later steps account for.

Question 3

Why can all Pauli measurements of an MBQC pattern be performed in the first round?

  1. Pauli measurements do not disturb the state
  2. They are only ever performed on output qubits
  3. Pauli measurements always give outcome +1+1
  4. 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 θ→−θ\theta\to-\theta; for θ∈{0,±π/2}\theta\in\{0,\pm\pi/2\}, or the ZZ basis, that is the same measurement with at most relabeled outcomes. Only non-Pauli angles must wait for earlier results.

Question 4

Which resource state is universal for measurement-based quantum computing?

  1. A long 1D cluster state
  2. The 2D square-lattice cluster state
  3. A large GHZ state
  4. 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).