Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Computing and Visualization in Science

Optimization problems in contracted tensor networks

Mike Espig, Wolfgang Hackbusch, Stefan Handschuh, Reinhold Schneider

Published Aug 1, 2011• 55 citations
Publisher
DOI
10.1007/s00791-012-0183-y

Related papers

Adiabatic Optimization of Tensor Networks

Christopher T. Olund, Snir Gazit, John McGreevy +1 more

Bulletin of the American Physical Society•Mar 8, 2018•0 citations

Towards a polynomial algorithm for optimal contraction sequence of tensor networks from trees

Jianyu Xu, Ling Liang, Lei Deng +3 more

The computational cost of contracting a tensor network depends on the sequence of contractions, but to decide the sequence of contractions with a minimal computational cost on an arbitrary network has been proved to be an NP-complete problem. In this work, we conjecture that the problem may be a polynomial one if we consider the computational complexity instead. We propose a polynomial algorithm for the optimal contraction complexity of tensor tree network, which is a specific and widely applied network structure. We prove that for any tensor tree network, the proposed algorithm can achieve a sequence of contractions that guarantees the minimal time complexity and a linear space complexity simultaneously. To illustrate the validity of our idea, numerical simulations are presented that evidence the significant benefits when the network scale becomes large. This work will have great potential for the efficient processing of various physical simulations and pave the way for the further exploration of the computational complexity of tensor contraction on arbitrary tensor networks.

Physical review. E•Oct 31, 2019•10 citations

Survey of Tensor Networks

Samuel Desrosiers, Glen Evenbly, Thomas E. Baker

Bulletin of the American Physical Society•Mar 5, 2019•0 citations

Optimized contraction scheme for tensor-network states

Z. Y. Xie, Haijun Liao, Rui-Zhen Huang +4 more

In the tensor-network framework, the expectation values of two-dimensional quantum states are evaluated by contracting a double-layer tensor network constructed from initial and final tensor-network states. The computational cost of carrying out this contraction is generally very high, which limits the largest bond dimension of tensor-network states that can be accurately studied to a relatively small value. We propose an optimized contraction scheme to solve this problem by mapping the double-layer tensor network onto an intersected single-layer tensor network. This reduces greatly the bond dimensions of local tensors to be contracted and improves dramatically the efficiency and accuracy of the evaluation of expectation values of tensor-network states. It almost doubles the largest bond dimension of tensor-network states whose physical properties can be efficiently and reliably calculated, and it extends significantly the application scope of tensor-network methods.

arXiv:1705.08577•Physical review. B./Physical review. B•Jul 20, 2017•54 citations

Algorithms for tensor network contraction ordering

Frank Schindler, Adam S. Jermyn

Contracting tensor networks is often computationally demanding. Well-designed contraction sequences can dramatically reduce the contraction cost. We explore the performance of simulated annealing and genetic algorithms, two common discrete optimization techniques, to this ordering problem. We benchmark their performance as well as that of the commonly-used greedy search on physically relevant tensor networks. Where computationally feasible, we also compare them with the optimal contraction sequence obtained by an exhaustive search. Furthermore, we present a systematic comparison with state-of-the-art tree decomposition and graph partitioning algorithms in the context of random regular graph tensor networks. We find that the algorithms we consider consistently outperform a greedy search given equal computational resources, with an advantage that scales with tensor network size. We compare the obtained contraction sequences and identify signs of highly non-local optimization, with the more sophisticated algorithms sacrificing run-time early in the contraction for better overall performance

•Jul 6, 2020•11 citations

DMRG Approach to Optimizing Two-Dimensional Tensor Networks

Katharine Hyatt, Miles Stoudenmire

Bulletin of the American Physical Society•Mar 5, 2020•0 citations
The computational cost of contracting a tensor network depends on the sequence of contractions, but to decide the sequence of contractions with a minimal computational cost on an arbitrary network has been proved to be an NP-complete problem. In this work, we conjecture that the problem may be a polynomial one if we consider the computational complexity instead. We propose a polynomial algorithm for the optimal contraction complexity of tensor tree network, which is a specific and widely applied network structure. We prove that for any tensor tree network, the proposed algorithm can achieve a sequence of contractions that guarantees the minimal time complexity and a linear space complexity simultaneously. To illustrate the validity of our idea, numerical simulations are presented that evidence the significant benefits when the network scale becomes large. This work will have great potential for the efficient processing of various physical simulations and pave the way for the further exploration of the computational complexity of tensor contraction on arbitrary tensor networks.
In the tensor-network framework, the expectation values of two-dimensional quantum states are evaluated by contracting a double-layer tensor network constructed from initial and final tensor-network states. The computational cost of carrying out this contraction is generally very high, which limits the largest bond dimension of tensor-network states that can be accurately studied to a relatively small value. We propose an optimized contraction scheme to solve this problem by mapping the double-layer tensor network onto an intersected single-layer tensor network. This reduces greatly the bond dimensions of local tensors to be contracted and improves dramatically the efficiency and accuracy of the evaluation of expectation values of tensor-network states. It almost doubles the largest bond dimension of tensor-network states whose physical properties can be efficiently and reliably calculated, and it extends significantly the application scope of tensor-network methods.
Contracting tensor networks is often computationally demanding. Well-designed contraction sequences can dramatically reduce the contraction cost. We explore the performance of simulated annealing and genetic algorithms, two common discrete optimization techniques, to this ordering problem. We benchmark their performance as well as that of the commonly-used greedy search on physically relevant tensor networks. Where computationally feasible, we also compare them with the optimal contraction sequence obtained by an exhaustive search. Furthermore, we present a systematic comparison with state-of-the-art tree decomposition and graph partitioning algorithms in the context of random regular graph tensor networks. We find that the algorithms we consider consistently outperform a greedy search given equal computational resources, with an advantage that scales with tensor network size. We compare the obtained contraction sequences and identify signs of highly non-local optimization, with the more sophisticated algorithms sacrificing run-time early in the contraction for better overall performance