A Caltech Library Service

Hyper-optimized tensor network contraction

Gray, Johnnie and Kourtis, Stefanos (2021) Hyper-optimized tensor network contraction. Quantum, 5 . Art. No. 410. ISSN 2521-327X.

[img] PDF - Published Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


Tensor networks represent the state-of-the-art in computational methods across many disciplines, including the classical simulation of quantum many-body systems and quantum circuits. Several applications of current interest give rise to tensor networks with irregular geometries. Finding the best possible contraction path for such networks is a central problem, with an exponential effect on computation time and memory footprint. In this work, we implement new randomized protocols that find very high quality contraction paths for arbitrary and large tensor networks. We test our methods on a variety of benchmarks, including the random quantum circuit instances recently implemented on Google quantum chips. We find that the paths obtained can be very close to optimal, and often many orders or magnitude better than the most established approaches. As different underlying geometries suit different methods, we also introduce a hyper-optimization approach, where both the method applied and its algorithmic parameters are tuned during the path finding. The increase in quality of contraction schemes found has significant practical implications for the simulation of quantum many-body systems and particularly for the benchmarking of new quantum chips. Concretely, we estimate a speed-up of over 10,000× compared to the original expectation for the classical simulation of the Sycamore 'supremacy' circuits.

Item Type:Article
Related URLs:
URLURL TypeDescription
Gray, Johnnie0000-0001-9461-3024
Additional Information:This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. Published: 2021-03-15. We thank S. Boixo and B. Villalonga for useful feedback on the manuscript. JG acknowledges the Samsung Advanced Institute of Technology Global Research Partnership. SK was supported in part by funding from the Canada First Research Excellence Fund.
Funding AgencyGrant Number
Samsung Advanced Institute of TechnologyUNSPECIFIED
Canada First Research Excellence FundUNSPECIFIED
Record Number:CaltechAUTHORS:20210506-130409930
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:108992
Deposited By: Tony Diaz
Deposited On:06 May 2021 20:58
Last Modified:06 May 2021 20:58

Repository Staff Only: item control page