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

• Main Authors: Xu, Jianyu, Liang, Ling, Deng, Lei, Wen, Changyun, Xie, Yuan, Li, Guoqi
• Other Authors: School of Electrical and Electronic Engineering
• Format: Article
• Language: English
• Published: 2020
• Subjects: Engineering::Electrical and electronic engineering; Network Optimization; Tensor Network Methods
• Online Access: https://hdl.handle.net/10356/141943
• Institution: Nanyang Technological University

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 pol...