Matrix product states & bond dimension

The one-dimensional special case where the meter reads pathwidth.

MPS as bounded-width tensor networks

A matrix product state (MPS) represents a quantum state as a chain of tensors — a tensor network whose structure is a path. The bond dimension is the size of the indices linking neighboring tensors, and it is the exponential of the entanglement entropy across each cut.

Because the structure is a path, the relevant invariant is pathwidth, and the simulation cost is polynomial whenever the bond dimension stays bounded. MPS is the cleanest worked example of the meter: low entanglement ⇒ small bond dimension ⇒ efficient classical representation.

Generalizing the structure

Move from a path to a tree and you get a tree tensor network; to a grid and you get PEPS, where contraction is hard precisely because the grid has growing treewidth. The progression MPS → tree → PEPS is the progression from pathwidth to treewidth to intractable width.