Carving-width and contraction trees for tensor networks

Abstract

We study the problem of finding contraction orderings on tensor networks for physical simulations using a syncretic abstract data type, the $\text{contraction-tree}$, and explain its connection to temporal and spatial measures of tensor contraction computational complexity (nodes express time; arcs express space). We have implemented the Ratcatcher of Seymour and Thomas for determining the carving-width of planar networks, in order to offer experimental evidence that this measure of spatial complexity makes a generally effective heuristic for limiting their total contraction time.

16 pages, 7 figures, 1 table

References in corpus (4)

• Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
• Fast convergence of imaginary time evolution tensor network algorithms by recycling the environment
• The quantum FFT can be classically simulated
• Simulation of Quantum Many-Body Systems on Amazon Cloud