Graph States

A graph state is a multipartite qubit state specified by a simple undirected graph. Vertices are qubits, edges prescribe entangling controlled-$Z$ operations, and the resulting state is characterized by a set of commuting local Pauli operators.

Graph states are important because they turn complicated multipartite entanglement into combinatorial data. They include cluster states used in measurement-based quantum computing, give compact examples of stabilizer states, and provide useful test cases for entanglement witnesses and quantum error correction.

This page treats graph states as structured composite states. The full stabilizer formalism, Clifford circuits, measurement-based computation, and quantum-error-correcting-code theory belong in quantum information.

Graphs and Qubits

Let

$$G=(V,E)$$

be a simple undirected graph with vertex set

$$V=\{1,2,\ldots,n\}.$$

Each vertex labels one qubit, so the Hilbert space is

$$\mathcal H_G = \bigotimes_{v\in V}\mathbb C^2.$$

The neighborhood of a vertex $v$ is

$$N(v) = \{u\in V:\{u,v\}\in E\}.$$

Thus the graph records which qubits are directly connected in the state-preparation circuit. It is not, by itself, a physical lattice unless a particular implementation supplies one.

Controlled-Z Construction

Start with every qubit in

$$\lvert+\rangle = \frac{1}{\sqrt2} \bigl( \lvert0\rangle+\lvert1\rangle \bigr), \qquad \lvert+\rangle^{\otimes n}.$$

For each edge $\{i,j\}\in E$, apply the controlled-$Z$ gate

$$CZ_{ij} = \operatorname{diag}(1,1,1,-1)$$

on qubits $i$ and $j$ in the computational basis. The graph state is

$$\lvert G\rangle = \prod_{\{i,j\}\in E} CZ_{ij} \lvert+\rangle^{\otimes n}.$$

All controlled-$Z$ gates are diagonal in the computational basis, so they commute. The product therefore does not depend on the order of the edges.

Equivalently,

$$\lvert G\rangle = \frac{1}{2^{n/2}} \sum_{x\in\{0,1\}^{n}} (-1)^{ \sum_{\{i,j\}\in E}x_i x_j } \lvert x_1x_2\cdots x_n\rangle.$$

The exponent is interpreted modulo $2$: every edge whose two endpoint bits are both $1$ contributes a minus sign.

First Examples

If $E$ is empty, then

$$\lvert G\rangle = \lvert+\rangle^{\otimes n},$$

so the state is fully product.

For a graph with two vertices and one edge,

$$\lvert G\rangle = CZ\lvert++\rangle = \frac{1}{2} \bigl( \lvert00\rangle + \lvert01\rangle + \lvert10\rangle - \lvert11\rangle \bigr).$$

This is an entangled two-qubit state. It is locally unitarily equivalent to a Bell state. For example, applying a Hadamard gate to the second qubit gives

$$(I\otimes H)\lvert G\rangle = \frac{1}{\sqrt2} \bigl( \lvert00\rangle+\lvert11\rangle \bigr) = \lvert\Phi^+\rangle.$$

For a three-qubit path graph

$$1-2-3,$$

the graph state is a linear three-qubit cluster state. For a star graph with one center connected to all other vertices, the graph state is locally Clifford equivalent to a GHZ state.

These equivalences are useful, but they do not mean the graph is irrelevant. Different graphs organize correlations, measurements, and code constructions in different ways.

Stabilizer Description Preview

Graph states have a compact Pauli-eigenvalue description. For each vertex $v$, define

$$K_v = X_v \prod_{u\in N(v)} Z_u,$$

where $X_v$ acts as the Pauli $X$ on qubit $v$, and $Z_u$ acts as the Pauli $Z$ on qubit $u$.

The graph state is the unique simultaneous $+1$ eigenstate of all these operators:

$$K_v\lvert G\rangle = \lvert G\rangle, \qquad v\in V.$$

The reason is simple. The product state $\lvert+\rangle^{\otimes n}$ is stabilized by every $X_v$:

$$X_v\lvert+\rangle^{\otimes n} = \lvert+\rangle^{\otimes n}.$$

Conjugating $X_v$ by the controlled-$Z$ gates incident on $v$ gives

$$\left( \prod_{\{i,j\}\in E} CZ_{ij} \right) X_v \left( \prod_{\{i,j\}\in E} CZ_{ij} \right) = X_v\prod_{u\in N(v)}Z_u.$$

Thus the simple $X_v$ stabilizers of $\lvert+\rangle^{\otimes n}$ become the graph-state stabilizers $K_v$.

The operators $K_v$ commute with each other. If two vertices are not adjacent, the corresponding Pauli factors do not conflict. If two vertices are adjacent, each stabilizer has one $X$ where the other has one $Z$, giving two anticommutations in the product and hence an overall commutation.

Linear Cluster Example

For the path graph $1-2-3$, the neighborhoods are

$$N(1)=\{2\}, \qquad N(2)=\{1,3\}, \qquad N(3)=\{2\}.$$

The stabilizer generators are

$$K_1=X_1Z_2, \qquad K_2=Z_1X_2Z_3, \qquad K_3=Z_2X_3.$$

These three commuting observables specify the three-qubit graph state as their common $+1$ eigenstate. Notice that each stabilizer is local in the graph-theoretic sense: it acts on a vertex and its neighbors.

For a longer one-dimensional chain, the interior generators have the form

$$K_j = Z_{j-1}X_jZ_{j+1}.$$

This pattern is the algebraic signature of a one-dimensional cluster state.

Entanglement from Graph Connectivity

Disconnected graphs give product states across connected components. If

$$G=G_1\sqcup G_2,$$

with no edge connecting the two components, then

$$\lvert G\rangle = \lvert G_1\rangle\otimes \lvert G_2\rangle$$

up to the ordering convention for tensor factors.

Connected graph states are entangled across every nontrivial bipartition of the vertices. More quantitatively, for a bipartition $A\vert\bar A$, the Schmidt rank of a graph state is determined by the adjacency matrix connecting the two sides:

$$\operatorname{SR}_{A\vert\bar A}(\lvert G\rangle) = 2^{r_A}, \qquad r_A = \operatorname{rank}_{\mathbb F_2} \Gamma_{A,\bar A}.$$

Here $\Gamma_{A,\bar A}$ is the submatrix of the graph adjacency matrix with rows in $A$ and columns in $\bar A$, and the rank is over the two-element field $\mathbb F_2$. This formula is one reason graph states are analytically tractable: some entanglement data can be read from binary linear algebra.

The formula should not be mistaken for a full multipartite classification. Graph states are a structured family, not the space of all multipartite states.

Cluster States Preview

A cluster state is a graph state whose graph is usually a regular lattice: a line, square grid, cubic lattice, or related geometry. Measurement-Based Quantum Computation owns how an open graph becomes a computation through declared inputs and outputs, adaptive single-qubit measurements, byproduct propagation, and flow or gflow. The measurement choices and classical feed-forward determine the implemented logical map.

The composite-systems lesson is that entanglement can be arranged as a global resource distributed across many qubits. This page remains canonical for graph-state construction, stabilizers, connectivity, and entanglement structure; the computation-model owner develops pattern determinism and universality.

Blind and Delegated Quantum Computation uses this measurement pattern as a cryptographic interface: randomized graph-state preparations and masked adaptive angles hide a computation from the server, while hidden traps can add integrity. The graph-state construction itself remains canonical here.

Applications Preview

Graph states appear in several parts of quantum physics:

• stabilizer-state examples with compact Pauli descriptions;
• cluster states for measurement-based quantum computation;
• graph-based quantum error-correcting code constructions;
• multipartite entanglement witnesses using stabilizer correlations;
• many-body models whose Hamiltonians are sums of commuting stabilizer terms.

The common thread is that the graph controls both the entanglement pattern and a family of measurable Pauli correlations.

Common Mistakes

• Thinking an edge is an ordinary pairwise interaction present after preparation. The edge specifies the entangling gate used in the graph-state construction.
• Assuming graph connectivity is the same thing as geometric locality in the laboratory.
• Treating graph states as all multipartite states. They are a special stabilizer family.
• Forgetting that graph states related by local Clifford operations can represent the same entanglement class in different graph forms.
• Confusing the graph-state stabilizers with Hamiltonian terms unless a Hamiltonian has actually been defined.
• Assuming cluster-state computation belongs in this composite-systems page. Only the state structure is previewed here.

Cross-Links

• Multipartite Systems
• Stabilizer States Preview
• Multipartite Separability
• GHZ States
• W States
• Entanglement Sharing
• Entangled States
• Local Unitary Equivalence
• Schmidt Rank
• Entanglement Entropy
• Entanglement Witnesses
• Reduced Density Operators
• Operators on Composite Systems
• Interactions and Coupling Terms
• Photonic Qubits for cluster-resource generation, probabilistic fusion, destructive measurements, and architecture-level loss accounting.
• Pauli Matrices
• Pauli Matrix Table

References

• R. Raussendorf and H. J. Briegel, “A One-Way Quantum Computer,” Physical Review Letters 86, 5188-5191, 2001.
• D. Schlingemann and R. F. Werner, “Quantum Error-Correcting Codes Associated with Graphs,” Physical Review A 65, 012308, 2001.
• M. Hein, J. Eisert, and H. J. Briegel, “Multi-Party Entanglement in Graph States,” Physical Review A 69, 062311, 2004.
• M. Van den Nest, J. Dehaene, and B. De Moor, “Graphical Description of the Action of Local Clifford Transformations on Graph States,” Physical Review A 69, 022316, 2004.
• M. Hein, W. Dur, J. Eisert, R. Raussendorf, M. Van den Nest, and H.-J. Briegel, “Entanglement in Graph States and Its Applications,” in Quantum Computers, Algorithms and Chaos, IOS Press, 2006.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2010.

Exercises

1. Show that all controlled-$Z$ gates in the graph-state construction commute.

Solution

Each controlled-$Z$ gate is diagonal in the computational basis. Diagonal matrices commute with each other, even when they act on overlapping qubits. Therefore the product

$$\prod_{\{i,j\}\in E}CZ_{ij}$$

is independent of the order chosen for the edges.

2. Compute the two-qubit graph state for one edge and verify that applying $I\otimes H$ gives $\lvert\Phi^+\rangle$.

Solution

Starting from

$$\lvert++\rangle = \frac12 \bigl( \lvert00\rangle+\lvert01\rangle+\lvert10\rangle+\lvert11\rangle \bigr),$$

the controlled-$Z$ gate flips the sign only on $\lvert11\rangle$:

$$\lvert G\rangle = \frac12 \bigl( \lvert00\rangle+\lvert01\rangle+\lvert10\rangle-\lvert11\rangle \bigr).$$

Using

$$H\lvert0\rangle = \frac{\lvert0\rangle+\lvert1\rangle}{\sqrt2}, \qquad H\lvert1\rangle = \frac{\lvert0\rangle-\lvert1\rangle}{\sqrt2},$$

one finds

$$(I\otimes H)\lvert G\rangle = \frac{1}{\sqrt2} \bigl( \lvert00\rangle+\lvert11\rangle \bigr).$$

3. For the path graph $1-2-3$, verify that $K_1=X_1Z_2$ and $K_2=Z_1X_2Z_3$ commute.

Solution

The only qubits where nonidentity Pauli operators from both products meet are qubits $1$ and $2$. On qubit $1$, $X_1$ anticommutes with $Z_1$. On qubit $2$, $Z_2$ anticommutes with $X_2$. These two minus signs cancel, so

$$K_1K_2 = K_2K_1.$$

4. If a graph has two disconnected components $G_1$ and $G_2$, show that the graph state factors across those components.

Solution

The initial state factors:

$$\lvert+\rangle^{\otimes n} = \lvert+\rangle_{G_1}^{\otimes \lvert V_1\rvert} \otimes \lvert+\rangle_{G_2}^{\otimes \lvert V_2\rvert}.$$

Because there are no edges between components, the controlled-$Z$ gates split into a product of gates internal to $G_1$ and gates internal to $G_2$. Hence

$$\lvert G\rangle = \lvert G_1\rangle\otimes\lvert G_2\rangle$$

up to tensor-factor ordering.

5. For a cut $A\vert\bar A$, suppose the binary adjacency submatrix $\Gamma_{A,\bar A}$ has rank $0$ over $\mathbb F_2$. What does the graph-state Schmidt-rank formula imply?

Solution

The formula gives

$$\operatorname{SR}_{A\vert\bar A} = 2^0 = 1.$$

Schmidt rank one means the graph state is product across that bipartition. Graphically, rank zero occurs when there are no effective binary connections across the cut; in particular, if no edge crosses the cut, the state factors across it.