Claim record · edition 0.1.0
tn-008Established result
The cost of contracting a tensor network is governed by the contraction order and by structural properties of the network graph such as its treewidth.
Quantum circuits and spin models alike can be expressed as tensor networks, and the feasibility of evaluating them depends on graph structure rather than on the arithmetic of any single contraction step.
Limits of this claim
Favourable structure is a property of the instance. Hardware acceleration improves the constant factor; it does not change the complexity class, and a dense problem graph produces a network with no good contraction order to find.
Supporting 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 →