5 Cluster States

Cluster states are the workhorses of MBQC. In this chapter, we’ll explore their mathematical structure using the stabilizer formalism - a powerful framework that makes cluster states computationally tractable despite their exponential complexity.

5.1 Graph States: General Framework

Cluster states are special cases of graph states - a family of entangled states defined by simple graphs.

5.1.1 Definition

Graph State Definition

Given an undirected graph \(G = (V, E)\) with \(n\) vertices (qubits), the graph state \(|G\rangle\) is:

\[ |G\rangle = \prod_{(i,j) \in E} CZ_{ij} \cdot |+\rangle^{\otimes n} \]

where:

\(|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)\) is the Hadamard state
\(CZ_{ij}\) is the controlled-Z gate between qubits \(i\) and \(j\)
The product is over all edges in the graph

Key properties:

Order-independent: \(CZ_{ij}\) gates commute, so edge order doesn’t matter
Self-inverse: \(CZ_{ij}^2 = I\) (applying \(CZ\) twice does nothing)
Local unitaries + entanglement: Start with product state, entangle via graph structure

5.1.2 Examples

Single qubit (no edges): \[ |G\rangle = |+\rangle \]

Two qubits, one edge (\(1 — 2\)): \[ |G\rangle = CZ_{12}(|+\rangle \otimes |+\rangle) = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle - |11\rangle) \]

Triangle (\(1 — 2 — 3 — 1\)): \[ |G\rangle = CZ_{12} \cdot CZ_{23} \cdot CZ_{13} \cdot |+\rangle^{\otimes 3} \]

5.2 Cluster States vs General Graph States

Cluster state specifically refers to graph states on lattice graphs (regular grids):

1D cluster: Linear chain \(1 — 2 — 3 — \cdots — n\)
2D cluster: Square lattice (like a checkerboard)
3D cluster: Cubic lattice

These regular structures have special properties useful for universal quantum computation.

5.3 The Stabilizer Formalism

Directly computing graph state amplitudes requires \(O(2^n)\) operations. The stabilizer formalism provides a polynomial-time classical representation.

5.3.1 Pauli Operators

Recall the single-qubit Pauli operators:

\[ \begin{aligned} X &= \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \quad Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}, \quad I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \end{aligned} \]

Properties:

\(X^2 = Y^2 = Z^2 = I\)
\(XY = iZ, \quad YZ = iX, \quad ZX = iY\)
\(\{X, Z\} = 0\) (anticommute)

5.3.2 n-Qubit Pauli Group

For \(n\) qubits, the Pauli group \(\mathcal{P}_n\) consists of all tensor products of single-qubit Paulis with phases \(\pm 1, \pm i\):

\[ \mathcal{P}_n = \{\pm 1, \pm i\}^{\times} \cdot \{I, X, Y, Z\}^{\otimes n} \]

Example for 2 qubits: \[ X \otimes Z, \quad I \otimes Y, \quad X \otimes X, \quad \ldots \]

Shorthand notation: \(XZ, IY, XX, \ldots\) (omit \(\otimes\))

5.3.3 Stabilizers

Stabilizer Definition

An operator \(S\) stabilizes a state \(|\psi\rangle\) if:

\[ S|\psi\rangle = |\psi\rangle \]

The set of all operators that stabilize \(|\psi\rangle\) forms the stabilizer group of the state.

Example: \(Z\) stabilizes \(|0\rangle\): \[ Z|0\rangle = |0\rangle \checkmark \]

but not \(|1\rangle\): \[ Z|1\rangle = -|1\rangle \neq |1\rangle \]

5.3.4 Stabilizer States

A state is a stabilizer state if:

It has a stabilizer group generated by \(n\) independent Pauli operators
These generators commute with each other

Key theorem: An \(n\)-qubit stabilizer state is uniquely determined by \(n\) independent stabilizers.

This means we can represent the state by \(O(n^2)\) bits instead of \(O(2^n)\) complex amplitudes!

5.4 Graph State Stabilizers

For a graph state \(|G\rangle\) on graph \(G = (V, E)\), the stabilizers have a beautiful form.

Graph State Stabilizer Generators

For each vertex \(i \in V\), define:

\[ K_i = X_i \prod_{j \in N(i)} Z_j \]

where \(N(i)\) is the set of neighbors of \(i\) in the graph.

These \(n\) operators generate the stabilizer group of \(|G\rangle\), meaning:

\[ K_i |G\rangle = |G\rangle \quad \text{for all } i \]

5.4.1 Example: 2-Qubit Chain

Graph: \(1 — 2\)

Neighbors:

\(N(1) = \{2\}\)
\(N(2) = \{1\}\)

Stabilizers: \[ \begin{aligned} K_1 &= X_1 Z_2 \\ K_2 &= Z_1 X_2 \end{aligned} \]

Verification: Let’s prove \(K_1 |G\rangle = |G\rangle\) where \(|G\rangle = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle - |11\rangle)\).

\[ \begin{aligned} K_1|G\rangle &= X_1 Z_2 \cdot \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle - |11\rangle) \\ &= \frac{1}{2}X_1(|00\rangle - |01\rangle + |10\rangle + |11\rangle) \\ &= \frac{1}{2}(|10\rangle - |11\rangle + |00\rangle + |01\rangle) \\ &= \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle - |11\rangle) \\ &= |G\rangle \quad \checkmark \end{aligned} \]

5.4.2 Example: 3-Qubit Chain

Graph: \(1 — 2 — 3\)

Neighbors:

\(N(1) = \{2\}\)
\(N(2) = \{1, 3\}\)
\(N(3) = \{2\}\)

Stabilizers: \[ \begin{aligned} K_1 &= X_1 Z_2 \\ K_2 &= Z_1 X_2 Z_3 \\ K_3 &= Z_2 X_3 \end{aligned} \]

These three operators completely characterize the 3-qubit cluster state!

5.5 Why Stabilizers Are Powerful

5.5.1 Efficient Classical Representation

State vector approach:

Store \(2^n\) complex amplitudes
Requires exponential memory

Stabilizer approach:

Store \(n\) stabilizer generators
Each generator is \(n\) Pauli operators
Total: \(O(n^2)\) bits (polynomial!)

5.5.2 Example: 100-Qubit Cluster

State vector:

\(2^{100} \approx 10^{30}\) complex amplitudes
\(10^{31}\) bytes (more atoms than in the observable universe!)

Stabilizers:

100 stabilizer generators
Each: 100 Pauli operators
\(100 \times 100 = 10,000\) symbols (trivial to store!)

5.5.3 Efficient Simulation

Operations on stabilizer states can be simulated efficiently:

Clifford gates: Update stabilizers in \(O(n^2)\) time
Pauli measurements: Sample outcome and update stabilizers in \(O(n^2)\) time
Clifford circuits: Full simulation in \(O(n^3)\) time per gate

Limitation: Non-Clifford gates (like \(T\)-gate, arbitrary rotations) take exponential time.

MBQC uses mostly Pauli measurements (efficient) plus adaptive basis choices (can be non-Clifford).

5.6 Local Complementation

Graph states have a fascinating property: local operations can transform one graph into another.

Local Complementation Rule

Applying a Hadamard gate to qubit \(i\) of graph state \(|G\rangle\) produces a new graph state \(|G'\rangle\) where \(G'\) is obtained by complementing the induced subgraph on \(N(i)\) (neighbors of \(i\)).

Complement: If edge \((j,k)\) exists, remove it; if it doesn’t exist, add it.

5.6.1 Example

Graph \(G\):

1 — 2 — 3

Apply \(H_2\) (Hadamard on qubit 2):

Neighbors of 2: \(N(2) = \{1, 3\}\)

Complement induced subgraph on \(\{1, 3\}\):

Currently no edge \((1,3)\) → add edge \((1,3)\)

Resulting graph \(G'\):

1 — 2 — 3
 \     /
  \   /
   \ /
    X

(Triangle: \(1 — 2 — 3 — 1\))

State transformation: \[ H_2 |G\rangle = |G'\rangle \]

This allows us to transform between graph states using only local operations!

5.7 Creating Cluster States in Practice

5.7.1 Deterministic Preparation

Circuit method (what we’ve defined):

Initialize \(|+\rangle^{\otimes n}\)
Apply \(CZ\) gates according to graph \(G\)

Problem: \(CZ\) gates are hard to implement in some platforms (especially photonics).

5.7.2 Photonic Preparation: Fusion Gates

For photonic qubits, cluster states are created using fusion gates:

Generate Bell pairs: Create many \(|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)\) states
Fuse pairs: Perform Bell measurements between qubits from different pairs
Success: With probability \(\frac{1}{2}\), fusion creates a larger entangled state
Repeat: Fuse many pairs to create large cluster states

Advantage: Only requires single-photon sources and linear optical elements (beamsplitters, detectors).

This is why photonic quantum computers use MBQC!

5.8 Measuring Graph States

5.8.1 Single-Qubit Measurement

When you measure qubit \(i\) in a graph state:

Z-basis measurement (outcome \(s \in \{0,1\}\)):

Remove qubit \(i\) from graph
Apply \(Z^s\) correction to all neighbors of \(i\)

X-basis measurement:

Remove qubit \(i\) and all edges touching \(i\)
No corrections needed
Remaining qubits: still in a graph state!

Y-basis measurement:

More complex update rules
Used less frequently in practice

5.8.2 Example: Measuring 3-Qubit Chain

Graph: \(1 — 2 — 3\)

Measure qubit 1 in X-basis:

Remove qubit 1
Remove edge \(1—2\)
Remaining graph: \(2 — 3\) (2-qubit chain)
No corrections

The state is now a 2-qubit cluster state on qubits 2-3!

5.8.3 Adaptive Measurements

In MBQC, measurement bases adapt based on previous outcomes:

Example pattern:

Measure qubit 1 in X → outcome \(s_1\)
Measure qubit 2 in basis \(|\pm_\theta\rangle\) where \(\theta' = \theta + \pi s_1\)
Apply corrections based on \(s_1, s_2\)

This feed-forward is what makes MBQC universal.

5.9 Stabilizers Under Measurement

When measuring qubit \(i\), stabilizers update:

Before measurement: Stabilizers \(\{K_1, \ldots, K_n\}\)

After measuring qubit \(i\) with outcome \(s\):

Fix outcome: Replace \(K_i\) with \((-1)^s Z_i\) (Z-basis) or \((-1)^s X_i\) (X-basis)
Propagate: Update other stabilizers by multiplying with \(K_i\) to eliminate dependence on qubit \(i\)
Reduce: New stabilizer group has \(n-1\) generators (one qubit measured out)

This keeps the stabilizer representation efficient throughout the measurement process.

5.10 2D Cluster States and Universality

Universal Resource Theorem

Any quantum circuit of depth \(d\) on \(n\) qubits can be simulated on a 2D cluster state of size \(O(d \times n)\) using only single-qubit measurements.

Why 2D specifically?

1D clusters can only simulate constant-depth circuits
2D clusters are universal for any depth
3D clusters offer no additional computational power

Practical significance: A large 2D cluster state is a “universal quantum computer in a box” - all computation is performed by measurement choices.

5.11 Summary

In this chapter, you learned:

✅ Graph states are defined by simple graphs and \(CZ\) gates ✅ Stabilizer formalism provides polynomial classical representation ✅ Graph state stabilizers: \(K_i = X_i \prod_{j \in N(i)} Z_j\) ✅ Stabilizers enable efficient simulation of Clifford operations ✅ Local complementation transforms graphs via local unitaries ✅ Photonic cluster states created via fusion gates ✅ Measuring graph states preserves graph structure ✅ 2D cluster states are universal for quantum computation

5.12 Exercises

5.12.1 Exercise 5.1: Stabilizer Verification

For the 2-qubit graph state on \(1 — 2\), verify that \(K_2 = Z_1 X_2\) stabilizes: \[ |G\rangle = \frac{1}{2}(|00\rangle + |01\rangle + |10\rangle - |11\rangle) \]

Solution →

5.12.2 Exercise 5.2: 4-Qubit Chain Stabilizers

Write down the four stabilizer generators for a 4-qubit linear cluster state: \[ 1 — 2 — 3 — 4 \]

Solution →

5.12.3 Exercise 5.3: Stabilizer Commutation

Prove that the stabilizers \(K_1 = X_1 Z_2\) and \(K_2 = Z_1 X_2 Z_3\) commute: \[ K_1 K_2 = K_2 K_1 \]

Solution →

5.12.4 Exercise 5.4: Local Complementation

Starting with a 4-qubit path graph \(1 — 2 — 3 — 4\), apply Hadamard to qubit 3 using local complementation rules. Draw the resulting graph.

Solution →

5.12.5 Exercise 5.5: Measurement Update

For a 3-qubit chain \(1 — 2 — 3\) with stabilizers: \[ K_1 = X_1 Z_2, \quad K_2 = Z_1 X_2 Z_3, \quad K_3 = Z_2 X_3 \]

If qubit 1 is measured in the X-basis with outcome 0, what are the stabilizers for the remaining 2-qubit state?

Solution →

5.12.6 Exercise 5.6: Graph State Entanglement

For a star graph (one central qubit connected to \(n\) outer qubits), calculate the entanglement entropy between the central qubit and the rest.

Solution →

5.12.7 Exercise 5.7: Resource Comparison

Estimate the number of qubits needed in a 2D cluster state to simulate: (a) Grover’s algorithm on 10 qubits (b) Quantum Fourier Transform on 20 qubits

Solution →

Next: Chapter 6: Measurement Patterns - Compiling circuits to MBQC