Benchmarking treewidth as a practical component of tensor network simulations

Area of Science:

• Computational physics
• Quantum information science
• Graph theory

Background:

• Tensor networks are crucial for simulating quantum many-body systems, but their computational cost depends heavily on contraction order.
• Finding optimal contraction sequences is NP-complete, posing a significant challenge for efficient simulation.
• Previous research often overlooked graph theory approaches, favoring specialized algorithms.

Purpose of the Study:

• To demonstrate the practical utility of treewidth-based methods for optimizing tensor network contractions.
• To compare the performance of treewidth algorithms against domain-specific methods in quantum simulation contexts.
• To provide an accessible software framework for evaluating and advancing tensor network simulation techniques.

Main Methods:

• Relating tensor network contraction sequences to optimal tree decompositions of their line graphs.
• Applying treewidth-based algorithms to multi-scale entanglement renormalization ansatz (MERA) datasets.
• Evaluating treewidth algorithms on quantum circuits generated by the quantum approximate optimization algorithm (QAOA).

Main Results:

• Treewidth-based algorithms show superior performance over domain-specific methods in several simulation regimes.
• The optimal algorithm choice is complex, depending on network density, expected complexity, and runtime constraints.
• An open-source software framework is introduced to facilitate reproducible research and exploration of competing methods.

Conclusions:

• Treewidth decomposition offers a powerful, practical approach to optimizing tensor network simulations.
• The developed framework enables broader adoption and further investigation into efficient quantum simulation algorithms.
• This work bridges graph theory and quantum information, paving the way for more efficient computational approaches.