On the Optimal Linear Contraction Order of Tree Tensor Networks, and Beyond

Abstract

The contraction cost of a tensor network depends on the contraction order. However, the optimal contraction ordering problem is known to be NP-hard. We show that the linear contraction ordering problem for tree tensor networks admits a polynomial-time algorithm, by drawing connections to database join ordering. The result relies on the adjacent sequence interchange property of the contraction cost, which enables a global decision of the contraction order based on local comparisons. Based on that, we specify a modified version of the IKKBZ database join ordering algorithm to find the optimal tree tensor network linear contraction order. Finally, we extend our algorithm as a heuristic to general contraction orders and arbitrary tensor network topologies.

Journal version: 16 pages, 14 figures

References in corpus (11)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• The density-matrix renormalization group in the age of matrix product states
• Characterizing Quantum Supremacy in Near-Term Devices
• Simulating quantum computation by contracting tensor networks
• Low-Rank Tensor Networks for Dimensionality Reduction and Large-Scale Optimization Problems: Perspectives and Challenges PART 1
• Tensor product methods and entanglement optimization for ab initio quantum chemistry
• Tensor Networks for Dimensionality Reduction and Large-Scale Optimizations. Part 2 Applications and Future Perspectives
• Hyper-optimized tensor network contraction
• Faster identification of optimal contraction sequences for tensor networks
• An adaptive algorithm for quantum circuit simulation
• Improving the efficiency of variational tensor network algorithms