⚛️ quantum physics

On the Complexity of Level-Synchronized Tree Automata for Quantum Circuit Verification

This paper analyzes the computational complexity and representation size of level-synchronized tree automata for quantum circuit verification, establishing NP-complete and EXPSPACE-complete bounds for key decision problems while demonstrating inherent quadratic growth under gate operations and proposing a reordering construction to maintain synchronization.

Original authors: Michael Blondin, Samy Chady Khoumsi-Kasmi, Guillermo A. Pérez, Marnix Suilen

Published 2026-10-20

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Michael Blondin, Samy Chady Khoumsi-Kasmi, Guillermo A. Pérez, Marnix Suilen

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

Verifying that a quantum computer will do what we ask of it is a problem of immense scale. Unlike a classical computer, which processes information as a simple sequence of zeros and ones, a quantum machine operates on a vast landscape of possibilities simultaneously. A system with just a few dozen particles can exist in a number of states that exceeds the total number of atoms in the observable universe. To check if a quantum circuit works correctly, researchers must navigate this landscape without getting lost in the sheer volume of data. They need a way to represent these complex states compactly, to track how they change when a gate is applied, and to prove that the final result matches the intended outcome. For years, a mathematical tool called a level-synchronized tree automaton has offered a promising path. These structures act like a compressed map of the quantum state, grouping together identical branches of possibilities to save space, while carefully coordinating choices across different parts of the map to ensure the rules of quantum mechanics are followed.

A team of researchers has now rigorously tested the limits of this tool, asking two fundamental questions: how hard is it to use these maps to verify a circuit, and how much do these maps grow when the circuit performs a calculation? Their work reveals that while these automata are powerful, they come with strict boundaries. The researchers proved that checking whether a set of quantum states is empty is a difficult problem, one that belongs to a class of challenges known to be computationally heavy. Furthermore, they showed that comparing two different sets of states to see if one is contained within the other is even harder, requiring resources that grow exponentially with the size of the problem. This means that for certain types of verification tasks, the time required to solve the problem could become unmanageable as the quantum system gets larger.

The study also uncovered a surprising sensitivity to the order in which the quantum particles are arranged. In a quantum circuit, the particles are often treated as a fixed sequence, much like beads on a string. The researchers demonstrated that applying a specific type of quantum gate to a state can cause the size of the representation to explode, growing from a manageable linear size to a quadratic one, simply because of the gate's position relative to the particles it affects. If a gate acts on a particle that comes later in the sequence than the particle controlling it, the mathematical map must remember every possible combination of the two, forcing the representation to swell dramatically. This finding suggests that the efficiency of verification is not just about the gates themselves, but critically depends on how the particles are ordered before the calculation begins.

However, the paper does not leave the field in a state of impasse. The authors provided a method to rearrange the particles, swapping neighbors in the sequence to place controlling particles before the ones they affect. They showed that this reordering can be done efficiently, in a time that scales linearly with the size of the current map. This offers a practical strategy: a verifier could apply a block of gates, check if the representation is growing too large, and then swap the order of particles to reset the growth before continuing. By combining these efficient swaps with blocks of gates that are known to keep the representation small, it may be possible to verify complex quantum circuits without hitting the exponential wall. The work clarifies that while the automata-theoretic approach has inherent limits, those limits are well-defined, and with careful management of the particle order, the tool remains a viable and powerful ally in the quest to build reliable quantum computers.

Technical Summary: On the Complexity of Level-Synchronized Tree Automata for Quantum Circuit Verification

Problem Statement
Reliable quantum computation necessitates rigorous methods for verifying quantum circuits. Verification involves reasoning about the sets of quantum states a circuit can produce from allowed inputs. Since an $n$ -qubit state comprises $2^n$ amplitudes, and specifications often describe sets of states rather than single vectors, efficient symbolic representation is critical. Level-synchronized tree automata (LSTAs) were recently introduced to represent such sets by sharing subtrees and coordinating choices across tree levels, addressing the exponential cost of representing dependencies between distant branches found in ordinary tree automata.

Despite the utility of LSTAs in tools like AutoQ, the theoretical limits of their applicability remain under-explored. Specifically, the complexity of fundamental decision problems (nonemptiness and language inclusion) for LSTAs, and the inherent growth of representation size when applying quantum gates, require formal characterization. This paper addresses these gaps to clarify the scope of the automata-theoretic toolbox for quantum circuit verification.

Methodology
The authors analyze LSTAs through two primary axes:

Complexity Analysis: They investigate the computational complexity of the nonemptiness and language inclusion problems for both acyclic LSTAs (sufficient for fixed-qubit applications) and general LSTAs.
Representation Growth: They study the size of LSTA representations under quantum gate operations. This involves counting distinct "residuals" (subtrees) at specific tree depths to establish lower bounds on state requirements. They also propose a construction for reordering adjacent qubits to mitigate representation growth.

The analysis relies on reductions from known hard problems (e.g., 3-SAT, $\forall\exists$ -SAT, and trace inclusion for 1-safe Petri nets) and combinatorial arguments regarding the number of distinct subtrees required to represent specific quantum states.

Key Contributions and Results

1. Complexity of Decision Problems
The paper settles the complexity of key decision problems for LSTAs, distinguishing between acyclic and general cases:

Acyclic LSTAs:
- Nonemptiness: Proven to be NP-complete (Theorem 6). This contrasts with general LSTAs, where nonemptiness is PSPACE-complete.
- Language Inclusion: Proven to be $\Pi^P_2$ -complete (Theorem 11). This hardness holds even with a single initial state and a fixed ranked alphabet.
General LSTAs:
- Language Inclusion: Proven to be EXPSPACE-complete (Theorem 12). This result closes a gap in previous work, matching the known EXPSPACE upper bound and establishing hardness even with one initial state and singleton choice sets.

2. Inherent Representation Growth
The authors establish lower bounds on the size of LSTA representations when applying specific quantum gates in a fixed qubit order:

Quadratic Growth: They demonstrate that applying a Hadamard gate or a controlled-NOT (CX) gate (where the control follows the target in the qubit order) to a specific input state forces any accepting LSTA to have a number of states quadratic in the input size.
- For the Hadamard gate, the number of distinct residuals grows from $O(m)$ to $\Omega(m^2)$ (Proposition 15).
- For the backward CX gate, the number of distinct residuals grows to $m^2$ (Proposition 16).
- This result extends to controlled- $U$ gates for any fixed non-diagonal one-qubit unitary $U$ (Corollary 17).
Optimal Construction: While the lower bound is quadratic, the authors show that a singleton LSTA representing the output tree can be constructed with size $O(m^2)$ , confirming that the quadratic growth is inherent but not super-quadratic for these specific cases.

3. Qubit Reordering
To mitigate the sensitivity of representation size to qubit ordering (a phenomenon known from Binary Decision Diagrams), the paper provides an efficient construction for swapping adjacent qubits in a layered LSTA (Proposition 18).

The construction takes linear time relative to the automaton size for a fixed number of available choices.
This operation preserves level synchronization, allowing verifiers to dynamically reorder qubits to place control bits before their targets, potentially reducing representation growth.

Significance and Claims
The paper claims to clarify the theoretical boundaries of using LSTAs for quantum circuit verification. By establishing that language inclusion for general LSTAs is EXPSPACE-complete, it highlights the intrinsic difficulty of verifying unbounded or cyclic structures. Furthermore, the proof of inherent quadratic representation growth under specific gate applications underscores the importance of careful qubit ordering and transformation sequences.

The authors argue that these results motivate a verification strategy that combines:

Application of circuit blocks with "controlled representation growth" (e.g., monomial gates or gates where control precedes target).
Dynamic reordering of qubits using the efficient adjacent-swap construction to optimize the order before processing subsequent blocks.
The use of adjoints (conjugate transposes) to process postconditions backward, offering alternative intermediate representations.

The work does not propose new experimental applications but rather provides the theoretical justification for the heuristics and optimizations employed in tools like AutoQ, ensuring that the automata-theoretic approach remains viable within known complexity constraints.

More like this