151
Part Three · E · Hardware, simulation and practice

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, ∑i=1χλi∣Li⟩∣Ri⟩\sum_{i=1}^{\chi}\lambda_i|L_i\rangle|R_i\rangle, and the number of terms χ\chi measures entanglement across that cut. A matrix product state (MPS) stores one small tensor per qubit, of size 2×χ×χ2\times\chi\times\chi, so memory grows as nχ2n\chi^2 rather than 2n2^n. Guifré Vidal showed in 2003 how to simulate circuits this way, truncating to the largest χ\chi Schmidt values after each gate. Ground states of gapped one-dimensional systems obey an area law, needing only modest χ\chi; 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 χ=\chi = 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 χ=2n/2\chi = 2^{n/2} 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.

How does MPS memory scale?tap
As n × 2 × χ² numbers, instead of 2ⁿ.
Why are shallow circuits easy for MPS?tap
Each layer of two-qubit gates can at most double the bond dimension across a cut.
Why does noise help Pauli propagation?tap
It suppresses high-weight Pauli strings, which can then be dropped.

And one to work out. An MPS of 100 qubits with χ=1000\chi = 1000, at 16 bytes per number: how many gigabytes?

GB =

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.

Next · Chapter 152
Programming practice: Qiskit, Cirq, PennyLane

Same circuit, three frameworks. Spot why their outputs differ.

Turn the page