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:2611.01890

Tensor Contraction with ZX Calculus, a Graph-Theoretic Approach

Yuhao Han

quant-phmath-phmath.NASubmitted Nov 1, 2026• Announced Nov 3, 2026
arXivHTMLPDF

Abstract

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.

Related papers

A Parallel Tensor Network Contraction Algorithm and Its Applications in Quantum Computation

Fang Zhang

Tensors are a natural generalization of matrices, and tensor networks are a natural generalization of matrix products. Despite the simple definition of tensor networks, they are versatile enough to represent many different kinds of "products" that arise in various theoretical and practical problems. In particular, the powerful computational model of quantum computation can be defined almost entirely in terms of matrix products and tensor products, both of which are special cases of tensor networks. As such, (classical) algorithms for evaluating tensor networks have profound importance in the study of quantum computation. In this thesis, we design and implement a parallel algorithm for tensor network contraction. In addition to finding efficient contraction orders for a tensor network, we also dynamically slice it into multiple sub-tasks with lower space and time costs, in order to evaluate the tensor network in parallel. We refer to such an evaluation strategy as a contraction scheme for the tensor network. In addition, we introduce a local optimization procedure that improves the efficiency of the contraction schemes we find. We also investigate the applications of our parallel tensor network contraction algorithm in quantum computation. The most ready application is the simulation of random quantum supremacy circuits, where we benchmark our algorithm to demonstrate its advantage over other similar tensor network based simulators. Other applications we found include evaluating the energy function of a Quantum Approximate Optimization Algorithm (QAOA), and simulating surface codes under a realistic error model with crosstalk.

•Jan 1, 2020•0 citations

Simplification Strategies for the Qutrit ZX-Calculus

Alex Townsend-Teague, Konstantinos Meichanetzidis

The ZX-calculus is a graphical language for suitably represented tensor networks, called ZX-diagrams. Calculations are performed by transforming ZX-diagrams with rewrite rules. The ZX-calculus has found applications in reasoning about quantum circuits, condensed matter systems, quantum algorithms, quantum error correcting codes, and counting problems. A key notion is the stabiliser fragment of the ZX-calculus, a subfamily of ZX-diagrams for which rewriting can be done efficiently in terms of derived simplifying rewrites. Recently, higher dimensional qudits - in particular, qutrits - have gained prominence within quantum computing research. The main contribution of this work is the derivation of efficient rewrite strategies for the stabiliser fragment of the qutrit ZX-calculus. Notably, this constitutes a first non-trivial step towards the simplification of qutrit quantum circuits. We then give further unexpected areas in which these rewrite strategies provide complexity-theoretic insight; namely, we reinterpret known results about evaluating the Jones polynomial, an important link invariant in knot theory, and counting graph colourings.

arXiv:2103.06914•Mar 11, 2021•6 citations

Hyperoptimized Approximate Contraction of Tensor Networks with Arbitrary Geometry

Johnnie Gray, Garnet Kin‐Lic Chan

Tensor network contraction is central to problems ranging from many-body physics to computer science. We describe how to approximate tensor network contraction through bond compression on arbitrary graphs. In particular, we introduce a hyperoptimization over the compression and contraction strategy itself to minimize error and cost. We demonstrate that our protocol outperforms both handcrafted contraction strategies in the literature as well as recently proposed general contraction algorithms on a variety of synthetic and physical problems on regular lattices and random regular graphs. We further showcase the power of the approach by demonstrating approximate contraction of tensor networks for frustrated three-dimensional lattice partition functions, dimer counting on random regular graphs, and to access the hardness transition of random tensor network models, in graphs with many thousands of tensors. Published by the American Physical Society 2024

arXiv:2206.07044•Physical Review X•Jan 26, 2024•29 citations

qTorch: The quantum tensor contraction handler

Eliot Fried, Nicolas P. D. Sawaya, Yudong Cao +3 more

Classical simulation of quantum computation is necessary for studying the numerical behavior of quantum algorithms, as there does not yet exist a large viable quantum computer on which to perform numerical tests. Tensor network (TN) contraction is an algorithmic method that can efficiently simulate some quantum circuits, often greatly reducing the computational cost over methods that simulate the full Hilbert space. In this study we implement a tensor network contraction program for simulating quantum circuits using multi-core compute nodes. We show simulation results for the Max-Cut problem on 3- through 7-regular graphs using the quantum approximate optimization algorithm (QAOA), successfully simulating up to 100 qubits. We test two different methods for generating the ordering of tensor index contractions: one is based on the tree decomposition of the line graph, while the other generates ordering using a straight-forward stochastic scheme. Through studying instances of QAOA circuits, we show the expected result that as the treewidth of the quantum circuit's line graph decreases, TN contraction becomes significantly more efficient than simulating the whole Hilbert space. The results in this work suggest that tensor contraction methods are superior only when simulating Max-Cut/QAOA with graphs of regularities approximately five and below. Insight into this point of equal computational cost helps one determine which simulation method will be more efficient for a given quantum circuit. The stochastic contraction method outperforms the line graph based method only when the time to calculate a reasonable tree decomposition is prohibitively expensive. Finally, we release our software package, qTorch (Quantum TensOR Contraction Handler), intended for general quantum circuit simulation. For a nontrivial subset of these quantum circuits, 50 to 100 qubits can easily be simulated on a single compute node.

arXiv:1709.03636•PLoS ONE•Dec 10, 2018•48 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

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
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.
Tensors are a natural generalization of matrices, and tensor networks are a natural generalization of matrix products. Despite the simple definition of tensor networks, they are versatile enough to represent many different kinds of "products" that arise in various theoretical and practical problems. In particular, the powerful computational model of quantum computation can be defined almost entirely in terms of matrix products and tensor products, both of which are special cases of tensor networks. As such, (classical) algorithms for evaluating tensor networks have profound importance in the study of quantum computation. In this thesis, we design and implement a parallel algorithm for tensor network contraction. In addition to finding efficient contraction orders for a tensor network, we also dynamically slice it into multiple sub-tasks with lower space and time costs, in order to evaluate the tensor network in parallel. We refer to such an evaluation strategy as a contraction scheme for the tensor network. In addition, we introduce a local optimization procedure that improves the efficiency of the contraction schemes we find. We also investigate the applications of our parallel tensor network contraction algorithm in quantum computation. The most ready application is the simulation of random quantum supremacy circuits, where we benchmark our algorithm to demonstrate its advantage over other similar tensor network based simulators. Other applications we found include evaluating the energy function of a Quantum Approximate Optimization Algorithm (QAOA), and simulating surface codes under a realistic error model with crosstalk.
The ZX-calculus is a graphical language for suitably represented tensor networks, called ZX-diagrams. Calculations are performed by transforming ZX-diagrams with rewrite rules. The ZX-calculus has found applications in reasoning about quantum circuits, condensed matter systems, quantum algorithms, quantum error correcting codes, and counting problems. A key notion is the stabiliser fragment of the ZX-calculus, a subfamily of ZX-diagrams for which rewriting can be done efficiently in terms of derived simplifying rewrites. Recently, higher dimensional qudits - in particular, qutrits - have gained prominence within quantum computing research. The main contribution of this work is the derivation of efficient rewrite strategies for the stabiliser fragment of the qutrit ZX-calculus. Notably, this constitutes a first non-trivial step towards the simplification of qutrit quantum circuits. We then give further unexpected areas in which these rewrite strategies provide complexity-theoretic insight; namely, we reinterpret known results about evaluating the Jones polynomial, an important link invariant in knot theory, and counting graph colourings.
Tensor network contraction is central to problems ranging from many-body physics to computer science. We describe how to approximate tensor network contraction through bond compression on arbitrary graphs. In particular, we introduce a hyperoptimization over the compression and contraction strategy itself to minimize error and cost. We demonstrate that our protocol outperforms both handcrafted contraction strategies in the literature as well as recently proposed general contraction algorithms on a variety of synthetic and physical problems on regular lattices and random regular graphs. We further showcase the power of the approach by demonstrating approximate contraction of tensor networks for frustrated three-dimensional lattice partition functions, dimer counting on random regular graphs, and to access the hardness transition of random tensor network models, in graphs with many thousands of tensors. Published by the American Physical Society 2024
Classical simulation of quantum computation is necessary for studying the numerical behavior of quantum algorithms, as there does not yet exist a large viable quantum computer on which to perform numerical tests. Tensor network (TN) contraction is an algorithmic method that can efficiently simulate some quantum circuits, often greatly reducing the computational cost over methods that simulate the full Hilbert space. In this study we implement a tensor network contraction program for simulating quantum circuits using multi-core compute nodes. We show simulation results for the Max-Cut problem on 3- through 7-regular graphs using the quantum approximate optimization algorithm (QAOA), successfully simulating up to 100 qubits. We test two different methods for generating the ordering of tensor index contractions: one is based on the tree decomposition of the line graph, while the other generates ordering using a straight-forward stochastic scheme. Through studying instances of QAOA circuits, we show the expected result that as the treewidth of the quantum circuit's line graph decreases, TN contraction becomes significantly more efficient than simulating the whole Hilbert space. The results in this work suggest that tensor contraction methods are superior only when simulating Max-Cut/QAOA with graphs of regularities approximately five and below. Insight into this point of equal computational cost helps one determine which simulation method will be more efficient for a given quantum circuit. The stochastic contraction method outperforms the line graph based method only when the time to calculate a reasonable tree decomposition is prohibitively expensive. Finally, we release our software package, qTorch (Quantum TensOR Contraction Handler), intended for general quantum circuit simulation. For a nontrivial subset of these quantum circuits, 50 to 100 qubits can easily be simulated on a single compute node.
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.
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.