Tensor Contraction with ZX Calculus, a Graph-Theoretic Approach

Title: Tensor Contraction with ZX Calculus: A Graph-Theoretic Approach
Author: Yuhao Han
Institution: University of Oxford (MSc in Mathematics and Foundations of Computer Science)
Date: September 2026

1. Problem Statement

Tensor networks provide a diagrammatic representation of complex relations between tensors, ubiquitous in quantum many-body physics, quantum computation, and machine learning. The central computational bottleneck in utilizing these networks is tensor contraction: the evaluation of the network, analogous to matrix multiplication.

The complexity of contracting a tensor network depends heavily on the order in which bonds (indices) are summed. Finding the optimal contraction order is an NP-hard problem. Theoretically, this problem is equivalent to finding the treewidth of the line graph of the tensor network. While heuristic algorithms (e.g., minimum degree, simulated annealing) exist to find good contraction orders for a fixed network, they operate on a static structure. The dissertation posits that in many practical cases, the network itself can be transformed into an equivalent structure with a lower treewidth before the contraction order is determined, thereby reducing the exponential cost of contraction.

2. Methodology

The thesis proposes a new paradigm: Rewrite Preprocessing. Instead of searching for an optimal order on a fixed graph, the method transforms the tensor network into an equivalent network with a lower treewidth line graph using graph-theoretic operations derived from ZX calculus.

The methodology proceeds in three stages:

1. Theoretical Foundation: Establishing the equivalence between tensor contraction complexity and the treewidth of the network's line graph ($G^*$). The author proves that contracting a bond in the original graph $G$ corresponds exactly to a simplicial elimination of the corresponding vertex in $G^*$. Consequently, the optimal contraction cost is $O(n \cdot d^{tw(G^*)+1})$, where $n$ is the number of edges, $d$ is the bond dimension, and $tw(G^*)$ is the treewidth.
2. Graph Operations via ZX Calculus: The thesis focuses on ZX calculus, a diagrammatic language for quantum circuits (where bond dimension $d=2$). It utilizes specific rewrite rules to perform graph operations that reduce treewidth without increasing contraction complexity. The core operations identified are:
   • $K_3$ Remove Edge: Based on the $K_3$ local complementation identity, this operation removes a vertex from the line graph (by removing a bond in the tensor network) under specific conditions (a degree-2 vertex with connected neighbors).
   • Unfuse and $K_3$ Complementation: A composite operation for graph-like ZX diagrams. It involves "unfusing" a vertex to create a valid target for local complementation, applying the complementation to remove an edge (a triangle of Hadamard edges), and effectively reducing the line graph's complexity.
3. Algorithmic Implementation: The author implements these operations in a Rust program named Cartographer. The algorithm iteratively applies these rewrite rules to a graph-like ZX diagram until no further changes can be made, then passes the resulting graph to a standard bond-by-bond contraction algorithm.

3. Key Contributions

• Formal Equivalence: The thesis provides a self-contained proof (Theorem 3.32) that the best possible bond-by-bond contraction complexity is strictly determined by the treewidth of the line graph, $O(n \cdot d^{tw(G^*)+1})$. The author notes that while this result is known in literature (e.g., Markov and Shi), the proof provided here is original.
• Rewrite Preprocessing Paradigm: The introduction of "Rewrite Preprocessing" as a distinct step prior to contraction ordering. The thesis proves that the proposed graph operations ($K_3$ remove edge and Unfuse + $K_3$ Complementation) never increase the contraction complexity (Lemma 5.1, 5.2, 5.4).
• Graph-Theoretic Reduction: The demonstration that ZX calculus rewrite rules can be interpreted as graph operations that reduce the treewidth of the line graph. Specifically, the $K_3$ local complementation identity in ZX calculus corresponds to removing a vertex from the line graph.
• Software Implementation: The development of Cartographer, a tool that automates the rewrite preprocessing, and ZXW Graphboard for visualization.
• Extension to Generic Tensors: The discussion of ZXW calculus (which handles arbitrary bond dimensions) and the proof (Theorem 6.4) that a set of symmetric generators exists which can represent any tensor, suggesting a path for extending these graph-theoretic methods beyond qubits ($d=2$).

4. Results

The thesis presents empirical results based on 441 randomly generated graph-like ZX diagrams (using the Erdős–Rényi model):

• Treewidth Reduction: In 254 out of 441 cases (approx. 57.6%), the treewidth of the line graph decreased after rewrite preprocessing. In the remaining cases, it remained unchanged. No cases showed an increase in treewidth.
• Magnitude of Reduction: The average decrease in treewidth was 1.62, against a mean initial treewidth of 5.56. Given the exponential dependence of contraction cost on treewidth, this reduction is significant.
• Vertex Count: The preprocessing increased the number of vertices in the line graph (from an average of 13.35 to 15.56), indicating that the reduction in treewidth is not achieved by simply shrinking the graph, but by altering its connectivity structure.
• Limitations: The current implementation is restricted to quantum circuits (bond dimension 2). The author notes that while the rewrite rules apply to the generators of ZX diagrams, applying them to general tensor networks with sparse generators requires careful handling, as conjugation by unitaries (required for some transformations) may destroy sparsity.

5. Significance and Claims

The author claims that this work offers a complementary approach to existing contraction heuristics. While current methods search for a good order on a fixed network, this method transforms the network itself into a "strictly easier" version before ordering.

• Safety Guarantee: A primary claim is the safety guarantee: the proposed rewrite operations are proven to never increase the optimal contraction cost.
• Efficiency: The preprocessing step has a computational overhead of $O(n^2)$, which is negligible compared to the exponential cost of the subsequent contraction for high-treewidth networks.
• Modesty: The thesis is modest regarding the theoretical understanding of why these reductions occur. The author explicitly states that the theoretical conditions under which treewidth decreases are "extremely complicated" and not fully covered, relying instead on empirical evidence. The work is framed as a proof-of-concept for a new paradigm rather than a complete solution to the NP-hard problem of optimal contraction.
• Future Directions: The author identifies the extension of these graph-theoretic rewrite rules to generic tensor networks (using ZXW calculus) and the theoretical analysis of the treewidth reduction mechanisms as key areas for future research.

In summary, the dissertation demonstrates that by leveraging the structural properties of ZX calculus, one can algorithmically simplify the graph-theoretic representation of quantum circuits to lower their contraction complexity, offering a practical and safe preprocessing step for tensor network simulations.