Cluster States and Graph States

Cluster states are the beating heart of photonic quantum computing, where two-qubit gates are hard but measurements are easy — exactly the trade the one-way model rewards. In 2019 the group of Furusawa and Andersen deterministically generated continuous-variable cluster states spanning more than a million entangled temporal modes on a single optical table, and independent work produced large two-dimensional CV clusters, giving measurement-based photonics a scalable substrate. Discrete-variable photonic efforts take a related route: fusion-based quantum computation, the model behind PsiQuantum's architecture, manufactures small resource states and stitches them into a fault-tolerant cluster with probabilistic "fusion" measurements, while Xanadu's roadmap builds Gottesman–Kitaev–Preskill qubits into CV clusters. On the error-correction side, the surface code's fault-tolerant operation is most naturally phrased as a measurement pattern on a three-dimensional cluster state, the Raussendorf–Harrington–Goyal construction, where topological protection emerges from the same single-qubit measurements. Neutral-atom arrays (QuEra) and trapped ions have prepared graph and cluster states of tens of qubits and demonstrated their stabilizers directly. And the graphical language pays off far from hardware: graph states power quantum-network primitives — conference key agreement, anonymous transmission, and secret sharing whose access structures mirror graph connectivity — making the humble picture of dots and lines a working blueprint for a quantum internet.

Start with $n$ qubits, each in $|+\rangle$ — think of them as $n$ independent classical-superposition wires, every bit-string equally weighted. A $\mathrm{CZ}$ on edge $(a,b)$ does one thing: it stamps a minus sign onto exactly those amplitudes where both $x_a$ and $x_b$ are $1$. Lay down a $\mathrm{CZ}$ for every edge and the accumulated sign on the amplitude of $|\mathbf{x}\rangle$ is $(-1)^{\sum_{(a,b)\in E}x_ax_b}$ — a quadratic form read straight off the graph. Nothing about the magnitudes changes; all the entanglement lives in a pattern of signs dictated by which vertices are joined. This is why the graph and the state are the same information: the edge set is the quadratic form, and the quadratic form is the state.

The stabilizer is where the structure turns physical. The operator $K_a=X_a\prod_{b\in N(a)}Z_b$ is a symmetry: flipping qubit $a$ with $X_a$ scrambles the state, but the phases picked up by its neighbours under $\prod Z_b$ undo the damage exactly, so the net action fixes $|G\rangle$. The state is the simultaneous fixed point of all $n$ such symmetries — one commuting parity check per vertex. Two generators $K_a,K_b$ always commute, because if $a$ and $b$ are joined then the $X$ on each meets a $Z$ on the other, giving two anticommuting overlaps that cancel, and if they are not joined they overlap only on $Z$'s. Measurement is the dynamics: measuring a qubit in a tilted basis teleports its wire's information onto its neighbours, and stacked across a two-dimensional lattice these teleportations weave into arbitrary circuits. The second figure shows that computational substrate — a 2D cluster consumed by single-qubit measurements.

Finally, a single graph move captures all the freedom hidden in these states. Two graph states describe the same entanglement — they are related by local unitaries acting qubit-by-qubit — whenever their graphs are connected by local complementation: pick a vertex $v$, and toggle every edge among its neighbours. This one combinatorial rule generates the entire local-Clifford orbit, so classifying stabilizer entanglement reduces to classifying graphs under complementation. Entanglement, usually a continuous and forbidding quantity, becomes a discrete graph invariant.

The construction is a one-line recipe. Everything downstream — stabilizers, amplitudes, entanglement — is a consequence of applying a commuting network of $\mathrm{CZ}$ gates to a product of $|+\rangle$ states.

where: $G=(V,E)$ — a graph, one qubit per vertex $V$, one $\mathrm{CZ}$ per edge $E$; $\mathrm{CZ}_{ab}=\mathrm{diag}(1,1,1,-1)$ — the symmetric controlled-$Z$ on qubits $a,b$; $|+\rangle=(|0\rangle+|1\rangle)/\sqrt2$ — the $+1$ eigenstate of $X$. Reading: because $\mathrm{CZ}$ is diagonal, all edge gates commute, so the product needs no ordering and $|G\rangle$ is a function of the graph alone. The stabilizer generators are the real definition — they specify $|G\rangle$ without ever writing an amplitude. One generator lives at each vertex.

where: $N(a)$ — the neighbourhood of $a$, the vertices joined to it by an edge; $X_a$ — Pauli $X$ on the vertex itself; $Z_b$ — Pauli $Z$ on each neighbour. Reading: $K_a$ is a "flip $a$, phase its neighbours" symmetry; the $n$ generators commute and their common $+1$ eigenspace is one-dimensional, so $\{K_a\}$ uniquely determine $|G\rangle$. Expanding the $\mathrm{CZ}$ network in the computational basis makes the graph appear as a quadratic phase — the most concrete face of the state.

where: $\mathbf{x}=(x_1,\dots,x_n)$ — a bit-string labelling a basis state; $\sum_{(a,b)\in E}x_ax_b$ — the graph's quadratic form, evaluated mod $2$. Reading: every amplitude has the same magnitude $2^{-n/2}$; the entire entanglement is carried by the sign pattern, and the sign flips precisely when both endpoints of some edge are set to $1$. The generators generate an abelian group whose two structural properties — its size and its avoidance of $-\mathbb{1}$ — are exactly what guarantee a unique stabilized state.

where: $\mathcal{S}$ — the abelian subgroup of the Pauli group $\mathcal{P}_n$ stabilizing $|G\rangle$; $n=|V|$ — the number of qubits. Reading: $n$ independent commuting generators each halve the surviving space, cutting $2^n$ dimensions down to $2^0=1$; the absence of $-\mathbb{1}$ keeps that one-dimensional space nonempty. For a graph state, bipartite entanglement is not an integral to evaluate but a rank to compute — an integer, read off a submatrix of the adjacency matrix.

where: $S_A$ — the von Neumann entanglement entropy of region $A$, in ebits (units of $\log 2$); $\Gamma$ — the $0/1$ adjacency matrix of $G$; $\Gamma_{A\bar A}$ — its off-diagonal block linking $A$ to the complement $\bar A$; $\mathrm{rank}_{\mathbb{F}_2}$ — matrix rank over the binary field. Reading: the "cut-rank" counts the independent entangling links across the bipartition, so entanglement is always a whole number of Bell pairs. Local complementation is the graph rule that generates the local-Clifford orbit — the equivalence class of graphs describing the same entanglement.

where: $\tau_v$ — local complementation at $v$: complement the subgraph induced on the neighbourhood $N(v)$; $\triangle$ — symmetric difference, i.e. toggle each affected edge. Reading: $\tau_v$ is realized on the state by the on-site Clifford $\exp(-i\tfrac{\pi}{4}X_v)\prod_{b\in N(v)}\exp(+i\tfrac{\pi}{4}Z_b)$, so $\tau_v(G)$ and $G$ are local-Clifford equivalent and share all entanglement. The computational punchline: a single-qubit measurement in a tilted basis drives a logical rotation, up to a Pauli byproduct, and a 2D cluster of such measurements is universal.

where: $|\pm_\theta\rangle=(|0\rangle\pm e^{i\theta}|1\rangle)/\sqrt2$ — the measurement basis tilted by angle $\theta$ in the $X$–$Y$ plane; $s$ — the measurement outcome; $X^s$ — the induced Pauli byproduct. Reading: the outcome is random, but known, so the byproduct is tracked classically and absorbed into the basis angles of later measurements (feedforward), which restores deterministic logic on the 2D square-lattice cluster.

Special graphs collapse the general construction to states every quantum-information student already knows — a useful set of sanity checks on the machinery:

1 · The box cluster $C_4$, its stabilizers, and its cut-dependent entanglement (fully worked)

Take the four-qubit ring (a square) with vertices $1,2,3,4$ and edges $(1,2),(2,3),(3,4),(4,1)$. Write its stabilizers and amplitude form, then compute the entanglement entropy across two different bipartitions.

Step 1. Write the generators from Eq. (2). Each vertex has two neighbours around the ring, so $K_1=X_1Z_2Z_4$, $K_2=X_2Z_1Z_3$, $K_3=X_3Z_2Z_4$, $K_4=X_4Z_1Z_3$. These four commute (adjacent generators share the two anticommuting overlaps of Derivation 1), none equals $-\mathbb{1}$, and being four independent generators on four qubits they fix a unique state — the box cluster.

Step 2. Write the amplitude form from Eq. (3). The quadratic phase is $x_1x_2+x_2x_3+x_3x_4+x_4x_1\pmod 2$, so $|C_4\rangle=\tfrac14\sum_{\mathbf{x}\in\{0,1\}^4}(-1)^{x_1x_2+x_2x_3+x_3x_4+x_4x_1}|\mathbf{x}\rangle$. All sixteen amplitudes have magnitude $\tfrac14$; only the signs distinguish the state, and a sign flips whenever two ring-adjacent bits are both $1$ — for instance $|1010\rangle$ picks up $(-1)^{0}=+1$ while $|1100\rangle$ picks up $(-1)^{1}=-1$.

Step 3. Entangle across the "edge" cut $A=\{1,2\}$, $\bar A=\{3,4\}$. The edges crossing this cut are $(2,3)$ and $(4,1)$, so the adjacency block, with rows $\{1,2\}$ and columns $\{3,4\}$, is $\Gamma_{A\bar A}=\begin{pmatrix}0&1\\1&0\end{pmatrix}$ (row $1$ links only to $4$, row $2$ only to $3$). Its binary rank is $2$, so by Eq. (5) $S_A=\mathbf{2}$ ebits — the maximum possible for a two-versus-two split, i.e. two Bell pairs of entanglement.

Step 4. Now cut through the opposite corners, $A'=\{1,3\}$, $\bar A'=\{2,4\}$. Every one of the four edges crosses this cut, so with rows $\{1,3\}$ and columns $\{2,4\}$ the block is $\Gamma_{A'\bar A'}=\begin{pmatrix}1&1\\1&1\end{pmatrix}$. Over $\mathbb{F}_2$ the second row equals the first, so the rank is $1$ and $S_{A'}=\mathbf{1}$ ebit — half the entanglement of the previous cut, even though more edges are severed. Same state, different cut: $2$ ebits across a side, $1$ ebit across the diagonal — entanglement is combinatorial, an integer count of the independent links, not the raw number of cut edges.

2 · Programming a rotation on a cluster wire

A logical qubit rides a linear cluster. You want to apply the phase gate $S=e^{-i(\pi/4)Z}$ (a $\theta=\pi/2$ $Z$-rotation) by measurement. What basis do you choose, and what correction follows?

Step 1. Pick the measurement angle. By Eq. (7) and Derivation 2, measuring a wire qubit in the tilted basis $|\pm_\theta\rangle=(|0\rangle\pm e^{i\theta}|1\rangle)/\sqrt2$ enacts $H\,e^{-i\theta Z/2}$ on the next qubit. To realize the desired $e^{-i(\pi/4)Z}=e^{-i\theta Z/2}$ with $\theta=\pi/2$, choose the basis $|\pm_{\pi/2}\rangle=(|0\rangle\pm i|1\rangle)/\sqrt2$ — the $Y$ eigenbasis.

Step 2. Account for the Hadamard. The map carries a built-in $H$, so a single measurement gives $H\,S$, not $S$ alone. In a real pattern this $H$ is either wanted (the model's native gates come in $HR_z$ pairs) or undone by a following wire qubit measured in the plain $X$ basis ($\theta=0$), which contributes another $H$ and squares to the identity, $H\cdot H=\mathbb{1}$.

Step 3. Handle the byproduct. The outcome $s\in\{0,1\}$ is a fair coin; outcome $s=1$ leaves an $X$ byproduct. Feedforward absorbs it: the next measurement angle is flipped $\theta'\mapsto(-1)^{s}\theta'$, because pushing $X$ through the following $Z$-rotation sends $e^{-i\theta'Z/2}\,X=X\,e^{+i\theta'Z/2}$. Choosing the $Y$-basis realizes the $S$ gate (up to the intrinsic $H$), the outcome $s=1$ costs only a sign-flip in the next angle, and no correction is ever physically applied — the whole gate is a basis choice plus classical bookkeeping.

Cluster and graph states are young — barely a quarter-century old — but they redrew the map of quantum computation, showing that a fixed, pre-entangled resource plus a stream of single-qubit measurements is as powerful as any gate circuit. The idea and its name came from one collaboration.

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, Ch. 10 (stabilizer formalism and codes) · Raussendorf & Briegel, A One-Way Quantum Computer, Phys. Rev. Lett. 86, 5188 (2001) · Hein, Eisert & Briegel, Multiparty entanglement in graph states, Phys. Rev. A 69, 062311 (2004) · Hein et al., Entanglement in graph states and its applications, quant-ph/0602096 · Preskill, Lecture Notes on Quantum Computation, Ch. 7 · Mermin, Quantum Computer Science, Ch. 5. Key results to keep in mind: the stabilizer $K_a=X_a\prod_{b\in N(a)}Z_b$ follows from the $\mathrm{CZ}$ conjugation rule $\mathrm{CZ}\,X_a\,\mathrm{CZ}=X_aZ_b$; the amplitude form carries a quadratic phase (Eq. 3); the box-cluster has two cut-rank entropies, $2$ ebits across a side and $1$ ebit across the diagonal (Worked Example 1, Eq. 5); the single-qubit teleportation-with-rotation step and feedforward are detailed in Derivation 2; an $L\times L$ cluster has $L^2$ qubits and $2L(L-1)$ edges. The named states (Bell, GHZ, product) are standard local-Clifford reductions.

Prerequisites. Stabilizer Formalism · Pauli Group and Clifford Operations · Entanglement Measures. Leads to. Measurement-Based Quantum Computation · One-Way Quantum Computer · Flow and Gflow Conditions · Measurement Calculus and Pattern Compilation · Toric Code and Topological Order.

Ask the tutor: Want to walk a full measurement pattern that compiles a two-qubit gate on a 2D cluster, or see exactly how local complementation carries the star graph into the GHZ orbit?