Skip to content
DraconiticResearch
Search Sources API
194,216 studies31 sourcesUpdated 27 min ago
PreprintCC BY 4.0arXiv

On the Complexity of Level-Synchronized Tree Automata for Quantum Circuit Verification

  • Michael Blondin
  • Samy Chady Khoumsi-Kasmi
  • Guillermo A. Pérez
  • Marnix Suilen
Open at sourcePDFDOICite

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 Π2P-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.

Related

  1. Sustained growth of quantum circuit complexity in many-body Hamiltonian dynamics
    Wonjun Lee, Saúl Pilatowsky-Cameo, Soonwon Choi
    arXivPreprintarXiv licenceFull textMathematical physicsQuantum physics & quantum informationarXiv
  2. Local Optimality Does Not Compose: Invariant Simplices and the Complexity of Shared Probabilistic Automata
    Yixin Zhao
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  3. Verification Complexity and Extension of Classical Shadows
    Georgios Karaiskos, Asad Raza, Dorian Rudolph +2
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  4. Circuit Complexity of Scalar and Tensor Perturbations in Luminal Einstein--Gauss--Bonnet Inflation
    Tao Li, Hai-Bing Fu, Lei-Hua Liu
    arXivPreprintCC BY 4.0Full textGravitation & general relativityHigh-energy & particle physicsarXiv
  5. Circuit complexity of coupled four-mode squeezed states in two-field inflation
    Tao Li, Hai-Bing Fu, Lei-Hua Liu
    arXivPreprintCC BY 4.0Full textGravitation & general relativityHigh-energy & particle physicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{blondin2026complexity,
  title = {{On the Complexity of Level-Synchronized Tree Automata for Quantum Circuit Verification}},
  author = {Michael Blondin and Samy Chady Khoumsi-Kasmi and Guillermo A. Pérez and Marnix Suilen},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.25138},
  eprint = {2610.25138},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.25138},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - On the Complexity of Level-Synchronized Tree Automata for Quantum Circuit Verification
AU  - Michael Blondin
AU  - Samy Chady Khoumsi-Kasmi
AU  - Guillermo A. Pérez
AU  - Marnix Suilen
PY  - 2026
DA  - 2026/10/18
PB  - arXiv
DO  - 10.48550/arxiv.2610.25138
UR  - https://arxiv.org/abs/2610.25138
AB  - 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.
ER  -