Substrate · Classical Simulation Limits

Tensor-Network Contraction Complexity Profile

The algorithmic boundary of tensor-network contraction modeled via graph theory.

Contracting a tensor network means summing over its internal indices, and the largest intermediate tensor you must hold is exponential in the contraction's treewidth. Every profile below reads the same substrate through a different graph invariant and structural regime, and prices it with Ross’s Law.

Read the volume (PDF, 895 pp)

A tensor network is the cleanest place to watch Ross’s Law work, because here the meter is not a metaphor — it is the literal cost of the computation. Each tensor is a vertex; each shared index is an edge. To contract the network you sum over those indices one cut at a time, and the largest intermediate tensor you are ever forced to hold is exponential in the width of the best contraction order. That width is the treewidth of the interaction graph. The exponent is not a bound on the cost. It is the cost.

So the question “how expensive is this contraction?” collapses, exactly, into “how far is this graph from a tree?” Five graph invariants answer that question from five angles. They do not disagree; they triangulate. Each one reads the same network and reports where it sits between two extremes: a shadow regime, where the structure is nearly separable and the cost stays tame, and a mirror regime, where the structure is an irreducible whole and the exponential runs away. Between them lies the equilibrium regime — the critical band where the network is poised on the edge of tractability.

classical cost ≈ exp(Θ(tw(G)))Ross’s Law, stated for this substrate: the time to simulate a contraction classically scales as the exponential of its treewidth. Everything below is one invariant’s view of where on that exponent a given network falls.

Treewidth bounds

Treewidth is the meter itself — the size of the largest bag in the best tree-shaped scaffold of the interaction graph, minus one. It is the amount of state you must carry across the worst cut of the contraction.

Shadow
tw(G) = O(1) — a chain or tree of tensors. The contraction sweeps left to right holding a constant-size boundary; cost is linear in the network and the exponential collapses to a constant.
Equilibrium
tw(G) = Θ(log N) — mild branching, the boundary grows logarithmically. Still polynomial to contract, but the constant in the exponent now matters; this is where careful ordering pays off.
Mirror
tw(G) = Ω(N) — a 2D grid or all-to-all coupling. No contraction order avoids a boundary that scales with the system, and the cost is genuinely exponential. This is quantum supremacy territory.

Graph degeneracy

Degeneracy is the cheap proxy: the densest interlinked core the graph cannot shed by peeling low-degree vertices. It is polynomial to compute and lower-bounds the treewidth, so it is the first number to check when you want to know which regime you are in without solving the hard problem.

Shadow
d(G) = O(1) — sparse enough to peel down to nothing. No dense core, so no obstruction to a narrow contraction.
Equilibrium
d(G) = Θ(log N) — a core that thickens slowly. The backbone is forming but has not yet locked.
Mirror
d(G) = Ω(N) — an irreducible core no small separator resolves. The degeneracy certifies the treewidth is large; the exponential is unavoidable.

Volume-law entanglement

For tensor networks the bridge to physics is exact: the entanglement entropy across a cut equals the log of the bond dimension you must carry there. Area-law states are shadow; volume-law states are mirror. This is why the meter and the physics are the same statement in two languages.

Shadow
S(ρ) ∝ ∂A — area law. Entanglement scales with the boundary, bond dimension stays bounded, and a matrix-product state captures it efficiently.
Equilibrium
S(ρ) ∝ log N — the critical scaling of a 1D system at a phase transition. Bond dimension grows polynomially; still simulable, but the cheap representation is straining.
Mirror
S(ρ) ∝ |A| — volume law. Entanglement fills the region, bond dimension is exponential, and no efficient classical tensor representation exists.

Fiedler-value connectivity

The Fiedler value — the second-smallest eigenvalue of the graph Laplacian — measures how tightly the network holds together under its weakest cut. It is the census taker: polynomial to compute, and it tells you whether the graph has a clean place to split.

Shadow
λ₂ → 0 — nearly disconnected. A bottleneck exists, so the contraction can be cut there cheaply.
Equilibrium
λ₂ = Θ(1/N) — weakly connected, a faint seam. A separator exists but it is not free.
Mirror
λ₂ = Ω(1) — an expander. The graph resists every cut equally; there is no seam, and the contraction stays maximally wide throughout.

Bipartite treewidth

The bipartite cut is the worst-case witness: split the tensors into two halves and ask how wide the interface between them must be. It pins the cost from below for the hardest bisection the network admits.

Shadow
twᵇ(G) = O(1) — the two halves touch along a constant-size interface. Trivially separable.
Equilibrium
twᵇ(G) = Θ(√N) — the planar-grid signature, the interface scaling as the perimeter of a 2D region. Sub-exponential but not cheap.
Mirror
twᵇ(G) = Ω(N) — every bisection cuts a linear number of indices. The network is irreducibly two-sided and the cost is full exponential.

The same substrate, four other ways

The contraction graph is one instance of the universal meter. The same five invariants read these substrates too:

Vector Databases & RAGNeural-Network Quantum StatesBiological ConnectomesSocial Clique Networks
The full matrix