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

arXiv:2001.10204

The Complexity of Contracting Planar Tensor Network

Ying Liu

Published Jan 28, 2020• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2001.10204

Related papers

Exponential time complexity for contracting tensor networks

Ying Liu, Boning Meng, Juqiu Wang

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.

The Computer Journal•Jun 23, 2025•0 citations

Tensor Networks in a Nutshell

Jacob Biamonte, Ville Bergholm

Tensor network methods are taking a central role in modern quantum physics and beyond. They can provide an efficient approximation to certain classes of quantum states, and the associated graphical language makes it easy to describe and pictorially reason about quantum circuits, channels, protocols, open systems and more. Our goal is to explain tensor networks and some associated methods as quickly and as painlessly as possible. Beginning with the key definitions, the graphical tensor network language is presented through examples. We then provide an introduction to matrix product states. We conclude the tutorial with tensor contractions evaluating combinatorial counting problems. The first one counts the number of solutions for Boolean formulae, whereas the second is Penrose's tensor contraction algorithm, returning the number of $3$-edge-colorings of $3$-regular planar graphs.

arXiv:1708.00006•Jul 31, 2017•113 citations

The resource theory of tensor networks

Matthias Christandl, Vladimir Lysikov, Vincent Steffan +2 more

Tensor networks provide succinct representations of quantum many-body states and are an important computational tool for strongly correlated quantum systems. Their expressive and computational power is characterized by an underlying entanglement structure, on a lattice or more generally a (hyper)graph, with virtual entangled pairs or multipartite entangled states associated to (hyper)edges. Changing this underlying entanglement structure into another can lead to both theoretical and computational benefits. We study a natural resource theory which generalizes the notion of bond dimension to entanglement structures using multipartite entanglement. It is a direct extension of resource theories of tensors studied in the context of multipartite entanglement and algebraic complexity theory, allowing for the application of the sophisticated methods developed in these fields to tensor networks. The resource theory of tensor networks concerns both the local entanglement structure of a quantum many-body state and the (algebraic) complexity of tensor network contractions using this entanglement structure. We show that there are transformations between entanglement structures which go beyond edge-by-edge conversions, highlighting efficiency gains of our resource theory that mirror those obtained in the search for better matrix multiplication algorithms. We also provide obstructions to the existence of such transformations by extending a variety of methods originally developed in algebraic complexity theory for obtaining complexity lower bounds. The resource theory of tensor networks allows to compare different entanglement structures and should lead to more efficient tensor network representations and contraction algorithms.

arXiv:2307.07394•Quantum•Dec 11, 2024•5 citations

Algorithms for tensor network contraction ordering

Frank Schindler, Adam S. Jermyn

Contracting tensor networks is often computationally demanding. Well-designed contraction sequences can dramatically reduce the contraction cost. We explore the performance of simulated annealing and genetic algorithms, two common discrete optimization techniques, to this ordering problem. We benchmark their performance as well as that of the commonly-used greedy search on physically relevant tensor networks. Where computationally feasible, we also compare them with the optimal contraction sequence obtained by an exhaustive search. Furthermore, we present a systematic comparison with state-of-the-art tree decomposition and graph partitioning algorithms in the context of random regular graph tensor networks. We find that the algorithms we consider consistently outperform a greedy search given equal computational resources, with an advantage that scales with tensor network size. We compare the obtained contraction sequences and identify signs of highly non-local optimization, with the more sophisticated algorithms sacrificing run-time early in the contraction for better overall performance

•Jul 6, 2020•11 citations

Algorithms for tensor network contraction ordering

Frank Schindler, Adam S Jermyn

Abstract Contracting tensor networks is often computationally demanding. Well-designed contraction sequences can dramatically reduce the contraction cost. We explore the performance of simulated annealing and genetic algorithms, two common discrete optimization techniques, to this ordering problem. We benchmark their performance as well as that of the commonly-used greedy search on physically relevant tensor networks. Where computationally feasible, we also compare them with the optimal contraction sequence obtained by an exhaustive search. Furthermore, we present a systematic comparison with state-of-the-art tree decomposition and graph partitioning algorithms in the context of random regular graph tensor networks. We find that the algorithms we consider consistently outperform a greedy search given equal computational resources, with an advantage that scales with tensor network size. We compare the obtained contraction sequences and identify signs of highly non-local optimization, with the more sophisticated algorithms sacrificing run-time early in the contraction for better overall performance.

arXiv:2001.08063•Machine Learning Science and Technology•May 20, 2020•8 citations

Contraction of matchgate tensor networks on non-planar graphs

Sergey B. Bravyi

A tensor network is a product of tensors associated with vertices of some graph $G$ such that every edge of $G$ represents a summation (contraction) over a matching pair of indexes. It was shown recently by Valiant, Cai, and Choudhary that tensor networks can be efficiently contracted on planar graphs if components of every tensor obey a system of quadratic equations known as matchgate identities. Such tensors are referred to as matchgate tensors. The present paper provides an alternative approach to contraction of matchgate tensor networks that easily extends to non-planar graphs. Specifically, it is shown that a matchgate tensor network on a graph $G$ of genus $g$ with $n$ vertices can be contracted in time $T=poly(n) + 2^{2g} O(m^3)$ where $m$ is the minimum number of edges one has to remove from $G$ in order to make it planar. Our approach makes use of anticommuting (Grassmann) variables and Gaussian integrals.

arXiv:0801.2989•Jan 18, 2008•1 citation
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.
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 network methods are taking a central role in modern quantum physics and beyond. They can provide an efficient approximation to certain classes of quantum states, and the associated graphical language makes it easy to describe and pictorially reason about quantum circuits, channels, protocols, open systems and more. Our goal is to explain tensor networks and some associated methods as quickly and as painlessly as possible. Beginning with the key definitions, the graphical tensor network language is presented through examples. We then provide an introduction to matrix product states. We conclude the tutorial with tensor contractions evaluating combinatorial counting problems. The first one counts the number of solutions for Boolean formulae, whereas the second is Penrose's tensor contraction algorithm, returning the number of 333-edge-colorings of 333-regular planar graphs.
Tensor networks provide succinct representations of quantum many-body states and are an important computational tool for strongly correlated quantum systems. Their expressive and computational power is characterized by an underlying entanglement structure, on a lattice or more generally a (hyper)graph, with virtual entangled pairs or multipartite entangled states associated to (hyper)edges. Changing this underlying entanglement structure into another can lead to both theoretical and computational benefits. We study a natural resource theory which generalizes the notion of bond dimension to entanglement structures using multipartite entanglement. It is a direct extension of resource theories of tensors studied in the context of multipartite entanglement and algebraic complexity theory, allowing for the application of the sophisticated methods developed in these fields to tensor networks. The resource theory of tensor networks concerns both the local entanglement structure of a quantum many-body state and the (algebraic) complexity of tensor network contractions using this entanglement structure. We show that there are transformations between entanglement structures which go beyond edge-by-edge conversions, highlighting efficiency gains of our resource theory that mirror those obtained in the search for better matrix multiplication algorithms. We also provide obstructions to the existence of such transformations by extending a variety of methods originally developed in algebraic complexity theory for obtaining complexity lower bounds. The resource theory of tensor networks allows to compare different entanglement structures and should lead to more efficient tensor network representations and contraction algorithms.
Contracting tensor networks is often computationally demanding. Well-designed contraction sequences can dramatically reduce the contraction cost. We explore the performance of simulated annealing and genetic algorithms, two common discrete optimization techniques, to this ordering problem. We benchmark their performance as well as that of the commonly-used greedy search on physically relevant tensor networks. Where computationally feasible, we also compare them with the optimal contraction sequence obtained by an exhaustive search. Furthermore, we present a systematic comparison with state-of-the-art tree decomposition and graph partitioning algorithms in the context of random regular graph tensor networks. We find that the algorithms we consider consistently outperform a greedy search given equal computational resources, with an advantage that scales with tensor network size. We compare the obtained contraction sequences and identify signs of highly non-local optimization, with the more sophisticated algorithms sacrificing run-time early in the contraction for better overall performance
Abstract Contracting tensor networks is often computationally demanding. Well-designed contraction sequences can dramatically reduce the contraction cost. We explore the performance of simulated annealing and genetic algorithms, two common discrete optimization techniques, to this ordering problem. We benchmark their performance as well as that of the commonly-used greedy search on physically relevant tensor networks. Where computationally feasible, we also compare them with the optimal contraction sequence obtained by an exhaustive search. Furthermore, we present a systematic comparison with state-of-the-art tree decomposition and graph partitioning algorithms in the context of random regular graph tensor networks. We find that the algorithms we consider consistently outperform a greedy search given equal computational resources, with an advantage that scales with tensor network size. We compare the obtained contraction sequences and identify signs of highly non-local optimization, with the more sophisticated algorithms sacrificing run-time early in the contraction for better overall performance.
A tensor network is a product of tensors associated with vertices of some graph GGG such that every edge of GGG represents a summation (contraction) over a matching pair of indexes. It was shown recently by Valiant, Cai, and Choudhary that tensor networks can be efficiently contracted on planar graphs if components of every tensor obey a system of quadratic equations known as matchgate identities. Such tensors are referred to as matchgate tensors. The present paper provides an alternative approach to contraction of matchgate tensor networks that easily extends to non-planar graphs. Specifically, it is shown that a matchgate tensor network on a graph GGG of genus ggg with nnn vertices can be contracted in time T=poly(n)+22gO(m3)T=poly(n) + 2^{2g} O(m^3)T=poly(n)+22gO(m3) where mmm is the minimum number of edges one has to remove from GGG in order to make it planar. Our approach makes use of anticommuting (Grassmann) variables and Gaussian integrals.