💻 computer science

Quantum Term Rewrite Systems: Applications to Complexity Analysis

This paper introduces Quantum Term Rewrite Systems (QTRS) as a physically realizable extension of classical Term Rewrite Systems that enables complexity analysis and characterizes the class of functions computable in quantum polynomial time ( $\mathtt{FBQP}$ ) by establishing a correspondence between terminating QTRS and uniform families of quantum circuits.

Original authors: Kostia Chardonnet, Emmanuel Hainry, Romain Péchoux, Thomas Vinet

Published 2026-07-23

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Kostia Chardonnet, Emmanuel Hainry, Romain Péchoux, Thomas Vinet

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 a world where computers don't just crunch numbers one by one, but dance through a fog of possibilities, exploring many paths at once. This is the realm of quantum computing, a field that promises to solve problems currently impossible for our standard machines. But here's the catch: while quantum computers are incredibly powerful, they are also notoriously fragile and hard to control. It's like trying to conduct an orchestra where the musicians can be in two places at once; if you don't know exactly how the music will end up, you might accidentally create a screeching noise instead of a symphony.

To keep these digital symphonies in tune, scientists use "Term Rewrite Systems" (TRS). Think of TRS as a set of strict, step-by-step instructions for simplifying complex expressions, like a recipe that tells you exactly how to turn a pile of ingredients into a finished dish. In the classical world, these recipes are great for proving that a program will eventually stop (termination) and for guessing how long it will take (complexity). But when you try to apply these old-school recipes to the quantum world, they break down because they can't handle the "superposition" (being in multiple states at once) or the strict rules of physics that govern quantum particles.

This is where the story of "Quantum Term Rewrite Systems" (QTRS) begins. The researchers in this paper asked a big question: Can we create a new kind of recipe book that works for quantum computers, one that not only handles the weirdness of superposition but also lets us prove, with mathematical certainty, that the program will finish and how much "quantum fuel" (resources) it will need? They didn't just guess; they built a rigorous framework to answer this, bridging the gap between abstract math and the physical reality of quantum circuits.

The Quantum Recipe Book

The authors, Kostia Chardonnet, Emmanuel Hainry, Romain Péchoux, and Thomas Vinet, have introduced a new computational model called Quantum Term Rewrite Systems (QTRS). You can think of this as a magical instruction manual for quantum computers. In a normal computer, a program is like a train moving on a single track: it goes from point A to point B, step by step. In a quantum computer, the program is more like a swarm of bees; it can explore many different paths simultaneously.

The paper's main achievement is showing how to write these "swarm" instructions in a way that is both physically realizable (it obeys the laws of physics) and analyzable (we can mathematically prove how long it will take).

The Rules of the Game

To make this work, the authors had to invent a new set of rules. In their system, a "term" (a piece of data) isn't just a single value; it can be a superposition, which is like a weighted sum of different possibilities. For example, instead of a coin being just "Heads" or "Tails," a quantum term can be "0.7 Heads + 0.7 Tails" (with the numbers adjusted so the total probability is 1).

The paper establishes that these systems have a "type system," which acts like a quality control inspector. This inspector checks two vital things:

Physicality: Does the program respect the laws of quantum mechanics? For instance, it ensures that the total probability of all outcomes always adds up to 1 (you can't create or destroy probability out of thin air).
Structure: Does the program keep the "shape" of the data consistent? If you start with a list of 3 qubits, you shouldn't end up with a list of 5 qubits unless you explicitly added them.

The Good News and the Bad News

The researchers found some exciting possibilities, but also hit a few hard walls.

The Good News:
They proved that for a specific, well-behaved class of these quantum programs, you can automatically translate them into quantum circuits. A quantum circuit is the actual blueprint of gates and wires that a quantum computer would use.

The Magic Link: They showed a direct connection between the "runtime" of their rewrite system (how many steps the rules take to simplify the expression) and the size of the resulting quantum circuit. If the rewrite system finishes quickly, the circuit is small. If it takes a long time, the circuit is big.
The Ultimate Characterization: Most importantly, they showed that this specific class of QTRS captures exactly the set of functions that can be computed in quantum polynomial time (a complexity class known as FBQP). In plain English: if a problem can be solved efficiently on a quantum computer, there is a QTRS recipe for it, and vice versa.

The Bad News (and the Limits):
The paper is very careful about what it doesn't claim.

Type Inference is Hard: They proved that automatically figuring out if a random, complex quantum program is "well-typed" (physically valid) is undecidable in the general case. This means there is no universal algorithm that can look at any quantum program and tell you if it's valid. It's like trying to write a program that can predict if any other program will ever stop running; mathematically, it's impossible to do perfectly for every case.
However: They found a "sweet spot." If you restrict the programs to a certain expressive subset (which still covers most useful things), type inference becomes decidable and can be done very quickly (in polynomial time).

How They Did It: The "Worst Path" Trick

One of the most clever parts of the paper is how they handle complexity. In classical computing, to prove a program is fast, you might look at the longest path it takes. In quantum computing, because the program splits into many paths at once, the authors introduced a concept called "Worst Path Ordering."

Imagine you are sending a message through a network of tunnels. In a classical world, you send one messenger. In a quantum world, you send a cloud of messengers, and they all take different tunnels. To know how long the message takes, you don't care about the fastest tunnel; you care about the slowest one, because the message isn't "done" until the last messenger arrives. The authors adapted standard mathematical tools (like polynomial interpretations and dependency pairs) to always look at this "worst path." This allows them to use existing techniques from classical computer science to prove that quantum programs will terminate and to estimate their resource usage.

The Verdict

The paper doesn't just suggest these ideas; it provides mathematical proofs. They didn't just simulate a few examples on a computer; they built a formal theory that guarantees these properties hold.

They demonstrated that:

QTRS are universal: They can express any quantum circuit.
Compilation is possible: You can turn a QTRS into a circuit family.
Complexity is bounded: For programs that finish in polynomial time, the resulting circuits are also polynomial in size.
The class FBQP is characterized: The set of functions computable by these systems is exactly the set of functions computable in quantum polynomial time.

In short, the authors have handed us a new, rigorous language for quantum programming. It's a language that doesn't just let us write quantum code; it lets us prove that the code is safe, will finish, and won't require more resources than a quantum computer can physically provide. While we can't automatically check every single possible quantum program, for the vast majority of useful ones, we now have a powerful toolkit to certify their efficiency and correctness.

Technical Summary: Quantum Term Rewrite Systems: Applications to Complexity Analysis

Problem Statement

The emergence of quantum computation offers a paradigm where specific problems can be solved more efficiently than with classical counterparts. While various computational models exist (e.g., quantum circuits, ZX-calculus), the development of higher-level models, particularly quantum programming languages featuring quantum control (where control flow depends on quantum data), has created a need for rigorous static analysis.

Existing approaches to resource analysis in quantum computing face two primary limitations:

Hardware Specificity: Many analyses are tied to specific hardware constraints or low-level gate sets, making generic resource analysis difficult.
Lack of Generality: Implicit Computational Complexity (ICC) languages that characterize complexity classes (e.g., polynomial time) often rely on specific typing or syntactic restrictions tailored to a single class, rendering them unsuitable for generic complexity analysis or for reusing established termination techniques.

Conversely, classical Term Rewrite Systems (TRS) provide a robust, abstract model with numerous generic techniques for analyzing termination and runtime complexity (e.g., polynomial interpretations, dependency pairs). However, an extension of TRS to the quantum setting that preserves these analytical benefits while ensuring physical realizability (unitarity, norm preservation) has been missing.

Methodology

The paper introduces Quantum Term Rewrite Systems (QTRS), an extension of standard TRS designed to model quantum computation with superposition and quantum control. The methodology involves three core components:

1. Syntax and Semantics (STRS)

The authors first define Superposed Term Rewrite Systems (STRS).

Syntax: Terms are extended to include superpositions ( $+$ ) and amplitude multiplication ( $\alpha \cdot$ ). Amplitudes are drawn from a signature allowing for complex scalars.
Semantics: The reduction strategy mimics quantum parallelism via a call-by-basis strategy. Reductions occur on canonical forms (superpositions of distinct classical terms with non-zero amplitudes). The system utilizes an equivalence relation ( $\equiv$ ) based on vector space axioms (linearity, associativity, commutativity) to handle amplitudes semantically.
Parallelism: The reduction relation $\to_R$ reduces all components of a superposition simultaneously if they are in a canonical form, ensuring the system captures quantum parallelism rather than classical simulation (which would require $2^n$ steps for $n$ qubits).

2. Type System for Physicality

To ensure STRS correspond to physically realizable quantum processes, a type system is imposed to define QTRS.

Linearity and Norm: The type system distinguishes between classical and quantum types. It enforces that superpositions represent normalized vectors (sum of squared moduli of amplitudes equals 1) and that terms in a superposition are orthogonal.
Isometry: Function symbols must act as isometries, preserving orthogonality between inputs.
Decidability: The authors prove that general type inference is $\Pi^0_2$ -hard (undecidable) due to the need to check orthogonality over all possible substitutions. However, they identify an "easily typed" fragment where type inference is decidable in polynomial time, provided the system is terminating.

3. Complexity Analysis and Compilation

The paper adapts standard TRS termination and complexity techniques to the QTRS setting:

Worst Path Orderings: To handle superpositions, the authors define a "worst path" extension of classical orders. This order takes the maximum reduction path among the components of a superposition, allowing standard well-founded orders to prove termination for QTRS.
Adapted Techniques: They demonstrate that Polynomial Interpretations and Dependency Pairs can be adapted to QTRS using these worst path orderings.
Compilation to Circuits: A specific fragment, QTRSCirc, is defined. It restricts constructors to standard quantum data types and requires function symbols to be "structure-preserving" (outputting values with the same classical shape regardless of input) and either encoding a unitary or "quantum controlling" (acting as controlled statements).
- Universality: QTRSCirc is shown to be universal for quantum circuits.
- Compilation: Any terminating QTRS in this fragment can be compiled into a uniform family of quantum circuits.
- Complexity Bound: For "simply recursive" QTRS, the size of the compiled circuit is bounded by the runtime complexity of the rewrite system.

Key Contributions and Results

Formal Definition of QTRS: The introduction of QTRS as a typed extension of TRS that achieves quantum parallelism and ensures physicality through a type system enforcing normalization and orthogonality.
Standard Properties: Proof of standard properties for QTRS, including confluence (up to equivalence), subject reduction (typing is preserved under reduction for terminating terms), and the uniqueness of canonical forms.
Type Inference Complexity:
- General type inference is proven $\Pi^0_2$ -hard (Theorem 15).
- A polynomial-time decidable fragment ("easy type inference") is identified for terminating systems with arity-0 amplitude symbols (Theorem 16).
Universality and Compilation:
- Theorem 21: QTRSCirc is universal for uniform families of quantum circuits.
- Theorem 22: Any terminating QTRS in QTRSCirc can be compiled into a family of quantum circuits that approximates the system's output with probability $2/3$ .
- Theorem 25: For simply recursive QTRS, the circuit size is bounded by $O(\tau(|v|)^{rk(f)+1})$ , where $\tau$ is the runtime complexity and $rk(f)$ is the rank of the function symbol.
Characterization of FBQP:
- Theorem 27: The class of binary functions computable by QTRS in QTRS(Poly) (polynomial-time terminating QTRS on lists of qubits) is exactly FBQP (functions computable in quantum polynomial time).
Adaptation of Termination Techniques:
- Theorem 32: Monotonic polynomial interpretations guarantee termination for STRS.
- Theorem 37: Dependency pairs can be adapted to prove termination for QTRS.
- Theorem 41: Additive assignments provide a decidable criterion for polynomial-time termination, enabling the verification of whether a QTRS computes a function in FBQP.

Significance

The paper claims to fill a critical gap in the theoretical foundations of quantum programming by providing a generic, high-level model (QTRS) that bridges the gap between abstract quantum algorithms and low-level circuit complexity.

Reuse of Classical Techniques: The primary significance lies in the ability to reuse the extensive toolkit of classical TRS analysis (termination and complexity proofs) for quantum systems. This avoids the need to develop entirely new, ad-hoc analysis tools for every new quantum language.
Quantum Control: Unlike previous resource-aware languages that often restricted control to classical data, QTRS natively supports quantum control, allowing for the analysis of superpositions of programs.
Implicit Complexity: The work provides a precise characterization of FBQP using a rewrite-based formalism, offering a syntactic and structural way to understand the limits of quantum polynomial time without relying solely on circuit families.
Physical Soundness: By integrating a type system that enforces physical constraints (norm preservation, orthogonality), the model ensures that the analyzed programs are not just computationally valid but also physically realizable.

In summary, the paper establishes QTRS as a robust computational model that unifies the expressiveness of quantum control with the analytical power of term rewriting, enabling the certification of termination and complexity for a broad class of quantum programs.