betaFeedback

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 C\mathbb{C}. 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 nn spin-half particles inhabits a Hilbert space of dimension 2n2^n, 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 G∗G^{*} and a contraction order of GG 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 — K3K_3 remove edge and unfuse and K3K_3 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 n∈Nn \in\mathbb{N}, let [n][n] denote the set {0,1,⋯ ,n−1}\{0,1,\cdots,n-1\}. A tensor of rank k∈Nk \in\mathbb{N} is a function T:[n0]×[n1]×⋯×[nk−1]→CT : [n_0] \times[n_1] \times\cdots\times[n_{k-1}] \to\mathbb{C}.

By convention, we shall write the value T(i0,i1,⋯ ,ik−1)T(i_0,i_1,\cdots,i_{k-1}) as Ti0i1⋯ik−1T_{i_0i_1\cdots i_{k-1}}, where each ii is called an index. Of course, the output of TT can be R\mathbb{R} or any other ring. We take it to be C\mathbb{C} in this dissertation for convenience. The value njn_j is called the dimension of the jj-th index, which will always be clear from the context.

Following the convention of Einstein summation, a tensor TT 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 Tijk⋯\mathcal{T}_{ijk\cdots}.

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 nn such matrix slices.

A rank-three tensor regarded as a stack of matrices

Figure 2.1. A rank-three tensor TijkT_{ijk} regarded as a stack of nn matrices.

Ti=(T0T1⋮Tn−1),Tij=(T00T01⋯T0,n−1T10T11⋯T1,n−1⋮⋮⋱⋮Tn−1,0Tn−1,1⋯Tn−1,n−1).T_i = \begin{pmatrix} T_0\\ T_1\\ \vdots\\ T_{n-1} \end{pmatrix}, \qquad T_{ij} = \begin{pmatrix} T_{00} & T_{01} & \cdots& T_{0,n-1}\\ T_{10} & T_{11} & \cdots& T_{1,n-1}\\ \vdots& \vdots& \ddots& \vdots\\ T_{n-1,0} & T_{n-1,1} & \cdots& T_{n-1,n-1} \end{pmatrix}.

There are at least seven natural operations for tensors.

Observation 2.2.

  • Addition Tijk⋯+Tijk⋯→T\mathcal{T}_{ijk\cdots}+\mathcal{T}_{ijk\cdots}\to\mathcal{T}. Let Tijk⋯T_{ijk\cdots} and Sijk⋯S_{ijk\cdots} be two tensors of the same rank. Then their sum is defined by (T+S)ijk⋯=Tijk⋯+Sijk⋯(T+S)_{ijk\cdots}=T_{ijk\cdots}+S_{ijk\cdots}.

  • Scalar multiplication C×Tijk⋯→Tijk⋯\mathbb{C}\times\mathcal{T}_{ijk\cdots}\to\mathcal{T}_{ijk\cdots}. Let Tijk⋯T_{ijk\cdots} be a tensor and c∈Cc\in\mathbb{C}. Define (cT)ijk⋯=c(Tijk⋯)(cT)_{ijk\cdots}=c(T_{ijk\cdots}).

  • Permutation. Tijk⋯→Tijk⋯\mathcal{T}_{ijk\cdots}\to\mathcal{T}_{ijk\cdots}. Let Tijk⋯T_{ijk\cdots} be a tensor of rank mm. For any permutation σ∈Sm\sigma\in S_m, the permuted tensor is defined by (σ⋅T)iσ(1)iσ(2)⋯iσ(m)=Ti1i2⋯im(\sigma\cdot T)_{i_{\sigma(1)}i_{\sigma(2)}\cdots i_{\sigma(m)}}=T_{i_1i_2\cdots i_m}.

  • Flatten Tijk⋯→Tjk⋯\mathcal{T}_{ijk\cdots}\to\mathcal{T}_{jk\cdots}. Let Tijk⋯T_{ijk\cdots} be a tensor. Any two of the indices of TT can be flattened into one to create a new tensor. Say we would like to flatten the indices ii and jj, of dimensions n1n_1 and n2n_2. Let α\alpha be an index of dimension n1n2n_1n_2, and we define the new tensor Sαk⋯S_{\alpha k\cdots} as S(n2i+j)k⋯=Tijk⋯S_{(n_2i+j)k\cdots}=T_{ijk\cdots}.

  • Unflatten, which is exactly the opposite operation of flatten.

  • Outer product Tijk⋯×Tαβγ⋯→Tijk⋯αβγ⋯\mathcal{T}_{ijk\cdots}\times\mathcal{T}_{\alpha\beta\gamma\cdots}\to\mathcal{T}_{ijk\cdots\alpha\beta\gamma\cdots}. Let Tijk⋯T_{ijk\cdots} and Slmn⋯S_{lmn\cdots} be any two tensors. Their tensor product is defined by (T⊗S)ijklmn⋯=Tijk⋯Slmn⋯(T\otimes S)_{ijklmn\cdots}=T_{ijk\cdots}S_{lmn\cdots}. Outer product is sometimes called tensor product or Kronecker product.

  • Contraction. Tijk⋯×Tilm⋯→Tjk⋯lm⋯\mathcal{T}_{ijk\cdots}\times\mathcal{T}_{ilm\cdots}\to\mathcal{T}_{jk\cdots lm\cdots}. Let Tijk⋯T_{ijk\cdots} and Silm⋯S_{ilm\cdots} be tensors of rank mm and nn. Their contraction over the index ii is a tensor of rank m+n−2m+n-2 defined by (T⋅S)jk⋯lm⋯=∑i=0di−1Tijk⋯Silm⋯(T\cdot S)_{jk\cdots lm\cdots}=\sum_{i=0}^{d_i-1}T_{ijk\cdots}S_{ilm\cdots}, where did_i is the dimension of the index ii. If there are many different tensors with the corresponding contraction indices specified, their full contraction gives a new tensor defined as

∑i1=0n1−1∑i2=0n2−1⋯∑ik−1=0nk−1−1Ti1j1⋯(1)Ti1i2j2⋯(2)⋯Tik−1jk⋯(k)(1)\sum_{i_1=0}^{n_1-1}\sum_{i_2=0}^{n_2-1}\cdots\sum_{i_{k-1}=0}^{n_{k-1}-1}T^{(1)}_{i_1j_1\cdots}T^{(2)}_{i_1i_2j_2\cdots}\cdots T^{(k)}_{i_{k-1}j_k\cdots} \tag*{(1)}

where i1i_1 to ik−1i_{k-1} 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 TT, and define Sij=TjiS_{ij}=T_{ji}.

Tij=(T00T01⋯T10T11⋯⋮⋮⋱),Sij=(T00T10⋯T01T11⋯⋮⋮⋱)T_{ij}=\begin{pmatrix} T_{00} & T_{01} & \cdots\\ T_{10} & T_{11} & \cdots\\ \vdots& \vdots& \ddots\end{pmatrix}, \qquad S_{ij}=\begin{pmatrix} T_{00} & T_{10} & \cdots\\ T_{01} & T_{11} & \cdots\\ \vdots& \vdots& \ddots\end{pmatrix}

Outer product and flattening are demonstrated in Figure 2.2.

Outer product and flattening of tensors

Figure 2.2. (a) The outer product of a vector viv_i and a matrix MjkM_{jk} yields the rank-three tensor TijkT_{ijk}. (b) Flattening the indices ii and jj of TijkT_{ijk} into a single index α=n2i+j\alpha=n_2i+j yields the matrix SαkS_{\alpha k}.

Usually, outer product and flattening are used together to convert tensor products of two arbitrary tensors into a single matrix, for example

A⊗v⃗=(a00a01a10a11)(v0v1)=(a00v0a01v0a10v0a11v0a00v1a01v1a10v1a11v1)(2)A\otimes\vec{v}=\begin{pmatrix} a_{00} & a_{01} \\ a_{10} & a_{11} \end{pmatrix}\begin{pmatrix} v_0 \\ v_1 \end{pmatrix}=\begin{pmatrix} a_{00}v_0 & a_{01}v_0 \\ a_{10}v_0 & a_{11}v_0 \\ a_{00}v_1 & a_{01}v_1 \\ a_{10}v_1 & a_{11}v_1 \end{pmatrix} \tag*{(2)}

In general, if we have two matrices MM and NN, their outer product will be

M⊗N=(M00NM01N⋯M10NM11N⋯⋮⋮⋱)(3)M \otimes N = \begin{pmatrix} M_{00}N & M_{01}N & \cdots\\ M_{10}N & M_{11}N & \cdots\\ \vdots& \vdots& \ddots \end{pmatrix} \tag*{(3)}

Contraction is the most complicated operation. For the matrices, MijM_{ij} and NjkN_{jk}, their contraction over the index jj is a matrix PikP_{ik} defined by Pik=∑j=0n−1MijNjkP_{ik} = \sum_{j=0}^{n-1} M_{ij}N_{jk}, 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.

∑i1=0n1−1∑i2=0n2−1⋯∑ik−1=0nk−1−1Ti1j1⋯(1)Ti2j2⋯(2)⋯Tik−1jk⋯(k)=∑i2=0n2−1∑i1=0n1−1⋯∑ik−1=0nk−1−1Ti1j1⋯(1)Ti2j2⋯(2)⋯Tik−1jk⋯(k)=∑i1=0n1−1∑i2=0n2−1⋯∑ik−1=0nk−1−1Ti1j1⋯(1)(Ti2j2⋯(2)⋯Tik−1jk⋯(k))=∑i1=0n1−1∑i2=0n2−1⋯∑ik−1=0nk−1−1(Ti1j1⋯(1)Ti2j2⋯(2))⋯Tik−1jk⋯(k)=⋯(4)\begin{aligned} &\sum_{i_1=0}^{n_1-1}\sum_{i_2=0}^{n_2-1}\cdots\sum_{i_{k-1}=0}^{n_{k-1}-1} T^{(1)}_{i_1j_1\cdots}T^{(2)}_{i_2j_2\cdots}\cdots T^{(k)}_{i_{k-1}j_k\cdots} \\ &= \sum_{i_2=0}^{n_2-1}\sum_{i_1=0}^{n_1-1}\cdots\sum_{i_{k-1}=0}^{n_{k-1}-1} T^{(1)}_{i_1j_1\cdots}T^{(2)}_{i_2j_2\cdots}\cdots T^{(k)}_{i_{k-1}j_k\cdots} \\ &= \sum_{i_1=0}^{n_1-1}\sum_{i_2=0}^{n_2-1}\cdots\sum_{i_{k-1}=0}^{n_{k-1}-1} T^{(1)}_{i_1j_1\cdots}\left(T^{(2)}_{i_2j_2\cdots}\cdots T^{(k)}_{i_{k-1}j_k\cdots}\right) \\ &= \sum_{i_1=0}^{n_1-1}\sum_{i_2=0}^{n_2-1}\cdots\sum_{i_{k-1}=0}^{n_{k-1}-1}\left(T^{(1)}_{i_1j_1\cdots}T^{(2)}_{i_2j_2\cdots}\right)\cdots T^{(k)}_{i_{k-1}j_k\cdots} \\ &= \cdots \tag*{(4)} \end{aligned}

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 V,WV,W be vector spaces over a field F\mathbb{F}. Their tensor product, denoted as V⊗WV \otimes W, is the unique vector space over F\mathbb{F} that satisfies the following universal property as demonstrated in Figure 2.3: there exists a bilinear map η:V×W→V⊗W\eta: V \times W \to V \otimes W, and for every bilinear map f:V×W→Uf : V \times W \to U to any vector space UU, there exists a unique linear map f^:V⊗W→U\hat{f} : V \otimes W \to U such that f=f^∘ηf = \hat{f} \circ\eta.

Figure 2.3. Commutative triangle for tensor product.

Equivalently, the tensor product of two finite-dimensional vector spaces VV and WW, with basis v1,…,vnv_1,\ldots,v_n and w1,…,wmw_1,\ldots,w_m is the n⋅mn \cdot m dimensional vector space V⊗WV \otimes W with basis vi⊗wj,1≤i≤n,1≤j≤mv_i \otimes w_j, 1 \leq i \leq n, 1 \leq j \leq m, that satisfies the following bilinearity conditions:

(vi+vj)⊗wk=vi⊗wk+vj⊗wk,vi⊗(wj+wk)=vi⊗wj+vi⊗wk,c(vi⊗wj)=(cvi)⊗wj=vi⊗(cwj),c∈F.\begin{aligned} (v_i+v_j)\otimes w_k &= v_i\otimes w_k+v_j\otimes w_k,\\ v_i\otimes(w_j+w_k) &= v_i\otimes w_j+v_i\otimes w_k,\\ c(v_i\otimes w_j) &= (cv_i)\otimes w_j=v_i\otimes(cw_j),\quad c\in\mathbb{F}. \end{aligned}

where i,j,ki,j,k 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

  1. A rank-one tensor, TiT_i, is a vector in some vector space VV, where the dimension of the index ii is the dimension of VV.

  1. In general, a rank-kk tensor Ti1i2⋯T_{i_1i_2\cdots} has additions and scalar multiplications, so the set of rank-kk tensors with fixed dimension for each of their indices, denoted by Ti1,i2…\mathcal{T}_{i_1,i_2\ldots}, is a vector space. This vector space has a basis {ej1,j2,…,jk,…}\{e_{j_1,j_2,\ldots,j_k,\ldots}\}, where ej1,j2,…(i1,i2,…)=1e_{j_1,j_2,\ldots}(i_1,i_2,\ldots)=1 if and only if i1=j1,i2=j2,…i_1=j_1,i_2=j_2,\ldots, and 0 otherwise. This set of bases is precisely the basis of the tensor product of vector spaces V0,V1,…,VkV_0,V_1,\ldots,V_k.

  1. Flatten is the canonical isomorphism between the vector space V1⊗V2⊗⋯⊗Vk→(V1⊗V2)⊗⋯⊗VkV_1\otimes V_2\otimes\cdots\otimes V_k\to(V_1\otimes V_2)\otimes\cdots\otimes V_k. (And unflatten is its inverse.)

  1. Outer product (T1,T2)→T1⊗T2(\mathcal{T}_1,\mathcal{T}_2)\to\mathcal{T}_1\otimes\mathcal{T}_2 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 VV a vector is an element of VV. Its dual is a function V→CV\to\mathbb{C}, and a matrix is a function V→VV\to V. In physics, the inputs and outputs of a tensor are differentiated by the upper and lower indices. For example, Tlk\mathcal{T}^{k}_{l} denotes the class of tensors V⊗V⊗⋯⊗V⏟k⊗V∗⊗V∗⊗⋯⊗V∗⏟l≅V⊗⋯⊗V⏟l→V⊗⋯⊗V⏟k\underbrace{V\otimes V\otimes\cdots\otimes V}_{k}\otimes\underbrace{V^*\otimes V^*\otimes\cdots\otimes V^*}_{l}\cong\underbrace{V\otimes\cdots\otimes V}_{l}\to\underbrace{V\otimes\cdots\otimes V}_{k}, where VV is a vector space and V∗V^* 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 TijkT_{ijk} and SklS_{kl}, where indices ii and jj have dimensions n1n_1 and n2n_2 while both of the indices kk and ll have dimension n1n_1. Suppose that we would like to perform the following operation: ‘contracting the first index of TT with the second index of SS, and contracting the last index of the resulting tensor with the first index of another copy of TT. 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-kk tensor is represented as a node with kk edges. Usually, the shape, color, and labels of the nodes are used to differentiate different tensors. For example, a vector vv, a matrix MM, and a rank-three tensor TT are represented as in Figure 2.4.

Rank 1, 2, and 3 tensors

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.

Outer product in tensor network: $v_i \otimes w_j = v_i w_j$

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

  1. it allows loops and multiple edges,

  1. its vertices are of different types,

  1. 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 H=(1234)H = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}. In explicit tensor notation, H00=1,H01=2,H10=3H_{00} = 1, H_{01} = 2, H_{10} = 3 and H11=4H_{11} = 4. In tensor network notation, HH 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 HH.

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.

Contracting two rank-two tensors over their shared index

Figure 2.8. Contracting the two rank-two tensors MijM_{ij} and NjkN_{jk} over their shared index jj gives the rank-two tensor (MN)ik=∑jMijNjk(MN)_{ik} = \sum_j M_{ij}N_{jk}.

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 MM and NN can be regarded as a new node MNMN with two edges, and in Figure 2.5, the two nodes vv and ww can be regarded as a new node v⊗wv \otimes w 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 Tijk…T_{ijk\ldots} is called symmetric if it is invariant under any permutation of its indices, i.e. for any permutation σ∈Sk\sigma\in S_k, we have

Ti1i2⋯ik=Tiσ(1)iσ(2)⋯iσ(k).T_{i_1i_2\cdots i_k} = T_{i_{\sigma(1)}i_{\sigma(2)}\cdots i_{\sigma(k)}}.

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

Permuting the edges of a symmetric tensorVector (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 dd.

Contraction of two rank-2 tensors, MijM_{ij} and NjkN_{jk}, gives another rank-2 tensor PikP_{ik}. Each entry of PP is computed using the formula

Pik=∑j=0d−1MijNjkP_{ik} = \sum_{j=0}^{d-1} M_{ij}N_{jk}

Computing a single entry thus takes dd multiplications and d−1d-1 additions. There are a total of d2d^2 entries to compute, so the total number of operations is d2(d+d−1)=O(d3)d^2(d+d-1)=O(d^3).

Similarly, contraction of one bond between a rank mm and a rank nn tensor will result in a rank m+n−2m+n-2 tensor. Each entry of the resulting tensor is computed by summing over dd products of entries from the two tensors, so the total number of operations is O(dm+n−1)O(d^{m+n-1}).

We may also choose to contract multiple bonds simultaneously. In general, contracting kk bonds between a rank mm and a rank nn tensor will result in a rank m+n−2km+n-2k tensor. Each entry of the resulting tensor is computed by summing over dkd^k products of entries from the two tensors, so the total number of operations is O(dm+n−k)O(d^{m+n-k}).

It is thus clear that contracting kk bonds simultaneously over a tensor network with nn external bonds will take O(dn+k)O(d^{n+k}) operations. This is an important observation that is worth writing down.

Lemma 2.8 (Complexities of Tensor Contraction by Counting Edges). Let TT be a tensor network with nn external bonds and kk internal bonds. Contracting all the internal bonds of TT will take O(dn+k)O(d^{n+k}) 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 O(d5)O(d^5), while the second contraction order takes O(d4)O(d^4).

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

(a1+a2+⋯+an)(b1+b2+⋯+bm)=a1b1+a1b2+⋯+anbm(a_1+a_2+\cdots+a_n)(b_1+b_2+\cdots+b_m)=a_1b_1+a_1b_2+\cdots+a_nb_m

The left-hand side of the equation takes n−1n-1 additions for aia_i, m−1m-1 additions for bib_i, and one multiplication between the sums, which is a total of m+n−1m+n-1 operations. The right-hand side, however, takes nmnm multiplications between aia_i and bib_i and nm−1nm-1 additions, amounting to a total of 2nm−12nm-1 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 v⃗1,v⃗2∈Cn\vec{v}_1,\vec{v}_2 \in\mathbb{C}^{n} and M∈Cn×nM \in\mathbb{C}^{n\times n}. Consider the following operations calculated in two different orders:

(Mv⃗1)v⃗2T=M(v⃗1v⃗2T)(M\vec{v}_1)\vec{v}_2^{T}=M(\vec{v}_1\vec{v}_2^{T})

The left-hand side takes two matrix-vector multiplications, which is O(n2)O(n^2) operations, while the right-hand side takes one outer product, costing O(n2)O(n^2), and one matrix-matrix multiplication, costing O(n3)O(n^3) 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

∑k=0n−1AikBkj\sum_{k=0}^{n-1} A_{ik}B_{kj}

may have a more efficient algorithm than the naive O(n3)O(n^{3}) complexity [12]. The first matrix algorithm that beats the naive algorithm was Strassen’s algorithm with complexity O(n2.81)O(n^{2.81}) [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 G1,G2,…G_1,G_2,\ldots, there exist indices i<ji<j such that GiG_i is a minor of GjG_j.

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 GG be a finite graph and VV its vertex set. A tree decomposition of GG is a pair (T,{Xt}t∈V(T))(T,\{X_t\}_{t\in V(T)}) where TT is a tree and {Xt}t∈V(T)\{X_t\}_{t\in V(T)} is a family of subsets of VV (called bags) such that

  1. ⋃t∈V(T)Xt=V\bigcup_{t\in V(T)} X_t=V,

  1. If vertices u,v∈Gu,v\in G are adjacent, there exists a t∈Tt\in T such that u,v∈Xtu,v\in X_t.

  1. Let a,ba,b be vertices of TT. Since TT is a tree, there is a unique path connecting aa and bb, which is denoted as PP. If v∈Gv\in G and v∈Xa,v∈Xbv\in X_a,v\in X_b, then for all c∈Pc\in P, we have v∈Xcv\in X_c.

Let XtX_t be the bag such that ∀i∈V(T),∣Xt∣≥∣Xi∣\forall i\in V(T), |X_t|\geq|X_i| (That is, XtX_t is the bag of the largest order). The width of the tree decomposition (T,{Xt})(T,\{X_t\}) is ∣Xt∣−1|X_t|-1.

Definition 3.3 (Treewidth). The treewidth of a graph GG 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 u,v∈Gu,v \in G and ∃t\exists t such that u,v∈Xtu,v \in X_t, however, this does not guarantee that uu and vv are adjacent in GG.

Exempli Gratia 3.4. (All graphs have a trivial tree decomposition.) Let GG be a graph with vertex set VV. Then (T,{Xt})(T,\{X_t\}) is a tree decomposition of GG where TT is a single node and Xt=VX_t = V. The width of this tree decomposition is ∣V∣−1|V|-1.

Therefore, the treewidth of any graph GG is bounded above by ∣V∣−1|V|-1. By Zorn’s lemma, there must exist a tree decomposition of GG with minimum width.

Let us look at some examples of tree decompositions.

Exempli Gratia 3.5. (Tree decomposition of a Tree). Let GG be a tree. We can construct a tree decomposition of GG in the following way.

  1. Let each vertex of GG be a bag that contains only itself.

  1. On each edge of GG, 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 GG be a graph and TT its tree decomposition with at least three vertices. Let a∈V(T)a \in V(T). If deleting aa from TT produces at least two disconnected subgraphs of TT, which we label as T1,T2T_1,T_2, then the subgraphs of GG induced by the vertex sets ⋃t∈V(T1)Xt∖Xa\bigcup_{t\in V(T_1)} X_t \setminus X_a and ⋃t∈V(T2)Xt∖Xa\bigcup_{t\in V(T_2)} X_t \setminus X_a are disconnected.

Proof. It is sufficient to show that no vertex v∈⋃t∈V(T1)Xt∖Xav \in\bigcup_{t\in V(T_1)} X_t \setminus X_a is adjacent to any vertex u∈⋃t∈V(T2)Xt∖Xau \in\bigcup_{t\in V(T_2)} X_t \setminus X_a.

Assume that v∈⋃t∈V(T1)Xt∖Xav \in\bigcup_{t\in V(T_1)} X_t \setminus X_a and u∈⋃t∈V(T2)Xt∖Xau \in\bigcup_{t\in V(T_2)} X_t \setminus X_a and they are adjacent. Let v∈Xsv \in X_s, u∈Xru \in X_r, and let P0P_0 be the unique path from ss to rr in TT. Since ss and rr lie in different components of TT after deleting aa, the path P0P_0 contains the vertex aa.

By property 2 of tree decomposition, there exists t∈Tt \in T such that v,u∈Xtv,u \in X_t. Since TT is connected, there exists a path P1P_1 from ss to tt and path P2P_2 from rr to tt. If none of them pass through aa, then there is a cycle in TT consisting of P0P_0, P1P_1, and P2P_2. This contradicts the fact that TT is a tree. Therefore, at least one of them must pass through aa.

Without loss of generality, let P1P_1 pass through aa. P1P_1 is a path whose endpoints are bags that contain vv, so by property 3 of tree decomposition the bag XaX_a contains vv as well. This is a contradiction to the assumption that v∉Xav \notin X_a. Q.E.D.

Exempli Gratia 3.8 (Treewidth of a Complete Graph). The treewidth of a complete graph KnK_n is n−1n-1, as all tree decompositions of KnK_n must contain a bag that contains all vertices of KnK_n.

To prove this claim, assume TT is a tree decomposition of KnK_n and let XiX_i be the largest bag of TT that does not contain all vertices of KnK_n. Since XiX_i does not contain all vertices of KnK_n, there exists a vertex v∈Knv \in K_n such that v∉Xiv \notin X_i, which lies in some other bag XjX_j. Again, as vv is connected to all other vertices and XjX_j does not contain all vertices, there must be a third bag in TT.

In a tree with at least three vertices, there must exist a vertex aa such that deleting aa from TT produces at least two disconnected subgraphs of TT. Now we can invoke lemma 3.1, which states that the corresponding subgraphs of KnK_n are disconnected. This is not possible, as KnK_n is a complete graph, so all vertices are connected.

Therefore, all tree decompositions of KnK_n must contain a bag that contains all vertices of KnK_n, which proves the claim.

If a graph GG is a minor of HH, then the treewidth of GG is less than or equal to the treewidth of HH. The definition of graph minor is presented here for reference.

Definition 3.9 (Graph Minor). Let GG and HH be two graphs. We say that GG is a minor of HH if GG can be obtained from HH by a sequence of the following operations:

  1. Deleting an edge,

  2. Deleting a vertex,

  3. Contracting an edge.

The process of contracting an edge e=(u,v)e=(u,v) is to delete the edge ee and merge the two vertices uu and vv into a single vertex ww. The new vertex ww is adjacent to all the neighbours of uu and vv.

Lemma 3.10 (Graph Minor and Treewidth). Let GG and HH be two graphs. If GG is a minor of HH, then the treewidth of GG is less than or equal to the treewidth of HH.

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 δ\delta be the minimum vertex degree of a simple graph GG. The treewidth of GG is at least δ\delta.

Proof. The cases δ=0\delta=0 or δ=1\delta=1 are trivial, because only one-vertex trivial graph has tree width 0 and everything else has treewidth at least 1.

For graph with δ≥2\delta\ge2, we only need to realise that

  1. There are at least δ+1\delta+1 vertices in GG

  2. Contracting an edge connected two vertices a,ba,b each with degree equal or more than 2 will create a new vertex with degree greater than or equal to max⁡(a,b)\max(a,b).

Therefore, we can continuously contract edges in GG until we obtain a complete graph KσK_\sigma, where σ≥δ+1\sigma\ge\delta+1. By lemma 3.10, the treewidth of GG is at least the treewidth of Kσ+1K_{\sigma+1}, which is greater than δ\delta.

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 aa be the start of the cycle. Delete one edge next to aa and treat the rest of the graph as a tree, with the maximum bag of size 2. Adding aa 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.

A cycle graph and its tree decomposition

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 GG 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.

Examples of two triangulated graphs and two 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 GG be a triangulated graph and vv any vertex in GG. Then the graph G∖{v}G \setminus\{v\} is triangulated. Note that G∖{v}G \setminus\{v\} is the graph induced by the vertex set V(G)∖{v}V(G) \setminus\{v\}.

Proof. If G∖{v}G \setminus\{v\} is not triangulated, then there exists a cycle of length greater than or equal to 44 in G∖{v}G \setminus\{v\} that does not have a chord. The same cycle exists in GG and does not have a chord, meaning GG 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 GG be a triangulated graph and HH an induced subgraph of GG. Then HH is triangulated.

Definition 3.16 (Simplicial Vertex). A vertex vv in a graph GG is simplicial if the subgraph induced by the neighbours of vv 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 GG is an ordering of the vertices [v1,v2,…,vn][v_1,v_2,\ldots,v_n] such that each vertex viv_i is simplicial in the subgraph induced by [vi,vi+1,…,vn][v_i,v_{i+1},\ldots,v_n].

The reason it is called a perfect elimination is that v1v_1 is a simplicial vertex in GG, v2v_2 is a simplicial vertex in G∖{v1}G \setminus\{v_1\} (that is, the graph GG with vertex v1v_1 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 GG is triangulated if and only if it has a perfect elimination ordering.

Proof. Proof of the sufficient condition. Assume GG has a perfect elimination ordering [v1,v2,…,vn][v_1,v_2,\ldots,v_n]. Let PP be a cycle of length greater than 3. Among the vertices in PP, one of them is ordered first in the perfect elimination ordering, say viv_i. viv_i connects to at least two other vertices in PP, which we label as a,ba,b. Since viv_i is simplicial in the subgraph induced by [vi,a,b][v_i,a,b], there is an edge connecting a,ba,b, which is our desired chord.

The necessary condition can be proved by induction on the number of vertices in GG using lemma 3.17.

The base case is when GG has only one vertex, which is trivially simplicial.

Let GG be a triangulated graph with nn vertices. By lemma 3.17, there exists a simplicial vertex vv in GG. Elimination of vv gives G∖{v}G \setminus\{v\} with n−1n-1 vertices. G∖{v}G \setminus\{v\} 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 GG is a graph formed from a subset of the vertices of GG 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 GG, there exists a triangulated graph TT such that GG is the induced subgraph of TT and tw⁡(G)=tw⁡(T)\operatorname{tw}(G) = \operatorname{tw}(T).

Proof. Let GG be a graph. It is sufficient to show that for every tree decomposition of GG, which we label as TT, there exists a triangulated graph FF with the same tree decomposition and such that GG is the induced subgraph of FF. We shall give a constructive proof.

We can construct the triangulated graph FF from GG in the following way. Start by initialising FF with only the vertices of GG and no connections between them. Perform the following steps, where in each step we add more edges to FF and remove bags in TT. The algorithm terminates when TT becomes an empty graph.

  1. Let XlX_l be a leaf in TT.1 Let XpX_p be the parent of XlX_l in TT. We assume that Xl∖XpX_l \setminus X_p is a set of one element. If it is not, modify the tree decomposition TT in the process described below to make it so.

  1. Let vv be the unique vertex in Xl∖XpX_l \setminus X_p. We claim that no other bag in TT contains vv. If there is another bag that contains vv, the path from XlX_l to that bag must pass through XpX_p, and XpX_p must contain vv by property 3 of tree decomposition. This is a contradiction to the assumption that v∉Xpv \notin X_p.

  1. Add enough edges to the graph FF such that the subgraph induced by XlX_l becomes a complete graph.

  1. Remove XlX_l from TT and repeat the process until TT is empty.

This process must terminate because in each iteration one bag is eliminated from TT and TT is finite. In the ii-th iteration, we work on the special vertex viv_i that is the only vertex contained in Xl∖XpX_l \setminus X_p. It is clear that [v1,v2,⋯ ][v_1,v_2,\cdots] is a perfect elimination ordering of FF; therefore FF is triangulated. The original tree decomposition TT is still a valid tree decomposition of FF, because the structure and the bags of TT are not changed, and each edge added to FF is contained in some bag of TT.

If Xl∖XpX_l \setminus X_p is a set of more than one element, we perform the following modification to the tree decomposition TT to make it have one leaf bag that contains exactly one more vertex than its parent.

  1. If Xl∖XpX_l \setminus X_p is empty (that is, XlX_l does not contain any vertices beyond those in XpX_p), then we can remove XlX_l from TT and the tree decomposition is still valid.

  1. If Xl∖XpX_l \setminus X_p has more than one element, we can split XlX_l into multiple bags, each containing one more element of Xl∖XpX_l \setminus X_p. 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 FF constructed from GG in theorem 3.20 is also called an optimal triangulation or an optimal chordal completion of GG in the literature [47].

This constructive procedure is summarised in Algorithm 1.

Algorithm 1 Triangulation from a tree decomposition

Require: A graph G=(V,E)G=(V,E) and a tree decomposition (T,{Xt})(T,\{X_t\}) of GG.

Ensure: Return a triangulated graph FF with V(F)=VV(F)=V and G⊆FG\subseteq F, and a perfect elimination ordering σ\sigma of FF, such that (T,{Xt})(T,\{X_t\}) is a tree decomposition of FF.

  1. F←(V,∅)F\gets(V,\varnothing); initialise σ\sigma as the empty list.

  2. while TT has at least two bags do

  3. Let XlX_l be a leaf bag of TT and XpX_p its parent.

  4. if Xl⊆XpX_l\subseteq X_p then

  5. Delete XlX_l from TT. ▷ redundant leaf

  6. else

  7. Write Xl∖Xp={w1,…,wk}X_l\setminus X_p=\{w_1,\ldots,w_k\}.

  8. Replace XlX_l by the path Xp−(Xp∪{w1})−⋯−(Xp∪{w1,…,wk})X_p-(X_p\cup\{w_1\})-\cdots-(X_p\cup\{w_1,\ldots,w_k\}). ▷ leaf now has one extra vertex

  9. for i←k,k−1,…,1i\gets k,k-1,\ldots,1 do

  10. B←Xp∪{w1,…,wi}B\gets X_p\cup\{w_1,\ldots,w_i\}.

  11. Make BB a clique in FF (add all edges among its vertices).

  12. Append wiw_i to σ\sigma; delete BB from TT.

  13. end for

  14. end if

  15. end while

  16. Let XrX_r be the single remaining bag of TT.

  17. Make XrX_r a clique in FF; append the vertices of XrX_r to σ\sigma.

  18. return (F,σ)(F,\sigma).

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 GG be a graph and vv any vertex, not necessarily simplicial, in GG. The graph operation of simplicial elimination of vv from GG is to add edges between all the neighbours of vv in GG and then remove vv from GG to produce a new graph.

Treewidth is the Complexity of Tensor Contraction

Corollary 3.22 (Simplicial Elimination Process to Generate Triangulated Graph). Let GG be a graph and [v1,v2,…,vn][v_1,v_2,\ldots,v_n] be an ordering of the vertices generated by the process described in theorem 3.20. Simplicially eliminate v1v_1 from GG to produce a new graph H1H_1. Inductively simplicially eliminate viv_i from Hi−1H_{i-1} to produce a new graph HiH_i for i=2,…,ni=2,\ldots,n.

Let HH be the graph on the vertices of GG obtained by adding to GG all the edges that are added during the process of eliminations above. The graph HH is triangulated and GG is an induced subgraph of HH. (That is, the graph HH contains all the vertices of GG and all the edges of $G.)

The order of vertices [v1,…,vn][v_1,\ldots,v_n] in theorem 3.20 is a simplicial elimination ordering of GG. This ordering is important for our later discussion, and therefore deserves a formal definition.

Definition 3.23 (Simplicial Elimination Ordering). 2 Let GG be a graph not necessarily triangulated. Let TT be one of its tree decompositions and [v1,v2,…,vn][v_1,v_2,\ldots,v_n] be an ordering of the vertices generated by the process described in theorem 3.20. The ordering [v1,v2,…,vn][v_1,v_2,\ldots,v_n] is called a simplicial elimination ordering of GG.

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 GG be a tensor network with no loose bonds, regarded as a graph. Let all the bonds of GG be of dimension dd. It is possible to contract GG with a cost of O(dtw⁡(G∗)+1)O(d^{\operatorname{tw}(G^*)+1}), where tw⁡(G∗)\operatorname{tw}(G^*) is the treewidth of the line graph of GG.

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 GG be a graph. The line graph of GG, denoted as G∗G^*,3 is a graph such that each vertex of G∗G^* represents an edge of GG, and two vertices of G∗G^* are adjacent if and only if their corresponding edges share a common endpoint in GG. For an edge e∈Ge \in G, we label the corresponding vertex in G∗G^* as vev_e.

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 GG and its line graph G∗G^*. The edges of GG and vertices of G∗G^* are labelled with the same letter.

Let GG be a graph and G∗G^* its line graph. An edge ee in GG has a corresponding vertex in G∗G^*, which we denote as vev_e. The number of edge neighbours of ee in GG precisely equals the degree of vertex vev_e in G∗G^*. Therefore, using lemma 2.8, we see that the cost of contracting a bond ee in GG is O(ddeg⁡(ve)+1)O(d^{\deg(v_e)+1}).

Lemma 3.27 (Complexity and Vertex Order). Contracting an edge ee in a graph GG has a cost of O(ddeg⁡(ve)+1)O(d^{\deg(v_e)+1}), where vev_e is the corresponding vertex of ee in the line graph G∗G^*.

If an edge ee is contracted in GG, all the neighbouring edges of ee become neighbours of each other if they are not already. The corresponding changes in its line graph G∗G^* are exactly simplicial elimination (definition 3.21) of the vertex vev_e in G∗G^*. This process is demonstrated in Figure 3.9.

Figure 3.9. Contracting an edge aa (in dotted red) in GG makes all the neighbours of the corresponding vertex vav_a in G∗G^* neighbours of each other. This is exactly the simplicial elimination of vav_a in G∗G^*. The cost of this contraction is O(d3)O(d^3), as the degree of vav_a in G∗G^* is 2.

Lemma 3.28 (Contracting Edge is Simplicial Elimination). Contracting an edge ee in a graph GG is equivalent to simplicially eliminating the corresponding vertex vev_e in the line graph G∗G^*.

Therefore, given any tree decomposition of G∗G^*, we can find a simplicial elimination ordering [vα,vβ,⋯ ][v_\alpha,v_\beta,\cdots] guaranteed by theorem 3.20. The corresponding ordering of edges in GG, [α,β,⋯ ][\alpha,\beta,\cdots] is our desired contraction order. Each contraction will take at most O(dtw⁡(G∗)+1)O(d^{\operatorname{tw}(G^*)+1}) time, and the total cost of contracting GG is bounded above by O(n⋅dtw⁡(G∗)+1)O(n \cdot d^{\operatorname{tw}(G^*)+1}), where nn 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 GG be a tensor network with no loose bonds, regarded as a graph. Let all the bonds of GG be of dimension dd. Given a tree decomposition of G∗G^* (which is the line graph of GG), it is possible to find a contraction order with a cost of O(dtw⁡(G∗)+1)O(d^{\operatorname{tw}(G^*)+1}).

Tensor Contraction Gives a Tree Decomposition

Theorem 3.20 gives us important insights into how to generate a perfect elimination ordering [v1,v2,⋯ ,vn][v_1,v_2,\cdots,v_n] 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 viv_i has in the subgraph induced by [vi,vi+1,⋯ ,vn][v_i,v_{i+1},\cdots,v_n].

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 GG be a triangulated graph and [v1,v2,⋯ ,vn][v_1,v_2,\cdots,v_n] be a perfect elimination ordering of GG. Define the simplex number 4 of vertex viv_i as the number of neighbours viv_i has in the subgraph induced by [vi,vi+1,⋯ ,vn][v_i,v_{i+1},\cdots,v_n]. It is possible to construct a tree decomposition of GG with treewidth equal to the maximum simplex number. (By maximum simplex number, we mean the maximum of all simplex numbers of all vertices in GG.)

Proof. We will present a constructive proof using induction on the number of vertices in GG. 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 [v1,⋯ ,vn][v_1,\cdots,v_n], there exists a tree decomposition of GG with treewidth equal to the maximum simplex number, and there is a bag containing exactly the vertex v1v_1 and all of its neighbours. This bag is also a leaf in the tree decomposition.

The base case: when GG has only one vertex, the statement is trivially true. Let TT be our desired tree decomposition promised by the induction hypothesis on the subgraph induced by [v1,…,vn][v_1,\ldots,v_n], and we want to show that the induction statement is also true when we add a new vertex v0v_0 to the front of the perfect elimination order, so that the new perfect elimination order is [v0,v1,…,vn][v_0,v_1,\ldots,v_n], and we create a new tree decomposition T′T' of the new graph G′G' induced by [v0,v1,…,vn][v_0,v_1,\ldots,v_n].

Now, let N={va,vb,…}N = \{v_a,v_b,\ldots\} be the set of neighbours of v0v_0 in the subgraph induced by [v0,v1,…,vn][v_0,v_1,\ldots,v_n]. Without loss of any generality let a<b<⋯a < b < \cdots. Now, vav_a is simplicial too and it is ordered first among all the neighbours of v0v_0, so by induction hypothesis there is a bag (not necessarily a leaf) in TT, which we label as BB, such that BB contains the vertex vav_a and all of its neighbours, which includes all of the elements in NN. Make a new bag {v0}∪N\{v_0\}\cup N and attach it to BB. 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 [a,b,c,d,e][a,b,c,d,e] on the graph GG shown on the lower left and boxed in dashed lines.

Algorithm 2 Tree decomposition from a perfect elimination ordering

Require: A triangulated graph GG and a perfect elimination ordering [v1,v2,…,vn][v_1,v_2,\ldots,v_n] of GG.

Ensure: The final output is a tree decomposition (T,{Xt})(T,\{X_t\}) of GG whose width equals the maximum simplex number of GG.

  1. Initialise TT as a single node t1t_1 with bag Xt1←{vn}X_{t_1}\leftarrow\{v_n\}.

  2. for i←n−1,n−2,…,1i\leftarrow n-1,n-2,\ldots,1 do

  3. N←{v∈{vi+1,…,vn}∣v is adjacent to vi}N\leftarrow\{v\in\{v_{i+1},\ldots,v_n\}\mid v\text{ is adjacent to }v_i\}. ▹\triangleright a clique, since viv_i is simplicial

  4. Let vav_a be the vertex in NN with the smallest index.

  5. Let BB be a bag of TT that contains {va}∪N\{v_a\}\cup N. ▹\triangleright exists, since {va}∪N\{v_a\}\cup N is a clique

  6. Add a new node tt with bag Xt←{vi}∪NX_t\leftarrow\{v_i\}\cup N, and attach tt to BB.

  7. end for

  8. return (T,{Xt})(T,\{X_t\}).

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 GG be a tensor network with no loose bonds, regarded as a graph. Given a contraction order of GG, it is possible to find a tree decomposition of G∗G^* (which is the line graph of GG), such that the complexity of the contraction order lower than or equal to O(n⋅ds)O(n\cdot d^s), where nn is the number of edges in GG and ss 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 GG, [e1,e2,e3,⋯ ][e_1,e_2,e_3,\cdots], the corresponding vertex order [ve1,ve2,ve3,⋯ ][v_{e_1},v_{e_2},v_{e_3},\cdots] is a perfect elimination order of some triangulation of G∗G^{*}. Now, Theorem 3.30 states that from this perfect elimination ordering we can find a tree decomposition of G∗G^{*} 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 GG be a tensor network with no loose bonds and let G∗G^{*} be its line graph. Let all bonds be of dimension dd and let G∗G^{*} have nn vertices. The best possible complexity of contracting GG, bond by bond, is O(n⋅dtw⁡(G∗)+1)O(n \cdot d^{\operatorname{tw}(G^{*})+1}), where tw⁡(G∗)\operatorname{tw}(G^{*}) is the treewidth of G∗G^{*}.

Proof. The proof consists of two parts. First, there exists a contraction order with complexity O(n⋅dtw⁡(G∗)+1)O(n \cdot d^{\operatorname{tw}(G^{*})+1}). Second, no contraction order can have complexity better than O(n⋅dtw⁡(G∗)+1)O(n \cdot d^{\operatorname{tw}(G^{*})+1}).

The existence of a contraction order with complexity O(n⋅dtw⁡(G∗)+1)O(n \cdot d^{\operatorname{tw}(G^{*})+1}) 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 G∗G^{*} 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 O(dtw+1)O(d^{\mathrm{tw}+1}), 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, xx and zz spiders, and one special tensor called the Hadamard gate.

  1. A rank-kk zz-spider with phase ϕ\phi, which we denote as zϕz_{\phi}, is a symmetric tensor such that zϕ(0,…,0⏟k)=1z_{\phi}(\underbrace{0,\ldots,0}_{k})=1, zϕ(1,1,…,1)=exp⁡(iϕ)z_{\phi}(1,1,\ldots,1)=\exp(i\phi), and all other entries are 0.

  1. The Hadamard gate, denoted as HH, is a 2-legged symmetric tensor that equals

12(111−1)(5)\frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \tag*{(5)}

As a matrix, it is unitary and self-adjoint.

  1. A rank-kk xx-spider with phase ϕ\phi, denoted as xϕx_{\phi}, is a symmetric tensor that is the conjugation of zϕz_{\phi} of the same rank by the Hadamard gate.

These generators are shown in Figure 4.1. zz-spiders are shown as green nodes, xx-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 ∣a⟩\lvert a\rangle denotes a state (a vector, usually written as a column) and ⟨a∣\langle a\rvert denotes its dual (co-vector, also called an effect, written as a row), zz, xx and HH nodes can be represented in the following ways

zϕ=∣0⟩⊗n⟨0∣⊗m+eiϕ∣1⟩⊗n⟨1∣⊗mz_\phi= \lvert0\rangle^{\otimes n}\langle0\rvert^{\otimes m} + e^{i\phi}\lvert1\rangle^{\otimes n}\langle1\rvert^{\otimes m}
H=12(∣0⟩⟨0∣+∣0⟩⟨1∣+∣1⟩⟨0∣−∣1⟩⟨1∣)H = \frac{1}{\sqrt{2}}(\lvert0\rangle\langle0\rvert+ \lvert0\rangle\langle1\rvert+ \lvert1\rangle\langle0\rvert- \lvert1\rangle\langle1\rvert)
xϕ=∣+⟩⊗n⟨+∣⊗m+eiϕ∣−⟩⊗n⟨−∣⊗mx_\phi= \lvert+\rangle^{\otimes n}\langle+\rvert^{\otimes m} + e^{i\phi}\lvert-\rangle^{\otimes n}\langle-\rvert^{\otimes m}

where ∣+⟩\lvert+\rangle and ∣−⟩\lvert-\rangle denote the orthonormal basis 12(∣0⟩+∣1⟩)\frac{1}{\sqrt{2}}(\lvert0\rangle+ \lvert1\rangle) and 12(∣0⟩−∣1⟩)\frac{1}{\sqrt{2}}(\lvert0\rangle- \lvert1\rangle) respectively. Note that H∣+⟩=∣0⟩H\lvert+\rangle= \lvert0\rangle, H∣−⟩=∣1⟩H\lvert-\rangle= \lvert1\rangle, and HH=IHH = I.

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 ∝\propto 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.

  1. Spider fusion, denoted as f. A ZX diagram consisting only of zz-spiders is equivalent to a single zz-spider with the sum of the phases of the original spiders as its phase.

  1. Color change, denoted as c. A zz-spider with phase ϕ\phi is equivalent to an xx-spider with phase ϕ\phi conjugated by Hadamard gates on all its legs.

  1. Hadamard cancellation, denoted as hh. Two Hadamard gates are equivalent to the identity.

  1. Identity removal, denoted as id. A single rank-2 zz-spider with phase 0 and one input and one output leg is equivalent to the identity (a single bond).

  1. π\pi-copy, denoted as p. A π\pi-phase xx-spider can be copied through a zz-spider, and vice versa.

  1. Copy rule, denoted as cp. A 0-phase xx-spider can be copied through a zz-spider.

  1. Strong complementarity, denoted as sc. Two sets of 0-phase zz and xx spiders that form a complete bipartite graph can be transformed into a simpler graph where the set of zz spiders is replaced with the same-ranked xx-spider, and the set of xx-spiders is replaced with the same-ranked zz-spider. This is the most crucial one for our later discussion.

  1. Euler decomposition, denoted as e. The Hadamard gate can be decomposed into a sequence of zz and xx 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), π\pi-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 nn xx-spiders on the left-hand side of the rewriting rules, and mm xx-spiders on the right-hand side, then there is a constant factor of (12)n−m\left(\frac{1}{\sqrt{2}}\right)^{n-m} on the right-hand side.

There is also a meta rule.

  1. Since a zz-spider represents the same linear transformation as an xx-spider but in a different basis, there exists a dual rewrite rule for each rule, where zz and xx 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

  1. As all of the ZX generators are symmetric tensors, only connectivity matters (lemma 2.2.3) applies.

  1. 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 D1D_1 and D2D_2, if they represent the same tensor, then there exists a sequence of rewrites from definition 4.1 that transforms D1D_1 into D2D_2.

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

Common quantum gates represented as ZX diagrams

Figure 4.3. Common quantum gates represented as ZX diagrams.

In general, zz-spiders and xx-spiders are the rotation gates around the zz and xx 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 ∣0⋯0⟩|0\cdots0\rangle as shown in Figure 4.4, and for any state in C2n\mathbb{C}^{2^n}, there exists a unitary transformation that transforms ∣0⋯0⟩|0\cdots0\rangle to that state, we have the following corollary.

Figure 4.4. The state ∣0⋯0⟩|0\cdots0\rangle represented as a ZX diagram.

Corollary 4.6. ZX diagrams can represent any state in C2n\mathbb{C}^{2^n}.

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 V=C2nV = \mathbb{C}^{2^n} for some n∈Nn \in\mathbb{N}. A ZX diagram can represent any linear transformation T:V→VT : V \to V and any state ∣ψ⟩∈V|\psi\rangle\in V.

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:

  1. Start with the state ∣0⋯0⟩|0\cdots0\rangle.

  1. Apply a layer of single-qubit gates on each qubit selected from the set {X1/2,Y1/2,W1/2}\{X^{1/2},Y^{1/2},W^{1/2}\}, where W=12(X+Y)W=\frac{1}{\sqrt{2}}(X+Y).

  1. 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 zz- and xx-spiders Cancel). As shown in Figure 4.7, two edges between a zz-spider and an xx-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 zz- and xx-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 00-phase zz-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:

  1. All spiders are zz-spiders.

  1. All edges between spiders are Hadamard edges (dashed-blue edges).

  1. There are no parallel edges or self-loops.

  1. 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:

  1. Fuse as many zz- and xx-spiders as possible so that there are no interconnections between zz- and xx-spiders.

  1. Use color change to transform all xx-spiders into zz-spiders by adding Hadamard gates on all their legs.

  1. Use lemma 4.9 and lemma 4.10 to remove all parallel edges and self-loops.

  1. 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 (K3K_3 graph identity). As shown in Figure 4.12, a complete graph K3K_3 with z-spiders connected by Hadamard gates can be restructured so that the K3K_3 loop is opened.

Figure 4.12. The K3K_3 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 K3K_3 local complementation.

Lemma 4.16. Let the box labelled with KmK_m denote the ZX diagram of a complete graph with mm zz-spiders connected by Hadamard gates. Then, as shown in Figure 4.14, the KmK_m graph can be restructured so that the KmK_m clique is turned into a star graph.

The $K_m$ local complementation

Figure 4.14. The KmK_m local complementation.

The proof is by induction on mm 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 GG on a vertex vv is the operation that replaces the subgraph of GG induced by the neighbours of vv with its complement graph. The resulting graph is denoted as G∗vG * v. Let u,wu,w be two

A Categorical Approach to ZX Calculus

neighbours of vv in GG. uu is connected to ww in G∗vG * v if and only if uu is not connected to ww in GG. 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 GG on the vertex vv. The subgraph induced by the neighbours of vv is replaced with its complement graph.

Theorem 4.18 (Local Complementation Identity). Let GG be a ZX diagram consisting of z-spiders connected by Hadamard gates, and let vv be a vertex in GG. This ZX diagram is equivalent, up to a global constant and up to some local unitaries applied to vv and its neighbours, to the ZX diagram of the local complementation of GG on vv, denoted as G∗vG * v. See Figure 4.16.

General local complementation identity

Figure 4.16. General Local complementation identity. The ZX diagram of the local complementation of GG on vv is equivalent to the original ZX diagram up to a global constant and some local unitaries applied to vv 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 nn being read as nn parallel wires. A morphism D:n→mD : n \to m is a ZX diagram with nn inputs and mm outputs, the composition D′∘DD' \circ D plugs the outputs of DD into the inputs of D′D', and id⁡n\operatorname{id}_{n} is the diagram of nn bare wires. On objects the monoidal product is n⊗m:=n+mn \otimes m := n + m, 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 AA has a dual A∗A^{*} equipped with a cup η:0→A∗⊗A\eta: 0 \to A^{*} \otimes A and a cap ε:A⊗A∗→0\varepsilon: A \otimes A^{*} \to0 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 zz-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 nn is the vector space (C2)⊗n≅C2n(\mathbb{C}^2)^{\otimes n} \cong\mathbb{C}^{2^n} and whose morphisms n→mn \to m are the linear maps between them, a full subcategory of finite dimensional complex vector spaces. The interpretation ⟦D⟧\llbracket D\rrbracket of a ZX diagram DD is the linear map obtained by contracting the tensor network DD as in chapter 2.

As contraction respects both plugging and stacking, ⟦⋅⟧:ZX→Qubit\llbracket\cdot\rrbracket: \mathbf{ZX} \to\mathbf{Qubit} 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 ∼\sim therefore be the smallest equivalence relation on diagrams such that D1∼D2D_1 \sim D_2 for every rule of Figure 4.2, and such that D1∼D2D_1 \sim D_2 implies both E∘D1∘C∼E∘D2∘CE \circ D_1 \circ C \sim E \circ D_2 \circ C and E⊗D1⊗C∼E⊗D2⊗CE \otimes D_1 \otimes C \sim E \otimes D_2 \otimes C for all diagrams CC and EE; these two conditions are the licence, used freely above, to rewrite a subdiagram in place. As ∼\sim is a congruence, its classes D‾\overline{D} are the morphisms of a PROP ZX/∼\mathbf{ZX}/\sim, and the assertion that ⟦D‾⟧:=⟦D⟧\llbracket\overline{D}\rrbracket:= \llbracket D\rrbracket 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 ⟦D⟧\llbracket D\rrbracket for some diagram DD, which for a functor is the analogue of surjectivity and is called fullness; theorem 4.4 says that ⟦D1⟧=⟦D2⟧\llbracket D_1\rrbracket= \llbracket D_2\rrbracket implies D1∼D2D_1 \sim D_2, the analogue of injectivity, called faithfulness. Universality and completeness together therefore assert that ⟦⋅⟧:ZX/∼→Qubit\llbracket\cdot\rrbracket: \mathbf{ZX}/\sim\to\mathbf{Qubit} is full and faithful, which is to say an equivalence of categories.

A monoid in a monoidal category is an object MM with morphisms μ:M⊗M→M\mu: M \otimes M \to M and ν:0→M\nu: 0 \to M satisfying the following identities.

μ∘(μ⊗id)=μ∘(id⊗μ)\mu\circ(\mu\otimes\mathrm{id}) = \mu\circ(\mathrm{id} \otimes\mu)
μ∘(ν⊗id)=id=μ∘(id⊗ν)\mu\circ(\nu\otimes\mathrm{id}) = \mathrm{id} = \mu\circ(\mathrm{id} \otimes\nu)

Take M=1M = 1, let μ\mu be the rank-three zz-spider read with two inputs and one output, and let ν\nu be the rank-one zz-spider: associativity and unitality are then instances of spider fusion and identity removal, and reading the same two spiders backwards gives a comonoid δ=μ†\delta= \mu^\dagger, ϵ=ν†\epsilon= \nu^\dagger. These four maps and the laws they obey are drawn in Figure 4.17.

Figure 4.17. The zz-spider as a monoid and a comonoid. Top: the multiplication μ\mu, the unit ν\nu, the comultiplication δ\delta and the counit ε\varepsilon. 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 (id⊗μ)∘(δ⊗id)=δ∘μ=(μ⊗id)∘(id⊗δ)(\mathrm{id} \otimes\mu) \circ(\delta\otimes\mathrm{id}) = \delta\circ\mu= (\mu\otimes\mathrm{id}) \circ(\mathrm{id} \otimes\delta) form a Frobenius algebra, special when μ∘δ=id\mu\circ\delta= \mathrm{id} and a dagger-Frobenius algebra when the two halves are related by †\dagger as above. Both conditions are drawn in Figure 4.18, and both are again instances of spider fusion, so that the zz-spiders, and by the meta rule the xx-spiders, form a commutative special dagger-Frobenius algebra.

Figure 4.18. The Frobenius conditions (top) and speciality (bottom) for the zz-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 VV arises from an orthonormal basis ∣v1⟩,⋯ ,∣vn⟩|v_1\rangle,\cdots,|v_n\rangle of VV, its spiders being ∑i∣vi⋯vi⟩⟨vi⋯vi∣\sum_i |v_i\cdots v_i\rangle\langle v_i\cdots v_i|. Spider fusion is thus no arbitrary axiom but a diagrammatic characterisation of the notion of an orthonormal basis, of which the zz-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 ∝\propto. 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 KmK_m 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 C2\mathbb{C}^{2}. Every equation derived by the rewrite rules therefore holds in each model of the theory, under any monoidal functor out of ZX/∼\mathrm{ZX}/\sim, 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 GG be a graph of a tensor network (we assume GG is connected and contains at least 2 edges.), G′G' be another graph obtained by the operation of splitting a vertex, which is the opposite of spider fusion (ff in Figure 4.2, and in Figure 5.1). The best bond-by-bond tensor contraction algorithm on G′G' is not more complex than that of GG.

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 GG be a graph of a tensor network (which we assume to be connected and contains at least two edges.), G′G' 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 G′G' is not more complex than that of GG.

Original graph and graph after dividing an edge

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 GG being a connected non-trivial graph is necessary for both lemmata. This is because, if GG is the graph with two vertices and one edge, its line graph GG 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 GG denote a tensor network. Let vv be a vertex of degree two with both of its neighbours connected. Let G′G' be the diagram with K3 local complementation (lemma 4.4) applied to vv. The transformation from GG to G′G' 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 GG. Therefore the complexity cannot be greater.

Tensor Network and Line Graph transformations under local complementation

Figure 5.3. K3 complementation on GG is equivalent to removing a vertex in the line graph G∗G^*.

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 GG be a graph-like ZX diagram. Let vv be a vertex in GG such that vv has degree 3 or more and two of its neighbours n1n_1 and n2n_2 are connected by a Hadamard edge. We may unfuse vv to form v1,v2v_1,v_2 such that v1v_1 is connected to n1n_1 and n2n_2, while the rest of the neighbours of vv are connected to v2v_2. By applying K3 local complementation to v1v_1, we can remove the edge (n1,n2)(n_1,n_2). We label the resulting graph as G′G'. We do not require G′G' 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 zz-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 GG, 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 GG.

We propose a straightforward algorithm, shown in algorithm 3.

Algorithm 3 Tensor Contraction with Graph Operation

  1. Input: A graph-like ZX diagram GG.1

  2. Perform Rewrite Preprocessing on GG to obtain a new graph G′G'.

  3. Perform regular tensor contraction algorithm on G′G'.

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 O(n2)O(n^2) time. Note that contraction can be done in O(nd2)O(nd^2) only for a tree tensor network, where dd is the dimension of the bond (in our case, d=2d = 2). 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 GG be a graph-like ZX diagram with nn vertices. The complexity of algorithm 3 is O(n2)O(n^2) 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 GG with nn vertices via the Erdős–Rényi algorithm [16]. Its line graph is computed, which we label as G∗G^*. We also compute the treewidth of G∗G^*. The new graph FF is obtained by applying the rewrite preprocessing to GG. The treewidth of F∗F^* is also computed. The treewidths are found via Tamaki’s positive-instance driven dynamic programming algorithm [55].

These are our key findings.

  1. 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.

∣V(G)∣|V(G)|∣V(G∗)∣|V(G^*)|∣V(F∗)∣|V(F^*)|tw⁡(G∗)\operatorname{tw}(G^*)tw⁡(F∗)\operatorname{tw}(F^*)decrease
10334217107
11354416106
1026321385
20435015114
1936421284
923281284
820251174
71619963
141821642
71518862
61114642
61114642
579422
5810532
162730761
142022761
141820541
111112431
689431
61012541

Table 5.1. The table of treewidth before and after rewrite preprocessing on 20 random graphs. ∣V(G)∣|V(G)| is the number of vertices in the original graph, ∣V(G∗)∣|V(G^*)| is the number of vertices in the line graph of the original graph, ∣V(F∗)∣|V(F^*)| is the number of vertices in the line graph of the graph after rewrite preprocessing, tw⁡(G∗)\operatorname{tw}(G^*) is the treewidth of the line graph of the original graph, tw⁡(F∗)\operatorname{tw}(F^*) is the treewidth of the line graph of the graph after rewrite preprocessing, and decrease is tw⁡(G∗)−tw⁡(F∗)\operatorname{tw}(G^*)-\operatorname{tw}(F^*).

Scatter plot of treewidth before and after preprocessing

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 y=xy=x. The points below the red line are the graphs whose treewidth is reduced by rewrite preprocessing.

  1. The average decrease of treewidth is 1.62, out of the mean treewidth 5.56.

  1. 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.

  1. 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.

  1. 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.

  1. 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.

∣V(G)∣|V(G)|∣V(G∗)∣|V(G^*)|∣V(F∗)∣|V(F^*)|tw⁡(G∗)\operatorname{tw}(G^*)tw⁡(F∗)\operatorname{tw}(F^*)decrease
10364520128
9293617107
9313918117
9334120137
12415020137
10334217107
10324017116
10323917116
10324017116
1027341376

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 zz-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, ω\omega denotes the dd-th root of unity, where dd is the dimension of the bond.

We have assumed that all wires have dimension dd 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:

  1. 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.

  2. All generators in ZX calculus are symmetric tensors. The xx-node and WW-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 HH is still unitary, but it is no longer self-adjoint.

H†=H3,HH†=IH^\dagger= H^3,\qquad HH^\dagger= I

XX-nodes are still similar to ZZ-nodes (they are conjugate to each other), but now HHHZH=XHHHZH = X.

Most importantly, we still have strong complementarity between ZZ-box and XX-node as well as another bialgebra rule between ZZ-box and WW-box.

Figure 6.3. Some rewrite rules of ZXW calculus. The empty zz node is defined as ∑∣i⟩∣j⟩\sum|i\rangle|j\rangle, and the empty xx node is defined as xK0xK_0.

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

  1. multiple edges between two vertices,

  2. loops,

  3. directed edges,

  4. 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 Xs_s-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, Xs_s-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.

Image not extracted

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 O(n⋅dtw⁡(G∗)+1)O(n \cdot d^{\operatorname{tw}(G^*)+1}), where G∗G^* is the line graph of the network (theorem 3.32) and nn is number of edges in GG. The proof depends on one observation: contracting a bond is exactly a simplicial elimination in the line graph, so tree decompositions of G∗G^* 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 GG be a graph and TT its tree decomposition. For any vertex v∈Gv \in G, the set of bags in TT that contain vv is the vertex subtree of vv in TT.

The reason why it is called a subtree is that the vertex subtree of vv must be connected by property 3 of tree decomposition.

Lemma A.2 (Clique Bag). If a graph GG has a clique of size kk, then any tree decomposition of GG must have a bag containing all the vertices of the clique. Therefore, the treewidth of GG is at least k−1k - 1.

Proof. Let the clique consist of vertices v1,v2,…,vkv_1,v_2,\ldots,v_k.

Now, the vertex subtree of v1v_1 intersects with the vertex subtree of v2,v3,…,vkv_2,v_3,\ldots,v_k, because all of them are adjacent. The vertex subtree of v2v_2 intersects with the vertex subtree of v3,…,vkv_3,\ldots,v_k, and so on. By simple set theory we see that the intersection of all the vertex subtrees of v1,v2,…,vkv_1,v_2,\ldots,v_k is non-empty. All bags in the intersection contain all the vertices of the clique, and therefore the treewidth of GG is at least k−1k - 1. Q.E.D.

Miscellaneous Proofs

Proof of Lemma 3.10. We only need to prove that if a graph GG can be obtained from HH by performing one of the three graph-minor operations, then the treewidth of GG is less than or equal to the treewidth of HH. The lemma follows as any minor can be obtained by a finite sequence of these three operations. Let TT be a tree decomposition of HH. We have three cases to consider.

  1. If GG is obtained from HH by deleting an edge, then TT is also a tree decomposition of GG.

  1. If GG is obtained from HH by deleting a vertex vv, let T′T' be the tree decomposition of GG isomorphic to TT with vv removed from all bags. (We allow empty bags). It is clear that T′T' is a tree decomposition of GG and the width of T′T' is less than or equal to the width of TT.

  1. If GG is obtained from HH by contracting an edge (u,v)(u,v), let ww denote the new vertex after contraction. Let T′T' be the tree decomposition of GG isomorphic to TT with uu and vv replaced by a new vertex ww in all bags that contain uu or vv.

In all cases, we can construct a tree decomposition of GG from a tree decomposition of HH with width less than or equal to the width of TT. Therefore, the treewidth of GG is less than or equal to the treewidth of HH. Q.E.D.

Lemma A.3 (Connection between Triangulated Graph and Cut Vertices). Let GG be a triangulated graph. Let PP be a cycle in GG and let vertices u,v∈Gu,v \in G be a pair of non-adjacent vertices in PP. u,vu,v are cut vertices of PP (removing u,vu,v makes PP disconnected). Let C1,C2C_1,C_2 be the two components of PP after removing u,vu,v. If C1,C2C_1,C_2 are not adjacent in GG, then uu must be adjacent to vv in GG.

Proof. Provided C1,C2C_1,C_2 are not adjacent in GG, there must be a cycle of length four. If not, let C\mathcal{C} be the smallest cycle of GG that contains u,vu,v. Since GG is triangulated, C\mathcal{C} 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.

Image not extracted

Figure A.1. Provided C1C_1 and C2C_2 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 uu and vv.

Let C\mathcal{C} be the length four cycle. There are two cases:

Miscellaneous Proofs

  1. u,vu,v are adjacent in C\mathcal{C}. Then we are done.

  1. u,vu,v are not adjacent in C\mathcal{C}. Then the cycle must be of the form [a,u,b,v][a,u,b,v], where a∈C1a \in C_1 and b∈C2b \in C_2. Since aa cannot connect to bb, uu must be adjacent to vv.

Q.E.D.

Proof of Lemma 3.17. We shall prove the following stronger statement.

For any triangulated graph GG, given any vertex v∈Gv \in G, let HH be the set of vertices in GG that are farthest away from vv. Then there exists a simplicial vertex in HH.

Recall that the distance between two vertices uu and vv in a graph is the length of the shortest path connecting them.

The proof is by induction. The base case is when GG has only one vertex vv. This means H={v}H = \{v\} and vv is simplicial.

For a generic triangulated graph GG with a chosen vertex vv, let H1H_1 be one of the connected components of HH. Let SS be the set of vertices that are adjacent to H1H_1 and are not in H1H_1. See figure A.2 for a demonstration of this setup.

Image not extracted

Figure A.2. Demonstration of the proof of lemma 3.17. H1H_1 is a connected component of farthest vertices from vv. SS is the set of vertices that are adjacent to H1H_1 and are not in H1H_1.

We claim that SS is a clique.

If SS contains only one vertex, there is nothing to prove. Assume SS contains at least two vertices. Let u,w∈Su,w \in S be any distinct vertices. Both of u,wu,w are connected to vv via some vertices not in HH, as they are closer to vv. Both of them are also connected to some vertices in the connected component H1H_1. Note that no vertices in H1H_1 shall connect to any other vertices closer to vv except those in SS, as this would make the distance from vv to H1H_1 smaller. Therefore we are in a position to apply lemma A.3 to the cycle formed by u,wu,w and any two vertices in H1H_1. In such a way we have proved that any uu and w∈Sw \in S are adjacent, and therefore SS is a clique.

Now apply the induction hypothesis to the subgraph induced by H1∖SH_1 \setminus S. If H1∖SH_1 \setminus S is not a clique, then we can find a vertex w∈H1w \in H_1 and u∈Su \in S such that ww is at distance 2 from uu, and applying the induction hypothesis to the subgraph induced by H1∪SH_1 \cup S with uu as the chosen vertex shows that there is a simplicial vertex in H1H_1. This vertex is also simplicial in GG as it is not adjacent to any vertices outside of H1∪SH_1 \cup S. If H1∪SH_1 \cup S is a clique, then any vertex in H1H_1 is simplicial in GG. 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 aa have n+mn+m incident edges. After splitting the vertex aa into two vertices bb and cc, bb has nn incident edges and cc has mm incident edges. (We may safely assume that both nn and mm are greater than 1, because otherwise the case is trivial and we have ruled out the case when the graph GG has treewidth 0.) Splitting a vertex creates one more edge, whose corresponding vertex in the line graph we label as α\alpha. The line graph of the graph GG before and after splitting a vertex is shown in figure A.3.

Image not extracted

Figure A.3. The line graph of GG before and after splitting a vertex.

Let us construct a tree decomposition of H∗H^* with treewidth no more than that of G∗G^*. Since G∗G^* has a clique of size n+mn+m, there must be a bag in the tree decomposition of G∗G^* that contains all of the vertices in this clique. Denote this bag as AA. We label these vertices as v1,⋯ ,vn,u1,⋯ ,umv_1,\cdots,v_n,u_1,\cdots,u_m. The treewidth of G∗G^* must be greater than or equal to n+m−1n+m-1.

If the treewidth of G∗G^* is greater than n+m−1n+m-1, adding α\alpha to the bag AA gives a tree decomposition of H∗H^* with the same treewidth as G∗G^*.

Let us now consider the case when the treewidth of G∗G^* is n+m−1n+m-1. Again, here we have two cases to consider.

  1. AA is a leaf in the tree decomposition of G∗G^*. In this case there must be a vertex w∈Aw \in A such that ww is not in any other bag. We can remove ww from AA and add α\alpha to AA, and attach the original bag that contains ww to AA. This gives a tree decomposition of H∗H^* with the same treewidth as G∗G^*.

  1. Removing AA from the tree decomposition of G∗G^* leaves two or more connected components. Again, in this case we claim that there must be a vertex w∈Aw \in A such that there exist two components of the tree decomposition of G∗G^* that do not contain ww. If it is not the case, it means that all the vertices in AA are connected to some components. Reducing that component to a single vertex makes a clique of size n+m+1n+m+1, which is impossible as the treewidth of G∗G^* is n+m−1n+m-1.

So we have found at least one component C1C_1 such that it does not contain ww. (C1C_1 can contain several connected components.) In this case we can create a new bag BB that contains α\alpha and all the vertices in AA except ww, attach BB to C1C_1, connect BB to AA, and remove the connections between AA and C1C_1

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 GG before and after dividing an edge is shown in figure A.4.

Again, we may safely assume that both nn and mm are greater than 1, because otherwise the case is trivial and we have ruled out the case when the graph GG has treewidth 0

Let us first consider the tree decomposition of G∗G^*. By lemma A.2, there exist two bags, A,BA,B, such that AA contains all of the vertices in KnK_n and α\alpha, while BB contains all of the vertices in KmK_m and α\alpha.

There must be a path connecting AA and BB in the tree decomposition of G∗G^*, and every bag on this path must contain α\alpha by the third property of tree decomposition. (This path may contain only AA and BB, in which case α\alpha is a cut vertex of G∗G^*.)

Image not extracted

Figure A.4. The line graph of GG before and after dividing an edge.

Since α\alpha is not connected to any other vertices in G∗G^*, we can remove α\alpha from all other bags that are not on the path connecting AA and BB without violating any of the properties of tree decomposition. Label this tree decomposition as T(G∗)T(G^*).

We will construct a tree decomposition of H∗H^*, which we label as T(H∗)T(H^*), and it shall have the same width as T(G∗)T(G^*). Start with T(H∗)=T(G∗)T(H^*) = T(G^*) and replace α\alpha in AA with β\beta and α\alpha in BB with γ\gamma. All other α\alpha shall be removed.

Now T(H∗)T(H^*) is still a tree and all properties of tree decomposition are satisfied except that there is no bag specifying the connection between the vertex β\beta and γ\gamma.

If the path from AA to BB does not contain any other vertices than the end point, we simply add another bag between AA and BB that contains β\beta and γ\gamma. If the path from AA to BB contains other vertices, what we need to do is add β\beta to the first kk bags, γ\gamma to the rest of the bags, and γ\gamma and β\beta shall both be added to one of the bags in the middle of the path. This is shown in figure A.5.

Changing α\alpha to β\beta or γ\gamma in the new tree decomposition will not change the width of the tree decomposition. The only issue is that we need to add both α\alpha and β\beta 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, C,DC,D, contain different vertices and have the same order, we can add another bag EE that contains their intersection (which has fewer vertices) between them.

This completes the proof. Q.E.D.

Image not extracted

Figure A.5. Up: the path ABAB in the tree decomposition of G∗G^*. Down: the path ABAB in the tree decomposition of H∗H^*.

Remark A.6. The insight of the previous proof is that if there is a path A1,A2,⋯ ,AkA_1,A_2,\cdots,A_k in the tree decomposition, then it is possible to create a bag BB, connected only to AiA_i and Ai+1A_{i+1}, that contains the intersection of AiA_i and Ai+1A_{i+1} without increasing the width of the tree decomposition. Moreover, the size of bag BB must be smaller than the size of AiA_i and Ai+1A_{i+1}, so we can add more vertices to BB without increasing the width of the tree decomposition.

Definition A.7 (Graph Substitution). Let GG be a graph and HH be an induced subgraph of GG. HH is connected to the rest of GG via a set of edges EE. Regarding HH as a graph with loose edges, we can substitute HH with another graph H′H' that has the same number of loose edges as HH. This is exactly the operation we perform for diagrammatic rewrites in ZX calculus.

Conjecture A.8 (Graph Substitution may Reduce Treewidth). Let GG be a graph and HH be its induced subgraph. Let SS be another graph with the same number of loose edges as HH. Let kk be the number of loose edges in HH and SS. Let G′G' be the graph obtained by substituting HH with SS in GG.

Regarding each loose edge as ending with a new vertex, we have the following inequality

tw⁡(G′)≤tw⁡(G)−tw⁡(H)+tw⁡(S)+k\operatorname{tw}(G') \le\operatorname{tw}(G) - \operatorname{tw}(H) + \operatorname{tw}(S) + k

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.

Image not extracted

(a) The Wagner graph. 8 vertices, 12 edges, treewidth 4.

Image not extracted

(b) The Petersen graph. 10 vertices, 15 edges, treewidth 4.

Image not extracted

(c) The cubical graph (the graph of the cube). 8 vertices, 12 edges, treewidth 3.

Image not extracted

(d) The gem graph. 5 vertices, 7 edges, treewidth 2.

Image not extracted

(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.

Image not extracted

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 (ZZ-boxes, XX-nodes, Hadamard boxes, WW-boxes, AND gates, boundary markers and an empty node), with phases typed as LaTeX expressions such as π/4\pi/4 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 GG and its line graph, as well as the graph FF 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 GG be a random graph generated by the Erdős–Rényi algorithm with a finite number of vertices. The probability that the treewidth of GG is smaller than d−2d-2, where dd is the average degree of GG, is zero.

Here I plotted another graph (Figure B.3), which shows a strong linear correlation between n−tw⁡n-\operatorname{tw} and n(1−p)/p\sqrt{n(1-p)/p}, where nn is the number of vertices and pp is the probability of edge generation in the Erdős–Rényi algorithm (so that the expected average degree is p(n−1)p(n-1)).

The treewidth of the Erdős–Rényi model G(n,p)G(n,p) 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 G(n,d/n)G(n,d/n) is linear in nn with high probability for d≥2.36d \ge2.36 [29]; Gao improved the threshold to m/n≥1.073m/n \ge1.073 in the uniform model G(n,m)G(n,m) (where mm edges are placed uniformly at random among the (n2)\binom{n}{2} 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 tw⁡(G(n,p))=n−O(n/p)\operatorname{tw}(G(n,p)) = n-O(\sqrt{n/p}) asymptotically almost surely (that is, with probability tending to one as n→∞n \to\infty) [42], so the deficit n−tw⁡n-\operatorname{tw} is of order n/p\sqrt{n/p} — precisely the order of the horizontal axis n(1−p)/p\sqrt{n(1-p)/p} of figure B.3 when pp 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 tw⁡(G)≥d−2\operatorname{tw}(G) \ge d-2 holds with high probability. This is immediate in the sparse regimes, where the treewidth is linear in nn while dd stays constant, and for fixed pp it follows from the dense asymptotics, since d=p(n−1)d=p(n-1) and the deficit O(n/p)O(\sqrt{n/p}) is negligible compared with n−d=n(1−p)+pn-d=n(1-p)+p; the two sides are closest in the near-complete regime 1−p=O(1/n)1-p=O(1/n).

Image not extracted

Figure B.1. (a) A random graph-like ZX diagram GG. (b) Graph FF, which is GG after the preprocessing algorithm (definition 5.6). (c) Line graph of GG, treewidth 11. (d) Line graph of FF, treewidth 7. A random graph-like ZX diagram before and after preprocessing and their line graphs.

Image not extracted

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.

Image not extracted

Figure B.3. Using the same data as figure B.2, we plotted n−twn-\mathrm{tw} versus n(1−p)/p\sqrt{n(1-p)/p}, where nn is the number of vertices and pp is the probability of edge generation in the Erdős–Rényi algorithm (so that the expected average degree is p(n−1)p(n-1)). 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 n−twn-\mathrm{tw} is low) between the two quantities.

References

  1. [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
  2. [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
  3. [50]Selinger, P. (2007). Dagger compact closed categories and completely positive maps. Electronic Notes in Theoretical Computer Science, 170:139–163.DOI
  4. [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.
  5. [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
  6. [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.
  7. [54]Strassen, V. (1969). Gaussian elimination is not optimal.DOI
  8. [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.
  9. [56]van de Wetering, J. (2020). Zx-calculus for the working quantum computer scientist.arxiv.org/abs/2012.13966
  10. [57]Verstraete, F. and Cirac, J. I. (2004). Renormalization algorithms for quantum-many body systems in two and higher dimensions.DOI
  11. [58]Voigt, W. (1898). Die fundamentalen physikalischen Eigenschaften der Krystalle in elementarer Darstellung. Verlag von Veit & Comp., Leipzig.DOI
  12. [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
  13. [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
  14. [61]Wang, Q., Poór, B., and Shaikh, R. A. (2026). Completeness of qufinite zxw calculus, a graphical language for finite-dimensional quantum theory.
  15. [62]West, D. B. et al. (2001). Introduction to graph theory, volume 2. Prentice hall Upper Saddle River.
  16. [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
  17. [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
  18. [65]Zhou, Y., Stoudenmire, E. M., and Waintal, X. (2020). What limits the simulation of quantum computers? Physical Review X, 10(4):041038.DOI

Paper details

vlnc:W_zrccvr7x
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents