A quantum state has exponentially many amplitudes, but that fact alone does not make it hard to simulate. Classical algorithms exploit structure. Random-graph sampling is designed to frustrate two of the most important structures: low entanglement and low magic.
Entanglement and the graph adjacency matrix
Split the vertices into two sets, A and B. Let ΓAB be the part of the graph’s adjacency matrix that records edges crossing the cut. For a graph state, the Schmidt rank across that bipartition is determined by a binary matrix rank:
\[\chi_{A|B}=2^{\operatorname{rank}_{GF(2)}(\Gamma_{AB})}.\]This is a remarkably direct bridge from graph theory to entanglement. If many independent edge patterns cross a cut, ΓAB has high rank and the state has many Schmidt coefficients.
Why this matters for tensor networks
A matrix-product state represents a chain by passing a bond index from one site to the next. The required bond dimension must be at least the Schmidt rank across the corresponding cut if the state is represented exactly. Low-entanglement states can therefore be compressed efficiently; high-cut-rank graph states cannot.
The brickwork circuit is local, but repeated layers spread correlations across the chain. Its difficulty for MPS is governed not simply by the number of CZ gates, but by the entanglement generated across the worst cuts. Approximate MPS simulation remains possible by truncating small Schmidt values, but convergence must then be measured rather than assumed.
Why entanglement is not enough
Graph states prepared only with Clifford gates can be highly entangled and still be efficiently simulated with the Gottesman–Knill stabilizer formalism. A tableau stores the action of Pauli generators without storing every amplitude. Entanglement can defeat a small-bond MPS while leaving a stabilizer simulator almost effortless.
Magic closes the Clifford shortcut
The final face-state basis rotation is non-Clifford. Stabilizer-based algorithms handle such a circuit by expressing the non-Clifford resource as a combination of stabilizer states or by truncating a related expansion. The cost is controlled by a magic measure such as stabilizer rank or stabilizer extent, not by entanglement alone.
That gives the benchmark a two-axis design:
- large graph cut rank targets tensor-network compression;
- non-Clifford measurement rotations target stabilizer decompositions.
Modern hybrid methods can move Clifford structure into a tableau and reserve a tensor network for the magic degrees of freedom. They may outperform either naïve method. This is why no single entanglement or magic number proves classical hardness for the fixed instance.
How the repository tests the classical side
The project uses a ladder of increasingly demanding checks:
- exact statevector simulation for small induced circuits;
- exact and truncated MPS on the same small circuits;
- larger MPS runs with explicit bond-dimension convergence checks;
- extended-stabilizer sampling for a measured size range;
- observable-specific Majorana propagation, clearly separated from full-distribution sampling.
Each method answers a different question. A fast selected-observable estimator is not automatically a sampler, and a fast low-bond MPS is not automatically accurate. A defensible comparison must specify the output task and the error target before comparing time.
Further reading
- Bravyi et al.: Simulation of quantum circuits by low-rank stabilizer decompositions
- Clifford-augmented matrix-product-state simulation
Part 5 returns to the special advantage of graph states: despite the difficult sampling basis, their Clifford prefix provides Pauli symmetries that can be checked experimentally.