Limits of Classical Simulation

Tensor networks are powerful, but they are not magic. They succeed only when the entanglement of the target state stays bounded; when it does not, the bond dimension explodes and the method falls back to exponential cost. Knowing where tensor networks fail is essential — it is the line that separates classically simulable quantum computation from the regime where quantum hardware can claim an advantage.

The single failure mode: entanglement growth

Every limit of tensor networks traces back to one quantity: the entanglement entropy across a cut, and how it grows. The bond dimension needed for a faithful representation is

\chi \gtrsim 2^{S_{\max}} ,

where $S_{\max}$ is the largest entanglement entropy across any cut. So:

If $S$ stays $O(1)$ (1D area law), $\chi$ is constant — easy.
If $S$ grows logarithmically (1D critical), $\chi$ grows polynomially — still feasible.
If $S$ grows linearly with subsystem size (volume law), $\chi$ grows exponentially — tensor networks fail.

When entanglement runs away

Three common situations push entanglement into the volume-law regime:

Deep, generic circuits. A random circuit on $n$ qubits builds up entanglement roughly linearly in its depth. After about $O(n)$ layers the half-chain entropy saturates near its maximum $\sim n/2$ , demanding $\chi \sim 2^{n/2}$ . This is the design principle behind random-circuit sampling experiments used to argue for quantum advantage.
Long-time dynamics (quench / thermalisation). Evolving a generic state for a long time grows entanglement linearly in time until it thermalises into a volume-law state. MPS time evolution (TEBD) is accurate only up to a time that grows logarithmically with the affordable $\chi$ — the "entanglement barrier".
Genuinely 2D or 3D systems. Even ground states obey only a 2D/3D area law, so the required PEPS bond dimension and its contraction cost climb steeply with linear size, as the previous lesson described.

Other structural obstacles

Beyond raw entanglement, two structural issues matter:

Contraction-order blow-up. Even a low-entanglement network can be expensive if its connectivity forces large intermediate tensors. For 2D and irregular networks, finding a good contraction order is itself NP-hard, and a bad order can make an otherwise feasible problem intractable.
The sign problem's cousin. Some quantities (like simulating real-time dynamics or certain fermionic systems) require near-cancellations between large terms, so even when storage is fine the precision demands explode. Tensor networks mitigate but do not eliminate these difficulties.

The link to quantum advantage

A claim of quantum advantage is, at bottom, a claim that no efficient classical method — tensor networks included — can reproduce the device's output. That is why advantage experiments deliberately target the volume-law regime: deep random circuits whose entanglement exceeds any affordable bond dimension. Conversely, every improvement in tensor-network contraction (better orders, larger $\chi$ , approximate sampling) chips away at such claims, which is why the boundary between "classically simulable" and "quantum-hard" keeps being renegotiated.

The practical heuristic

When you face a simulation, ask in order: What dimension is the system? Does its entanglement obey an area law? How deep or how long is the evolution? The answers estimate $S_{\max}$ , hence the required $\chi$ , hence whether a tensor-network simulation will fit in memory and time. Turning that reasoning into a concrete number is exactly what the module checkpoint asks you to do next.