Faster identification of optimal contraction sequences for tensor networks

Autor(en)

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

Abstrakt

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 ansatze 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.

Organisation(en)

Quantenoptik, Quantennanophysik und Quanteninformation

Externe Organisation(en)

Perimeter Institute for Theoretical Physics, Ghent University

Journal

Physical Review E

Band

90

Anzahl der Seiten

18

ISSN

1539-3755

DOI

https://doi.org/10.1103/PhysRevE.90.033315

Publikationsdatum

09-2014

Peer-reviewed

Ja

ÖFOS 2012

103025 Quantenmechanik, 103036 Theoretische Physik

Schlagwörter

ASJC Scopus Sachgebiete

Condensed Matter Physics, Statistical and Nonlinear Physics, Statistics and Probability

Link zum Portal

https://ucrisportal.univie.ac.at/de/publications/c3046507-cc45-4610-84b6-6778fadb90db