Concept record · edition 0.1.0
Contraction complexity
The cost of evaluating a tensor network, governed by the contraction order chosen and by structural properties of the network graph such as its treewidth.
Why it matters
Contraction order search, not tensor arithmetic, is often what decides whether a network is evaluable at all.
What this does not establish
Exact contraction of general networks is computationally hard; hardware acceleration changes the constant factor, not the complexity class.
Claims using this concept
- tn-008 · Established resultThe cost of contracting a tensor network is governed by the contraction order and by structural properties of the network graph such as its treewidth.
- tn-009 · Established resultPEPS extend tensor networks beyond one dimension, but exact contraction of PEPS is computationally hard.
- tn-011 · Established resultClassical tensor-network contraction has been reported to solve the Sycamore random-circuit sampling problem, narrowing the advantage originally claimed for that specific task.
- tn-014 · Active researchNo source in this atlas establishes that classical tensor-network contraction generally outperforms quantum hardware on industrial optimization workloads.
Sources
primary paper · identifier verified
Simulating quantum computation by contracting tensor networks
Igor L. Markov, Yaoyun Shi · 2005
arXiv:quant-ph/0511069
Connects the cost of contracting a tensor network to the treewidth of its graph, which is the structural quantity behind contraction-order search.
Source record →primary paper · identifier verified
The computational complexity of PEPS
Norbert Schuch, Michael M. Wolf, Frank Verstraete, J. Ignacio Cirac · 2006
arXiv:quant-ph/0611050
Establishes hardness results for contracting PEPS — the reason higher-dimensional tensor networks are approximated, not contracted exactly.
Source record →