Measurement-Based Quantum Computing

In the circuit model you build a computation by doing things to qubits — firing gate after gate, weaving entanglement as you go. Measurement-based quantum computing (MBQC) turns that picture inside out. First you lay down one enormous, fixed sheet of entanglement — a cluster state — before the program even starts. Then you compute by doing the one thing the circuit model saves for last: you measure, one qubit at a time, in cleverly chosen directions. No gates run during the computation at all. Discovered by Raussendorf and Briegel in 2001, this is the one-way quantum computer, and — astonishingly — it is exactly as powerful as the circuit model.

The recipe: entangle first, then measure

MBQC splits every computation into two clean phases:

  1. Prepare the resource. Take a big lattice of qubits, put every one into the state |{+}\rangle = \tfrac{1}{\sqrt2}(|0\rangle + |1\rangle), and apply a controlled-Z gate between every pair of neighbours. This one-off step spends all the entanglement up front and produces a fixed, problem-independent cluster state.
  2. Drive with measurements. Now sweep across the lattice performing single-qubit measurements. The direction (basis angle) you measure each qubit in is the program. Crucially the angles are adaptive: each choice depends on the random outcomes you have already seen — a classical feed-forward loop running alongside the quantum hardware.

That is the whole machine. During phase 2 there are no two-qubit gates — the entanglement was all made in phase 1, and measurement gradually consumes it. Because measurement is irreversible, the resource is used up as you go and can never be rewound: hence one-way.

What a cluster state is, precisely

A graph state (a cluster state is the special case on a regular lattice) is defined by a graph G=(V,E): put a qubit on every vertex, initialise each to |{+}\rangle, and apply a controlled-Z along every edge:

|G\rangle \;=\; \Bigg(\prod_{(i,j)\in E} \mathrm{CZ}_{ij}\Bigg)\, |{+}\rangle^{\otimes |V|}.

The controlled-Z gate is symmetric and diagonal — it just flips the sign of the |11\rangle amplitude:

\mathrm{CZ} \;=\; \begin{pmatrix} 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&-1 \end{pmatrix}, \qquad \mathrm{CZ}\,|{+}{+}\rangle = \tfrac12\big(|00\rangle+|01\rangle+|10\rangle-|11\rangle\big).

All the \mathrm{CZ}s commute (they are diagonal), so the order of edges does not matter — the resource depends only on the graph, not on how you built it.

The computation flows across the sheet

Picture the lattice as a fabric of entanglement. Measuring the leftmost column does not destroy the computation — it pushes the logical information one step to the right, into the still-entangled remainder, while imprinting a chosen operation on it. Column by column, the answer marches across the sheet until it lands on the final, unmeasured column. Step through it:

The graph chosen for the resource, together with the pattern of measurement angles, is what encodes a particular algorithm.

Worked example 1: one measurement = one gate

Here is the primitive that makes the whole model tick. Take a data qubit in an unknown state |\psi\rangle = a|0\rangle + b|1\rangle and a fresh resource qubit in |{+}\rangle. Entangle them with one controlled-Z:

\mathrm{CZ}\,\big(|\psi\rangle \otimes |{+}\rangle\big) = \tfrac{1}{\sqrt2}\Big[\,a|0\rangle\big(|0\rangle+|1\rangle\big) + b|1\rangle\big(|0\rangle-|1\rangle\big)\Big].

Now measure the first qubit in the tilted basis |{\pm_\varphi}\rangle = \tfrac{1}{\sqrt2}\big(|0\rangle \pm e^{-i\varphi}|1\rangle\big), getting outcome s\in\{0,1\} (the + result is s=0). Projecting and normalising, the second qubit is left in

|\psi_{\text{out}}\rangle \;=\; X^{s}\, H\, R_z(\varphi)\, |\psi\rangle, \qquad R_z(\varphi) = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\varphi} \end{pmatrix}.

Read what just happened. The data teleported one node to the right, and in transit it was rotated by the single-qubit gate H\,R_z(\varphi) — and you picked \varphi by choosing the measurement angle. One measurement, one programmable gate. The only blemish is the random Pauli byproduct X^{s}: half the time (s=1) an extra X is stuck on the front, entirely determined by the coin-flip outcome. This is a close cousin of quantum teleportation — MBQC is teleportation harnessed to compute.

Worked example 2: a concrete rotation and its byproduct

Let us feed a definite state through the primitive. Take |\psi\rangle = |{+}\rangle (so a=b=\tfrac{1}{\sqrt2}) and measure the first qubit in the plain X basis, i.e. angle \varphi = 0 so |{\pm_\varphi}\rangle = |{\pm}\rangle. The two-qubit cluster is

\mathrm{CZ}\,|{+}{+}\rangle = \tfrac12\big(|00\rangle + |01\rangle + |10\rangle - |11\rangle\big).

Plug \varphi=0 into the general result. With R_z(0)=I we get output X^{s}H|{+}\rangle = X^{s}|0\rangle:

s=0:\ \ |\psi_{\text{out}}\rangle = |0\rangle, \qquad\qquad s=1:\ \ |\psi_{\text{out}}\rangle = X|0\rangle = |1\rangle.

Each outcome occurs with probability \tfrac12. Notice the two jobs the single measurement did at once: it rotated the logical state by H (the chosen gate for \varphi=0) and transferred it to the next qubit — but it also injected a random X byproduct that flips the answer between |0\rangle and |1\rangle. To build a longer gate sequence, the next qubit's measurement angle is flipped to (-1)^{s}\varphi to pre-compensate for that known byproduct. That angle-flip is the adaptive feed-forward: later bases genuinely depend on earlier outcomes.

Just as powerful as a circuit — and made for photons

MBQC is not a curiosity or a weaker relative of the circuit model. It is polynomially equivalent to it: any quantum circuit on n qubits can be compiled into a cluster state (of size polynomial in the circuit's) plus a fixed measurement pattern, and vice versa. Universality is inherited entirely from the resource state and the choice of measurement angles — a suitable graph plus adaptive single-qubit measurements reproduces any universal gate set.

Why does anyone care about a second, harder-to-picture model? Because it matches hardware. On photonic platforms, deterministic two-qubit entangling gates are notoriously difficult, but generating entangled resource states offline and performing fast single-qubit measurements is comparatively easy. MBQC plays exactly to those strengths — build the cluster once, then compute with measurements — which is why it is the leading paradigm for photonic quantum computing. More broadly, it cleanly separates the two ingredients of quantum computation: entanglement is the pre-made resource, and measurement is the driver.

The one-way computer runs on a strange kind of thrift. You begin by weaving a single, expensive sheet of entanglement — a cluster state you will never mend or reuse — and then you compute by tearing pieces off it, one measurement at a time. Every measurement is a tiny act of demolition: it collapses that qubit forever, but in doing so it nudges the whole computation one step forward, printing your chosen rotation onto the survivors. By the time the answer emerges on the far edge, the sheet is gone. It is the opposite of the reversible, gate-by-gate circuit picture: here the computation is what remains as the resource is consumed, like a sculpture that appears only as the marble is chipped away.

Two traps. First, do not read "computing by measurement" as some cheap, measurement-only magic that must be weaker than a real gate-based machine — MBQC is exactly as powerful as the circuit model, provably equivalent up to polynomial overhead. Its power is not conjured from nothing: it is banked in the entanglement of the cluster state, all of which is created up front before a single measurement. Second — and this is the subtle one — the measurements are not a fixed script. They must be adaptive: because every measurement leaves a random Pauli byproduct, the angle of each later measurement has to be adjusted based on the outcomes already seen (classical feed-forward). Strip out the adaptivity and measure every qubit in a pre-set basis, and the byproducts never cancel — you get a random mess, not a computation.