Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation

Roman Schutski, Taras Khakhulin, Ivan Oseledets, Dmitry Kolmakov

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


Tensor networks are the main building blocks in various computational sciences, ranging from many-body theory and quantum computing to probability and machine learning. Here we propose a parallel algorithm for the contraction of tensor networks using probabilistic graphical models. Given a tensor network, this algorithm splits the contraction task almost optimally into subtasks, which can be contracted independently in parallel. Our approach is based on the heuristic solution of the μ-treewidth deletion problem in graph theory. We apply the resulting algorithm to the simulation of random quantum circuits and discuss the extensions for general tensor network contractions. According to our estimates, the lower bound on the simulation time of 1 million amplitudes of a 49-qubit circuit of depth 40 on the Summit supercomputer is >5 seconds.

Original languageEnglish
Article number062614
JournalPhysical Review A
Issue number6
Publication statusPublished - 28 Dec 2020
Externally publishedYes


Dive into the research topics of 'Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation'. Together they form a unique fingerprint.

Cite this