Please use this identifier to cite or link to this item:
Title: Towards a polynomial algorithm for optimal contraction sequence of tensor networks from trees
Authors: Xu, Jianyu
Liang, Ling
Deng, Lei
Wen, Changyun
Xie, Yuan
Li, Guoqi
Keywords: Engineering::Electrical and electronic engineering
Issue Date: 2019
Source: Xu, J., Liang, L., Deng, L., Wen, C., Xie, Y., & Li, G. (2019). Towards a polynomial algorithm for optimal contraction sequence of tensor networks from trees. Physical Review E, 100(4), 043309-. doi:10.1103/PhysRevE.100.043309
Journal: Physical Review E
Abstract: 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.
ISSN: 2470-0045
DOI: 10.1103/PhysRevE.100.043309
Rights: © 2019 American Physical Society. All rights reserved. This paper was published in Physical Review E and is made available with permission of American Physical Society.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:EEE Journal Articles

Page view(s)

Updated on May 19, 2022

Download(s) 20

Updated on May 19, 2022

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.