Faster identification of optimal contraction sequences for tensor networks

Area of Science:

• Computational physics
• Quantum many-body physics
• Quantum chemistry

Background:

• Efficient tensor expression evaluation is crucial for quantum many-body physics, loop quantum gravity, and quantum chemistry.
• Determining the optimal contraction sequence for tensor networks is NP-hard, with current methods being computationally expensive for large systems.

Purpose of the Study:

• To develop a more efficient algorithm for finding the operation-minimizing contraction sequence of tensor networks.
• To improve upon existing exhaustive search methods that are impractical for large-scale quantum many-body physics problems.

Main Methods:

• A modified search algorithm incorporating enhanced pruning techniques was developed.
• The algorithm guarantees identification of an optimal operation-minimizing contraction sequence for single tensor networks.

Main Results:

• The enhanced pruning algorithm demonstrates a performance increase of several orders of magnitude compared to previous methods.
• The algorithm maintains the guarantee of finding the optimal contraction sequence.

Conclusions:

• The developed algorithm offers a significant computational advantage for evaluating tensor expressions in fields like quantum many-body physics.
• A reference implementation in MATLAB is provided, compatible with existing network contractors.