Faster identification of optimal contraction sequences for tensor networks

Abstract

The efficient evaluation of tensor expressions involving sums over multiple indices is of significant importance to many fields of research, including quantum many-body physics, loop quantum gravity, and quantum chemistry. The computational cost of evaluating an expression may depend strongly upon the order in which the index sums are evaluated, and determination of the operation-minimising contraction sequence for a single tensor network (single term, in quantum chemistry) is known to be NP-hard. The current preferred solution is an exhaustive search, using either an iterative depth-first approach with pruning or dynamic programming and memoisation, but these approaches are impractical for many of the larger tensor network Ansaetze encountered in quantum many-body physics. We present a modified search algorithm with enhanced pruning which exhibits a performance increase of several orders of magnitude while still guaranteeing identification of an optimal operation-minimising contraction sequence for a single tensor network. A reference implementation for MATLAB, compatible with the ncon() and multienv() network contractors of arXiv:1402.0939 and arXiv:1310.8023 respectively, is supplied.

25 pages, 12 figs, 2 tables, includes reference implementation of algorithm, v2.01. Update corrects the display of contraction sequences involving single-tensor traces (i.e. where an index in the input appears twice on the same tensor)

References in corpus (17)

• The density-matrix renormalization group in the age of matrix product states
• Classical simulation of infinite-size quantum lattice systems in one spatial dimension
• A class of quantum many-body states that can be efficiently simulated
• Classical simulation of infinite-size quantum lattice systems in two spatial dimensions
• Interacting anyons in topological quantum liquids: The golden chain
• Simulating Strongly Correlated Quantum Systems with Tree Tensor Networks
• Characterizing topological order by studying the ground states of an infinite cylinder
• Entanglement renormalization and topological order
• Spin-orbital quantum liquid on the honeycomb lattice
• Entanglement renormalization, scale invariance, and quantum criticality
• Collective states of interacting Fibonacci anyons
• A class of highly entangled many-body states that can be efficiently simulated
• Simulation of anyons with tensor network algorithms
• Scaling of entanglement entropy in the (branching) multi-scale entanglement renormalization ansatz
• Anyonic entanglement renormalization
• Improving the efficiency of variational tensor network algorithms
• Symmetry protected entanglement renormalization

Cited by in corpus (45)

• The ITensor Software Library for Tensor Network Calculations
• Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks
• Hyper-optimized tensor network contraction
• Lecture Notes of Tensor Network Contractions
• The Tensor Networks Anthology: Simulation techniques for many-body quantum lattice systems
• Tensor Network Algorithms: a Route Map
• Two- and three-pion finite-volume spectra at maximal isospin from lattice QCD
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• Renormalization of tensor networks using graph independent local truncations
• qTorch: The Quantum Tensor Contraction Handler
• The Tensor Network Theory Library
• Tensor Networks for Big Data Analytics and Large-Scale Optimization Problems
• Tensor Renormalization Group with Randomized Singular Value Decomposition
• Anomalies and entanglement renormalization
• An adaptive algorithm for quantum circuit simulation
• Automatic derivation of fermionic many-body theories based on general Fermi vacua
• Entanglement renormalization for disordered systems
• Density-matrix renormalization group: a pedagogical introduction
• Tensor networks for quantum computing
• Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation
• Q${}^2$Chemistry: A quantum computation platform for quantum chemistry
• Benchmarking treewidth as a practical component of tensor-network--based quantum simulation
• Finite Density Matrix Renormalisation Group Algorithm for Anyonic Systems
• Automatic Contraction of Unstructured Tensor Networks
• Minimum Cost Loop Nests for Contraction of a Sparse Tensor with a Tensor Network
• Efficient Contraction of Large Tensor Networks for Weighted Model Counting through Graph Decompositions
• Algorithms for Tensor Network Contraction Ordering
• Connector tensor networks: a renormalization-type approach to quantum certification
• Efficient Decomposition of High-Rank Tensors
• Convergence and Quantum Advantage of Trotterized MERA for Strongly-Correlated Systems
• Méthodes de calcul avec réseaux de tenseurs en physique (Basic tensor network computations in physics)
• TTC: A high-performance Compiler for Tensor Transpositions
• Avoidance, Adjacency, and Association in Distributed Systems Design
• The landscape of software for tensor computations
• Simulation of Quantum Many-Body Systems on Amazon Cloud
• Scaling of contraction costs for entanglement renormalization algorithms including tensor Trotterization and variational Monte Carlo
• The Cytnx Library for Tensor Networks
• Carving-width and contraction trees for tensor networks
• GuiTeNet: A graphical user interface for tensor networks
• On the Optimal Linear Contraction Order of Tree Tensor Networks, and Beyond
• Les Houches Lecture Notes on Tensor Networks
• Maximal Simplification of Polyhedral Reductions
• SeQuant Framework for Symbolic and Numerical Tensor Algebra. I. Core Capabilities
• A-priori sparsification of Galerkin-based reduced order models
• Who can compete with quantum computers? Lecture notes on quantum inspired tensor networks computational techniques