analiza aiqbench
This research establishes fundamental complexity bounds for Level-Synchronized Tree Automata, demonstrating that language inclusion is EXPSPACE-complete and revealing inherent quadratic growth in representation size under standard quantum gates. These findings critically define the theoretical limits of automata-theoretic methods for verifying quantum circuits, indicating where such approaches remain tractable versus where they face insurmountable computational barriers.
On the Complexity of Level-Synchronized Tree Automata for Quantum Circuit Verification
arXiv:2610.25138v1 Announce Type: new 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 $\Pi_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.
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 $\Pi_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.
Quantum Physics (quant-ph); Formal Languages and Automata Theory (cs.FL)
arXiv:2610.25138 [quant-ph]
(or arXiv:2610.25138v1 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2610.25138 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 207 cuvinte