Certifying Quantum Gates via Automata Advantage
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912641163722752 |
|---|---|
| author | Schroeder, Anna Vieira, Lucas B. Nöller, Jan Miklin, Nikolai Gachechiladze, Mariami |
| author_facet | Schroeder, Anna Vieira, Lucas B. Nöller, Jan Miklin, Nikolai Gachechiladze, Mariami |
| contents | There is growing interest in developing rigorous tests of quantumness that are feasible even before practical quantum advantages become a reality. Such tests not only aim to certify the quantum nature of a system but also serve as benchmarks for precise quantum control. In this work, we argue that promise problems, studied in the theory of finite automata, provide a natural framework for designing sound tests of quantum gate quality. Soundness, the property that only implementations of sufficiently high quality can pass the test, is a central requirement for meaningful certification. We study several promise problems relevant to quantum gate testing and establish separations between the memory resources required by quantum and classical finite automata to solve them. These separations form the theoretical basis for using promise problems as tests of quantumness. Finally, we show how results from automata theory, in particular the minimality of automata, can be used to derive soundness guarantees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_09575 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Certifying Quantum Gates via Automata Advantage Schroeder, Anna Vieira, Lucas B. Nöller, Jan Miklin, Nikolai Gachechiladze, Mariami Quantum Physics There is growing interest in developing rigorous tests of quantumness that are feasible even before practical quantum advantages become a reality. Such tests not only aim to certify the quantum nature of a system but also serve as benchmarks for precise quantum control. In this work, we argue that promise problems, studied in the theory of finite automata, provide a natural framework for designing sound tests of quantum gate quality. Soundness, the property that only implementations of sufficiently high quality can pass the test, is a central requirement for meaningful certification. We study several promise problems relevant to quantum gate testing and establish separations between the memory resources required by quantum and classical finite automata to solve them. These separations form the theoretical basis for using promise problems as tests of quantumness. Finally, we show how results from automata theory, in particular the minimality of automata, can be used to derive soundness guarantees. |
| title | Certifying Quantum Gates via Automata Advantage |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2510.09575 |