arXiv:2611.01890
Tensor Contraction with ZX Calculus, a Graph-Theoretic Approach
Yuhao Han
Abstract
Tensors are higher dimensional generalisations of vectors and matrices. Tensor networks are a diagrammatic representation of complicated relations between tensors, and tensor contraction is the evaluation of a tensor network analogous to matrix multiplication. Tensor networks and tensor contraction are ubiquitous in computer science, physics, and applied mathematics. Most existing tensor contraction algorithms are focused on finding an optimal contraction order of the tensors' bonds. However, finding the optimal order is an NP-hard problem. It is equivalent to another possibly more straightforward but still NP-hard problem of finding the treewidth of the line graph of the tensor network. While in general finding the optimal bond-by-bond contraction order is hard, in many practical cases there is no need to find an optimal order. This observation leads to the core innovation of this thesis, which is a new tensor contraction paradigm that uses graph theoretic operations to produce an equivalent tensor network whose line graph has lower treewidth than the original tensor network, before applying the bond-by-bond contraction algorithm. We call these graph theoretical operations \textit{rewrite preprocessing}, and we name the algorithms that apply rewrite preprocessing before regular bond-by-bond contraction \textit{Tensor Contraction with Graph Operation}. There are many possible ways to perform rewrite preprocessing; in this thesis, we focus on the graph operations of ZX calculus, a diagrammatic language for quantum circuits. Ample numerical simulations have been performed to demonstrate the effectiveness of our proposed method.
AI Summary
The paper asks whether ZX-calculus rewrites can reduce tensor-network contraction cost before a contraction order is chosen. Its optimisation target is the treewidth of the network’s line graph, which controls the exponential cost of bond-by-bond contraction for uniform bond dimension. Much of the thesis reviews tensor networks, treewidth and ZX calculus; the algorithmic contribution concerns graph-like qubit ZX diagrams. The preprocessing repeatedly applies two triangle-based rewrites: a $K_3$ local-complementation identity that removes an edge, and a version preceded by spider unfusion. The paper gives graph-theoretic arguments that these operations cannot increase line-graph treewidth, using edge deletion, vertex splitting and edge subdivision. The resulting diagram is then passed to a conventional contraction algorithm. A Rust implementation is provided, and preprocessing overhead is stated as $O(n^2)$ for a diagram with $n$ vertices. Benchmarks use 441 Erdős–Rényi graph-like diagrams, with line-graph treewidth computed using Tamaki’s exact algorithm. Treewidth decreased in 254 cases, remained unchanged in 187, and never increased. The mean decrease was $1.62$ from an initial mean of $5.56$; mean line-graph vertex count increased from $13.35$ to $15.56$. The evaluation measures treewidth rather than end-to-end contraction runtime and does not compare against existing simplification pipelines. Stated limitations include restriction to two-dimensional bonds, other opportunities to exploit ZX-tensor sparsity, and the absence of a theoretical characterisation of achievable treewidth reductions. Extensions to generic tensor calculi are discussed but not developed.
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.
Central claim may not hold: The vertex-splitting proof fails to cover the edge between its newly introduced line-graph vertex alpha and the removed bag element w, leaving a key preprocessing safety guarantee unproved. The single-bond contraction cost formula based on line-graph degree fails for parallel bonds, so the stated derivation does not establish the contraction-cost correspondence for the allowed multigraph networks. The stated Hadamard-self-loop removal rule omits a necessary pi shift of the spider phase and therefore does not preserve the represented tensor up to a global scalar.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.