ZX-Calculus: Rewriting Your Way to Smaller Circuits

Quantum circuit optimization is hard. Gates are ordered, qubits are indexed, and moving any gate can break the computation. But there’s another representation - ZX-calculus - where circuits become graphs, and optimization becomes pattern matching. You apply local rewrites that preserve the computation’s meaning, and out comes a simpler circuit.

ZX rewriting can find optimizations that are nearly invisible at the gate level. Phases teleport through entangled connections. Redundant rotations collapse across distant parts of the circuit. The rewrites are simple; the results can be dramatic.

This post covers the ZX representation, three core rewrite rules with proof sketches, and a working Python implementation.

Why Circuits Are Rigid

A quantum circuit is a sequence of gates applied to indexed qubits in a specific order. RZ(α)R_Z(\alpha) followed by RZ(β)R_Z(\beta) on the same qubit simplifies to RZ(α+β)R_Z(\alpha + \beta) - but only if they’re adjacent. Insert a CNOT between them and the simplification breaks.

This rigidity makes optimization difficult. You can’t simply cancel two “obviously redundant” gates when other operations appear between them. Circuit identities exist, but applying them requires careful bookkeeping of what commutes with what.

ZX-calculus takes a different approach: throw away the rigid sequential structure and work with graphs instead.

ZX Diagrams: Spiders and Wires

A ZX diagram is built from two types of nodes - Z-spiders (green) and X-spiders (red) - connected by wires. Each spider has a phase α∈[0,2π)\alpha \in [0, 2\pi). Wires can connect any spiders, and there’s no inherent “time flows left to right” ordering.

Only connectivity matters. You can bend, stretch, and rearrange wires freely. The diagram represents a linear map determined purely by its topology and the spider phases.

Spider Semantics

A Z-spider with phase α\alpha, mm inputs, and nn outputs represents the linear map:

⟦Zm,nα⟧=∣0⟩⊗n⟨0∣⊗m+eiα∣1⟩⊗n⟨1∣⊗m\llbracket Z^\alpha_{m,n} \rrbracket = |0\rangle^{\otimes n} \langle 0|^{\otimes m} + e^{i\alpha} |1\rangle^{\otimes n} \langle 1|^{\otimes m}

This definition is abstract, but the special cases are familiar.

  • Z1,10Z^0_{1,1} (phase 0, one input, one output): ∣0⟩⟨0∣+∣1⟩⟨1∣=I|0\rangle\langle 0| + |1\rangle\langle 1| = I - the identity
  • Z1,1αZ^\alpha_{1,1}: ∣0⟩⟨0∣+eiα∣1⟩⟨1∣=RZ(α)|0\rangle\langle 0| + e^{i\alpha}|1\rangle\langle 1| = R_Z(\alpha) - a Z-rotation
  • Z1,20Z^0_{1,2}: ∣00⟩⟨0∣+∣11⟩⟨1∣|00\rangle\langle 0| + |11\rangle\langle 1| - copies the computational basis (like a CNOT’s action on the control)

X-spiders are analogous but work in the X-basis (∣+⟩|+\rangle, ∣−⟩|-\rangle):

⟦Xm,nα⟧=∣+⟩⊗n⟨+∣⊗m+eiα∣−⟩⊗n⟨−∣⊗m\llbracket X^\alpha_{m,n} \rrbracket = |{+}\rangle^{\otimes n} \langle {+}|^{\otimes m} + e^{i\alpha} |{-}\rangle^{\otimes n} \langle {-}|^{\otimes m}

Composition: Tensor Products and Contraction

Placing diagrams side by side is the tensor product. Connecting an output of one spider to an input of another contracts the corresponding indices - just like matrix multiplication or tensor network contraction.

This means a ZX diagram is essentially a tensor network with a specific structure. Evaluation is contraction. Equivalence is equality of the resulting tensor up to a global phase, which we ignore because it doesn’t affect measurement outcomes.

Circuits Inside ZX

Standard gates translate directly into ZX:

  • RZ(α)R_Z(\alpha): A Z-spider with phase α\alpha and arity (1,1)(1,1)
  • RX(α)R_X(\alpha): An X-spider with phase α\alpha and arity (1,1)(1,1)
  • Hadamard: A special “H” node (or represented by an edge with an H marker)
  • CNOT: A Z-spider (arity 1,2) connected to an X-spider (arity 2,1)

The CNOT decomposition is worth seeing explicitly. A CNOT with control cc and target tt becomes:

c ─●─     becomes     c ──Z──●──
   │                         │
t ─⊕─                 t ──●──X──

The Z-spider has one input and two outputs (the control wire splits), and the X-spider has two inputs and one output (the target wire joins and exits).

The Rewrite Rules

ZX derives its power from rewrite rules - local graph transformations that provably preserve the represented linear map. Apply them repeatedly, and you can simplify diagrams without ever computing matrices.

Rule 1: Spider Fusion

Statement: Two spiders of the same color connected by one or more wires fuse into a single spider. Their phases add (mod 2π2\pi).

Before:

───Z^α───Z^β───

After:

───Z^(α+β)───

This works regardless of how many wires connect them or what other connections exist.

Proof sketch: Consider the simplest case - two Z-spiders in sequence:

Z1,1β∘Z1,1α=(∣0⟩⟨0∣+eiβ∣1⟩⟨1∣)(∣0⟩⟨0∣+eiα∣1⟩⟨1∣)Z^\beta_{1,1} \circ Z^\alpha_{1,1} = (|0\rangle\langle 0| + e^{i\beta}|1\rangle\langle 1|)(|0\rangle\langle 0| + e^{i\alpha}|1\rangle\langle 1|)

Since ⟨0∣0⟩=1\langle 0|0\rangle = 1, ⟨1∣1⟩=1\langle 1|1\rangle = 1, and ⟨0∣1⟩=0\langle 0|1\rangle = 0:

=∣0⟩⟨0∣+ei(α+β)∣1⟩⟨1∣=Z1,1α+β= |0\rangle\langle 0| + e^{i(\alpha + \beta)}|1\rangle\langle 1| = Z^{\alpha+\beta}_{1,1}

The general case follows from the tensor structure. When you contract the shared indices between same-color spiders, only matching basis elements survive (both ∣0⟩|0\rangle or both ∣1⟩|1\rangle). The phases multiply, which means the exponents add.

Why it optimizes: Fusion collapses chains of rotations. Two RZR_Z gates on the same qubit become one, even if the diagram picked them up from distant parts of the original circuit.

Rule 2: Identity Removal

Statement: A spider with phase 00 and exactly two wires (one input, one output) is the identity. Remove it and directly connect its neighbors.

Before:

───a───Z^0───b───

After:

───a───b───

Proof: Direct calculation:

Z1,10=∣0⟩⟨0∣+ei⋅0∣1⟩⟨1∣=∣0⟩⟨0∣+∣1⟩⟨1∣=IZ^0_{1,1} = |0\rangle\langle 0| + e^{i \cdot 0}|1\rangle\langle 1| = |0\rangle\langle 0| + |1\rangle\langle 1| = I

Why it optimizes: After fusion and other rewrites, you often end up with phase-zero spiders that contribute nothing to the computation. Removing them cleans up the diagram.

Rule 3: Hadamard Cancellation

Statement: Two Hadamard nodes in sequence cancel to the identity.

Before:

───H───H───

After:

─────────

Proof: H2=IH^2 = I (Hadamard is self-inverse).

Bonus rule - Color Change: Passing a Hadamard through a spider flips its color (Z becomes X, X becomes Z). This reflects the fact that HZH=XHZH = X and HXH=ZHXH = Z.

───H───Z^α───H───  =  ───X^α───

Why it optimizes: When converting circuits to ZX and back, Hadamards can accumulate. Cancellation removes redundant pairs, and color-change enables more fusions between what were originally different-colored spiders.

Python Implementation

With the theory established, here is a working implementation: ZX graphs, the three rewrite rules, and a simplification loop.

Data Structures

from __future__ import annotations
from dataclasses import dataclass
from fractions import Fraction
import math
from typing import Literal

NodeKind = Literal["Z", "X", "H", "B"]  # B = boundary


@dataclass(frozen=True)
class Phase:
    """Phase as rational multiple of pi: value = k * pi"""
    k: Fraction

    def __add__(self, other: Phase) -> Phase:
        return Phase((self.k + other.k) % 2)

    def is_zero(self) -> bool:
        return (self.k % 2) == 0

    def to_radians(self) -> float:
        return float(self.k) * math.pi

    @classmethod
    def from_pi_fraction(cls, num: int, denom: int = 1) -> Phase:
        return cls(Fraction(num, denom))

The Phase class stores angles as rational multiples of π\pi. This avoids floating-point issues and makes “is this phase zero mod 2π2\pi?” a clean integer check.

class ZXGraph:
    """ZX diagram as a multigraph with labeled nodes"""

    def __init__(self):
        self.nodes: dict[int, dict] = {}
        self.edges: list[tuple[int, int]] = []
        self._next_id = 0

    def add_node(self, kind: NodeKind, phase: Phase | None = None) -> int:
        nid = self._next_id
        self._next_id += 1
        self.nodes[nid] = {"kind": kind, "phase": phase}
        return nid

    def add_edge(self, u: int, v: int) -> None:
        self.edges.append((u, v))

    def kind(self, n: int) -> NodeKind:
        return self.nodes[n]["kind"]

    def phase(self, n: int) -> Phase:
        return self.nodes[n]["phase"]

    def set_phase(self, n: int, ph: Phase) -> None:
        self.nodes[n]["phase"] = ph

    def neighbors(self, n: int) -> list[int]:
        """Return neighbors with multiplicity (for multigraph)"""
        result = []
        for u, v in self.edges:
            if u == n:
                result.append(v)
            elif v == n:
                result.append(u)
        return result

    def degree(self, n: int) -> int:
        return len(self.neighbors(n))

    def remove_node(self, n: int) -> None:
        del self.nodes[n]
        self.edges = [(u, v) for u, v in self.edges if u != n and v != n]

    def remove_edge(self, u: int, v: int) -> bool:
        """Remove one edge between u and v, return True if found"""
        for i, (a, b) in enumerate(self.edges):
            if (a, b) == (u, v) or (a, b) == (v, u):
                self.edges.pop(i)
                return True
        return False

    def node_count(self) -> int:
        return len(self.nodes)

This is a minimal multigraph representation. Nodes have a kind (Z, X, H, or B for boundary) and an optional phase. Edges are stored as a list of pairs, allowing multiple edges between the same nodes.

Rewrite Rules

def fuse_spiders(g: ZXGraph) -> bool:
    """Fuse two adjacent same-color spiders, return True if applied"""
    for u, v in list(g.edges):
        if u not in g.nodes or v not in g.nodes:
            continue
        ku, kv = g.kind(u), g.kind(v)
        if ku not in ("Z", "X") or ku != kv:
            continue

        # Fuse v into u: combine phases
        new_phase = g.phase(u) + g.phase(v)
        g.set_phase(u, new_phase)

        # Redirect all of v's edges to u (except u-v edges)
        for a, b in list(g.edges):
            if a == v and b != u:
                g.edges.remove((a, b))
                g.add_edge(u, b)
            elif b == v and a != u:
                g.edges.remove((a, b))
                g.add_edge(a, u)

        # Remove all u-v edges
        g.edges = [(a, b) for a, b in g.edges if not ((a == u and b == v) or (a == v and b == u))]

        g.remove_node(v)
        return True
    return False
def remove_identity(g: ZXGraph) -> bool:
    """Remove phase-0 degree-2 spiders, return True if applied"""
    for n in list(g.nodes.keys()):
        if g.kind(n) not in ("Z", "X"):
            continue
        if not g.phase(n).is_zero():
            continue
        if g.degree(n) != 2:
            continue

        nbrs = g.neighbors(n)
        a, b = nbrs[0], nbrs[1]

        # Remove edges to n, add edge between neighbors
        g.remove_node(n)
        g.add_edge(a, b)
        return True
    return False
def cancel_hadamards(g: ZXGraph) -> bool:
    """Cancel adjacent H-H pairs, return True if applied"""
    for u, v in list(g.edges):
        if u not in g.nodes or v not in g.nodes:
            continue
        if g.kind(u) != "H" or g.kind(v) != "H":
            continue
        if g.degree(u) != 2 or g.degree(v) != 2:
            continue

        # Find the other neighbors
        u_nbrs = [x for x in g.neighbors(u) if x != v]
        v_nbrs = [x for x in g.neighbors(v) if x != u]

        if len(u_nbrs) != 1 or len(v_nbrs) != 1:
            continue

        a, b = u_nbrs[0], v_nbrs[0]

        g.remove_node(u)
        g.remove_node(v)
        g.add_edge(a, b)
        return True
    return False

The Simplification Loop

def simplify(g: ZXGraph, max_steps: int = 10000) -> int:
    """Apply rewrites until fixed point, return number of steps taken"""
    rules = [fuse_spiders, remove_identity, cancel_hadamards]
    steps = 0

    for _ in range(max_steps):
        progress = False
        for rule in rules:
            if rule(g):
                progress = True
                steps += 1
                break
        if not progress:
            return steps

    raise RuntimeError("simplify hit max_steps - possible non-termination")

Verification

To confirm rewrites preserve semantics, we can compute the matrix represented by a diagram before and after simplification. Each spider becomes a tensor, each wire becomes an index contraction, and we compare the resulting matrices up to global phase.

import numpy as np

def z_spider_matrix(phase: float, inputs: int, outputs: int) -> np.ndarray:
    """Build tensor for Z-spider with given phase and arity"""
    shape = [2] * (inputs + outputs)
    tensor = np.zeros(shape, dtype=complex)
    tensor[(0,) * (inputs + outputs)] = 1
    tensor[(1,) * (inputs + outputs)] = np.exp(1j * phase)
    return tensor


def verify_spider_fusion():
    """Verify that fusing two Z-spiders adds their phases"""
    alpha, beta = np.pi / 4, np.pi / 3
    z_alpha = z_spider_matrix(alpha, 1, 1)
    z_beta = z_spider_matrix(beta, 1, 1)
    composed = np.einsum("ij,jk->ik", z_alpha, z_beta)
    fused = z_spider_matrix(alpha + beta, 1, 1)
    assert np.allclose(composed, fused)
    print("Spider fusion verified: phases add correctly")


def verify_identity_removal():
    """Verify that phase-0 degree-2 spider is identity"""
    identity_spider = z_spider_matrix(0, 1, 1)
    assert np.allclose(identity_spider, np.eye(2))
    print("Identity removal verified: Z^0 = I")
verify_spider_fusion()
verify_identity_removal()
Spider fusion verified: phases add correctly
Identity removal verified: Z^0 = I

The proof sketches above correspond directly to these tensor calculations.

Circuit Translation

To make this practical, we need to convert circuits to ZX diagrams and back.

def circuit_to_zx(gates: list[tuple]) -> tuple[ZXGraph, list[int], list[int]]:
    """
    Convert a simple circuit to ZX.

    Gates are tuples: ("RZ", qubit, angle_pi_frac) or ("CNOT", ctrl, tgt) or ("H", qubit)
    Returns (graph, input_boundaries, output_boundaries)
    """
    # Determine qubit count
    qubits_used = set()
    for gate in gates:
        if gate[0] in ("RZ", "RX", "H"):
            qubits_used.add(gate[1])
        elif gate[0] == "CNOT":
            qubits_used.add(gate[1])
            qubits_used.add(gate[2])
    n_qubits = max(qubits_used) + 1

    g = ZXGraph()

    # Create input and output boundaries
    inputs = [g.add_node("B") for _ in range(n_qubits)]
    outputs = [g.add_node("B") for _ in range(n_qubits)]

    # Track current "wire endpoint" for each qubit
    wire_end = list(inputs)

    for gate in gates:
        if gate[0] == "RZ":
            _, q, angle = gate
            node = g.add_node("Z", Phase(Fraction(angle)))
            g.add_edge(wire_end[q], node)
            wire_end[q] = node

        elif gate[0] == "RX":
            _, q, angle = gate
            node = g.add_node("X", Phase(Fraction(angle)))
            g.add_edge(wire_end[q], node)
            wire_end[q] = node

        elif gate[0] == "H":
            _, q = gate
            node = g.add_node("H")
            g.add_edge(wire_end[q], node)
            wire_end[q] = node

        elif gate[0] == "CNOT":
            _, ctrl, tgt = gate
            # CNOT = Z-spider (1 in, 2 out) connected to X-spider (2 in, 1 out)
            z_node = g.add_node("Z", Phase(Fraction(0)))
            x_node = g.add_node("X", Phase(Fraction(0)))

            g.add_edge(wire_end[ctrl], z_node)
            g.add_edge(wire_end[tgt], x_node)
            g.add_edge(z_node, x_node)

            wire_end[ctrl] = z_node
            wire_end[tgt] = x_node

    # Connect to outputs
    for q in range(n_qubits):
        g.add_edge(wire_end[q], outputs[q])

    return g, inputs, outputs

Unintuitive But Correct: Examples

These examples show optimizations that are hard to see at the circuit level.

Example 1: Rotation Accumulation

Circuit: RZ(pi/4) ; RZ(pi/4) ; RZ(pi/4) ; RZ(pi/4)

gates = [
    ("RZ", 0, Fraction(1, 4)),
    ("RZ", 0, Fraction(1, 4)),
    ("RZ", 0, Fraction(1, 4)),
    ("RZ", 0, Fraction(1, 4)),
]
g, ins, outs = circuit_to_zx(gates)
print(f"Before: {g.node_count()} nodes")

simplify(g)
print(f"After: {g.node_count()} nodes")
Before: 6 nodes
After: 3 nodes

Four separate rotations collapse into one Z(π)Z(\pi) - a single ZZ gate.

Example 2: Distant Phase Collapse

Circuit: RZ(pi/4) ; H ; H ; RZ(pi/4)

The Hadamards appear to block the Z rotations from combining. But watch:

gates = [
    ("RZ", 0, Fraction(1, 4)),
    ("H", 0),
    ("H", 0),
    ("RZ", 0, Fraction(1, 4)),
]
g, ins, outs = circuit_to_zx(gates)
print(f"Before: {g.node_count()} nodes")

steps = simplify(g)
print(f"After: {g.node_count()} nodes, {steps} rewrite steps")
Before: 6 nodes
After: 3 nodes, 3 rewrite steps

First the H-H pair cancels (1 step), then the two Z-spiders become adjacent and fuse (2 more steps). The circuit RZ(pi/4) ; H ; H ; RZ(pi/4) simplifies to just RZ(pi/2).

Example 3: CNOT + Phase Commutation

A Z-rotation commutes through the control of a CNOT. Circuit notation requires verifying this identity manually, but ZX spider fusion handles it automatically:

gates = [
    ("RZ", 0, Fraction(1, 2)),  # Z(pi/2) on qubit 0
    ("CNOT", 0, 1),              # CNOT with control 0, target 1
]
g, ins, outs = circuit_to_zx(gates)

# The Z(pi/2) spider and the CNOT's Z-spider (phase 0) are same color and adjacent
# They'll fuse into a single Z(pi/2) spider

before = g.node_count()
simplify(g)
after = g.node_count()

print(f"Before: {before} nodes, After: {after} nodes")
Before: 6 nodes, After: 5 nodes

The rotation has been absorbed into the CNOT’s Z-spider. When you extract a circuit, the phase may appear on a different gate or may have “teleported” through the entangling operation.

Beyond Greedy: The Search Problem

ZX rewriting isn’t confluent - the order you apply rules affects the final result. Some sequences lead to dead ends; others find deep simplifications. For our three rules, greedy application typically finds the optimal result. But with more rules (local complementation, pivoting, bialgebra), the search space becomes complex enough that simulated annealing or beam search provides real benefits.

Research has moved toward learning-based approaches. Reinforcement learning agents trained on graph neural network representations of ZX diagrams can outperform hand-crafted heuristics for 2-qubit gate reduction (Nägele et al., 2023). The rewrite system formulation makes this natural: states are diagrams, actions are rewrite applications, rewards are cost reductions.

What ZX Can and Can’t Do

Soundness vs completeness. Our rewrite rules are sound - they preserve the linear map. But they’re not complete - there exist equivalent diagrams our rules can’t transform into each other. The full ZX-calculus has been proven complete for stabilizer quantum mechanics, and completeness for the universal Clifford+T gate set was established by Jeandel, Perdrix, and Vilmart (2018). Our three-rule subset is much weaker.

Extraction isn’t always easy. This post did not address circuit extraction in detail - turning a simplified ZX diagram back into gates. For arbitrary diagrams, this can be #P-hard. Practical tools like PyZX use restricted diagram families (like “graph-like” diagrams with gflow) where extraction is efficient.

This implementation is intentionally minimal. Real ZX optimizers like PyZX include many more rules: local complementation, pivoting, phase gadget simplification, and T-count reduction via phase teleportation. The T-count reductions alone - crucial for fault-tolerant quantum computing - have shown order-of-magnitude improvements on benchmark circuits.

Conclusion

  1. Circuits are rigid; ZX diagrams are flexible. By converting circuits to graph-like diagrams, we unlock manipulation strategies that are invisible at the gate level.

  2. Optimization = rewriting. Spider fusion, identity removal, and Hadamard cancellation are simple pattern-matching rules, but they compose to find non-obvious simplifications.

  3. Soundness is provable. Each rewrite rule has a straightforward proof via matrix/tensor calculation. The system is trustworthy.

  4. Extraction is the bottleneck. The hard part isn’t simplifying the diagram - it’s getting an efficient circuit back out. This is where practical tools demonstrate their value.

  5. Search over rewrites is an active research area. As rule sets grow, choosing good rewrite sequences becomes a learning/search problem. RL and GNN approaches show promise.

Further Reading

References