Classical and quantum Merlin-Arthur automata
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914875156987904 |
|---|---|
| author | Yakaryılmaz, Abuzer |
| author_facet | Yakaryılmaz, Abuzer |
| contents | We introduce Merlin-Arthur (MA) automata where Merlin provides a certificate at the beginning of computation and it is scanned by Arthur before reading the input. We define Merlin-Arthur deterministic, probabilistic, and quantum finite state automata (resp., MA-DFAs, MA-PFAs, and MA-QFAs) and postselecting MA-PFAs and MA-QFAs (resp., MA-PostPFA and MA-PostQFA). We present several results using different certificate lengths.
We show that MA-DFAs use constant length certificates, and they are equivalent to multi-entry DFAs. Thus, they recognize all and only regular languages, but they can be exponential and polynomial state efficient over binary and unary languages, respectively. With sublinear length certificates, MA-PFAs can recognize several nonstochastic unary languages with cutpoint 1/2. With linear length certificates, MA-PostPFAs can recognize these nonstochastic unary languages with bounded error. With arbitrarily long certificates, bounded-error MA-PostPFAs can verify every unary decidable language. With sublinear length certificates, bounded-error MA-PostQFAs can verify several nonstochastic unary languages. With linear length certificates, they can verify every unary language and some NP-complete binary languages. With exponential length certificates, they can verify every binary language. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_13801 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Classical and quantum Merlin-Arthur automata Yakaryılmaz, Abuzer Formal Languages and Automata Theory Computational Complexity Quantum Physics We introduce Merlin-Arthur (MA) automata where Merlin provides a certificate at the beginning of computation and it is scanned by Arthur before reading the input. We define Merlin-Arthur deterministic, probabilistic, and quantum finite state automata (resp., MA-DFAs, MA-PFAs, and MA-QFAs) and postselecting MA-PFAs and MA-QFAs (resp., MA-PostPFA and MA-PostQFA). We present several results using different certificate lengths. We show that MA-DFAs use constant length certificates, and they are equivalent to multi-entry DFAs. Thus, they recognize all and only regular languages, but they can be exponential and polynomial state efficient over binary and unary languages, respectively. With sublinear length certificates, MA-PFAs can recognize several nonstochastic unary languages with cutpoint 1/2. With linear length certificates, MA-PostPFAs can recognize these nonstochastic unary languages with bounded error. With arbitrarily long certificates, bounded-error MA-PostPFAs can verify every unary decidable language. With sublinear length certificates, bounded-error MA-PostQFAs can verify several nonstochastic unary languages. With linear length certificates, they can verify every unary language and some NP-complete binary languages. With exponential length certificates, they can verify every binary language. |
| title | Classical and quantum Merlin-Arthur automata |
| topic | Formal Languages and Automata Theory Computational Complexity Quantum Physics |
| url | https://arxiv.org/abs/2212.13801 |