Classical simulation: tensor networks, stabilizer methods, Pauli propagation
The best way to test a quantum computer is to try very hard to simulate it on a classical one. Storing a general state of 50 qubits needs 18 petabytes, but most states that real devices produce are not general. They carry limited entanglement, or are close to stabilizer states, or the observables of interest depend only on a small part of the dynamics. Each structure is a loophole a classical algorithm can exploit, and each tells you precisely what a quantum device must do to escape it.
On the plate: how much entanglement a circuit creates, and what that costs to store.
Matrix product states
Cut a chain of qubits in two. Any state can be written as a Schmidt decomposition across the cut, , and the number of terms measures entanglement across that cut. A matrix product state (MPS) stores one small tensor per qubit, of size , so memory grows as rather than . Guifré Vidal showed in 2003 how to simulate circuits this way, truncating to the largest Schmidt values after each gate. Ground states of gapped one-dimensional systems obey an area law, needing only modest ; this is why the density-matrix renormalization group works so well. Projected entangled pair states (PEPS) extend the idea to two dimensions, and contracting them approximately, recently with belief propagation borrowed from coding theory (Chapter 136), is what Tindall and colleagues used against IBM’s 2023 experiment. Román Orús reviewed tensor networks in 2014. Established
Entanglement grows; memory follows
Choose a 12-qubit state: , , or of depth 3 (layers of random two-qubit gates between neighbours). The plate computes the Schmidt spectrum at the middle cut exactly. Keep 8 values and see the truncation error. Each layer can at most double the bond dimension, so shallow circuits are cheap; deep random circuits saturate at and the MPS is no cheaper than the full vector. Established
Stabilizers, magic, and Pauli propagation
Clifford circuits are efficiently simulable whatever their entanglement (Gottesman–Knill, Chapter 108). Sergey Bravyi and David Gosset showed in 2016 that circuits with few T gates can be simulated at a cost exponential only in the T-count, through the stabilizer rank of magic states. So the classical cost of a circuit is set by two resources: entanglement and magic. A third approach works in the Heisenberg picture: Pauli propagation evolves the observable backwards through the circuit, expands it in Pauli strings, and discards strings with tiny coefficients or high weight. Noise helps it, because noise damps high-weight strings. Begušić, Gray and Chan used sparse Pauli dynamics against IBM’s 2023 utility experiment. Any claim of quantum advantage must beat all three. Established
What you now have
Schmidt decomposition and bond dimension, MPS and PEPS, the area law, belief-propagation contraction, truncation error, stabilizer-rank simulation, Pauli propagation, and entanglement and magic as the two sources of classical hardness.
· · ·
Three questions to carry with you.
And one to work out. An MPS of 100 qubits with , at 16 bytes per number: how many gigabytes?
Sources: G. Vidal, Phys. Rev. Lett. 91, 147902 (2003). R. Orús, Ann. Phys. 349, 117 (2014). S. Bravyi and D. Gosset, Phys. Rev. Lett. 116, 250501 (2016). J. Tindall et al., PRX Quantum 5, 010308 (2024). T. Begušić, J. Gray and G. K.-L. Chan, Sci. Adv. 10, eadk4321 (2024). Checked by the plate: exact Schmidt spectra by diagonalizing the 64 × 64 reduced matrix.