arXiv preprint ·
On the Complexity of Level-Synchronized Tree Automata for Quantum Circuit Verification
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Reward Objectives for Robust (PO)MDPs: A Law-Preserving Equivalence with (Partially Observable) Games
At the Limits of Computability: Steps Towards Autonomous AI Discovery on the Busy Beaver Frontier
Runtime Semantic Discovery for Evolving Action Alphabets
Jumbled Simon's Equivalence and Embeddings
Relational Composition as Parallel Transport: What Per-Entity Frames Force in Attention
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.