Carving-width and contraction trees for tensor networks
arXiv:1908.11034
Abstract
We study the problem of finding contraction orderings on tensor networks for physical simulations using a syncretic abstract data type, the , 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.
arXiv comment16 pages, 7 figures, 1 table
References in corpus (9)
- Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
- Simulating quantum computation by contracting tensor networks
- Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks
- Faster identification of optimal contraction sequences for tensor networks
- Fast convergence of imaginary time evolution tensor network algorithms by recycling the environment
- The quantum FFT can be classically simulated
- Designing Multi-Commodity Flow Trees
- Benchmarking treewidth as a practical component of tensor-network--based quantum simulation
- Simulation of Quantum Many-Body Systems on Amazon Cloud