Graph States and MBQC

Cluster states are the special case of graph states living on regular lattices. Generalising to arbitrary graphs reveals the structure that makes MBQC work, gives a clean stabilizer formalism for predicting how measurements transform the resource, and exposes a surprising local-equivalence symmetry — local complementation — that explains which graphs carry the same entanglement.

Graph states: definition and stabilizers

For any simple graph $G = (V, E)$ , place a qubit on each vertex in $|+\rangle$ and apply $CZ$ across every edge:

|G\rangle = \prod_{(a,b)\in E} CZ_{ab} \bigotimes_{v\in V}|+\rangle_v .

A cluster state is exactly $|G\rangle$ for $G$ a square lattice (or a path, in 1D). The graph state is the unique joint $+1$ eigenstate of the $|V|$ commuting stabilizer generators

K_a = X_a \prod_{b \in N(a)} Z_b , \qquad a \in V,

where $N(a)$ is the neighbourhood of $a$ . The generators read directly off the graph: an $X$ on the vertex, a $Z$ on each neighbour. Because they commute and there is one per qubit, they pin $|G\rangle$ down completely — and they let us track measurements in the stabilizer formalism rather than with exponential state vectors.

Measurements act on the graph

The power of the stabilizer description is that Pauli measurements on a graph state produce another graph state (up to local Cliffords), and the new graph is computed by simple combinatorial rules on $G$ :

A $Z$ measurement on vertex $a$ deletes $a$ and all its edges. The neighbours lose their link to $a$ ; everything else is unchanged (up to local $Z$ corrections depending on the outcome). This is how unwanted qubits are pruned from a resource.
A $Y$ measurement on $a$ removes $a$ but first local-complements its neighbourhood: it toggles every edge among $a$ 's neighbours (present becomes absent and vice versa), then deletes $a$ .
An $X$ measurement on $a$ removes $a$ and rewires its neighbourhood through a chosen neighbour, effecting the teleportation step that underlies single-qubit gates.

So a measurement pattern is, at the Pauli level, a sequence of graph edits. The teleportation gadget of earlier lessons is precisely the $X$ -measurement rule applied along a chain.

Local complementation and LU-equivalence

Two graph states are local-unitary (LU) equivalent — interconvertible by single-qubit gates, hence carrying identical entanglement — whenever their graphs are related by a sequence of local complementations. A local complementation at vertex $a$ replaces the subgraph induced on $N(a)$ by its complement (toggle every edge among the neighbours of $a$ ). This single move generates the whole LU-equivalence class of a graph state under local Clifford operations.

The classic illustration: the star graph $K_{1,n}$ (one centre joined to $n$ leaves) is local-Clifford equivalent to the complete graph $K_{n+1}$ , and both represent the same $n{+}1$ -qubit GHZ-type entanglement. The two-qubit cluster state's equivalence to a Bell state, met earlier, is the smallest instance. Local complementation therefore answers "which different-looking resources are really the same?" — a practical question when choosing a hardware-friendly graph.

Why graphs are the right language for MBQC

Resource design. Universality needs a graph with enough connectivity (a 2D lattice suffices); $Z$ -measurements then carve a generic lattice down to the specific graph an algorithm requires.
Entanglement accounting. Graph-theoretic quantities (neighbourhoods, the Schmidt rank across a cut, local-complementation orbits) translate directly into entanglement properties, so one reasons about a many-qubit resource without leaving combinatorics.
Error structure. Stabilizer generators tied to the graph make graph states the natural setting for the error-correcting codes that underpin fault-tolerant MBQC, the topic of the next lesson.

The takeaway

A graph state assigns a qubit to each vertex and entangles every edge with $CZ$ ; its stabilizers are read off the graph as $K_a = X_a \prod_{b\in N(a)} Z_b$ , and cluster states are the lattice special case. Pauli measurements act as edge-deletion and local-complementation rules on the graph, so an MBQC pattern is a controlled sequence of graph surgeries. Local complementation classifies which graph states are locally equivalent. This graph-state formalism is the language in which the entire model — universality, patterns, and fault tolerance — is most naturally expressed.