Faster identification of optimal contraction sequences for tensor networks

Robert N. C. Pfeifer*, Jutho Haegeman, Frank Verstraete

*Corresponding author for this work

Research output: Contribution to journalArticle

26 Citations (Scopus)

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

Original languageEnglish
Article number033315
Pages (from-to)033315-1-033315-18
Number of pages18
JournalPhysical Review E - Statistical, Nonlinear, and Soft Matter Physics
Volume90
Issue number3
DOIs
Publication statusPublished - 30 Sep 2014
Externally publishedYes

Fingerprint Dive into the research topics of 'Faster identification of optimal contraction sequences for tensor networks'. Together they form a unique fingerprint.

  • Cite this