arXiv:2610.25138
On the Complexity of Level-Synchronized Tree Automata for Quantum Circuit Verification
Michael Blondin, Samy Chady Khoumsi-Kasmi, Guillermo A. Pérez, Marnix Suilen
Abstract
Reliable quantum computation requires methods for verifying quantum circuits. Level-synchronized tree automata (LSTAs) were recently introduced to represent sets of quantum states for this purpose. We study LSTAs along two axes relevant to verification: the complexity of their decision problems and the size of their representations under circuit operations. We prove that acyclic LSTAs have NP-complete nonemptiness and $Π_2^P$-complete language inclusion, and that general language inclusion is EXPSPACE-complete. We further prove inherent quadratic representation growth under individual quantum gates in a fixed qubit order, and give an adjacent-qubit reordering construction that preserves level synchronization. These results clarify the scope of applicability of the automata-theoretic toolbox for quantum circuit verification.
AI Summary
Level-synchronized tree automata (LSTAs) represent sets of quantum-state amplitude trees, allowing circuit verification by successive gate transformations followed by language inclusion. This paper determines the complexity of these decision problems and studies unavoidable representation growth and qubit reordering. For acyclic LSTAs, which suffice for fixed-qubit state sets, nonemptiness is $\mathrm{NP}$-complete and language inclusion is $\Pi_2^P$-complete. Polynomial certificates specify an initial state and one synchronized choice per level; hardness reductions encode satisfying assignments, hiding existential variables while exposing universal ones. For general, potentially cyclic LSTAs, inclusion is $\mathrm{EXPSPACE}$-complete, closing the previous gap between $\mathrm{PSPACE}$ hardness and an $\mathrm{EXPSPACE}$ upper bound. The new lower bound reduces finite-trace inclusion for labeled 1-safe Petri nets to LSTA inclusion. In a fixed qubit order, a single Hadamard or backward controlled-NOT can transform a singleton representation of size $s$ into a tree requiring $\Omega(s^2)$ states, matching existing quadratic upper bounds. The controlled-gate result extends to every fixed non-diagonal one-qubit unitary. These bounds count distinct residual amplitude functions at a tree cut. An adjacent-qubit reordering construction preserves synchronization and costs $O(|\mathcal A|+|\Delta_i||K|)$, hence linear time for bounded choice count. An appendix formalizes forward-memory width $w$ for supported monomial blocks, giving $O(2^w|\mathcal A|)$ application cost after compilation. Combining blocks, reordering, and evaluation from either circuit end remains an unimplemented scheduling proposal without benchmark evaluation. Optimizing width through circuit rewriting remains open, and the inclusion hardness reduction does not directly transfer to synchronized weighted automata’s functional inclusion.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.