A graph state is where elementary graph theory meets multipartite entanglement. The vertices label qubits, the edges specify entangling gates, and the resulting state has enough algebraic structure to be verified without storing its exponentially large state vector.
From a random graph to a quantum state
A graph is a pair G = (V,E). The vertex set V contains the objects and the edge set E records which pairs are connected. Equivalently, an adjacency matrix Γ has Γij = 1 when vertices i and j share an edge and zero otherwise.
In the Erdős–Rényi model G(n,p), every possible edge is included independently with probability p. A random regular graph instead fixes the degree of every vertex and randomizes which vertices are connected. These ensembles are useful theoretical models, but the circuit in this repository is not produced by naively drawing all-to-all edges from G(n,p). It uses a hardware-aware brickwork construction discussed in part 2.
For any simple graph, assign one qubit to every vertex, prepare every qubit in |+⟩, and apply a controlled-Z gate for every edge:
\[|G\rangle = \prod_{(i,j)\in E} CZ_{ij}\, |+\rangle^{\otimes |V|}.\]A CZ gate contributes a minus sign only to the |11⟩ component of its two qubits. The amplitudes therefore acquire a phase pattern determined by the graph’s adjacency matrix. The classical graph is compact, while the quantum state occupies a Hilbert space of dimension 2|V|.
The stabilizer description
Every vertex v defines a Pauli operator
\[K_v = X_v \prod_{u\in N(v)} Z_u,\]where N(v) is the neighbourhood of v. The graph state is the simultaneous +1 eigenstate of all these commuting generators:
\[K_v |G\rangle = |G\rangle \qquad \text{for every } v\in V.\]Products of the generators form the full stabilizer group. This gives two descriptions of the same state: a graph of CZ edges and an algebra of Pauli symmetries. The first is intuitive for construction; the second is ideal for verification.
What is being sampled?
If the graph state were measured only in the computational basis, its structure would be too easy to miss. Random-graph sampling therefore measures the state in a product basis obtained from local rotations. If R denotes those rotations and x is an output bit string, the target distribution is
\[p(x)=|\langle x|R|G\rangle|^2.\]The experimental task is to draw samples from p(x), not to print the full distribution. The full table contains exponentially many probabilities. A useful experiment must therefore combine a hard sampling task with checks that can still be evaluated efficiently.
Why random graphs are interesting
The connectivity of a graph controls entanglement across cuts. Dense or suitably random graph states can have large binary adjacency rank across many bipartitions, which forces large Schmidt rank and challenges matrix-product-state simulations. Measuring graph states in random product bases also connects the problem to IQP circuits and measurement-based quantum computation.
Complexity results for random regular graph states provide important motivation, including anticoncentration and measurement-based universality in specified degree regimes. They do not automatically prove that this one fixed hardware instance is classically hard. The repository therefore separates general theory, properties measured for the chosen circuit, and empirical classical benchmarks.
Further reading
- Ghosh, Hangleiter and Helsen: Random regular graph states are complex at almost any depth
- Wei: Measurement-Based Quantum Computation
Part 2 shows how the repository turns this abstract graph-state idea into a circuit that respects nearest-neighbour hardware connectivity.