title: 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 on the order in which the index sums are evaluated, and determination of the operation-minimizing 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 memoization, but these approaches are impractical for many of the larger tensor network ansätze 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-minimizing 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 Evenbly and Pfeifer, Phys. Rev. B 89, 245118 (2014), respectively, is supplied.
authors.affiliation: Perimeter Institute for Theoretical Physics, 31 Caroline St. N, Waterloo Ontario N2L 2Y5, Canada.
authors.forename: Robert N C
authors.initials: RN
authors.lastname: Pfeifer
authors.affiliation: Department of Physics and Astronomy, Ghent University, Krijgslaan 281-S9, B-9000 Ghent, Belgium.
authors.forename: Jutho
authors.initials: J
authors.lastname: Haegeman
authors.affiliation: Perimeter Institute for Theoretical Physics, 31 Caroline St. N, Waterloo Ontario N2L 2Y5, Canada and Department of Physics and Astronomy, Ghent University, Krijgslaan 281-S9, B-9000 Ghent, Belgium and Vienna Center for Quantum Science, Universität Wien, Boltzmanngasse 5, A-1090 Wien, Austria.
authors.forename: Frank
authors.initials: F
authors.lastname: Verstraete
mesh_terms: D000465:Algorithms; D008962:Models, Theoretical; D011789:Quantum Theory; D013997:Time Factors