{"id":"arxiv/2610.25138","url":"https://arxiv.org/abs/2610.25138","tags":["quant-ph","cs.FL"],"score":0,"title":"On the Complexity of Level-Synchronized Tree Automata for Quantum Circuit Verification","domain":"quant-ph","source":"arxiv","authors":["Michael Blondin","Samy Chady Khoumsi-Kasmi","Guillermo A. Pérez","Marnix Suilen"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-18","reactions":{}}