WorksPhysics and Astronomy
Tensor Contraction with ZX Calculus, a Graph-Theoretic Approach
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 rewrite preprocessing, and we name the algorithms that apply rewrite preprocessing before regular bond-by-bond contraction 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.
This dissertation is submitted for the degree of MSc in Mathematics and Foundations of Computer Science
Reuben College
I would like to dedicate this thesis to my loving parents . . .
Declaration
The author hereby declares that except where specific reference is made, the contents of this dissertation are original and have not been submitted in whole or in part for consideration for any other degree or qualification in this, or any other university. This dissertation is the independent work of the author under the supervision of the author’s supervisors, and contains nothing which is the outcome of work done in collaboration with others, except as specified otherwise. The author has made his best efforts to ensure the correctness of the results presented, yet there can be no guarantee that the results are free from errors.
Yuhao Han
September 2026
Acknowledgements
Crystal dew on the morning grass Warm lights out of the evening glass Lo, the larks sing and the owls bark We have come a good way through!
We alone cannot do this Without constant support behind us My parents, for most, for their constant support And always being my last resort. Dr Quanlong Wang, our unsolicited tutor, Professor Aleks Kissinger, his voluntary mentor, And Professor Bob Coecke, his kind referrals.
The city of academics, Oxford And the college of newborn, Reuben Such a pleasure to study here! Delicious food, welcoming staff, And shelf after shelf of books Under the ancient name of Bodleian Library. And as importantly, the University Park Home of larks, owls, purple beeches, And both kinds of chestnuts.
James, Ketong, Tianrun, my friends, Who sailed the same boat with me. Gwen, Huari, Jason and Xiaotong, Who ate in the same bowl as me! And, of course, Lulu, my dear The penultimate line is reserved for you And the ultimate for our lovely memories!
List of figures xiii
1 Introduction 1
1.1 Background of Tensor Networks 1
1.2 Related Work: Finding Good Contraction Orders 3
1.3 Outline 4
1.4 Statement of Originality 4
1.4.1 Format and Diagram 5
2 Tensors 7
2.1 Tensors and Basic Operations 7
2.1.1 Abstract Tensor Product 10
2.2 Tensor Networks 12
2.2.1 Order of Edges 13
2.2.2 Only Topology Matters 14
2.2.3 Symmetric Tensors 14
2.3 Complexity of Contraction 15
2.3.1 Why is There a Difference in Complexity? 16
3 Treewidth and Tensor Contraction 19
3.1 Treewidth and its Elementary Properties 19
3.2 Triangulated Graphs and Treewidth 23
3.2.1 From Tree Decomposition to Perfect Elimination Order 25
3.3 Treewidth is the Complexity of Tensor Contraction 29
3.3.1 Tree decomposition Gives a Contraction Order 29
3.3.2 Tensor Contraction Gives a Tree Decomposition 31
4 ZX Calculus 37
4.1 Definition of ZX Calculus 37
Chapter 1
Introduction
Background of Tensor Networks
Tensors, to put it plainly, are arrays of numbers that can be regarded as higher dimensional matrices, and tensor contractions are operations between tensors that are analogous to matrix multiplication.
The word tensor was coined by Woldemar Voigt in his study of the elastic and optical properties of crystals in 1898 [58], and its use was further expanded by Ricci-Curbastro and Levi-Civita under the name absolute differential calculus [45]. They defined a tensor, in a simplified way, as a multilinear map on a product of vector spaces and their duals to . This definition later evolved to the current well accepted notion of tensor product in multilinear algebra defined via the universal property of a bilinear map [32].
The usefulness of tensors originates from their basis-independent property, which is especially important in physics. A physical law must be independent of the coordinate system, and a tensor equation is the most economical way of guaranteeing that it does not. The moment of inertia of a rigid body is a rank-two tensor rather than a single number, because how a body resists being spun depends on the axis about which one spins it. The stress inside a deformed solid is likewise rank-two, for it takes the orientation of a surface and returns the force transmitted across it, while the elastic moduli relating stress to strain form a rank-four tensor. General relativity carries the idea to its conclusion: gravity is not a force but the curvature of spacetime, and Einstein’s field equations [15] equate a curvature tensor with the energy-momentum tensor of matter, a statement whose very grammar asserts that no coordinate system is privileged. Quantum mechanics is no exception, for the state space of a composite system is by postulate the tensor product of the state spaces of its parts, the algebraic root of both entanglement and the exponential growth of Hilbert space [37].
In mathematics, tensor product is defined via the universal property of a bilinear map, as we will show in chapter 2. This universal property makes it a natural construction in category theory. In differential geometry a tensor field assigns a tensor to every point of a manifold, and metrics, differential forms, connections, and curvature are all tensor fields; the formalism is what makes calculus possible on a space that admits no preferred coordinates.
It was Roger Penrose who first used diagrammatic notation, called tensor networks, to represent complicated tensor structures [41]. His intuitive notation immediately promoted the popularity of tensors. Since then, tensor networks have found fruitful applications in many areas of science, and above all in the theoretical and numerical study of quantum many-body systems and of quantum computation [38]. A chain of spin-half particles inhabits a Hilbert space of dimension , so that merely storing the state of fifty of them exceeds any conceivable computer; but the states that nature actually realises are far from generic, and their modest entanglement allows them to be written as the contraction of a network of small tensors. This is the insight behind matrix product states and the density matrix renormalisation group [63, 49], and behind projected entangled pair states in two and higher dimensions [57]. Closer to the subject of this dissertation, the output amplitude of a quantum circuit is by definition the full contraction of a tensor network [35], so that the classical simulation of a quantum computer is precisely the problem of contracting a network efficiently. The claim of quantum advantage made for Google’s Sycamore processor [2] was contested, and largely deflated, by exactly such contraction algorithms [40].
Outside physics, tensors are the currency of high dimensional numerical computation and of data analysis. Low-rank decompositions of tensors, pioneered a century ago and long standard in psychometrics, form a classical toolkit [31]; the tensor-train format in particular is how numerical analysts defeat the curse of dimensionality [39]. Maybe most famously, tensors are the core and most indispensable data structure of machine learning, where the dominant numerical frameworks are built around them and indeed named after them, and where tensor network methods borrowed from physics serve as models in their own right [53].
What all of these applications share is a single computational bottleneck: the cost of evaluating a tensor network. The cost depends on the order in which its indices are summed away (this operation is called contraction of an edge), and finding the best order is NP-hard [64]. Finding the optimal contraction order is equivalent to finding a special graph theoretical property of the line graph of the tensor network, called treewidth.
Related Work: Finding Good Contraction Orders
Because finding the optimal contraction order is NP-hard, every practical contraction algorithm settles for a good order found by heuristic means. It is worth surveying these heuristics, both because they are the algorithms that our preprocessing is designed to complement, and because they arrange themselves naturally into the same graph-theoretic categories as chapter 3.
The first family descends from the treewidth literature itself. Markov and Shi [35] introduced tree-decomposition-based contraction of quantum circuits, the construction we restate as theorem 3.24; within graph theory, good tree decompositions have long been produced by elimination heuristics such as minimum degree and minimum fill-in [48] [47], by maximum cardinality search, and by combinations of these wrapped in randomisation [4]. In the language of this dissertation these are contraction order heuristics in disguise: simplicial elimination of a vertex of the line graph is exactly the contraction of the corresponding bond (lemma 3.28), so an elimination ordering of and a contraction order of are the same object, and each heuristic above is directly an ordering heuristic for tensor contraction.
The second family works directly on contraction trees, in the spirit of the dynamic programming solution of the matrix chain problem [22]. Its most widely used representative is opt_einsum [52], which since NumPy 1.12 has supplied the path optimiser of numpy.einsum: it repeatedly performs the pairwise contraction of least incremental cost, and for small networks it can branch and bound over partial orders to certify optimality.
The third family replaces greedy construction by randomised search. Gray’s hyper-optimised contraction [20] re-runs greedy ordering thousands of times with randomly perturbed costs, applies simulated annealing and genetic algorithms over the space of contraction trees, and hands very large or sparse networks to graph partitioners; this is the current state of the art for arbitrary tensor networks.
A fourth family exploits the structure of quantum circuits specifically. One approach divides the space-time volume of the circuit into patches that are contracted almost independently before being stitched back together [40]; another sweeps through the circuit line by line while keeping only a matrix product state boundary, so that the cost is governed by entanglement rather than by treewidth and degrades gracefully on noisy devices [65].
The family closest to this dissertation rewrites the diagram before an order is ever chosen. The standard rewrite rules of ZX calculus, applied automatically by PyZX [26], are routinely used to simplify circuits prior to contraction, and Cam and Martiel [6], whose work inspired this dissertation, likewise reduce the contraction cost of a circuit’s tensor network by graphical rewriting. What is missing from all of these, and what this dissertation contributes, is an explicit optimisation target together with a safety guarantee: we take the treewidth of the line graph as the quantity to be reduced, and we prove (chapter 5) that our rewrite operations — remove edge and unfuse and complementation — can never increase the cost of the best bond-by-bond contraction.
While existing algorithms search for a good contraction order on a fixed network, this dissertation adopts a different approach: transform the network itself into an equivalent tensor network whose line graph has lower treewidth before applying the bond-by-bond contraction algorithm. Our key observation is that in many circumstances this reduction can be achieved by graph operations alone. The preprocessing is complementary to every heuristic surveyed above, any of which can be run afterwards on the rewritten, strictly easier network. The idea is explored in detail in chapter 5.
Outline
We start this thesis with a thorough introduction to tensors and tensor networks in chapter 2. Chapter 3 introduces the concept of treewidth and how treewidth can be used to determine the complexity of tensor contraction. Chapter 4 describes a popular graphical language, ZX calculus, for a special type of tensor networks called quantum circuits. ZX calculus enables us to perform diagrammatic rewrites, which are transformations of a tensor network into another equivalent one. Some of these transformations may reduce treewidth and therefore reduce the complexity of tensor contraction. Chapter 5 explores and proves how each transformation affects treewidth. We also propose an algorithm to exploit these transformations to reduce the complexity of tensor contraction for quantum circuits. These transformations are named as rewrite preprocessing. In the last chapter 6, we discuss different diagrammatic calculi that have the potential to be used for generic tensor contraction.
Statement of Originality
Most of the results in this thesis except those in chapter 5 are well established in the literature and they are cited properly. All of the explanations, proofs, diagrams, demonstrations, and discussions are my own work and interpretations, unless otherwise stated.
All of the proofs in chapter 3 are my own, although they are classical results in graph theory. They drew much inspiration from Introduction to Graph Theory by Douglas B. West [62] and several other papers including [10, 17, 47, 19].
The sections on ZX and ZXW calculus in chapters 4 and 6 are mostly based on the book by Kissinger and van de Wetering [27], as well as several related papers including those by Wang et al. [60] [43].
The tensor contraction algorithms with rewrite preprocessing are novel, although they were inspired by the paper by Cam and Martiel [6].
Another important part of this thesis is the computer programs I wrote to implement the algorithms, which I named cartographer. It is responsible for most of the computer simulation and is available at https://github.com/harryhanYuhao/cartographer.
The figures in this thesis draw inspiration from the illustrations in [27] and [59]. Most of them are drawn by myself using cartographer and the open-source software zxw-graphboard1.
I use the open-source LLM DeepSeek, and Zhipu GLM, as well as the proprietary LLM ChatGPT to help with proofreading, literature search, and some coding tasks. No other parts of this thesis were involved with any AI tools. No other AI models are used.
Format and Diagram
The thesis is typeset using LaTeX and the CUED Template created by Krishna Kumar. The figures are created using TikZ and the open-source graph-board program at https://github.com/harryhanYuhao/graphboard.
Tensors
Tensors and Basic Operations
We present the following straightforward definition of tensors, which is a rephrasing of Penrose’s original definition [41].
Definition 2.1. Given , let denote the set . A tensor of rank is a function .
By convention, we shall write the value as , where each is called an index. Of course, the output of can be or any other ring. We take it to be in this dissertation for convenience. The value is called the dimension of the -th index, which will always be clear from the context.
Following the convention of Einstein summation, a tensor is denoted by a capital letter with its indices as free variables shown in the subscript. The class of all tensors is denoted by the calligraphic letter .
A tensor is, plainly and unostentatiously, an arrangement of numbers with specified orderings by the indices. For example, a rank-one tensor is a vector, a rank-two tensor is a matrix, and a rank-three tensor is an arrangement of matrices.
The following tensors denote a vector and a matrix, while Figure 2.1 depicts the rank-three tensor as a stack of such matrix slices.

Figure 2.1. A rank-three tensor regarded as a stack of matrices.
There are at least seven natural operations for tensors.
Observation 2.2.
Addition . Let and be two tensors of the same rank. Then their sum is defined by .
Scalar multiplication . Let be a tensor and . Define .
Permutation. . Let be a tensor of rank . For any permutation , the permuted tensor is defined by .
Flatten . Let be a tensor. Any two of the indices of can be flattened into one to create a new tensor. Say we would like to flatten the indices and , of dimensions and . Let be an index of dimension , and we define the new tensor as .
Unflatten, which is exactly the opposite operation of flatten.
Outer product . Let and be any two tensors. Their tensor product is defined by . Outer product is sometimes called tensor product or Kronecker product.
Contraction. . Let and be tensors of rank and . Their contraction over the index is a tensor of rank defined by , where is the dimension of the index . If there are many different tensors with the corresponding contraction indices specified, their full contraction gives a new tensor defined as
where to are the indices to be contracted.
Addition and scalar multiplication of tensors are clear enough. Permutation of indices is a generalisation of the matrix transpose. For example, consider a rank-two tensor , and define .
Outer product and flattening are demonstrated in Figure 2.2.

Figure 2.2. (a) The outer product of a vector and a matrix yields the rank-three tensor . (b) Flattening the indices and of into a single index yields the matrix .
Usually, outer product and flattening are used together to convert tensor products of two arbitrary tensors into a single matrix, for example
In general, if we have two matrices and , their outer product will be
Contraction is the most complicated operation. For the matrices, and , their contraction over the index is a matrix defined by , which is exactly the matrix multiplication.
Given a set of tensors and the corresponding contraction indices, the contraction order does not matter, because we can freely change the order of and add parentheses to nested summations.
This is an important observation and we will make it a lemma.
Lemma 2.3 (Contraction Order Does Not Matter). Given a set of tensors and the corresponding contraction indices, the contraction order does not matter.
Abstract Tensor Product
In multilinear algebra, the definition of tensor product is thus.
Definition 2.4 (Tensor Product of Vector Spaces). Let be vector spaces over a field . Their tensor product, denoted as , is the unique vector space over that satisfies the following universal property as demonstrated in Figure 2.3: there exists a bilinear map , and for every bilinear map to any vector space , there exists a unique linear map such that .
Figure 2.3. Commutative triangle for tensor product.
Equivalently, the tensor product of two finite-dimensional vector spaces and , with basis and is the dimensional vector space with basis , that satisfies the following bilinearity conditions:
where are the appropriate indices of the basis vectors.
I hope the original definitions of tensor product justify our nomenclature of tensor in definition 2.1. It is clear that
A rank-one tensor, , is a vector in some vector space , where the dimension of the index is the dimension of .
In general, a rank- tensor has additions and scalar multiplications, so the set of rank- tensors with fixed dimension for each of their indices, denoted by , is a vector space. This vector space has a basis , where if and only if , and 0 otherwise. This set of bases is precisely the basis of the tensor product of vector spaces .
Flatten is the canonical isomorphism between the vector space . (And unflatten is its inverse.)
Outer product is the canonical bilinear map guaranteed by the universal property of tensor product.
In linear algebra, there is an intrinsic notion of input and output. For example, in vector space a vector is an element of . Its dual is a function , and a matrix is a function . In physics, the inputs and outputs of a tensor are differentiated by the upper and lower indices. For example, denotes the class of tensors , where is a vector space and is its dual. While differentiating inputs and outputs seems an intuitive idea, it is unwieldy in our algorithmic investigation of tensor product. Therefore, we will not differentiate input from output unless otherwise specified.
Tensor Networks
Suppose we have two tensors and , where indices and have dimensions and while both of the indices and have dimension . Suppose that we would like to perform the following operation: ‘contracting the first index of with the second index of , and contracting the last index of the resulting tensor with the first index of another copy of . The precise statement of specifying operations on tensors is too verbose and painful to articulate. The tensor network, a graphical representation of tensors and their operations, is used to make these statements concise and clear.
Definition 2.5 (Tensor Network). A tensor network is a generic graph structure consisting of vertices and edges that denotes the tensor resulting from the various operations on a set of tensors, following the three rules below.
Rule 1. In a tensor network, a rank- tensor is represented as a node with edges. Usually, the shape, color, and labels of the nodes are used to differentiate different tensors. For example, a vector , a matrix , and a rank-three tensor are represented as in Figure 2.4.

Figure 2.4. Rank 1, 2, and 3 tensors
Rule 2. A diagram with two tensors placed side by side is interpreted as the outer product of the two tensors, as shown in Figure 2.5.

Figure 2.5. Outer Product in Tensor Network
Rule 3. An edge connecting two nodes represents the contraction of the two tensors over the index represented by that edge.
We may also define tensor networks as a special kind of subgraph such that
it allows loops and multiple edges,
its vertices are of different types,
the order of the edges of a vertex matters.
The value of a tensor can be evaluated by plugging in the values of the indices. In a tensor network, this is analogous to assigning a value to each of the edges and the graph can then be evaluated to some number.
For example, consider the tensor . In explicit tensor notation, and . In tensor network notation, is represented as a node with two edges. Labelling the edges with 0 and 1 respectively evaluates the tensor as shown in Figure 2.6.
Figure 2.6. Evaluating a tensor network
Order of Edges
While tensor networks do not differentiate input and output, they do differentiate the order of the bonds of a tensor. For example, Figure 2.7 shows the transpose of .
Figure 2.7. Transpose in Tensor Network
The edges are typically ordered from top to bottom and from left to right. Orders can also be specified by labelling the edges with indices of the tensor. For example, in Figure 2.8 we demonstrate matrix multiplication, a non-commutative operation, in tensor network notation.

Figure 2.8. Contracting the two rank-two tensors and over their shared index gives the rank-two tensor .
Only Topology Matters
Only Topology Matters
There is a subtlety in the graphical notation. Each subgraph of a tensor network can itself be regarded as a new tensor resulting from the full contraction of its nodes. For example, in Figure 2.8, the two nodes and can be regarded as a new node with two edges, and in Figure 2.5, the two nodes and can be regarded as a new node with two edges. Given a tensor network, there are many different ways to decompose a tensor network into subgraphs and many different orders for contraction; will all of them give the same result?
Fortunately, lemma 2.1 guarantees that the answer is yes, as long as the nodes and their connections are determined. The tensor network notation precisely captures the nodes and the connections between them, so the tensor network notation is unambiguous and well-defined. This property is summarised in the phrase ‘only topology matters’.
Symmetric Tensors
A special class of tensors is worth our attention.
Definition 2.6 (Symmetric Tensor). A tensor is called symmetric if it is invariant under any permutation of its indices, i.e. for any permutation , we have
In tensor network notation, permuting the edges of a symmetric tensor does not change the tensor, as shown in figure 2.9.
Tensor networks that consist of only symmetric tensors can be regarded as coloured hypergraphs, as the order of the edges of a symmetric tensor does not matter. Therefore, if there are no dangling legs, the networks of symmetric tensors can indeed be regarded as
Vector (PDF)
caption: Permuting the edges of a symmetric tensor does not change the tensor.
:::
coloured hypergraphs, and two networks that are isomorphic as hypergraphs are equivalent as tensor networks.
If there are dangling legs, the order and connection to those legs still matter, as contraction between symmetric tensors may give non-symmetric tensors. In this case, we can regard each dangling leg as a normal edge connected to a special node coloured in its unique colour.
We shall summarise this observation as only connectivity matters.
Lemma 2.7 (Only Connectivity Matters). Two tensor networks without dangling legs that are composed of only symmetric tensors are equivalent if they are isomorphic as coloured hypergraphs. That is, they equal the same tensor if they have the same nodes and connections between them.
If they do have dangling legs, the ordering of the dangling legs still matters.
Complexity of Contraction
Let us investigate the algorithmic complexity of tensor contraction, which is a problem of paramount importance as it is used in so many applications, such as quantum circuit simulation, machine learning, and almost all kinds of mathematical modelling.
For simplicity, we assume all indices in this section have dimension .
Contraction of two rank-2 tensors, and , gives another rank-2 tensor . Each entry of is computed using the formula
Computing a single entry thus takes multiplications and additions. There are a total of entries to compute, so the total number of operations is .
Similarly, contraction of one bond between a rank and a rank tensor will result in a rank tensor. Each entry of the resulting tensor is computed by summing over products of entries from the two tensors, so the total number of operations is .
We may also choose to contract multiple bonds simultaneously. In general, contracting bonds between a rank and a rank tensor will result in a rank tensor. Each entry of the resulting tensor is computed by summing over products of entries from the two tensors, so the total number of operations is .
It is thus clear that contracting bonds simultaneously over a tensor network with external bonds will take operations. This is an important observation that is worth writing down.
Lemma 2.8 (Complexities of Tensor Contraction by Counting Edges). Let be a tensor network with external bonds and internal bonds. Contracting all the internal bonds of will take operations.
It may surprise the reader that different orders of contraction may have different computation costs. For example, contracting the following tensor fully, which will give a scalar, can be done in two different orders as shown in Figure 2.10 and Figure 2.11. The first contraction order takes , while the second contraction order takes .
Figure 2.10. Slow contraction order
Figure 2.11. Fast contraction order
Why is There a Difference in Complexity?
As equation (1) shows, different orders of tensor contraction correspond to different orders of the nested summation, which is a result of three basic rules of arithmetic: commutativity, associativity, and distributivity. It is natural to wonder why such simple arithmetic identities can lead to such a difference in computation cost. This section examines the question.
Consider the following identity
The left-hand side of the equation takes additions for , additions for , and one multiplication between the sums, which is a total of operations. The right-hand side, however, takes multiplications between and and additions, amounting to a total of operations. This is a big difference all caused by the distributive law.
The impact of the order of operations for matrices is even more pronounced. For example, consider and . Consider the following operations calculated in two different orders:
The left-hand side takes two matrix-vector multiplications, which is operations, while the right-hand side takes one outer product, costing , and one matrix-matrix multiplication, costing operations.
In general, both finding the optimal order and determining if a given order is optimal are NP-hard problems. There are, nevertheless, many heuristic algorithms to find a good contraction order. In this thesis, we will discuss in detail one such algorithm, which relies on a graph-theoretic property called treewidth.
Note on Strassen’s Algorithm
While this dissertation focuses on tensor contraction, we do not touch the even more basic problem of matrix multiplication. It is perhaps surprising that even the simple matrix multiplication defined by computing the sum
may have a more efficient algorithm than the naive complexity [12]. The first matrix algorithm that beats the naive algorithm was Strassen’s algorithm with complexity [54].
Recently, there have been studies on whether the idea of Strassen’s algorithm can be generalised to tensor contraction. It has been discovered that the complexity of tensor contraction is closely related to another property called tensor rank, which is a generalisation of matrix rank.
Studying algorithms of this nature deserves another independent dissertation.
Chapter 3
Treewidth and Tensor Contraction
The concept of tree decomposition and treewidth was first introduced by Robertson and Seymour to prove the famous graph minor theorem, which we state here for reference.
Theorem 3.1 (Graph Minor Theorem, Robertson and Seymour [46]). For any infinite sequence of finite graphs , there exist indices such that is a minor of .
Treewidth was later proved to be very useful in many different areas of graph theory. As the core algorithmic idea in this dissertation relies on treewidth, it is worth our effort to introduce treewidth and its properties in detail.
Treewidth and its Elementary Properties
Definition 3.2 (Tree Decomposition). Let be a finite graph and its vertex set. A tree decomposition of is a pair where is a tree and is a family of subsets of (called bags) such that
,
If vertices are adjacent, there exists a such that .
Let be vertices of . Since is a tree, there is a unique path connecting and , which is denoted as . If and , then for all , we have .
Let be the bag such that (That is, is the bag of the largest order). The width of the tree decomposition is .
Definition 3.3 (Treewidth). The treewidth of a graph is the minimum width over all of its tree decompositions.
A tree decomposition requires the existence of a bag that contains all adjacent vertices. If and such that , however, this does not guarantee that and are adjacent in .
Exempli Gratia 3.4. (All graphs have a trivial tree decomposition.) Let be a graph with vertex set . Then is a tree decomposition of where is a single node and . The width of this tree decomposition is .
Therefore, the treewidth of any graph is bounded above by . By Zorn’s lemma, there must exist a tree decomposition of with minimum width.
Let us look at some examples of tree decompositions.
Exempli Gratia 3.5. (Tree decomposition of a Tree). Let be a tree. We can construct a tree decomposition of in the following way.
Let each vertex of be a bag that contains only itself.
On each edge of , add a bag that contains the two endpoints of the edge.
An example of this tree decomposition is shown in Figure 3.1. This shows that the treewidth of a tree is 1. For any tree with at least one edge, there must be a bag that contains two or more vertices. This proves that the treewidth of a non-trivial tree is exactly 1.
Figure 3.1. A tree decomposition of a tree.
Exempli Gratia 3.6. (Tree Decomposition of Some Triangulated Graphs). See figure 3.2 for an example of a tree decomposition of a triangulated graph.
The following lemma will be useful.
Figure 3.2. A tree decomposition of a triangulated graph.
Lemma 3.7. Let be a graph and its tree decomposition with at least three vertices. Let . If deleting from produces at least two disconnected subgraphs of , which we label as , then the subgraphs of induced by the vertex sets and are disconnected.
Proof. It is sufficient to show that no vertex is adjacent to any vertex .
Assume that and and they are adjacent. Let , , and let be the unique path from to in . Since and lie in different components of after deleting , the path contains the vertex .
By property 2 of tree decomposition, there exists such that . Since is connected, there exists a path from to and path from to . If none of them pass through , then there is a cycle in consisting of , , and . This contradicts the fact that is a tree. Therefore, at least one of them must pass through .
Without loss of generality, let pass through . is a path whose endpoints are bags that contain , so by property 3 of tree decomposition the bag contains as well. This is a contradiction to the assumption that . Q.E.D.
Exempli Gratia 3.8 (Treewidth of a Complete Graph). The treewidth of a complete graph is , as all tree decompositions of must contain a bag that contains all vertices of .
To prove this claim, assume is a tree decomposition of and let be the largest bag of that does not contain all vertices of . Since does not contain all vertices of , there exists a vertex such that , which lies in some other bag . Again, as is connected to all other vertices and does not contain all vertices, there must be a third bag in .
In a tree with at least three vertices, there must exist a vertex such that deleting from produces at least two disconnected subgraphs of . Now we can invoke lemma 3.1, which states that the corresponding subgraphs of are disconnected. This is not possible, as is a complete graph, so all vertices are connected.
Therefore, all tree decompositions of must contain a bag that contains all vertices of , which proves the claim.
If a graph is a minor of , then the treewidth of is less than or equal to the treewidth of . The definition of graph minor is presented here for reference.
Definition 3.9 (Graph Minor). Let and be two graphs. We say that is a minor of if can be obtained from by a sequence of the following operations:
Deleting an edge,
Deleting a vertex,
Contracting an edge.
The process of contracting an edge is to delete the edge and merge the two vertices and into a single vertex . The new vertex is adjacent to all the neighbours of and .
Lemma 3.10 (Graph Minor and Treewidth). Let and be two graphs. If is a minor of , then the treewidth of is less than or equal to the treewidth of .
The proof of this lemma is presented in section A.2.
We can use lemma 3.10 to prove various lower bounds on the treewidth.
Corollary 3.11. Let be the minimum vertex degree of a simple graph . The treewidth of is at least .
Proof. The cases or are trivial, because only one-vertex trivial graph has tree width 0 and everything else has treewidth at least 1.
For graph with , we only need to realise that
There are at least vertices in
Contracting an edge connected two vertices each with degree equal or more than 2 will create a new vertex with degree greater than or equal to .
Therefore, we can continuously contract edges in until we obtain a complete graph , where . By lemma 3.10, the treewidth of is at least the treewidth of , which is greater than .
Q.E.D.
Using these lemmas, we can find the treewidth of more complicated graphs.
Exempli Gratia 3.12. The treewidth of a cycle graph is 2. By corollary 3.11, the treewidth of a cycle graph is at least 2 as the minimum vertex degree of a cycle graph is 2. We can construct a tree decomposition of a cycle graph with width 2 as follows.
Let vertex be the start of the cycle. Delete one edge next to and treat the rest of the graph as a tree, with the maximum bag of size 2. Adding to all bags of the tree decomposition gives a tree decomposition of the cycle graph with bags of maximum size 3 and width 2.
See Figure 3.3 for an example.

Figure 3.3. A tree decomposition of a cycle graph.
Triangulated Graphs and Treewidth
Treewidth is closely related to triangulated graphs, as we shall explain in this section.
Definition 3.13 (Triangulated Graph). A graph is triangulated if every cycle of length greater than or equal to 4 has a chord. A chord is an edge that connects two non-adjacent vertices in the cycle. Triangulated graphs are also called chordal graphs.
The triangulation property is a subtle requirement for the connections between vertices. In one sense, for triangulated graph two vertices are far away from each other if and only if there is no loop connecting them.
Figure 3.4 shows examples of two triangulated graphs. All trees and complete graphs are triangulated. Cycles of length greater than three are not. Unions of triangles are not guaranteed to be triangulated. See Figure 3.4 for examples of triangulated and non-triangulated graphs.

Figure 3.4. Examples of two triangulated graphs (tree and clique) and two non-triangulated graphs (cycle and union of triangles). The chordless cycles of non-triangulated graphs are dashed in blue.
Lemma 3.14 (Removing a vertex does not make triangulated graph non-triangulated). Let be a triangulated graph and any vertex in . Then the graph is triangulated. Note that is the graph induced by the vertex set .
Proof. If is not triangulated, then there exists a cycle of length greater than or equal to in that does not have a chord. The same cycle exists in and does not have a chord, meaning is not triangulated either. This concludes the proof by contraposition. Q.E.D.
The following lemma follows by induction.
Lemma 3.15 (Induced Subgraph of Triangulated Graph is Triangulated). Let be a triangulated graph and an induced subgraph of . Then is triangulated.
Definition 3.16 (Simplicial Vertex). A vertex in a graph is simplicial if the subgraph induced by the neighbours of is a complete graph.
Lemma 3.17 (Existence of Simplicial Vertex in Triangulated Graphs). Every triangulated graph has at least one simplicial vertex.
The proof of this lemma is presented in section A.2.
Definition 3.18 (Perfect Elimination Ordering). A perfect elimination ordering of a graph is an ordering of the vertices such that each vertex is simplicial in the subgraph induced by .
The reason it is called a perfect elimination is that is a simplicial vertex in , is a simplicial vertex in (that is, the graph with vertex removed), and so on. An example of a perfect elimination ordering of a triangulated graph is shown in Figure 3.5.
Figure 3.5. Perfect elimination ordering of a triangulated graph. The simplicial vertices at each step of elimination are coloured in red.
Theorem 3.19 (Triangulated Graph and Perfect Elimination Ordering). A graph is triangulated if and only if it has a perfect elimination ordering.
Proof. Proof of the sufficient condition. Assume has a perfect elimination ordering . Let be a cycle of length greater than 3. Among the vertices in , one of them is ordered first in the perfect elimination ordering, say . connects to at least two other vertices in , which we label as . Since is simplicial in the subgraph induced by , there is an edge connecting , which is our desired chord.
The necessary condition can be proved by induction on the number of vertices in using lemma 3.17.
The base case is when has only one vertex, which is trivially simplicial.
Let be a triangulated graph with vertices. By lemma 3.17, there exists a simplicial vertex in . Elimination of gives with vertices. is triangulated by lemma 3.14. So the proof is done by induction. Q.E.D.
From Tree Decomposition to Perfect Elimination Order
Recall that an induced subgraph of a graph is a graph formed from a subset of the vertices of and all of the edges connecting pairs of vertices in that subset. Using the notion of induced subgraph, we have the following important theorem that connects treewidth and triangulated graphs.
Theorem 3.20 (Treewidth and Triangulated Graph). For every graph , there exists a triangulated graph such that is the induced subgraph of and .
Proof. Let be a graph. It is sufficient to show that for every tree decomposition of , which we label as , there exists a triangulated graph with the same tree decomposition and such that is the induced subgraph of . We shall give a constructive proof.
We can construct the triangulated graph from in the following way. Start by initialising with only the vertices of and no connections between them. Perform the following steps, where in each step we add more edges to and remove bags in . The algorithm terminates when becomes an empty graph.
Let be a leaf in .1 Let be the parent of in . We assume that is a set of one element. If it is not, modify the tree decomposition in the process described below to make it so.
Let be the unique vertex in . We claim that no other bag in contains . If there is another bag that contains , the path from to that bag must pass through , and must contain by property 3 of tree decomposition. This is a contradiction to the assumption that .
Add enough edges to the graph such that the subgraph induced by becomes a complete graph.
Remove from and repeat the process until is empty.
This process must terminate because in each iteration one bag is eliminated from and is finite. In the -th iteration, we work on the special vertex that is the only vertex contained in . It is clear that is a perfect elimination ordering of ; therefore is triangulated. The original tree decomposition is still a valid tree decomposition of , because the structure and the bags of are not changed, and each edge added to is contained in some bag of .
If is a set of more than one element, we perform the following modification to the tree decomposition to make it have one leaf bag that contains exactly one more vertex than its parent.
If is empty (that is, does not contain any vertices beyond those in ), then we can remove from and the tree decomposition is still valid.
If has more than one element, we can split into multiple bags, each containing one more element of . Check Figure 3.6 for a demonstration of this process.
Figure 3.6. The process of making a leaf in a tree decomposition contain only one more vertex than its parent.
Q.E.D.
Triangulated Graphs and Treewidth
The triangulated graph constructed from in theorem 3.20 is also called an optimal triangulation or an optimal chordal completion of in the literature [47].
This constructive procedure is summarised in Algorithm 1.
Algorithm 1 Triangulation from a tree decomposition
Require: A graph and a tree decomposition of .
Ensure: Return a triangulated graph with and , and a perfect elimination ordering of , such that is a tree decomposition of .
; initialise as the empty list.
while has at least two bags do
Let be a leaf bag of and its parent.
if then
Delete from . ▷ redundant leaf
else
Write .
Replace by the path . ▷ leaf now has one extra vertex
for do
.
Make a clique in (add all edges among its vertices).
Append to ; delete from .
end for
end if
end while
Let be the single remaining bag of .
Make a clique in ; append the vertices of to .
return .
A demonstration of this process is shown in Figure 3.7. Note that this process generates a perfect elimination ordering for the triangulated graph.
Figure 3.7. Demonstration of constructing a triangulated graph with the same tree decomposition. The original graph is shown in the top left, and the tree decomposition is shown in the top right. Each step of generating the triangulated graph is shown in the bottom with boxes. The corresponding bags in the tree decomposition are highlighted in red.
There is a different way to describe this process, using the term simplicially eliminated.
Definition 3.21 (Simplicial Elimination). Let be a graph and any vertex, not necessarily simplicial, in . The graph operation of simplicial elimination of from is to add edges between all the neighbours of in and then remove from to produce a new graph.
Treewidth is the Complexity of Tensor Contraction
Corollary 3.22 (Simplicial Elimination Process to Generate Triangulated Graph). Let be a graph and be an ordering of the vertices generated by the process described in theorem 3.20. Simplicially eliminate from to produce a new graph . Inductively simplicially eliminate from to produce a new graph for .
Let be the graph on the vertices of obtained by adding to all the edges that are added during the process of eliminations above. The graph is triangulated and is an induced subgraph of . (That is, the graph contains all the vertices of and all the edges of $G.)
The order of vertices in theorem 3.20 is a simplicial elimination ordering of . This ordering is important for our later discussion, and therefore deserves a formal definition.
Definition 3.23 (Simplicial Elimination Ordering). 2 Let be a graph not necessarily triangulated. Let be one of its tree decompositions and be an ordering of the vertices generated by the process described in theorem 3.20. The ordering is called a simplicial elimination ordering of .
Treewidth is the Complexity of Tensor Contraction
This section gives the major result of this chapter, theorem 3.32.
Tree decomposition Gives a Contraction Order
It is possible to derive an upper bound for tensor contraction cost using treewidth.
Theorem 3.24 (Treewidth Bound on Tensor Contraction Cost). Let be a tensor network with no loose bonds, regarded as a graph. Let all the bonds of be of dimension . It is possible to contract with a cost of , where is the treewidth of the line graph of .
Markov and Shi first discovered this connection [35]. The theorem is constructive, and there exists an algorithm to find such a contraction order, which we break down in the following steps.
Definition 3.25 (Line Graph). Let be a graph. The line graph of , denoted as ,3 is a graph such that each vertex of represents an edge of , and two vertices of are adjacent if and only if their corresponding edges share a common endpoint in . For an edge , we label the corresponding vertex in as .
Exempli Gratia 3.26. See Figure 3.8 for an example of a graph with 6 vertices and 7 edges and its line graph with 7 vertices and 11 edges.
Figure 3.8. Graph and its line graph . The edges of and vertices of are labelled with the same letter.
Let be a graph and its line graph. An edge in has a corresponding vertex in , which we denote as . The number of edge neighbours of in precisely equals the degree of vertex in . Therefore, using lemma 2.8, we see that the cost of contracting a bond in is .
Lemma 3.27 (Complexity and Vertex Order). Contracting an edge in a graph has a cost of , where is the corresponding vertex of in the line graph .
If an edge is contracted in , all the neighbouring edges of become neighbours of each other if they are not already. The corresponding changes in its line graph are exactly simplicial elimination (definition 3.21) of the vertex in . This process is demonstrated in Figure 3.9.
Figure 3.9. Contracting an edge (in dotted red) in makes all the neighbours of the corresponding vertex in neighbours of each other. This is exactly the simplicial elimination of in . The cost of this contraction is , as the degree of in is 2.
Lemma 3.28 (Contracting Edge is Simplicial Elimination). Contracting an edge in a graph is equivalent to simplicially eliminating the corresponding vertex in the line graph .
Therefore, given any tree decomposition of , we can find a simplicial elimination ordering guaranteed by theorem 3.20. The corresponding ordering of edges in , is our desired contraction order. Each contraction will take at most time, and the total cost of contracting is bounded above by , where is the total number of edges. The process of finding the contraction order is demonstrated in figure 3.10.
We shall summarise our important discovery in a theorem.
Lemma 3.29 (Treewidth Gives a Contraction Order with Same Complexity). Let be a tensor network with no loose bonds, regarded as a graph. Let all the bonds of be of dimension . Given a tree decomposition of (which is the line graph of ), it is possible to find a contraction order with a cost of .
Tensor Contraction Gives a Tree Decomposition
Theorem 3.20 gives us important insights into how to generate a perfect elimination ordering from a tree decomposition and how to use that to create a triangulated graph. Importantly, the treewidth of the triangulated graph by construction is the maximum number of neighbours any has in the subgraph induced by .
We can indeed go from the other direction as well. The converse direction produces what is known as the clique tree (also called a join tree) of a triangulated graph in the literature, which is a tree decomposition in which every bag is a clique. See the survey of Blair and Peyton [3].
Theorem 3.30 (Tree decomposition from Perfect Elimination Ordering). Let be a triangulated graph and be a perfect elimination ordering of . Define the simplex number 4 of vertex as the number of neighbours has in the subgraph induced by . It is possible to construct a tree decomposition of with treewidth equal to the maximum simplex number. (By maximum simplex number, we mean the maximum of all simplex numbers of all vertices in .)
Proof. We will present a constructive proof using induction on the number of vertices in . The idea of the proof is exactly the reverse of the proof of theorem 3.20.
Our induction statement is a bit stronger. That is, for a perfect elimination order , there exists a tree decomposition of with treewidth equal to the maximum simplex number, and there is a bag containing exactly the vertex and all of its neighbours. This bag is also a leaf in the tree decomposition.
The base case: when has only one vertex, the statement is trivially true. Let be our desired tree decomposition promised by the induction hypothesis on the subgraph induced by , and we want to show that the induction statement is also true when we add a new vertex to the front of the perfect elimination order, so that the new perfect elimination order is , and we create a new tree decomposition of the new graph induced by .
Now, let be the set of neighbours of in the subgraph induced by . Without loss of any generality let . Now, is simplicial too and it is ordered first among all the neighbours of , so by induction hypothesis there is a bag (not necessarily a leaf) in , which we label as , such that contains the vertex and all of its neighbours, which includes all of the elements in . Make a new bag and attach it to . This gives us the desired tree decomposition. Q.E.D.
The constructive steps of theorem 3.30 are summarised in Algorithm 2. Figure 3.11 is a demonstration of algorithm 2 to construct a tree decomposition from a perfect elimination ordering.
Figure 3.11. Demonstration of constructing a tree decomposition from a perfect elimination ordering using algorithm 2. The perfect elimination ordering is on the graph shown on the lower left and boxed in dashed lines.
Algorithm 2 Tree decomposition from a perfect elimination ordering
Require: A triangulated graph and a perfect elimination ordering of .
Ensure: The final output is a tree decomposition of whose width equals the maximum simplex number of .
Initialise as a single node with bag .
for do
. a clique, since is simplicial
Let be the vertex in with the smallest index.
Let be a bag of that contains . exists, since is a clique
Add a new node with bag , and attach to .
end for
return .
Using theorem 3.30 and theorem 3.20, we arrive at the following important theorem.
Theorem 3.30 ties well with lemma 3.28, and together they give us the following lemma.
Lemma 3.31 (Contraction Order Gives a Tree Decomposition). Let be a tensor network with no loose bonds, regarded as a graph. Given a contraction order of , it is possible to find a tree decomposition of (which is the line graph of ), such that the complexity of the contraction order lower than or equal to , where is the number of edges in and is the size of the maximal bag in the tree decomposition.
A tensor with no loose bond denote as constant after full contraction. We use this just for convenience.
Proof. We know by lemma 3.28 that contracting an edge is equivalent to simplicial elimination of the corresponding vertex in the line graph. Therefore, given a contraction order of , , the corresponding vertex order is a perfect elimination order of some triangulation of . Now, Theorem 3.30 states that from this perfect elimination ordering we can find a tree decomposition of with the size of the maximal bag minus one equal to the maximum degree of any vertex in the simplicial elimination ordering. This lemma follows from lemma 3.27. Q.E.D.
We now arrive at the following important theorem.
Theorem 3.32 (Treewidth is the Complexity of Tensor Contraction). Let be a tensor network with no loose bonds and let be its line graph. Let all bonds be of dimension and let have vertices. The best possible complexity of contracting , bond by bond, is , where is the treewidth of .
Proof. The proof consists of two parts. First, there exists a contraction order with complexity . Second, no contraction order can have complexity better than .
The existence of a contraction order with complexity is guaranteed by lemma 3.29.
The other direction is guaranteed by lemma 3.31, which states that given any contraction order, we can find a tree decomposition of with the size of maximal bag equal to the exponent of the complexity of the contraction order.
Theorem 3.32 is an equivalent statement of proposition 4.2 in Markov and Shi’s paper [35]. Our proof, however, is completely original.
Theorem 3.32 basically states that finding the best contraction order of a tensor network is equivalent to finding the treewidth of its line graph. This is, of course, not surprising, as we know both problems are NP-hard [5] [64].
It is important to note that theorem 3.32 only governs the complexity of a general contraction algorithm where in each step one bond of the tensor network is contracted. It is possible that a more efficient algorithm can exist that exploits the special structure of the tensor network and contracts multiple bonds at once.
An extreme example is that if we somehow know that a certain tensor is zero, then the whole tensor network must be zero no matter how complicated it is.
Our next chapter will also discuss a more efficient algorithm that exploits the special structure of the tensor network using ZX calculus.
Figure 3.10. Given the tree decomposition of the line graph of a tensor network, it is possible to find a contraction order with a cost of , where tw is the treewidth of the line graph. This figure is a continuation of Figure 3.9, and demonstrates how to find the total contraction order given the tree decomposition. The bond to be contracted, its corresponding vertex in the line graph, and the element in the bag of the tree decomposition are highlighted in red.
Figure 3.12. If the central tensor labelled with 0 is always evaluated to 0, then the whole tensor network must be zero regardless of how complicated it is.
ZX Calculus
This chapter is a quick introduction to ZX calculus, a graphical calculus for quantum circuits. Most parts of this chapter are based on the book [27] and the lecture notes [56].
Definition of ZX Calculus
The theory of ZX calculus consists of two parts: the tensor networks, which are called ZX diagrams, and certain ways they can transform into each other, which are called the rewrite rules. As ZX was invented to represent quantum circuits, all bonds in ZX diagrams are 2-dimensional.
ZX diagrams are generated by the following three classes of generators
Definition 4.1 (Generators of ZX diagrams). ZX diagrams have two classes of generators, and spiders, and one special tensor called the Hadamard gate.
A rank- -spider with phase , which we denote as , is a symmetric tensor such that , , and all other entries are 0.
The Hadamard gate, denoted as , is a 2-legged symmetric tensor that equals
As a matrix, it is unitary and self-adjoint.
A rank- -spider with phase , denoted as , is a symmetric tensor that is the conjugation of of the same rank by the Hadamard gate.
These generators are shown in Figure 4.1. -spiders are shown as green nodes, -spiders red nodes, and their phases are shown as labels on the nodes. The Hadamard gate is shown as a yellow square.
Figure 4.1. Generators of ZX diagrams.
Since ZX calculus was invented to represent quantum circuits, most authors treat ZX diagrams as linear maps with an input and an output instead of a generic tensor. Following the conventional bra-ket notation where denotes a state (a vector, usually written as a column) and denotes its dual (co-vector, also called an effect, written as a row), , and nodes can be represented in the following ways
where and denote the orthonormal basis and respectively. Note that , , and .
The second part of ZX calculus is its rewrite rules, which are the statements that certain combinations of generators are equivalent to each other. Two ZX diagrams are equivalent if they represent the same tensor or they represent the same tensor up to a global constant. (This is because in quantum computation a global constant does not change the result of a quantum measurement.) Throughout this dissertation, a strict equality will be denoted by a sign, while an equality up to a global constant will be denoted by a sign.1 There are infinitely many rewrite rules, but the following are the most crucial ones.
Definition 4.2 (Rewrite rules of ZX diagrams). Eight of the most important rewrite rules are shown in Figure 4.2 and explained as follows:
Figure 4.2. Rewrite rules of ZX diagrams.
Spider fusion, denoted as f. A ZX diagram consisting only of -spiders is equivalent to a single -spider with the sum of the phases of the original spiders as its phase.
Color change, denoted as c. A -spider with phase is equivalent to an -spider with phase conjugated by Hadamard gates on all its legs.
Hadamard cancellation, denoted as hh. Two Hadamard gates are equivalent to the identity.
Identity removal, denoted as id. A single rank-2 -spider with phase 0 and one input and one output leg is equivalent to the identity (a single bond).
-copy, denoted as p. A -phase -spider can be copied through a -spider, and vice versa.
Copy rule, denoted as cp. A 0-phase -spider can be copied through a -spider.
Strong complementarity, denoted as sc. Two sets of 0-phase and spiders that form a complete bipartite graph can be transformed into a simpler graph where the set of spiders is replaced with the same-ranked -spider, and the set of -spiders is replaced with the same-ranked -spider. This is the most crucial one for our later discussion.
Euler decomposition, denoted as e. The Hadamard gate can be decomposed into a sequence of and spiders with specific phases following the Euler decomposition of single qubit unitaries. We only showed one of the possible decompositions in Figure 4.2, but all the possible decompositions are included in the rule set.
As this thesis is focused on tensor contraction, we need to keep track of the constant phase term for the rewriting rules. Fortunately, this is simple.
Lemma 4.3 (Constant in Rewriting Rules). For the rule strong complementarity (sc), -copy (p), and copy rule (cp), the left-hand side and right-hand side of the rewriting rules are equal up to a global constant. If there are -spiders on the left-hand side of the rewriting rules, and -spiders on the right-hand side, then there is a constant factor of on the right-hand side.
There is also a meta rule.
Since a -spider represents the same linear transformation as an -spider but in a different basis, there exists a dual rewrite rule for each rule, where and spiders are swapped.
As ZX calculus is indeed one particular kind of tensor network, all of the properties of tensor networks apply to ZX diagrams, in particular
As all of the ZX generators are symmetric tensors, only connectivity matters (lemma 2.2.3) applies.
All of the tensor operations defined in chapter 2 apply to ZX diagrams.
The surprising property of ZX rewrite rules is that they are complete in the following sense.
Theorem 4.4 (Completeness of ZX rewrite rules). For any two ZX diagrams and , if they represent the same tensor, then there exists a sequence of rewrites from definition 4.1 that transforms into .
As the completeness of ZX rewrite rules is not relevant to our later discussion of the tensor contraction algorithm, the reader is encouraged to refer to the original paper for the proof [23].
Universality and Quantum Circuits
Let us demonstrate the power of ZX calculus in this section by proving the universality theorem of ZX diagrams.
The following quantum gates can be represented as ZX diagrams

Figure 4.3. Common quantum gates represented as ZX diagrams.
In general, -spiders and -spiders are the rotation gates around the and axes of the Bloch sphere, respectively. Therefore, by Euler decomposition, any single qubit unitary can be represented as a ZX diagram. Since all unitary gates can be decomposed into single qubit unitaries and CNOT gates2, we have arrived at the following important lemma.
Lemma 4.5 (ZX diagrams are universal for quantum circuits). ZX diagrams can represent any unitary transformation up to a global phase, and therefore can represent any quantum circuit.
Now, since ZX diagrams can represent the state as shown in Figure 4.4, and for any state in , there exists a unitary transformation that transforms to that state, we have the following corollary.
Figure 4.4. The state represented as a ZX diagram.
Corollary 4.6. ZX diagrams can represent any state in .
Using the Choi–Jamiołkowski isomorphism, which states that any linear transformation can be represented as a state in a larger Hilbert space, we have demonstrated the universality of ZX diagrams.
Theorem 4.7 (Universality of ZX diagrams). Let for some . A ZX diagram can represent any linear transformation and any state .
Random Circuit of Google Sycamore
Let us demonstrate the universality of ZX calculus by expressing the random circuit used by Google’s Sycamore quantum processor [2] as a ZX diagram.
Google’s Sycamore quantum processor simulates a random quantum circuit that is generated in the following way:
Start with the state .
Apply a layer of single-qubit gates on each qubit selected from the set , where .
Choose two qubits at random and apply an iSwap gate on them.
The generators of the Sycamore random circuit can be expressed in ZX diagrams as shown in Figure 4.5, as can be verified by direct computations.
Figure 4.5. Generators of the Sycamore random circuit expressed as ZX diagrams.
Graph-like ZX diagrams
Let us first introduce a new notation, dashed-blue edges, that denotes a Hadamard gate between two spiders.
Graph-like ZX diagrams
Definition 4.8 (Dashed-blue edges). A dashed-blue edge between two spiders denotes a Hadamard gate between them, as shown in Figure 4.6.
Figure 4.6. Dashed-blue edges denote a Hadamard gate between two spiders.
We now prove several identities using the ZX rewrite rules.
Lemma 4.9 (Double Edges between - and -spiders Cancel). As shown in Figure 4.7, two edges between a -spider and an -spider can be removed without changing the tensor represented by the ZX diagram. Note that this identity only asserts that the two diagrams are proportional.
Figure 4.7. Double edges between - and -spiders cancel.
Proof. The proof exploits strong complementarity and the copy rule, and is shown in Figure 4.8.
Figure 4.8. Proof of the double edge cancellation identity.
Q.E.D.
Lemma 4.10 (Hadamard self-loop cancels). A Hadamard self loop on a spider can be removed and only change the tensor represented by the ZX diagram up to a global constant. This identity is proved using Euler decomposition, spider fusion, and lemma 4.9. The proof is shown in Figure 4.9.
Figure 4.9. Proof of the Hadamard self-loop cancellation identity.
Lemma 4.11 (Turning an Edge into a Hadamard Edge). Any edge can be turned into a Hadamard edge joined by a -phase -spider, as shown in Figure 4.10.
Figure 4.10. Turning an edge into a Hadamard edge joined by a 0-phase z-spider.
We are now ready to define a specific type of ZX diagram that will be important for our later discussion on the tensor contraction algorithm.
Definition 4.12 (Graph-like ZX diagrams). A ZX diagram is called graph-like if it satisfies the following conditions:
All spiders are -spiders.
All edges between spiders are Hadamard edges (dashed-blue edges).
There are no parallel edges or self-loops.
Every input and output is connected to a spider, and every spider is connected to at most one input or output.
It is evident that, using lemma 4.9 and lemma 4.10, any ZX diagram can be transformed into a graph-like ZX diagram.
Theorem 4.13 (Graph-like form of ZX diagrams). Any ZX diagram, in particular any quantum circuit, can be transformed into a graph-like ZX diagram.
Proof. The transformation procedure is thus:
Fuse as many - and -spiders as possible so that there are no interconnections between - and -spiders.
Use color change to transform all -spiders into -spiders by adding Hadamard gates on all their legs.
Use lemma 4.9 and lemma 4.10 to remove all parallel edges and self-loops.
If there are non-Hadamard edges, use lemma 4.11 to add 0-phase z-spiders to turn them into Hadamard edges.
See Figure 4.11 for an example of the transformation. Q.E.D.
Figure 4.11. Transformation of a ZX diagram into a graph-like ZX diagram.
Lemma 4.14 (Quantum Circuits in Graph-like form). Any quantum circuit can be transformed into a graph-like ZX diagram.
Local Complementation
This section explains the local complementation identity, which is crucial for our later discussion on the tensor contraction algorithm.
Lemma 4.15 ( graph identity). As shown in Figure 4.12, a complete graph with z-spiders connected by Hadamard gates can be restructured so that the loop is opened.
Figure 4.12. The local complementation.
Proof. Of course, we can prove it by brute force and evaluate the tensor that each side of the equation represents. Yet here we present a purely graphical proof. Q.E.D.
Using lemma 4.4, we can prove the following more general identity.
Figure 4.13. Proof of the local complementation.
Lemma 4.16. Let the box labelled with denote the ZX diagram of a complete graph with -spiders connected by Hadamard gates. Then, as shown in Figure 4.14, the graph can be restructured so that the clique is turned into a star graph.

Figure 4.14. The local complementation.
The proof is by induction on and uses lemma 4.4 as the base case. The reader is referred to lemma 5.2.4 of [27] for the detailed proof.
Using lemma 4.4, we can prove the general local complementation identity, which will be important for our later discussion on the tensor contraction algorithm.
Let us first define local complementation of a graph.
Definition 4.17 (Local Complementation). The local complementation of a graph on a vertex is the operation that replaces the subgraph of induced by the neighbours of with its complement graph. The resulting graph is denoted as . Let be two
A Categorical Approach to ZX Calculus
neighbours of in . is connected to in if and only if is not connected to in . All other connections are left unchanged. An example of local complementation is shown in Figure 4.15.
Figure 4.15. Local complementation of the graph on the vertex . The subgraph induced by the neighbours of is replaced with its complement graph.
Theorem 4.18 (Local Complementation Identity). Let be a ZX diagram consisting of z-spiders connected by Hadamard gates, and let be a vertex in . This ZX diagram is equivalent, up to a global constant and up to some local unitaries applied to and its neighbours, to the ZX diagram of the local complementation of on , denoted as . See Figure 4.16.

Figure 4.16. General Local complementation identity. The ZX diagram of the local complementation of on is equivalent to the original ZX diagram up to a global constant and some local unitaries applied to and its neighbours.
The concept of local complementation was introduced in [14], and is discussed in detail in the textbook [27].
A Categorical Approach to ZX Calculus
In this section, we will use category theory to justify the claim we have made repeatedly in this dissertation: ZX calculus captures the underlying abstract structure of tensor networks.
The ZX calculus was born in the categorical quantum mechanics programme of Abramsky and Coecke [1], and much of its literature is written in the language of categories [56] [8]. Although nothing in this thesis depends on the categorical language, it is worth explaining this approach. Fuller accounts are given by Heunen and Vicary [21]; the exposition follows section 7 of [56].
Definition 4.19 (The category ZX). The category ZX has the natural numbers as its objects, the object being read as parallel wires. A morphism is a ZX diagram with inputs and outputs, the composition plugs the outputs of into the inputs of , and is the diagram of bare wires. On objects the monoidal product is , with the empty diagram as its unit; on morphisms it stacks one diagram above the other.
Since wires may be crossed, ZX is symmetric monoidal. A symmetric monoidal category whose objects are the natural numbers and whose tensor product is their addition is called a PROP, short for product and permutation category, and many authors accordingly speak of the PROP of ZX diagrams. The coherence conditions imposed upon a monoidal category [34] are what licenses drawing diagrams at all rather than writing nested expressions; the principle that only connectivity matters (lemma 2.2.3) is the diagrammatic shadow of their coherence theorem [51] [24].
In definition 2.1 we declined to distinguish the inputs of a tensor from its outputs, whereas definition 4.19 appears to insist upon the distinction; the two are reconciled by compact closure. A symmetric monoidal category is compact closed when every object has a dual equipped with a cup and a cap satisfying the yanking equations [25], which let an output be bent into an input and back again. In ZX every object is its own dual, and both the cup and the cap are the phase-free rank-two -spider: read as undirected tensors in the sense of chapter 2, the identity wire, the cup and the cap are literally the same tensor, so that bending a leg is a redrawing rather than an operation, and nothing was lost by forgetting the distinction in the first place. Reflecting a diagram horizontally and negating its phases gives a dagger: involutive, contravariant, the identity on objects, and on the side of tensors the adjoint, it makes ZX a dagger compact closed category [50].
Until now we have deliberately confused a diagram with the tensor it denotes; to speak of completeness the two must be separated.
Definition 4.20 (Interpretation). Let Qubit be the PROP whose object is the vector space and whose morphisms are the linear maps between them, a full subcategory of finite dimensional complex vector spaces. The interpretation of a ZX diagram is the linear map obtained by contracting the tensor network as in chapter 2.
As contraction respects both plugging and stacking, is a strong monoidal functor which is the identity on objects. It is not injective on morphisms, nor could it be: the very point of the rewrite rules is that distinct diagrams denote the same map. Let therefore be the smallest equivalence relation on diagrams such that for every rule of Figure 4.2, and such that implies both and for all diagrams and ; these two conditions are the licence, used freely above, to rewrite a subdiagram in place. As is a congruence, its classes are the morphisms of a PROP , and the assertion that is well defined is exactly the soundness of the rewrite rules, which need be checked only on the rules of Figure 4.2, with the constants of lemma 4.3.
Two theorems already stated now become statements about this single functor. Theorem 4.7 says that every linear map is for some diagram , which for a functor is the analogue of surjectivity and is called fullness; theorem 4.4 says that implies , the analogue of injectivity, called faithfulness. Universality and completeness together therefore assert that is full and faithful, which is to say an equivalence of categories.
A monoid in a monoidal category is an object with morphisms and satisfying the following identities.
Take , let be the rank-three -spider read with two inputs and one output, and let be the rank-one -spider: associativity and unitality are then instances of spider fusion and identity removal, and reading the same two spiders backwards gives a comonoid , . These four maps and the laws they obey are drawn in Figure 4.17.
Figure 4.17. The -spider as a monoid and a comonoid. Top: the multiplication , the unit , the comultiplication and the counit . Middle: associativity, both sides reducing by spider fusion to the same rank-four spider. Bottom: the unit law. The comonoid laws are the mirror images of these. Redrawn after equations (110), (111) and (113) of [56].
A monoid and a comonoid on one object that satisfy form a Frobenius algebra, special when and a dagger-Frobenius algebra when the two halves are related by as above. Both conditions are drawn in Figure 4.18, and both are again instances of spider fusion, so that the -spiders, and by the meta rule the -spiders, form a commutative special dagger-Frobenius algebra.
Figure 4.18. The Frobenius conditions (top) and speciality (bottom) for the -spider. Redrawn after equations (115) and (116) of [56].
The illuminating fact is the converse, due to Coecke, Pavlović and Vicary [9]: every commutative special dagger-Frobenius algebra on a finite dimensional Hilbert space arises from an orthonormal basis of , its spiders being . Spider fusion is thus no arbitrary axiom but a diagrammatic characterisation of the notion of an orthonormal basis, of which the -spider is the instance for the computational basis. Frobenius algebras long predate this use [30], entering quantum theory through Coecke and Pavlović.
The interaction of the two colours is likewise a familiar structure. A bialgebra is a monoid together with a comonoid whose comultiplication is a homomorphism of the monoid; written diagrammatically, as in the upper half of Figure 4.19, its principal law is exactly the two-by-two case of strong complementarity (sc), with the copy rule (cp) supplying the unit conditions. A bialgebra carrying an antipode that obeys the Hopf law is a Hopf algebra, and here the antipode is the identity, so that the Hopf law reduces to the lower half of Figure 4.19, which the reader will recognise as lemma 4.9.
Figure 4.19. The bialgebra law (top) and the Hopf law (bottom) for the z- and x-spiders. The bialgebra law is the two-by-two case of strong complementarity, and the Hopf law, the antipode here being the identity, is the double edge cancellation of lemma 4.9. Both hold only up to the scalar of lemma 4.3, whence the . Redrawn after equations (118) and (119) of [56].
Either colour may supply the monoid, and a pair of Frobenius algebras so related is called a pair of interacting Frobenius algebras [13]; in the qubit model the law holds only up to the scalar of lemma 4.3, so what we have is a scaled bialgebra. The rule that does the most work in this dissertation is therefore the abstract statement that two orthonormal bases are complementary, which is how Coecke and Duncan introduced the calculus [7].
The ellipses of Figure 4.2 deserve a remark, since each rule containing them is strictly a family of rules indexed by the number of legs. Such families are made precise by the !-box of Dixon and Duncan [11], a subdiagram which may be duplicated any number of times, zero included, and which allows the rules to be given to automated tools such as Quantomatic [28]; not every family is so expressible, the complete graph of lemma 4.4 being the standard counterexample [36].
We are now in a position to state the claim of this section properly. A ZX diagram is a morphism in a free dagger compact closed PROP presented by two commutative special dagger-Frobenius algebras that interact as a Hopf algebra, and no part of that description mentions . Every equation derived by the rewrite rules therefore holds in each model of the theory, under any monoidal functor out of , and not merely under the interpretation of definition 4.20. This is what we mean when we say that ZX calculus captures the abstract structure of tensor networks: the qubit tensors of definition 4.1 are one interpretation of that structure, the qudit tensors and the ZXW calculus of chapter 6 are others, and the graphical reasoning, local complementation included, is the same in all of them.
An Algorithm using ZX Calculus
Theorem 3.32 is a final verdict on any bond-by-bond contraction algorithm of tensor networks. However, it is still possible to find a more efficient algorithm if we can exploit the structure of the tensor network. This chapter attempts to present such an algorithm for quantum circuits using ZX calculus.
Graph Operations and Their Effects on Contraction Complexity
Let us first look at the effect of some of the common graph operations on the complexity of tensor contraction and treewidth.
Lemma 5.1 (Splitting a Vertex Does not Increase Complexity). Let be a graph of a tensor network (we assume is connected and contains at least 2 edges.), be another graph obtained by the operation of splitting a vertex, which is the opposite of spider fusion ( in Figure 4.2, and in Figure 5.1). The best bond-by-bond tensor contraction algorithm on is not more complex than that of .
Figure 5.1. The operation of splitting a vertex
Splitting a vertex may create a different tensor. This lemma only regards the complexity of bond-by-bond contraction, and is not concerned with the equality of the resulting tensor.
Lemma 5.2 (Dividing an Edge Does not Increase Complexity). Let be a graph of a tensor network (which we assume to be connected and contains at least two edges.), be another graph obtained by the operation of dividing an edge (as shown in Figure 5.2). The best bond-by-bond tensor contraction algorithm on is not more complex than that of .

Figure 5.2. Dividing an edge does not increase the complexity of contraction. Left: the original graph. Right: the graph after dividing an edge.
Again, similar to lemma 5.1, this lemma only regards the complexity of bond-by-bond contraction, and is not concerned with the equality of the resulting tensor. The proof of lemma 5.2 is similar to that of lemma 5.1. Detailed proofs of both lemmas can be found in the appendix.
It is worth noting that the condition of the tensor network being a connected non-trivial graph is necessary for both lemmata. This is because, if is the graph with two vertices and one edge, its line graph is a single vertex graph, which has treewidth 0, and both operations will make it into a two-vertex tree which has teeeewidth 1.
Let us define a graph operation based on the K3 local complementation (lemma 4.4) in ZX calculus.
Definition 5.3 (K3 remove edge). Let the graph denote a tensor network. Let be a vertex of degree two with both of its neighbours connected. Let be the diagram with K3 local complementation (lemma 4.4) applied to . The transformation from to is called K3 remove edge.
K3 remove edge is demonstrated in Figure 5.3. K3 local complementation removes a bond and therefore a vertex in the line graph of . Therefore the complexity cannot be greater.

Figure 5.3. K3 complementation on is equivalent to removing a vertex in the line graph .
In practice, removing one vertex in the line graph may reduce the treewidth by one. This is a significant reduction considering that the complexity of tensor contraction is exponential in the treewidth.
We now define another graph operation, called Unfuse and K3 Complementation, specifically for graph-like ZX diagrams.
The Algorithm
Definition 5.4 (Unfuse and K3 Complementation). Let be a graph-like ZX diagram. Let be a vertex in such that has degree 3 or more and two of its neighbours and are connected by a Hadamard edge. We may unfuse to form such that is connected to and , while the rest of the neighbours of are connected to . By applying K3 local complementation to , we can remove the edge . We label the resulting graph as . We do not require to be graph-like.
This process is shown in Figure 5.4.
Figure 5.4. Unfuse a vertex to create a valid vertex for K3 local complementation. The vertex labelled with * is the one on which we want to apply K3 local complementation.
Unfuse and K3 complementation is a combination of dividing an edge, splitting a vertex, and K3 removing edge, therefore the contraction complexity of the resulting graph is no more than that of the original graph.
Unfuse and K3 complementation can be applied as long as there is a Hadamard triangle (a Hadamard triangle is a triangle whose edges are all Hadamard edges) among three -spiders. Since this operation does not create any triangles, we can apply this operation repeatedly until there are no more Hadamard triangles in the graph.
Remark 5.5. Although we know that both of the two operations we defined above (unfuse and K3 complementation, K3 remove edge) do not increase the complexity of tensor contraction, because treewidth is a complicated graph property, we do not know how effectively they can reduce treewidth.
The theoretical study of the effectiveness of these operations is extremely complicated, and, unfortunately, due to time constraints, is not covered in this thesis.
The Algorithm
If our tensor network is a ZX diagram, we can apply the two operations (unfuse and K3 complementation, K3 remove edge) to preprocess the tensor network to potentially reduce the complexity of tensor contraction.
Definition 5.6 (Rewrite Preprocessing). Given a graph-like ZX diagram , we can apply two operations (unfuse and K3 complementation, K3 remove edge) iteratively until they can no longer produce any changes. We call the operation the Rewrite Preprocessing of .
We propose a straightforward algorithm, shown in algorithm 3.
Algorithm 3 Tensor Contraction with Graph Operation
Input: A graph-like ZX diagram .1
Perform Rewrite Preprocessing on to obtain a new graph .
Perform regular tensor contraction algorithm on .
Both operations of K3 remove edge and unfuse and K3 complementation can be performed in constant time if a valid vertex is found. Finding a valid vertex can be done, in the worst case, by checking all vertices and their neighbours, which is time. Note that contraction can be done in only for a tree tensor network, where is the dimension of the bond (in our case, ). This gives reason to expect that our algorithm can be more efficient than the best bond-by-bond contraction algorithm applied to the original graph.
Lemma 5.7 (Complexity of Algorithm 3). Let be a graph-like ZX diagram with vertices. The complexity of algorithm 3 is plus the complexity of the best bond-by-bond contraction algorithm on the resulting graph.
It is very difficult to carry out the rewrite preprocessing by hand even for simple graph-like diagrams. To solve this issue, the entire rewrite preprocessing algorithm has been implemented in the Rust program cartographer available at https://github.com/harryhanYuhao/cartographer. More on the details of implementation can be found in the appendix. Check figure B.1.
Benchmarking Rewrite Preprocessing
Our rewrite preprocessing algorithm has been benchmarked in the following way. First, we generate a random graph-like ZX diagram with vertices via the Erdős–Rényi algorithm [16]. Its line graph is computed, which we label as . We also compute the treewidth of . The new graph is obtained by applying the rewrite preprocessing to . The treewidth of is also computed. The treewidths are found via Tamaki’s positive-instance driven dynamic programming algorithm [55].
These are our key findings.
Of the 441 random graphs generated, the treewidth of 254 decreased, that of 187 was unchanged, and none increased. 2 The comparison of treewidth is shown in Figure 5.5 and Table 5.1.
| decrease | |||||
| 10 | 33 | 42 | 17 | 10 | 7 |
| 11 | 35 | 44 | 16 | 10 | 6 |
| 10 | 26 | 32 | 13 | 8 | 5 |
| 20 | 43 | 50 | 15 | 11 | 4 |
| 19 | 36 | 42 | 12 | 8 | 4 |
| 9 | 23 | 28 | 12 | 8 | 4 |
| 8 | 20 | 25 | 11 | 7 | 4 |
| 7 | 16 | 19 | 9 | 6 | 3 |
| 14 | 18 | 21 | 6 | 4 | 2 |
| 7 | 15 | 18 | 8 | 6 | 2 |
| 6 | 11 | 14 | 6 | 4 | 2 |
| 6 | 11 | 14 | 6 | 4 | 2 |
| 5 | 7 | 9 | 4 | 2 | 2 |
| 5 | 8 | 10 | 5 | 3 | 2 |
| 16 | 27 | 30 | 7 | 6 | 1 |
| 14 | 20 | 22 | 7 | 6 | 1 |
| 14 | 18 | 20 | 5 | 4 | 1 |
| 11 | 11 | 12 | 4 | 3 | 1 |
| 6 | 8 | 9 | 4 | 3 | 1 |
| 6 | 10 | 12 | 5 | 4 | 1 |
Table 5.1. The table of treewidth before and after rewrite preprocessing on 20 random graphs. is the number of vertices in the original graph, is the number of vertices in the line graph of the original graph, is the number of vertices in the line graph of the graph after rewrite preprocessing, is the treewidth of the line graph of the original graph, is the treewidth of the line graph of the graph after rewrite preprocessing, and decrease is .

Figure 5.5. The scatter plot of treewidth before and after rewrite preprocessing. The x-axis is the treewidth of the line graph of the original graph, and the y-axis is the treewidth of the line graph of the graph after rewrite preprocessing. The red line is the line . The points below the red line are the graphs whose treewidth is reduced by rewrite preprocessing.
The average decrease of treewidth is 1.62, out of the mean treewidth 5.56.
Our algorithm also increases the number of vertices in the line graph. The average node count before and after the preprocessing is 13.35 and 15.56, with mean increase of 2.21.
The treewidth decrease is observed on the original line graphs of both high (23) and low (3) treewidth, as shown in Figure 5.5.
It is worth explaining why we did not choose to evaluate the run time of the tensor contraction algorithm before and after rewrite preprocessing. This is because the run time is extremely large on high treewidth graphs, to the extent that it is almost impossible to run on personal computers.
Limitations of Rewrite Preprocessing
The benchmarks show very promising results. However, it is also important to realise the limitations of our rewrite preprocessing algorithm.
Our algorithm so far only works on quantum circuits. That is, each bond is of dimension 2. The next chapter discusses the possibility of extending to general tensor networks.
The generators of ZX diagrams are sparse, and often there are many different ways to exploit the sparsity to create a very efficient tensor contraction algorithm.
| decrease | |||||
| 10 | 36 | 45 | 20 | 12 | 8 |
| 9 | 29 | 36 | 17 | 10 | 7 |
| 9 | 31 | 39 | 18 | 11 | 7 |
| 9 | 33 | 41 | 20 | 13 | 7 |
| 12 | 41 | 50 | 20 | 13 | 7 |
| 10 | 33 | 42 | 17 | 10 | 7 |
| 10 | 32 | 40 | 17 | 11 | 6 |
| 10 | 32 | 39 | 17 | 11 | 6 |
| 10 | 32 | 40 | 17 | 11 | 6 |
| 10 | 27 | 34 | 13 | 7 | 6 |
Table 5.2. Treewidth before and after rewrite preprocessing for the selected graphs with the largest decrease.
I shall in particular explain the second point. Our rewrite rules only apply to the generators of ZX diagrams, which are sparse tensors (in particular the -spider). However, the same rewrite rule also applies to any other set of generators that are conjugate to the ZX generators up to a self-adjoint matrix, and conjugation may make sparse matrices no longer sparse.3
Generic Diagrammatic Calculus
This chapter discusses more generic diagrammatic calculus that can represent any tensor. Due to constraints of time, however, we are not able to deduce the analogue of local complementation rules for these generic diagrammatic calculi. This question is left for future work.
ZXW Calculus
So far, we have only discussed ZX calculus with two dimensional bonds. It is possible to extend ZX calculus to more generic tensors. ZXW calculus, pioneered by Wang et al. [60], is one approach we describe in this section.
The generators and rewrite rules of ZX calculus are a subset of those in ZXW calculus. There are many different flavours of ZXW calculus; here we will introduce the mixed dimensional qufinite ZXW calculus, where each bond can have arbitrary dimensions.
Definition 6.1 (Generators of ZXW calculus). ZXW calculus has generators Z-box, Hadamard box, W-box, X-node, and dimension splitter as shown in Figure 6.1.
Figure 6.1. Generators of ZXW calculus. For the equation in Hadamard generator, denotes the -th root of unity, where is the dimension of the bond.
We have assumed that all wires have dimension unless otherwise labelled, and wires on the left side of a box are inputs, while wires on the right side are outputs.
ZXW calculus is different from ZX calculus in two key aspects:
All bonds in ZX are two dimensional, while bonds in ZXW can have arbitrary dimensions. The dimension of the bonds is labelled when necessary as a number near the bond.
All generators in ZX calculus are symmetric tensors. The -node and -box in ZXW are not symmetric.
Because of these differences, some rules in ZX calculus do not hold in ZXW calculus, as shown in Figure 6.2.
Figure 6.2. Some rules in ZX calculus do not hold in ZXW calculus.
ZXW has a large number of rewrite rules. We only list a few of them here. For a comprehensive list of rewrite rules, please refer to the papers by Wang et al. [60, 61] [44].
Lemma 6.2 (ZXW Rewrite Rules). Five of the interesting ZXW rewrite rules are summarised in the following figure. We still have identity rules for the Z-box and X-node (although X is no longer symmetric, and other identities, like those shown in Figure 6.2, do not hold). Hadamard
gate is still unitary, but it is no longer self-adjoint.
-nodes are still similar to -nodes (they are conjugate to each other), but now .
Most importantly, we still have strong complementarity between -box and -node as well as another bialgebra rule between -box and -box.
Figure 6.3. Some rewrite rules of ZXW calculus. The empty node is defined as , and the empty node is defined as .
Because of the differences in bond-dimension and more types of generators, in general, doing rewrites in ZXW calculus is a lot more complicated than in ZX calculus.
Fortunately, the universality of ZXW calculus still holds.
Theorem 6.3 (Universality of ZXW calculus). Any tensor can be represented as a qufinite mixed-dimensional ZXW diagram. That is, using the generators of ZXW calculus and any tensor operation we have defined in chapter 2, we can represent any tensor as a ZXW diagram. In particular, they can be represented with only two generators: Z-box and X-node.
The reader is referred to the original paper by Wang et al. [60] for a proof of this theorem.
Generic Diagrams with Symmetric Generators
As ZXW calculus also has strong complementarity rules, does it have an analogue of local complementation rules? The answer is affirmative, but may not be of much use to us.
We cannot readily apply our graph theoretical operations to ZXW diagrams because the X-node and W-box are not symmetric, and therefore their diagrams cannot be regarded as graphs.
In general, a graph, as in graph theory, is a very versatile structure that allows
multiple edges between two vertices,
loops,
directed edges,
coloured vertices, therefore different types of vertices
However, in none of the graph theoretical formulations do we specify the orders of edges. The order of the edges to a non-symmetric node does matter as we have shown in chapter 2. This means none of the graph theoretical operations we have are applicable to ZXW diagrams.
The natural question is, is there another diagrammatic language with symmetric generators that has the universality property of ZXW calculus? That is, is there a set of symmetric generators that can represent any tensor?
The answer is yes.
Theorem 6.4 (Existence of Symmetric Generators with Universality Property). There exists a finite set of symmetric generators that can represent any tensor via the tensor operations defined in chapter 2.
Proof. In theorem 6.3, we have shown that any tensor can be represented as a ZXW diagram using only two generators: Z-box and X-node.
Z-box is symmetric, but X-node is not.
Applying the dualiser on each bond of the input of the X-node will make a symmetric tensor, which we denote as X-node. As the dualiser is symmetric, and two dualisers cancel, we have arrived at our finite set of generators that has the universality property: Z-box, X-node, and dualiser.
See figure 6.4 for a demonstration. Q.E.D.
We believe that this theorem opens the prospect of proposing many other diagrammatic calculi that exploit the graph theoretical operations, as we have done in chapter 5. Constrained by time, we were not able to explore this direction and leave it for future work.
Figure 6.4. Symmetric generators with the universality property.
Conclusion and Future Work
Finding the optimal contraction order of a tensor network is NP-hard. This dissertation makes the statement precise: the best possible bond-by-bond contraction complexity is , where is the line graph of the network (theorem 3.32) and is number of edges in . The proof depends on one observation: contracting a bond is exactly a simplicial elimination in the line graph, so tree decompositions of and contraction orders determine one another.
This correspondence motivates the central innovation of the thesis: rather than searching for a good contraction order on a fixed network, we may try to transform the network itself into an equivalent one whose line graph has smaller treewidth — since the cost is exponential in treewidth, even a small reduction pays off. Chapter 5 develops this into the paradigm of Tensor Contraction with Graph Operation: two ZX rewrite operations, K3 remove edge and unfuse and K3 complementation, are proved never to increase contraction complexity, and their exhaustive application as a preprocessing step (algorithm 3) carries only quadratic overhead. In 441 random graph-like diagrams benchmarked with our Rust implementation cartographer, the line-graph treewidth fell in cases, never rose, and fell by 1.62 on average out of the mean treewidth 5.56.
Future Work
While we have proved that our preprocessing steps in chapter 5 never increase treewidth, we only have empirical evidence that they do decrease the treewidth of line graphs. Investigating the theoretical conditions under which the treewidth of line graphs decreases is an interesting direction for future work.
Our graph-theoretical rewrites currently only apply to tensor networks with dimension-2 bonds. We believe it is possible to extend our rewrite rules to more general tensor networks using more generic diagrammatic languages such as ZXW calculus.
Our powerful computer program has generated many interesting data, which are shown in the appendix. These data may reveal some deep theoretical properties of treewidth and random graphs such as those shown in figure B.2 and B.3, which will also be an interesting direction for future work.
More on Graph Theory
More on Treewidth
Let us first define several more concepts and prove several useful lemmata.
Definition A.1 (Vertex Subtree). Let be a graph and its tree decomposition. For any vertex , the set of bags in that contain is the vertex subtree of in .
The reason why it is called a subtree is that the vertex subtree of must be connected by property 3 of tree decomposition.
Lemma A.2 (Clique Bag). If a graph has a clique of size , then any tree decomposition of must have a bag containing all the vertices of the clique. Therefore, the treewidth of is at least .
Proof. Let the clique consist of vertices .
Now, the vertex subtree of intersects with the vertex subtree of , because all of them are adjacent. The vertex subtree of intersects with the vertex subtree of , and so on. By simple set theory we see that the intersection of all the vertex subtrees of is non-empty. All bags in the intersection contain all the vertices of the clique, and therefore the treewidth of is at least . Q.E.D.
Miscellaneous Proofs
Proof of Lemma 3.10. We only need to prove that if a graph can be obtained from by performing one of the three graph-minor operations, then the treewidth of is less than or equal to the treewidth of . The lemma follows as any minor can be obtained by a finite sequence of these three operations. Let be a tree decomposition of . We have three cases to consider.
If is obtained from by deleting an edge, then is also a tree decomposition of .
If is obtained from by deleting a vertex , let be the tree decomposition of isomorphic to with removed from all bags. (We allow empty bags). It is clear that is a tree decomposition of and the width of is less than or equal to the width of .
If is obtained from by contracting an edge , let denote the new vertex after contraction. Let be the tree decomposition of isomorphic to with and replaced by a new vertex in all bags that contain or .
In all cases, we can construct a tree decomposition of from a tree decomposition of with width less than or equal to the width of . Therefore, the treewidth of is less than or equal to the treewidth of . Q.E.D.
Lemma A.3 (Connection between Triangulated Graph and Cut Vertices). Let be a triangulated graph. Let be a cycle in and let vertices be a pair of non-adjacent vertices in . are cut vertices of (removing makes disconnected). Let be the two components of after removing . If are not adjacent in , then must be adjacent to in .
Proof. Provided are not adjacent in , there must be a cycle of length four. If not, let be the smallest cycle of that contains . Since is triangulated, must have a chord. This chord makes the cycle smaller, until the length of the cycle is four. See figure A.1 for an example of this process.
Figure A.1. Provided and are not adjacent, any chord in the cycle of length greater than 4, such as the one in dashed blue, will produce a smaller cycle that still contains and .
Let be the length four cycle. There are two cases:
Miscellaneous Proofs
are adjacent in . Then we are done.
are not adjacent in . Then the cycle must be of the form , where and . Since cannot connect to , must be adjacent to .
Q.E.D.
Proof of Lemma 3.17. We shall prove the following stronger statement.
For any triangulated graph , given any vertex , let be the set of vertices in that are farthest away from . Then there exists a simplicial vertex in .
Recall that the distance between two vertices and in a graph is the length of the shortest path connecting them.
The proof is by induction. The base case is when has only one vertex . This means and is simplicial.
For a generic triangulated graph with a chosen vertex , let be one of the connected components of . Let be the set of vertices that are adjacent to and are not in . See figure A.2 for a demonstration of this setup.
Figure A.2. Demonstration of the proof of lemma 3.17. is a connected component of farthest vertices from . is the set of vertices that are adjacent to and are not in .
We claim that is a clique.
If contains only one vertex, there is nothing to prove. Assume contains at least two vertices. Let be any distinct vertices. Both of are connected to via some vertices not in , as they are closer to . Both of them are also connected to some vertices in the connected component . Note that no vertices in shall connect to any other vertices closer to except those in , as this would make the distance from to smaller. Therefore we are in a position to apply lemma A.3 to the cycle formed by and any two vertices in . In such a way we have proved that any and are adjacent, and therefore is a clique.
Now apply the induction hypothesis to the subgraph induced by . If is not a clique, then we can find a vertex and such that is at distance 2 from , and applying the induction hypothesis to the subgraph induced by with as the chosen vertex shows that there is a simplicial vertex in . This vertex is also simplicial in as it is not adjacent to any vertices outside of . If is a clique, then any vertex in is simplicial in . Q.E.D.
Various Graph Operations and Treewidth
Lemma A.4 (Splitting a Vertex Does not Increase the Treewidth of the Line Graph).
Proof. Let our vertex have incident edges. After splitting the vertex into two vertices and , has incident edges and has incident edges. (We may safely assume that both and are greater than 1, because otherwise the case is trivial and we have ruled out the case when the graph has treewidth 0.) Splitting a vertex creates one more edge, whose corresponding vertex in the line graph we label as . The line graph of the graph before and after splitting a vertex is shown in figure A.3.
Figure A.3. The line graph of before and after splitting a vertex.
Let us construct a tree decomposition of with treewidth no more than that of . Since has a clique of size , there must be a bag in the tree decomposition of that contains all of the vertices in this clique. Denote this bag as . We label these vertices as . The treewidth of must be greater than or equal to .
If the treewidth of is greater than , adding to the bag gives a tree decomposition of with the same treewidth as .
Let us now consider the case when the treewidth of is . Again, here we have two cases to consider.
is a leaf in the tree decomposition of . In this case there must be a vertex such that is not in any other bag. We can remove from and add to , and attach the original bag that contains to . This gives a tree decomposition of with the same treewidth as .
Removing from the tree decomposition of leaves two or more connected components. Again, in this case we claim that there must be a vertex such that there exist two components of the tree decomposition of that do not contain . If it is not the case, it means that all the vertices in are connected to some components. Reducing that component to a single vertex makes a clique of size , which is impossible as the treewidth of is .
So we have found at least one component such that it does not contain . ( can contain several connected components.) In this case we can create a new bag that contains and all the vertices in except , attach to , connect to , and remove the connections between and
Q.E.D.
Lemma A.5 (Dividing an Edge Does not Increase the Treewidth of the Line Graph).
Proof. The line graph of the graph before and after dividing an edge is shown in figure A.4.
Again, we may safely assume that both and are greater than 1, because otherwise the case is trivial and we have ruled out the case when the graph has treewidth 0
Let us first consider the tree decomposition of . By lemma A.2, there exist two bags, , such that contains all of the vertices in and , while contains all of the vertices in and .
There must be a path connecting and in the tree decomposition of , and every bag on this path must contain by the third property of tree decomposition. (This path may contain only and , in which case is a cut vertex of .)
Figure A.4. The line graph of before and after dividing an edge.
Since is not connected to any other vertices in , we can remove from all other bags that are not on the path connecting and without violating any of the properties of tree decomposition. Label this tree decomposition as .
We will construct a tree decomposition of , which we label as , and it shall have the same width as . Start with and replace in with and in with . All other shall be removed.
Now is still a tree and all properties of tree decomposition are satisfied except that there is no bag specifying the connection between the vertex and .
If the path from to does not contain any other vertices than the end point, we simply add another bag between and that contains and . If the path from to contains other vertices, what we need to do is add to the first bags, to the rest of the bags, and and shall both be added to one of the bags in the middle of the path. This is shown in figure A.5.
Changing to or in the new tree decomposition will not change the width of the tree decomposition. The only issue is that we need to add both and to one of the intermediate bags. This can also be done safely, as long as the orders of the bags on the path are not all the same. (Then there is one bag that has at least one fewer vertices than the maximum, and we can add two more vertices to it without increasing the width of the tree decomposition.)
This is, of course, possible: if two adjacent bags on the path, , contain different vertices and have the same order, we can add another bag that contains their intersection (which has fewer vertices) between them.
This completes the proof. Q.E.D.
Figure A.5. Up: the path in the tree decomposition of . Down: the path in the tree decomposition of .
Remark A.6. The insight of the previous proof is that if there is a path in the tree decomposition, then it is possible to create a bag , connected only to and , that contains the intersection of and without increasing the width of the tree decomposition. Moreover, the size of bag must be smaller than the size of and , so we can add more vertices to without increasing the width of the tree decomposition.
Definition A.7 (Graph Substitution). Let be a graph and be an induced subgraph of . is connected to the rest of via a set of edges . Regarding as a graph with loose edges, we can substitute with another graph that has the same number of loose edges as . This is exactly the operation we perform for diagrammatic rewrites in ZX calculus.
Conjecture A.8 (Graph Substitution may Reduce Treewidth). Let be a graph and be its induced subgraph. Let be another graph with the same number of loose edges as . Let be the number of loose edges in and . Let be the graph obtained by substituting with in .
Regarding each loose edge as ending with a new vertex, we have the following inequality
Several observations support this conjecture, but we were not able to prove it.
Treewidth of Common Graphs
Here we list several common graphs and their treewidths in figure A.6.
(a) The Wagner graph. 8 vertices, 12 edges, treewidth 4.
(b) The Petersen graph. 10 vertices, 15 edges, treewidth 4.
(c) The cubical graph (the graph of the cube). 8 vertices, 12 edges, treewidth 3.
(d) The gem graph. 5 vertices, 7 edges, treewidth 2.
(e) The octahedron graph. 6 vertices, 12 edges, treewidth 4.
Figure A.6. Several common graphs.
We have also listed the treewidth of some random graphs, as shown in figure A.7. All of the treewidths and random graph generations are performed using the cartographer package which I wrote in Rust for this thesis. More information about the package can be found in section B.1.
Figure A.7. Several random graphs and their treewidths.
Software Implementation
There are two major pieces of software which I have used extensively for this project. The first, cartographer, I wrote from scratch. Available at https://github.com/harryhanYuhao/cartographer, it is a graph theory package that implements all of the graph operations mentioned in this thesis. The second one, ZXW graphboard, available at https://github.com/harryhanYuhao/graphboard, is an open-source web-based graphing calculator for simple ZX diagrams. Its graph utility in general is helpful for creating tikz diagrams.
Cartographer
Cartographer is the Rust compute crate behind all of the graph computations in this dissertation. It implements the common graph algorithms used throughout the thesis.
Functionality
Coloured multigraph core. A graph is an undirected multigraph with per-vertex and per-edge colours.
Treewidth Algorithm. Tamaki’s positive-instance driven dynamic programming (PID-BT) [55] is implemented.
Graph operations. The crate also implements common graph operations such as vertex elimination, line graph construction, and random graph generations.
ZX algorithm. This crate implements all of the ZX rewrite rules used in the dissertation.
The data for Figure 5.5 are created by the example/benchmark.rs file.
ZXW Graphboard
ZXW Graphboard
Although ZXW graphboard is open-source software, it has only recently been developed and therefore deserves a detailed description as well. The ZXW graphboard is a browser-based application for drawing and reasoning about ZXW diagrams (as well as generic tikz diagrams): the user places the generators of the calculus on a canvas, connects them with wires, and evaluates the tensor the diagram represents with a Rust compute engine compiled to WebAssembly. It is deployed at https://zxwgraphboard.netlify.app/ (documentation at https://zxwgraphboard-doc.netlify.app/) and runs client-side only; most of the ZXW TikZ figures in this dissertation were exported from it.
Functionality
Editor. All the generators used in this dissertation are built in (-boxes, -nodes, Hadamard boxes, -boxes, AND gates, boundary markers and an empty node), with phases typed as LaTeX expressions such as and rendered live with KaTeX. The canvas offers grid snapping, multi-tab editing, undo/redo and keyboard shortcuts, with autosave.
Tensor calculator. A back end Rust WASM engine computes the tensor contraction of the diagram. All algorithms are implemented by hand from scratch.
TikZ and JSON export. Diagrams export as self-contained TikZ figures or JSON documents for later editing; because the editor is a general graph canvas, the same export path produces TikZ for arbitrary graph diagrams.
Graphs and Data
I have made every effort to ensure that the software behaves as intended. The figures in this section visualise the workflow carried out by the software and demonstrate its capabilities.
A Complicated Graph
In figure B.1, we show a random graph-like ZX diagram and its line graph, as well as the graph after the preprocessing algorithm (definition 5.6) and its line graph.
Some Interesting Statistics
Since the package provides powerful graph theory and treewidth algorithms, I used it to generate some statistics of interest. For example, figure B.2 shows a scatter plot of treewidth vs average degree of random graphs, based on 20244 graphs generated using the Erdős–Rényi algorithm. From observing figure B.2, I propose the following hypothesis:
Conjecture B.1. Let be a random graph generated by the Erdős–Rényi algorithm with a finite number of vertices. The probability that the treewidth of is smaller than , where is the average degree of , is zero.
Here I plotted another graph (Figure B.3), which shows a strong linear correlation between and , where is the number of vertices and is the probability of edge generation in the Erdős–Rényi algorithm (so that the expected average degree is ).
The treewidth of the Erdős–Rényi model has in fact been well studied, and both the conjecture above and this correlation connect directly to that literature. Kloks first showed that the treewidth of is linear in with high probability for [29]; Gao improved the threshold to in the uniform model (where edges are placed uniformly at random among the possible positions) and conjectured that linearity holds throughout the supercritical regime [18], which Lee, Lee, and Oum confirmed by way of rank-width [33]. In the dense regime, Perarnau and Serra proved that asymptotically almost surely (that is, with probability tending to one as ) [42], so the deficit is of order — precisely the order of the horizontal axis of figure B.3 when is fixed. Their asymptotics also indicate how the conjecture should be read, since no event in a finite random graph has probability exactly zero: the intended statement is that holds with high probability. This is immediate in the sparse regimes, where the treewidth is linear in while stays constant, and for fixed it follows from the dense asymptotics, since and the deficit is negligible compared with ; the two sides are closest in the near-complete regime .
Figure B.1. (a) A random graph-like ZX diagram . (b) Graph , which is after the preprocessing algorithm (definition 5.6). (c) Line graph of , treewidth 11. (d) Line graph of , treewidth 7. A random graph-like ZX diagram before and after preprocessing and their line graphs.
Figure B.2. A scatter plot of treewidth vs average degree of random graphs. 20244 graphs are randomly generated using the Erdős–Rényi algorithm and their treewidth and average degree are computed. The colour of the points indicates the number of vertices in the graph. The data is generated by the example/treewidth_hypo.rs file in the cartographer crate.
Figure B.3. Using the same data as figure B.2, we plotted versus , where is the number of vertices and is the probability of edge generation in the Erdős–Rényi algorithm (so that the expected average degree is ). The colour of each point denotes the number of vertices in the graph of that particular data point. Note that there is a strong linear correlation (especially when is low) between the two quantities.
References
- [48]Rose, D. J., Tarjan, R. E., and Lueker, G. S. (1976). Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing, 5(2):266–283.DOI
- [49]Schollwöck, U. (2011). The density-matrix renormalization group in the age of matrix product states. Annals of Physics, 326(1):96–192.DOI
- [50]Selinger, P. (2007). Dagger compact closed categories and completely positive maps. Electronic Notes in Theoretical Computer Science, 170:139–163.DOI
- [51]Selinger, P. (2011). A survey of graphical languages for monoidal categories. In New Structures for Physics, volume 813 of Lecture Notes in Physics, pages 289–355. Springer, Berlin.
- [52]Smith, D. G. A. and Gray, J. (2018). opt_einsum — a python package for optimizing contraction order for einsum-like expressions. Journal of Open Source Software, 3(26):753.DOI
- [53]Stoudenmire, E. M. and Schwab, D. J. (2016). Supervised learning with tensor networks. In Advances in Neural Information Processing Systems 29, pages 4799–4807.
- [54]Strassen, V. (1969). Gaussian elimination is not optimal.DOI
- [55]Tamaki, H. (2017). Positive-instance driven dynamic programming for treewidth. In 25th Annual European Symposium on Algorithms (ESA 2017), volume 87 of Leibniz International Proceedings in Informatics (LIPIcs), pages 68:1–68:13. Schloss Dagstuhl — Leibniz-Zentrum für Informatik.
- [56]van de Wetering, J. (2020). Zx-calculus for the working quantum computer scientist.arxiv.org/abs/2012.13966
- [57]Verstraete, F. and Cirac, J. I. (2004). Renormalization algorithms for quantum-many body systems in two and higher dimensions.DOI
- [58]Voigt, W. (1898). Die fundamentalen physikalischen Eigenschaften der Krystalle in elementarer Darstellung. Verlag von Veit & Comp., Leipzig.DOI
- [59]Waintal, X., Huang, C.-H., and Groth, C. W. (2026). Who can compete with quantum computers? lecture notes on quantum inspired tensor networks computational techniques.DOI
- [60]Wang, Q., East, R. D. P., Shaikh, R. A., Yeh, L., Poór, B., and Coecke, B. (2025). Beyond penrose tensor diagrams with the zx calculus: Applications to quantum computing, quantum machine learning, condensed matter physics, and quantum gravity.arxiv.org/abs/2511.06012
- [61]Wang, Q., Poór, B., and Shaikh, R. A. (2026). Completeness of qufinite zxw calculus, a graphical language for finite-dimensional quantum theory.
- [62]West, D. B. et al. (2001). Introduction to graph theory, volume 2. Prentice hall Upper Saddle River.
- [63]White, S. R. (1992). Density matrix formulation for quantum renormalization groups. Physical Review Letters, 69(19):2863–2866.pubmed.ncbi.nlm.nih.gov/10046608
- [64]Xu, J., Liang, L., Deng, L., Wen, C., Xie, Y., and Li, G. (2019). Towards a polynomial algorithm for optimal contraction sequence of tensor networks from trees. Phys. Rev. E, 100:043309.DOI
- [65]Zhou, Y., Stoudenmire, E. M., and Waintal, X. (2020). What limits the simulation of quantum computers? Physical Review X, 10(4):041038.DOI



































