TY - JOUR

T1 - Faster identification of optimal contraction sequences for tensor networks

AU - Pfeifer, Robert N. C.

AU - Haegeman, Jutho

AU - Verstraete, Frank

PY - 2014/9/30

Y1 - 2014/9/30

N2 - 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)PRBMDO1098-012110.1103/PhysRevB.89.245118, respectively, is supplied.

AB - 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)PRBMDO1098-012110.1103/PhysRevB.89.245118, respectively, is supplied.

UR - http://www.scopus.com/inward/record.url?scp=84908046828&partnerID=8YFLogxK

U2 - 10.1103/PhysRevE.90.033315

DO - 10.1103/PhysRevE.90.033315

M3 - Article

C2 - 25314572

AN - SCOPUS:84908046828

SN - 1539-3755

VL - 90

SP - 033315-1-033315-18

JO - Physical Review E - Statistical, Nonlinear, and Soft Matter Physics

JF - Physical Review E - Statistical, Nonlinear, and Soft Matter Physics

IS - 3

M1 - 033315

ER -