Complexity limits level synchronized automata for quantum circuits
On the Complexity of Level-Synchronized Tree Automata for Quantum Circuit Verification
Formal Languages and Automata Theory
Summary
Verifying that quantum circuits work correctly is important but complicated. The authors study a special kind of mathematical tool called level-synchronized tree automata (LSTAs), which can represent sets of quantum states for this purpose. They found that key questions about these automata can be very hard to answer and that these automata often grow much larger after certain quantum operations. Their work helps clarify when and how these automata can be practically used for checking quantum circuits.
What this means in practice
- •For quantum software developers: Guide design of verification tools by understanding computational limits and representation growth of automata for quantum state sets.
- •For quantum hardware testers: Help identify which verification methods may be practical given the complexity constraints of automata representing circuit states.
A theory result. No direct application yet.
Authors
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.