Caltech Logo

IQI Weekly Seminar

Tuesday, October 1, 2019
3:00pm to 4:00pm
Add to Cal
Annenberg 107
Automatic Tensor Network Contraction
Johnnie Gray, Postdoctoral Scholar, Imperial College London,

Abstract: 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 the subsequent classical computational effort and memory footprint. In this work, we adapt a variety of tools from graph theory and network science to the contraction path problem and implement new randomized protocols that find very high quality contraction paths for arbitrary and large tensor networks. In some cases the paths found are more than a billion times better than the most established current approach. We find that different underlying geometries suit different methods and therefore suggest 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 further raises the bar for practically demonstrating a quantum advantage.

For more information, please contact Bonnie Leung by email at bjleung@caltech.edu.