{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T04:59:21Z","timestamp":1781153961571,"version":"3.54.1"},"reference-count":38,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T00:00:00Z","timestamp":1774742400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"publisher","award":["2023YFA1009500"],"award-info":[{"award-number":["2023YFA1009500"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"name":"General Program of National Natural Science Foundation of China","award":["NSFC62272448"],"award-info":[{"award-number":["NSFC62272448"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026,4,18]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>This article establishes a unified complexity framework for tensor network contraction\u2014a fundamental counting problem. Since the computational complexity crucially depends on the underlying graph\u2019s separator properties, we develop edge separator theorems for finite element graphs and $H$-minor-free graphs (excluding any simple graph $H$ as a minor), and present sub-exponential contraction algorithms for these graph classes. These algorithms, along with the algorithm for contraction on planar graphs are further accelerated by transforming each high-dimensional tensor into a series of low-dimensional tensors. Two methods are involved in this process respectively\u2014the \u201cadder\u201d gadget that can equivalently represent any Boolean symmetric tensor, and the CANDECOMP\/PARAFAC decomposition that can express any tensor as vector product sums. In particular, we prove corresponding lower bounds under #ETH, establishing near-optimality of our algorithms. Also, we present a treewidth-parameterized contraction algorithm, and therefore develop a fine-grained dichotomy for tensor network contraction, contingent on the Hadwiger number.<\/jats:p>","DOI":"10.1093\/comjnl\/bxaf082","type":"journal-article","created":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T07:22:11Z","timestamp":1750663331000},"page":"613-626","source":"Crossref","is-referenced-by-count":0,"title":["Exponential time complexity for contracting tensor networks"],"prefix":"10.1093","volume":"69","author":[{"given":"Ying","family":"Liu","sequence":"first","affiliation":[{"name":"Key Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, University of Chinese Academy of Sciences , 4# South Fourth Street, Zhong Guan Cun, Beijing 100190 ,","place":["China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Boning","family":"Meng","sequence":"additional","affiliation":[{"name":"Key Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, University of Chinese Academy of Sciences , 4# South Fourth Street, Zhong Guan Cun, Beijing 100190 ,","place":["China"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Juqiu","family":"Wang","sequence":"additional","affiliation":[{"name":"Key Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, University of Chinese Academy of Sciences , 4# South Fourth Street, Zhong Guan Cun, Beijing 100190 ,","place":["China"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2026,3,29]]},"reference":[{"key":"2026061100294408700_ref1","doi-asserted-by":"publisher","first-page":"065301","DOI":"10.1103\/PhysRevLett.122.065301","article-title":"Quantum entanglement in deep learning architectures","volume":"122","author":"Levine","year":"2019","journal-title":"Phys Rev Lett"},{"key":"2026061100294408700_ref2","doi-asserted-by":"publisher","first-page":"180405","DOI":"10.1103\/PhysRevLett.115.180405","article-title":"Tensor network renormalization","volume":"115","author":"Evenbly","year":"2015","journal-title":"Phys Rev Lett"},{"key":"2026061100294408700_ref3","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1137\/050644756","article-title":"Simulating quantum computation by contracting tensor networks","volume":"38","author":"Markov","year":"2008","journal-title":"SIAM J Comput"},{"key":"2026061100294408700_ref4","article-title":"Classical simulation of intermediate-size quantum circuits. arXiv","author":"Chen","year":"2018"},{"key":"2026061100294408700_ref5","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1038\/s41534-019-0196-1","article-title":"A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware","volume":"5","author":"Villalonga","year":"2019","journal-title":"npj Quantum Inf"},{"key":"2026061100294408700_ref6","doi-asserted-by":"publisher","first-page":"410","DOI":"10.22331\/q-2021-03-15-410","article-title":"Hyper-optimized tensor network contraction","volume":"5","author":"Gray","year":"2021","journal-title":"Quantum"},{"key":"2026061100294408700_ref7","first-page":"53","article-title":"k-way hypergraph partitioning via n-level recursive bisection","volume-title":"Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX), Arlington, Virginia, USA, 10 January, 2016","author":"Schlag","year":"2016"},{"key":"2026061100294408700_ref8","first-page":"28","article-title":"Engineering a direct k-way hypergraph partitioning algorithm","volume-title":"Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX), Barcelona, Spain, 17-18 January, 2017","author":"Akhremtsev","year":"2017"},{"key":"2026061100294408700_ref9","doi-asserted-by":"publisher","first-page":"60","DOI":"10.21468\/SciPostPhys.7.5.060","article-title":"Fast counting with tensor networks","volume":"7","author":"Kourtis","year":"2019","journal-title":"SciPost Phys"},{"key":"2026061100294408700_ref10","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1109\/MSP.2022.3156744","article-title":"Accelerating tensor contraction products via tensor-train decomposition [tips & tricks]","volume":"39","author":"Kisil","year":"2022","journal-title":"IEEE Signal Process Mag"},{"key":"2026061100294408700_ref11","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1137\/07070111X","article-title":"Tensor decompositions and applications","volume":"51","author":"Kolda","year":"2009","journal-title":"SIAM Rev"},{"key":"2026061100294408700_ref12","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1561\/2200000059","article-title":"Tensor networks for dimensionality reduction and large-scale optimization: part 1 low-rank tensor decompositions","volume":"9","author":"Cichocki","year":"2016","journal-title":"Found Trends Mach Learn"},{"key":"2026061100294408700_ref13","doi-asserted-by":"crossref","first-page":"918","DOI":"10.1007\/978-1-4939-2864-4_748","article-title":"Holant problems","volume-title":"Encyclopedia of Algorithms","author":"Cai","year":"2016"},{"key":"2026061100294408700_ref14","doi-asserted-by":"publisher","first-page":"1362","DOI":"10.1007\/s00224-020-09983-8","article-title":"Dichotomy for holant$^{\\ast }$ problems on the Boolean domain","volume":"64","author":"Cai","year":"2020","journal-title":"Theory Comput Syst"},{"key":"2026061100294408700_ref15","first-page":"12:1","article-title":"A complete dichotomy for complex-valued holant\u02c6c","volume-title":"45th International Colloquium on Automata, Languages, and Programming, Prague, Czech Republic, 9\u201311 July, (2018)","author":"Backens","year":"2018"},{"key":"2026061100294408700_ref16","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1137\/17M113304X","article-title":"The complexity of boolean holant problems with nonnegative weights","volume":"47","author":"Lin","year":"2018","journal-title":"SIAM J Comput"},{"key":"2026061100294408700_ref17","doi-asserted-by":"crossref","first-page":"1091","DOI":"10.1109\/FOCS46700.2020.00105","article-title":"A dichotomy for real boolean holant problems","volume-title":"IEEE 61st Annual Symposium on Foundations of Computer Science, Durham, NC, USA, 16\u201319 November, 2020","author":"Shao","year":"2020"},{"key":"2026061100294408700_ref18","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","article-title":"On the complexity of k-SAT","volume":"62","author":"Impagliazzo","year":"2001","journal-title":"J Comput Syst Sci"},{"key":"2026061100294408700_ref19","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","article-title":"Which problems have strongly exponential complexity?","volume":"63","author":"Impagliazzo","year":"2001","journal-title":"J Comput Syst Sci"},{"key":"2026061100294408700_ref20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2635812","article-title":"Exponential time complexity of the permanent and the tutte polynomial","volume":"10","author":"Dell","year":"2014","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"2026061100294408700_ref21","article-title":"The exponential-time complexity of counting (quantum) graph homomorphisms. 45th International Workshop on Graph-Theoretic Concepts in Computer Science, Vall de N\u00faria, Spain, 19\u201321 June pp. 364\u2013378, (2019). Springer International Publishing, Cham, Switzerland","author":"Chen","year":"2019"},{"key":"2026061100294408700_ref22","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/j.ic.2018.02.008","article-title":"Block interpolation: a framework for tight exponential-time counting complexity","volume":"261","author":"Curticapean","year":"2018","journal-title":"Inf Comput"},{"key":"2026061100294408700_ref23","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1007\/s00453-018-0472-z","article-title":"Fine-grained dichotomies for the tutte plane and Boolean #CSP","volume":"81","author":"Brand","year":"2019","journal-title":"Algorithmica"},{"key":"2026061100294408700_ref24","doi-asserted-by":"crossref","DOI":"10.1145\/3406325.3451124","article-title":"A full complexity dichotomy for immanant families","volume-title":"Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual, Italy, 21\u201325 June 1770\u20131783, (2021)","author":"Curticapean","year":"2021"},{"key":"2026061100294408700_ref25","first-page":"83","article-title":"Exponential time complexity of the complex weighted Boolean #CSP","volume-title":"Computing and Combinatorics, COCOON 2023, Hawaii, HI, USA, 15-17 December","author":"Liu","year":"2024"},{"key":"2026061100294408700_ref26","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1007\/BFb0017151","article-title":"Edge separators for planar graphs and their applications","volume-title":"Mathematical Foundations of Computer Science 1988, Carlsbad, Czechoslovakia, Aug. 29 - Sep. 2","author":"Diks","year":"1988"},{"key":"2026061100294408700_ref27","doi-asserted-by":"publisher","first-page":"271","DOI":"10.4064\/fm-15-1-271-283","article-title":"Sur le probl\u00e8me des courbes gauches en topologie","volume":"15","author":"Kuratowski","year":"1930","journal-title":"Fundamenta Mathematicae"},{"key":"2026061100294408700_ref28","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","article-title":"A separator theorem for planar graphs","volume":"36","author":"Lipton","year":"1979","journal-title":"SIAM J Appl Math"},{"key":"2026061100294408700_ref29","first-page":"293","article-title":"A separator theorem for graphs with an excluded minor and its applications","volume-title":"Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, Baltimore, Maryland, USA, 13\u201317 May, (1990)","author":"Alon","year":"1990"},{"key":"2026061100294408700_ref30","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1002\/1099-128X(200005\/06)14:3\u2329105::AID-CEM582\u232a3.0.CO;2-I","article-title":"Towards a standardized notation and terminology in multiway analysis","volume":"14","author":"Kiers","year":"2000","journal-title":"J Chemom"},{"key":"2026061100294408700_ref31","doi-asserted-by":"crossref","DOI":"10.1109\/FOCS.2008.34","article-title":"Holographic algorithms by fibonacci gates and holographic reductions for hardness","volume-title":"Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, Philadelphia, PA, 25\u201328 October 644\u2013653, (2008)","author":"Cai","year":"2008"},{"key":"2026061100294408700_ref32","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","article-title":"Graph minors. Ii. Algorithmic aspects of tree-width","volume":"7","author":"Robertson","year":"1986","journal-title":"J Algorithms"},{"key":"2026061100294408700_ref33","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","article-title":"Complexity of finding embeddings in a k -tree","volume":"8","author":"Arnborg","year":"1987","journal-title":"Siam Journal on Algebraic and Discrete Methods"},{"key":"2026061100294408700_ref34","doi-asserted-by":"crossref","DOI":"10.1145\/167088.167161","article-title":"A linear time algorithm for finding tree-decompositions of small treewidth","volume-title":"Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, San Diego, California, USA, 16\u201318 May 226\u2013234, (1993)","author":"Bodlaender","year":"1993"},{"key":"2026061100294408700_ref35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","article-title":"A partial k-arboretum of graphs with bounded treewidth","volume":"209","author":"Bodlaender","year":"1998","journal-title":"Theor Comput Sci"},{"key":"2026061100294408700_ref36","doi-asserted-by":"publisher","first-page":"1142","DOI":"10.1137\/S0097539793304601","article-title":"The complexity of planar counting problems","volume":"27","author":"Hunt","year":"1998","journal-title":"SIAM J Comput"},{"key":"2026061100294408700_ref37","first-page":"47","article-title":"Approximate counting via correlation decay on planar graphs","volume-title":"Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, USA, 6\u20138 January","author":"Yin","year":"2013"},{"key":"2026061100294408700_ref38","doi-asserted-by":"publisher","DOI":"10.1002\/047174882X.ch14","article-title":"Kolmogorov complexity","volume-title":"Elements of Information Theory","author":"Cover","year":"2005"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/69\/4\/613\/67636907\/bxaf082.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/69\/4\/613\/67636907\/bxaf082.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T04:29:52Z","timestamp":1781152192000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/69\/4\/613\/8555574"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,29]]},"references-count":38,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2026,3,29]]},"published-print":{"date-parts":[[2026,4,18]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxaf082","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2026,4]]},"published":{"date-parts":[[2026,3,29]]}}}