💻 computer science

Towards Term-based Verification of Diagrammatic Equivalence

This paper establishes a foundation for automated reasoning about diagrammatic equivalence by introducing normalizing term rewriting systems for two classes of diagrams and proving their termination and confluence using Isabelle/HOL.

Original authors: Julie Cailler, Noé Delorme, Simon Perdrix, Sophie Tourret

Published 2026-02-12

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Julie Cailler, Noé Delorme, Simon Perdrix, Sophie Tourret

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing with a set of high-tech, modular building blocks. These blocks represent complex processes—like the logic inside a quantum computer or the way a sentence is structured in linguistics.

The challenge is this: You can build the exact same structure using different sequences of blocks.

For example, you could snap a red block onto a blue block, then add a green one. Or, you could snap the green one onto the blue one first, then add the red one. Even though your "instruction manual" (the code) looks different, the final "machine" (the diagram) works exactly the same way.

In the world of computer science, this is called Diagrammatic Equivalence. If we want computers to design better quantum circuits, we need a way for them to look at two different sets of instructions and say, "Hey, these are actually the same thing!"

The Problem: The "Messy Manual"

Right now, checking if two complex diagrams are the same is like trying to prove two different recipes make the same cake just by looking at the lists of ingredients. It’s messy, prone to error, and very hard for a computer to do quickly.

The Solution: The "Universal Sorting Machine"

The researchers in this paper have designed a mathematical "Sorting Machine" (technically called a Term Rewriting System).

Instead of comparing two messy manuals side-by-side, their system takes any manual and follows a strict set of rules to "flatten" or "standardize" it. Think of it like this:

The Input: A messy, tangled instruction manual for a diagram.
The Process: The machine follows a set of "rewrite rules" (like: "If you see a block floating by itself, snap it to the next one" or "If two blocks are in the wrong order, swap them").
The Output: A Normal Form—a perfectly organized, standardized version of that manual.

The Magic Trick: If two different manuals are actually describing the same diagram, the Sorting Machine will turn them both into the exact same standardized manual. If the final manuals match, the diagrams are identical.

How They Proved It Works

The researchers didn't just say, "Trust us, it works." They used a high-level mathematical "referee" called Isabelle/HOL (a proof assistant) to verify their logic. They proved two critical things:

Termination: The machine won't get stuck in an infinite loop. It will always finish sorting.
Confluence: No matter which rule you apply first, you will always end up at the same final destination. There are no "wrong turns" that lead to a different result.

Why Does This Matter?

The ultimate goal is Quantum Computing. Quantum circuits are incredibly sensitive and complex. To build them, we need to optimize them—stripping away redundant steps to make them faster and more reliable.

By providing a mathematically "certified" way to check if two circuits are the same, these researchers have laid the foundation for a future where computers can automatically design, verify, and perfect the quantum machines of tomorrow.

Technical Summary: Towards Term-based Verification of Diagrammatic Equivalence

1. Problem Statement

Diagrammatic reasoning is a powerful tool used in quantum computing, linear algebra, and natural language processing to represent computations as two-dimensional graphical structures (string diagrams). A central challenge in automating this reasoning is equivalence checking: determining whether two different syntactic representations (terms) describe the same underlying diagram.

In mathematical terms, diagrams are represented using PROs (Product and Permutation categories without symmetry) and PROPs (which include symmetry/wire-swapping). Because different sequences of operations (sequential composition $\#$ and parallel composition $\otimes$ ) can result in the same visual diagram, the syntax must be "quotiented" by a set of coherence equations. The goal of this paper is to provide a rigorous, automated, and machine-checkable way to decide if two terms are diagrammatically equivalent.

2. Methodology

The authors adopt a term-based representation rather than a graph-based one. By encoding diagrams as algebraic terms, they can leverage Term Rewriting Systems (TRS). The core strategy involves:

Defining Normal Forms: Establishing a unique "canonical" or "normal" syntactic form for any given diagram.
Developing Rewriting Systems: Creating sets of directed rules that transform any arbitrary term into its corresponding normal form.
Proving Correctness: Using the Isabelle/HOL proof assistant to formally verify that these rewriting systems are:
- Terminating: The rewriting process will always end in a finite number of steps.
- Confluent: No matter the order in which rules are applied, the system will always reach the same unique normal form.

3. Key Contributions

The paper addresses two distinct classes of diagrammatic problems:

A. State-and-Effect-Free PROs

Scope: Diagrams where every generator has at least one input and one output (no "states" or "effects").
Approach: They introduce a "layer-based" normal form where generators are organized into sequential layers, and the order of commuting layers is strictly fixed.
Result: They define a normalizing rewriting system ( $R$ ) and prove its termination and confluence. This allows any two equivalent terms in this class to be reduced to the same normal form.

B. The PRO of Permutations (PROP without generators)

Scope: The simplest PROP, consisting only of wires and swaps (representing permutations).
Approach: They define a canonical form based on "toboggans" ( $\tau_d$ ), which are specific types of wire shifts. They provide an interpretation function that maps terms to mathematical permutations to ensure the canonical form is correct.
Result: They define a canonizing rewriting system ( $R_0$ ) and prove its termination and confluence. This ensures that any term representing a specific permutation can be uniquely reduced to its canonical representation.

4. Results

Formal Verification: Unlike many approaches that rely on heuristic or unverified algorithms, the authors successfully used Isabelle/HOL to verify the most critical steps of their termination and confluence proofs.
Effective Normalization: The paper proves that for both studied classes, the existence of a terminating and confluent TRS implies that diagrammatic equivalence is decidable: $t_1 \equiv t_2$ if and only if $NF(t_1) = NF(t_2)$ .
Complexity Management: By using lexicographical orders of multiple positive quantities (as seen in Figure 3), they successfully managed the proof of termination for complex, conditional rewrite rules.

5. Significance

This work provides the foundational "building blocks" for automated quantum circuit verification. By moving from graphical intuition to verified term-based rewriting, the authors bridge the gap between high-level diagrammatic reasoning and low-level machine-checkable proofs.

The ultimate significance lies in the potential to create a fully verified pipeline for quantum computing: a system where a user can design a quantum circuit diagrammatically, and a computer can automatically and rigorously certify that the circuit is equivalent to an optimized or target version, with mathematical certainty.