Graph State

Graph state is a multi-qubit entangled state defined on an arbitrary graph structure, where each qubit corresponds to a vertex and entanglement is imposed via CZ gates on edges. Graph states generalize cluster states and are the resource for measurement-based quantum computing.

A graph state is constructed from an undirected graph $G = (V, E)$:

1. Prepare each qubit (vertex) in state $|+\rangle$
2. Apply CZ gates between all pairs of qubits connected by edges: $\text{CZ}_{i,j}$ for each $(i, j) \in E$

The resulting entangled state is the graph state corresponding to graph $G$.

Graph states are stabilizer states, defined by commuting Pauli stabilizers. For each vertex $i$, the stabilizer generator is:

$$S_i = X_i \prod_{j \sim i} Z_j$$

where the product runs over all neighbors $j$ of $i$. All stabilizers commute, and the graph state is the unique $+1$ eigenstate of all stabilizers.

• 1D chain: linear graph yields cluster-like entanglement suitable for sequential computation
• 2D lattice: rectangular grid enables universal quantum computation via adaptive measurement
• General graphs: arbitrary topology allows tailoring entanglement to specific algorithms
• Tree graphs: no cycles; fewer stabilizer constraints but still highly entangled
• Periodic boundaries: toroidal topology enables topological order and protection against errors

• Deterministic preparation: CZ gates on prepared $|+\rangle$ states always yield the same graph state
• Local complementation: graph isomorphisms under local complementation produce the same graph state
• Entanglement structure: non-local correlations follow graph connectivity; isolated vertices are product states
• Measurement-based computation: implement quantum gates through adaptive single-qubit measurements without unitary rotations

1. Prepare graph state matching circuit architecture
2. Measure qubits sequentially in bases determined by classical computation logic
3. Measurement outcomes (eigenvalues ±1) reveal syndrome and determine subsequent measurement angles
4. Teleport quantum information through graph via measurements
5. Final unmeasured qubits encode output state

This model demonstrates that quantum computation requires only measurement (no unitary gates needed post-preparation).

• Universal quantum computation: 2D lattice graphs support arbitrary quantum algorithms
• Quantum error correction: planar graphs yield topological codes (e.g., surface codes) with local error detection
• Quantum networks: arbitrary graphs model distributed quantum systems
• Entanglement certification: graph structure defines required correlations for certification
• Quantum simulation: specific graphs encode Hamiltonian ground states of spin systems

Graph states with Clifford measurements only (X, Y, Z bases) can be simulated classically via the Gottesman-Knill theorem. Measurement outcomes are computable in polynomial time via Gaussian elimination on the stabilizer group.

Cluster states are graph states on regular lattices (1D chains, 2D grids, etc.). Cluster states are a special case of general graph states where the underlying graph has lattice structure.

On different platforms:

• Photonic: probabilistic creation via post-selection; linear cluster states are practical
• Trapped ions: CZ gates between all pairs or restricted subsets create limited topologies
• Superconducting qubits: mediated two-qubit interactions; bipartite connectedness limits topologies
• Neutral atoms: Rydberg blockade enables arbitrary nearest-neighbor connectivity

Creating large graph states requires:

• Maintaining superposition across all qubits during entanglement generation
• Suppressing two-qubit gate errors during CZ gate application
• Global coherence time longer than circuit depth

Scaling to thousands of qubits remains a significant experimental challenge due to accumulated gate errors and decoherence.