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

The Computer Journal

Exponential time complexity for contracting tensor networks

Ying Liu, Boning Meng, Juqiu Wang

Published Jun 23, 2025• 0 citations
Publisher

Abstract

Abstract This article establishes a unified complexity framework for tensor network contraction—a fundamental counting problem. Since the computational complexity crucially depends on the underlying graph’s 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—the “adder” 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.

DOI
10.1093/comjnl/bxaf082

Related papers

The Complexity of Contracting Planar Tensor Network

Ying Liu

Tensor networks have been an important concept and technique in many research areas, such as quantum computation and machine learning. We study the exponential complexity of contracting tensor networks on two special graph structures: planar graphs and finite element graphs. We prove that any finite element graph has a $O(d\sqrt{\max\{Δ,d\}N})$ size edge separator. Furthermore, we develop a $2^{O(d\sqrt{\max\{Δ,d\}N})}$ time algorithm to contracting a tensor network consisting of $N$ Boolean tensors, whose underlying graph is a finite element graph with maximum degree $Δ$ and has no face with more than $d$ boundary edges in the planar skeleton, based on the $2^{O(\sqrt{ΔN})}$ time algorithm \cite{fastcounting} for planar Boolean tensor network contractions. We use two methods to accelerate the exponential algorithms by transferring high-dimensional tensors to low-dimensional tensors. We put up a $O(k)$ size planar gadget for any Boolean symmetric tensor of dimension $k$, where the gadget only consists of Boolean tensors with dimension no more than $5$. Another method is decomposing any tensor into a series of vectors (unary functions), according to its \emph{CP decomposition} \cite{tensor-rank}. We also prove the sub-exponential time lower bound for contracting tensor networks under the counting \emph{Exponential Time Hypothesis} (\#ETH) holds.

arXiv:2001.10204•Jan 28, 2020•1 citation

Tensor Contraction with ZX Calculus, a Graph-Theoretic Approach

Yuhao Han

Tensors are higher dimensional generalisations of vectors and matrices. Tensor networks are a diagrammatic representation of complicated relations between tensors, and tensor contraction is the evaluation of a tensor network analogous to matrix multiplication. Tensor networks and tensor contraction are ubiquitous in computer science, physics, and applied mathematics. Most existing tensor contraction algorithms are focused on finding an optimal contraction order of the tensors' bonds. However, finding the optimal order is an NP-hard problem. It is equivalent to another possibly more straightforward but still NP-hard problem of finding the treewidth of the line graph of the tensor network. While in general finding the optimal bond-by-bond contraction order is hard, in many practical cases there is no need to find an optimal order. This observation leads to the core innovation of this thesis, which is a new tensor contraction paradigm that uses graph theoretic operations to produce an equivalent tensor network whose line graph has lower treewidth than the original tensor network, before applying the bond-by-bond contraction algorithm. We call these graph theoretical operations \textit{rewrite preprocessing}, and we name the algorithms that apply rewrite preprocessing before regular bond-by-bond contraction \textit{Tensor Contraction with Graph Operation}. There are many possible ways to perform rewrite preprocessing; in this thesis, we focus on the graph operations of ZX calculus, a diagrammatic language for quantum circuits. Ample numerical simulations have been performed to demonstrate the effectiveness of our proposed method.

quant-pharXiv:2611.01890•Nov 3, 2026

Parameterization of Tensor Network Contraction

Bryan O’Gorman

We present a conceptually clear and algorithmically useful framework for parameterizing the costs of tensor network contraction. Our framework is completely general, applying to tensor networks with arbitrary bond dimensions, open legs, and hyperedges. The fundamental objects of our framework are rooted and unrooted contraction trees, which represent classes of contraction orders. Properties of a contraction tree correspond directly and precisely to the time and space costs of tensor network contraction. The properties of rooted contraction trees give the costs of parallelized contraction algorithms. We show how contraction trees relate to existing tree-like objects in the graph theory literature, bringing to bear a wide range of graph algorithms and tools to tensor network contraction. Independent of tensor networks, we show that the edge congestion of a graph is almost equal to the branchwidth of its line graph.

arXiv:1906.00013•Leibniz international proceedings in informatics•Jan 1, 2019•7 citations

Treewidth-Driven Tensor Network Contraction via Categorical String Diagrams — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: Tensor network contraction complexity is governed by treewidth of hypergraph, optimized via hyper-optimized tree search, and formalized in free compact closure of symmetric monoidal categories. MATH: Treewidth \( \text{tw}(H) \) of hypergraph \( H \) determines contraction cost \( O(\exp(\text{tw}(H))) \); contraction sequence corresponds to elimination order; free compact closure adds adjoints to objects in symmetric monoidal category, yielding string diagrams as morphisms. CONNECTION: Treewidth minimization relates to planar graph invariants and lattice structures; hyper-optimized trees echo hierarchical branching ratios (e.g., 0.618, 1.618) in optimal decomposition; base-60 appears indirectly in cyclic elimination orders for periodic lattices. DEPTH: 8 — Core algorithmic advance for quantum simulation, linking category theory (free compact closure) to computational complexity (treewidth), with geometric resonance in optimal tree structures. Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Jul 25, 2026•0 citations

Reducing Computational Complexity of Tensor Contractions via Tensor-Train Networks

Ilya Kisil, Giuseppe G. Calvi, Kriton Konstantinidis +2 more

There is a significant expansion in both volume and range of applications along with the concomitant increase in the variety of data sources. These ever-expanding trends have highlighted the necessity for more versatile analysis tools that offer greater opportunities for algorithmic developments and computationally faster operations than the standard flat-view matrix approach. Tensors, or multi-way arrays, provide such an algebraic framework which is naturally suited to data of such large volume, diversity, and veracity. Indeed, the associated tensor decompositions have demonstrated their potential in breaking the Curse of Dimensionality associated with traditional matrix methods, where a necessary exponential increase in data volume leads to adverse or even intractable consequences on computational complexity. A key tool underpinning multi-linear manipulation of tensors and tensor networks is the standard Tensor Contraction Product (TCP). However, depending on the dimensionality of the underlying tensors, the TCP also comes at the price of high computational complexity in tensor manipulation. In this work, we resort to diagrammatic tensor network manipulation to calculate such products in an efficient and computationally tractable manner, by making use of Tensor Train decomposition (TTD). This has rendered the underlying concepts easy to perceive, thereby enhancing intuition of the associated underlying operations, while preserving mathematical rigour. In addition to bypassing the cumbersome mathematical multi-linear expressions, the proposed Tensor Train Contraction Product model is shown to accelerate significantly the underlying computational operations, as it is independent of tensor order and linear in the tensor dimension, as opposed to performing the full computations through the standard approach (exponential in tensor order).

arXiv:2109.00626•Sep 1, 2021•3 citations

Benchmarking treewidth as a practical component of tensor network simulations

Eugene Dumitrescu, Allison L. Fisher, Timothy D. Goodrich +3 more

Tensor networks are powerful factorization techniques which reduce resource requirements for numerically simulating principal quantum many-body systems and algorithms. The computational complexity of a tensor network simulation depends on the tensor ranks and the order in which they are contracted. Unfortunately, computing optimal contraction sequences (orderings) in general is known to be a computationally difficult (NP-complete) task. In 2005, Markov and Shi showed that optimal contraction sequences correspond to optimal (minimum width) tree decompositions of a tensor network's line graph, relating the contraction sequence problem to a rich literature in structural graph theory. While treewidth-based methods have largely been ignored in favor of dataset-specific algorithms in the prior tensor networks literature, we demonstrate their practical relevance for problems arising from two distinct methods used in quantum simulation: multi-scale entanglement renormalization ansatz (MERA) datasets and quantum circuits generated by the quantum approximate optimization algorithm (QAOA). We exhibit multiple regimes where treewidth-based algorithms outperform domain-specific algorithms, while demonstrating that the optimal choice of algorithm has a complex dependence on the network density, expected contraction complexity, and user run time requirements. We further provide an open source software framework designed with an emphasis on accessibility and extendability, enabling replicable experimental evaluations and future exploration of competing methods by practitioners.

arXiv:1807.04599•PLoS ONE•Dec 18, 2018•14 citations
Abstract This article establishes a unified complexity framework for tensor network contraction—a fundamental counting problem. Since the computational complexity crucially depends on the underlying graph’s separator properties, we develop edge separator theorems for finite element graphs and HHH-minor-free graphs (excluding any simple graph HHH 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—the “adder” 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.
Tensor networks have been an important concept and technique in many research areas, such as quantum computation and machine learning. We study the exponential complexity of contracting tensor networks on two special graph structures: planar graphs and finite element graphs. We prove that any finite element graph has a O(dmax⁡{Δ,d}N)O(d\sqrt{\max\{Δ,d\}N})O(dmax{Δ,d}N​) size edge separator. Furthermore, we develop a 2O(dmax⁡{Δ,d}N)2^{O(d\sqrt{\max\{Δ,d\}N})}2O(dmax{Δ,d}N​) time algorithm to contracting a tensor network consisting of NNN Boolean tensors, whose underlying graph is a finite element graph with maximum degree ΔΔΔ and has no face with more than ddd boundary edges in the planar skeleton, based on the 2O(ΔN)2^{O(\sqrt{ΔN})}2O(ΔN​) time algorithm \cite{fastcounting} for planar Boolean tensor network contractions. We use two methods to accelerate the exponential algorithms by transferring high-dimensional tensors to low-dimensional tensors. We put up a O(k)O(k)O(k) size planar gadget for any Boolean symmetric tensor of dimension kkk, where the gadget only consists of Boolean tensors with dimension no more than 555. Another method is decomposing any tensor into a series of vectors (unary functions), according to its \emph{CP decomposition} \cite{tensor-rank}. We also prove the sub-exponential time lower bound for contracting tensor networks under the counting \emph{Exponential Time Hypothesis} (\#ETH) holds.
Tensors are higher dimensional generalisations of vectors and matrices. Tensor networks are a diagrammatic representation of complicated relations between tensors, and tensor contraction is the evaluation of a tensor network analogous to matrix multiplication. Tensor networks and tensor contraction are ubiquitous in computer science, physics, and applied mathematics. Most existing tensor contraction algorithms are focused on finding an optimal contraction order of the tensors' bonds. However, finding the optimal order is an NP-hard problem. It is equivalent to another possibly more straightforward but still NP-hard problem of finding the treewidth of the line graph of the tensor network. While in general finding the optimal bond-by-bond contraction order is hard, in many practical cases there is no need to find an optimal order. This observation leads to the core innovation of this thesis, which is a new tensor contraction paradigm that uses graph theoretic operations to produce an equivalent tensor network whose line graph has lower treewidth than the original tensor network, before applying the bond-by-bond contraction algorithm. We call these graph theoretical operations \textit{rewrite preprocessing}, and we name the algorithms that apply rewrite preprocessing before regular bond-by-bond contraction \textit{Tensor Contraction with Graph Operation}. There are many possible ways to perform rewrite preprocessing; in this thesis, we focus on the graph operations of ZX calculus, a diagrammatic language for quantum circuits. Ample numerical simulations have been performed to demonstrate the effectiveness of our proposed method.
We present a conceptually clear and algorithmically useful framework for parameterizing the costs of tensor network contraction. Our framework is completely general, applying to tensor networks with arbitrary bond dimensions, open legs, and hyperedges. The fundamental objects of our framework are rooted and unrooted contraction trees, which represent classes of contraction orders. Properties of a contraction tree correspond directly and precisely to the time and space costs of tensor network contraction. The properties of rooted contraction trees give the costs of parallelized contraction algorithms. We show how contraction trees relate to existing tree-like objects in the graph theory literature, bringing to bear a wide range of graph algorithms and tools to tensor network contraction. Independent of tensor networks, we show that the edge congestion of a graph is almost equal to the branchwidth of its line graph.
FINDING: Tensor network contraction complexity is governed by treewidth of hypergraph, optimized via hyper-optimized tree search, and formalized in free compact closure of symmetric monoidal categories. MATH: Treewidth tw(H) \text{tw}(H) tw(H) of hypergraph H H H determines contraction cost O(exp⁡(tw(H))) O(\exp(\text{tw}(H))) O(exp(tw(H))); contraction sequence corresponds to elimination order; free compact closure adds adjoints to objects in symmetric monoidal category, yielding string diagrams as morphisms. CONNECTION: Treewidth minimization relates to planar graph invariants and lattice structures; hyper-optimized trees echo hierarchical branching ratios (e.g., 0.618, 1.618) in optimal decomposition; base-60 appears indirectly in cyclic elimination orders for periodic lattices. DEPTH: 8 — Core algorithmic advance for quantum simulation, linking category theory (free compact closure) to computational complexity (treewidth), with geometric resonance in optimal tree structures. Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
There is a significant expansion in both volume and range of applications along with the concomitant increase in the variety of data sources. These ever-expanding trends have highlighted the necessity for more versatile analysis tools that offer greater opportunities for algorithmic developments and computationally faster operations than the standard flat-view matrix approach. Tensors, or multi-way arrays, provide such an algebraic framework which is naturally suited to data of such large volume, diversity, and veracity. Indeed, the associated tensor decompositions have demonstrated their potential in breaking the Curse of Dimensionality associated with traditional matrix methods, where a necessary exponential increase in data volume leads to adverse or even intractable consequences on computational complexity. A key tool underpinning multi-linear manipulation of tensors and tensor networks is the standard Tensor Contraction Product (TCP). However, depending on the dimensionality of the underlying tensors, the TCP also comes at the price of high computational complexity in tensor manipulation. In this work, we resort to diagrammatic tensor network manipulation to calculate such products in an efficient and computationally tractable manner, by making use of Tensor Train decomposition (TTD). This has rendered the underlying concepts easy to perceive, thereby enhancing intuition of the associated underlying operations, while preserving mathematical rigour. In addition to bypassing the cumbersome mathematical multi-linear expressions, the proposed Tensor Train Contraction Product model is shown to accelerate significantly the underlying computational operations, as it is independent of tensor order and linear in the tensor dimension, as opposed to performing the full computations through the standard approach (exponential in tensor order).
Tensor networks are powerful factorization techniques which reduce resource requirements for numerically simulating principal quantum many-body systems and algorithms. The computational complexity of a tensor network simulation depends on the tensor ranks and the order in which they are contracted. Unfortunately, computing optimal contraction sequences (orderings) in general is known to be a computationally difficult (NP-complete) task. In 2005, Markov and Shi showed that optimal contraction sequences correspond to optimal (minimum width) tree decompositions of a tensor network's line graph, relating the contraction sequence problem to a rich literature in structural graph theory. While treewidth-based methods have largely been ignored in favor of dataset-specific algorithms in the prior tensor networks literature, we demonstrate their practical relevance for problems arising from two distinct methods used in quantum simulation: multi-scale entanglement renormalization ansatz (MERA) datasets and quantum circuits generated by the quantum approximate optimization algorithm (QAOA). We exhibit multiple regimes where treewidth-based algorithms outperform domain-specific algorithms, while demonstrating that the optimal choice of algorithm has a complex dependence on the network density, expected contraction complexity, and user run time requirements. We further provide an open source software framework designed with an emphasis on accessibility and extendability, enabling replicable experimental evaluations and future exploration of competing methods by practitioners.