Towards a polynomial algorithm for optimal contraction sequence of tensor networks from trees
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...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/141943 |
| _version_ | 1811690352239706112 |
|---|---|
| author | Xu, Jianyu Liang, Ling Deng, Lei Wen, Changyun Xie, Yuan Li, Guoqi |
| author2 | School of Electrical and Electronic Engineering |
| author_facet | School of Electrical and Electronic Engineering Xu, Jianyu Liang, Ling Deng, Lei Wen, Changyun Xie, Yuan Li, Guoqi |
| author_sort | Xu, Jianyu |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T06:02:38Z |
| format | Journal Article |
| id | ntu-10356/141943 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T06:02:38Z |
| publishDate | 2020 |
| record_format | dspace |
| spelling | ntu-10356/1419432020-06-12T02:50:33Z Towards a polynomial algorithm for optimal contraction sequence of tensor networks from trees Xu, Jianyu Liang, Ling Deng, Lei Wen, Changyun Xie, Yuan Li, Guoqi School of Electrical and Electronic Engineering Engineering::Electrical and electronic engineering Network Optimization Tensor Network Methods 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. Published version 2020-06-12T02:50:33Z 2020-06-12T02:50:33Z 2019 Journal Article 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 2470-0045 https://hdl.handle.net/10356/141943 10.1103/PhysRevE.100.043309 31770963 2-s2.0-85074907277 4 100 en Physical Review E © 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. application/pdf |
| spellingShingle | Engineering::Electrical and electronic engineering Network Optimization Tensor Network Methods Xu, Jianyu Liang, Ling Deng, Lei Wen, Changyun Xie, Yuan Li, Guoqi Towards a polynomial algorithm for optimal contraction sequence of tensor networks from trees |
| title | Towards a polynomial algorithm for optimal contraction sequence of tensor networks from trees |
| title_full | Towards a polynomial algorithm for optimal contraction sequence of tensor networks from trees |
| title_fullStr | Towards a polynomial algorithm for optimal contraction sequence of tensor networks from trees |
| title_full_unstemmed | Towards a polynomial algorithm for optimal contraction sequence of tensor networks from trees |
| title_short | Towards a polynomial algorithm for optimal contraction sequence of tensor networks from trees |
| title_sort | towards a polynomial algorithm for optimal contraction sequence of tensor networks from trees |
| topic | Engineering::Electrical and electronic engineering Network Optimization Tensor Network Methods |
| url | https://hdl.handle.net/10356/141943 |
| work_keys_str_mv | AT xujianyu towardsapolynomialalgorithmforoptimalcontractionsequenceoftensornetworksfromtrees AT liangling towardsapolynomialalgorithmforoptimalcontractionsequenceoftensornetworksfromtrees AT denglei towardsapolynomialalgorithmforoptimalcontractionsequenceoftensornetworksfromtrees AT wenchangyun towardsapolynomialalgorithmforoptimalcontractionsequenceoftensornetworksfromtrees AT xieyuan towardsapolynomialalgorithmforoptimalcontractionsequenceoftensornetworksfromtrees AT liguoqi towardsapolynomialalgorithmforoptimalcontractionsequenceoftensornetworksfromtrees |