Tensor network contraction
Why the contraction order is the whole game, and treewidth scores it.
Contraction order is the cost
Contracting a tensor network means summing over its internal indices, and the order you do it in determines the size of the largest intermediate tensor you ever hold in memory. That largest intermediate is exponential in the treewidth of the network — so finding a good contraction order is finding a good tree decomposition.
This is why state-of-the-art quantum-circuit simulators are, under the hood, treewidth heuristics: they search elimination orderings to minimize the width of the contraction, because the width is the exponent in both time and memory.
From bond dimension to width
The cost is more precisely exponential in the width times the log of the bond dimension. For a qubit circuit the bond dimension is 2, so the exponent is essentially the treewidth itself. Raise the bond dimension — qudits, fused gates — and you scale the same exponent.
Questions
Is finding the optimal contraction order NP-hard?
Yes — it is equivalent to computing treewidth, which is NP-hard. Simulators use the same heuristics (min-fill, greedy) that the treewidth community uses.
Why does memory blow up during contraction?
Because intermediate tensors are exponential in the width of the cut you are contracting across. A bad order creates a huge intermediate even if the final answer is a single number.