Algorithms for Tensor Network Contraction Ordering

Abstract

Contracting tensor networks is often computationally demanding. Well-designed contraction sequences can dramatically reduce the contraction cost. We explore the performance of simulated annealing and genetic algorithms, two common discrete optimization techniques, to this ordering problem. We benchmark their performance as well as that of the commonly-used greedy search on physically relevant tensor networks. Where computationally feasible, we also compare them with the optimal contraction sequence obtained by an exhaustive search. We find that the algorithms we consider consistently outperform a greedy search given equal computational resources, with an advantage that scales with tensor network size. We compare the obtained contraction sequences and identify signs of highly non-local optimization, with the more sophisticated algorithms sacrificing run-time early in the contraction for better overall performance.

arXiv comment10 pages, 10 figures

References in corpus (13)

• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Holographic duality from random tensor networks
• Studying Two Dimensional Systems With the Density Matrix Renormalization Group
• Tensor Network Renormalization
• Efficient Tree Tensor Network States (TTNS) for Quantum Chemistry: Generalizations of the Density Matrix Renormalization Group Algorithm
• Renormalization of tensor networks using graph independent local truncations
• Machine Learning by Unitary Tensor Network of Hierarchical Tree Structure
• Faster identification of optimal contraction sequences for tensor networks
• qTorch: The Quantum Tensor Contraction Handler
• Tensor Renormalization Group with Randomized Singular Value Decomposition
• Improving the efficiency of variational tensor network algorithms
• Benchmarking treewidth as a practical component of tensor-network--based quantum simulation
• Automatic Contraction of Unstructured Tensor Networks

Cited by in corpus (3)

• Jet: Fast quantum circuit simulations with parallel task-based tensor-network contraction
• Numerical Methods for Detecting Symmetries and Commutant Algebras
• Scaling of contraction costs for entanglement renormalization algorithms including tensor Trotterization and variational Monte Carlo