On the Complexity of Level-Synchronized Tree Automata for Quantum Circuit Verification
Diese Arbeit analysiert die Komplexität und die Repräsentationsgröße von level-synchronisierten Baumautomaten für die Verifizierung von Quantenschaltkreisen, wobei sie NP-vollständige und EXPSPACE-vollständige Schranken für zentrale Entscheidungsprobleme etabliert, während sie gleichzeitig ein inhärentes quadratisches Wachstum unter Gatteroperationen nachweist und eine Umordnungs-Konstruktion zur Aufrechterhaltung der Synchronisation vorschlägt.