Measurement-based quantum computation changes the architecture of a quantum algorithm. Instead of applying a long sequence of gates directly to data qubits, first prepare a highly entangled graph state. Then consume that resource one qubit at a time through single-qubit measurements. The algorithm lives largely in the choice, order and adaptivity of those measurements.
Guide 43 owns continuous-variable cluster computation. This guide owns the qubit version: graph states built from controlled-Z edges, stabilizer relations, one-bit teleportation, measurement-induced gates, Pauli byproducts, classical feed-forward and graph-theoretic conditions such as flow and gflow that guarantee determinism.
The striking idea is that measurement—normally treated as the end of a quantum computation—can itself become the engine of the computation when the entanglement resource is prepared in advance.
Prepare graph state → inject logical input → measure local bases → update classical Pauli frame → adapt later bases → leave output qubits carrying the computed state.
1. Graph states
Let G=(V,E) be a simple graph. Associate one qubit with each vertex.
Prepare every qubit in
|+⟩=(|0⟩+|1⟩)/√2.
For every edge (u,v), apply a controlled-Z gate
CZ=diag(1,1,1,−1).
The resulting graph state is
|G⟩=∏_{(u,v)∈E}CZ_{uv}|+⟩^{⊗|V|}.
2. Graph-state stabilizers
For each vertex v, define
K_v=X_v∏_{u∈N(v)} Z_u
where N(v) is the neighbourhood of v.
The graph state satisfies
K_v|G⟩=|G⟩
for every vertex.
These commuting stabilizers encode the graph entirely. The graph and stabilizer descriptions are two views of the same state.
3. Derive one stabilizer
Before entangling, |+⟩⊗n is stabilised by Xv on each site.
Conjugating Xv through a CZ on edge (v,u) gives
CZ_{vu} X_v CZ_{vu}=X_v Z_u.
Conjugate through all CZ edges incident on v and Xv acquires one Z on every neighbour. Thus
X_v→X_v∏_{u∈N(v)}Z_u=K_v.
4. Linear cluster state
A one-dimensional chain 1—2—…—n is a linear cluster state.
Interior stabilizers are
K_j=Z_{j−1}X_jZ_{j+1}.
The two end stabilizers have only one neighbouring Z.
A chain can teleport quantum information while applying single-qubit gates through measurement choices.
5. One-bit teleportation primitive
Take input |ψ⟩ on qubit 1 and |+⟩ on qubit 2.
Apply CZ12, then measure qubit 1 in the X basis.
If outcome m∈{0,1} labels |+⟩ and |−⟩, qubit 2 becomes
X^m H|ψ⟩
up to an overall phase.
The state has been teleported one edge and a Hadamard gate has been applied, with a measurement-dependent Pauli X byproduct.
6. Worked one-bit teleportation
Let |ψ⟩=α|0⟩+β|1⟩.
After CZ with |+⟩, the joint state is
[α|0⟩(|0⟩+|1⟩)+β|1⟩(|0⟩−|1⟩)]/√2.
Project qubit 1 onto |+⟩:
α(|0⟩+|1⟩)+β(|0⟩−|1⟩)
which is proportional to H|ψ⟩.
Project onto |−⟩ and the result is XH|ψ⟩.
7. Equatorial measurement basis
Define
|±_α⟩=(|0⟩±e^{iα}|1⟩)/√2.
Measuring the first qubit in this basis after CZ teleports the input while applying, up to convention and global phase,
X^m H R_z(−α)|ψ⟩.
Some references define the basis with e−iα, which flips the sign of the displayed rotation angle. The measurement convention and gate identity must be stated together.
8. Measurement becomes a programmable gate
The entangling resource can be fixed while the measurement angle α changes.
Thus the quantum program is partly classical information specifying which local basis to measure.
A sequence of measured cluster qubits implements a sequence of gates on the logical state moving along the remaining graph.
9. Pauli byproducts
Measurement outcomes are random. The resulting computation is nevertheless deterministic because randomness appears as known Pauli byproducts.
If a logical state carries a byproduct XxZz, later measurement bases can be changed so the intended logical gate is implemented despite that frame.
The controller can either apply physical Pauli corrections or track them classically in a Pauli frame.
10. Why adaptivity is required
Pauli operators do not commute through arbitrary rotations unchanged.
For example,
R_z(α)X = X R_z(−α).
Therefore an X byproduct from an earlier outcome flips the sign of a later equatorial measurement angle.
This is the origin of feed-forward: future bases depend on past classical outcomes so that random byproducts are steered into a known final frame.
11. Clifford gates are special
Clifford gates map Pauli operators to Pauli operators under conjugation.
As a result, Clifford-only measurement patterns can often be processed with fixed measurement bases or simple Pauli-frame updates.
Non-Clifford measurements generally require genuine adaptivity because byproduct-dependent angle signs cannot be postponed as trivially.
12. Two-dimensional cluster state
A one-dimensional chain supplies a logical wire and single-qubit processing.
A two-dimensional cluster supplies branching and interactions between logical wires, enabling entangling gates.
Raussendorf and Briegel showed that a sufficiently large two-dimensional cluster state is a universal resource for one-way quantum computation. [1]
13. Consuming the resource
Measured qubits are removed from the future quantum state.
The entanglement resource is therefore consumed irreversibly as the computation progresses.
This contrasts with the circuit model, where a register persists and gates are applied directly over time.
The two models are computationally equivalent for universal quantum computation, but their hardware and compilation costs differ.
14. Z measurement deletes a graph vertex
Measuring graph-state qubit v in the Z basis removes v and all incident edges from the remaining graph, up to known local Pauli corrections depending on the outcome.
This gives a simple graph surgery operation: create a large regular cluster, then carve out unnecessary regions by Z measurements.
15. X and Y measurements transform graph connectivity
X/Y measurements do more than delete a vertex. Up to local Clifford corrections, they can induce local complementations and edge transformations among neighbours before removing the measured vertex.
Graph-state measurement calculus therefore has a combinatorial layer: quantum measurements rewrite the entanglement graph.
16. Local Clifford equivalence
Two graph states related by single-qubit Clifford operations can represent the same entanglement resource class for many purposes.
Graph local complementation captures this equivalence combinatorially.
This reduces resource-state classification from arbitrary amplitudes to graph transformations plus local Clifford bookkeeping.
17. Measurement calculus
Measurement-based patterns can be written as sequences of commands:
- prepare qubits;
- entangle selected pairs with CZ;
- measure specified qubits at angles;
- apply or track outcome-dependent corrections.
Rewrite rules move corrections through later operations and reveal which dependencies are genuinely causal.
This command language makes MBQC compilation amenable to formal optimisation rather than ad hoc circuit translation.
18. Flow
A graph with chosen input and output sets can possess a flow: a mapping from measured vertices to correcting future vertices plus a partial order satisfying graph-theoretic neighbourhood conditions.
Flow guarantees that random measurement outcomes can be corrected using only operations on qubits that have not yet been measured.
It therefore certifies deterministic runnable time order for a broad class of patterns.
19. Generalised flow
Some useful graph patterns have no ordinary flow but still support deterministic MBQC.
Generalised flow, or gflow, lets one measurement outcome be corrected across a set of future qubits rather than one designated successor.
gflow widens the class of open graph states with guaranteed deterministic measurement semantics.
20. Classical side-processing is part of the computer
MBQC needs a classical controller to:
- receive measurement bits;
- compute parity functions of earlier outcomes;
- choose later measurement angles;
- maintain the Pauli frame;
- interpret final output bits.
Low-latency classical feed-forward is therefore a hardware resource, not a free afterthought.
21. Blind quantum computation
Measurement-based architectures naturally support delegated/blind computation protocols.
A client can hide computation angles using random rotations while a server prepares and entangles a larger resource state.
Corrected measurement instructions reveal little or no algorithmic information under the protocol’s security assumptions.
This illustrates that MBQC’s separation between resource preparation and measurement program can be cryptographically useful.
22. Fault-tolerant MBQC
Topological cluster-state schemes encode fault tolerance directly into a three-dimensional space-time resource graph.
Measurements define defects, logical world lines and braiding-like operations in the resource.
The relationship with Guide 26 is close: surface-code stabiliser geometry can be translated into measurement-based topological computation.
23. Photonic cluster states
Photons are natural measurement-based carriers because they are easy to measure and can travel through networks.
The hard part is entangling them deterministically. Linear-optical fusion measurements can probabilistically stitch smaller graph states into larger clusters.
Resource overhead then depends on photon loss, fusion success probability, multiplexing and feed-forward.
24. Matter-qubit cluster generation
Superconducting qubits, trapped ions, neutral atoms and spin systems can create graph states using native entangling gates.
In these platforms, measurement adaptivity and reset/reuse latency can matter as much as graph-state preparation fidelity.
The optimal architecture may blend circuit gates with measurement-based subroutines rather than choose one model exclusively.
25. Contextuality connection
Guide 56 introduced contextuality as a nonclassical resource.
In several MBQC frameworks, contextuality is necessary for deterministic computation of certain nonlinear Boolean functions beyond a restricted classical control model.
This does not mean every graph state is automatically computationally powerful. Stabilizer graph states with only Pauli measurements remain efficiently classically simulable by the Gottesman–Knill theorem.
26. Entanglement is necessary but not sufficient
A universal MBQC resource must possess the right form of multipartite entanglement and measurement structure.
Some highly entangled states are poor universal resources because local measurements cannot route and transform logical information appropriately.
Resource quality is operational: what computations become possible with the allowed measurements and classical controller?
27. Common misconception: measurement destroys the computation
Each measurement destroys one physical qubit’s quantum state, but entanglement transfers the logical state into unmeasured neighbours while applying a gate. The resource is consumed in a controlled way.
28. Common misconception: outcomes must be postselected
Universal MBQC does not wait for preferred random outcomes. It uses every outcome, records the byproduct and adapts future measurements or the final Pauli frame.
29. Common misconception: cluster-state MBQC is the same as CV cluster computation
The architecture is analogous, but the physical variables and error models differ. Qubit MBQC uses discrete graph-state stabilizers and binary outcomes; Guide 43 uses bosonic modes, nullifiers, homodyne outcomes and finite squeezing.
30. Worked synthesis problem
A logical qubit is teleported through two measured sites of a linear cluster.
Step 1: The first measurement produces bit m₁ and byproduct Xm₁.
Step 2: Because X changes the sign of a later Z-rotation angle, the controller changes the second measurement angle from α₂ to (−1)m₁α₂ under the chosen convention.
Step 3: The second measurement returns m₂, creating another known Pauli byproduct.
Step 4: The final unmeasured qubit carries the desired logical gate sequence multiplied by a Pauli operator determined by m₁,m₂.
Step 5: Track that Pauli classically instead of correcting physically unless a later non-Clifford measurement basis requires its effect to be absorbed immediately.
31. Practice set
- How is a graph state prepared from |+⟩ qubits?
- Write the graph-state stabilizer K_v.
- What state results from one-bit X-basis teleportation up to global phase?
- What is an equatorial measurement basis?
- Why do random outcomes not make MBQC nondeterministic?
- Why are later measurement angles sometimes adaptive?
- What role does a 2D cluster play that a 1D chain does not?
- What does Z measurement do to a graph-state vertex?
- What does flow certify?
- Why is low-latency classical processing part of MBQC hardware?
- Why are stabilizer graph states plus Pauli measurements not enough for universal quantum advantage?
- How does qubit MBQC differ from CV MBQC?
Answers
- Prepare |+⟩ on every vertex and apply CZ on every graph edge.
K_v=X_v∏_{u∈N(v)}Z_u.X^mH|ψ⟩.|±_α⟩=(|0⟩±e^{iα}|1⟩)/√2.- Outcomes create known Pauli byproducts that can be corrected or tracked.
- Earlier byproducts change the effective sign/frame of later non-Clifford measurement bases.
- It supplies branching/connectivity for entangling operations between logical wires.
- Deletes the measured vertex and incident edges, up to known local Pauli effects.
- A valid future correction structure and partial measurement order yielding deterministic computation.
- It must process outcomes and choose later bases before coherence is lost.
- They remain inside an efficiently simulable Clifford/stabilizer subtheory.
- Qubit MBQC uses discrete graph stabilizers/binary measurements; CV MBQC uses bosonic modes, nullifiers, continuous outcomes and finite-squeezing noise.
Sources and further study
[1] Robert Raussendorf and Hans J. Briegel, A One-Way Quantum Computer, Physical Review Letters 86, 5188 (2001). The foundational cluster-state model.
[2] Robert Raussendorf, Daniel E. Browne and Hans J. Briegel, Measurement-based quantum computation on cluster states, Physical Review A 68, 022312 (2003). Detailed universality and measurement-pattern treatment.
[3] Marc Hein, Wolfgang Dür, Jens Eisert, Robert Raussendorf, M. Van den Nest and Hans J. Briegel, Entanglement in Graph States and its Applications. A comprehensive graph-state review.
[4] Vincent Danos and Elham Kashefi, Determinism in the one-way model. Introduces flow as a graph-theoretic determinism condition for measurement patterns.
Continue through Quantum Mathematics
Guide 57: Quantum Amplitude Estimation, Approximate Counting, Monte Carlo and Quadratic Sampling Speedups develops a query-estimation primitive. Guide 58: Quantum Chemistry Mathematics, Electronic Structure, Fermionic Hamiltonians and Qubit Mappings develops an application encoding pipeline. Guide 60: Quantum Causal Models, Process Matrices, Causal Inequalities and Indefinite Causal Order asks what happens when even the order of operations becomes part of the quantum description.