QIP $ \subseteq $ AM(2QCFA)
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914011413479424 |
|---|---|
| author | Yakaryılmaz, Abuzer |
| author_facet | Yakaryılmaz, Abuzer |
| contents | The class of languages having polynomial-time classical or quantum interactive proof systems ($\mathsf{IP}$ or $\mathsf{QIP}$, respectively) is identical to $\mathsf{PSPACE}$. We show that $\mathsf{PSPACE}$ (and so $\mathsf{QIP}$) is subset of $\mathsf{AM(2QCFA)}$, the class of languages having Arthur-Merlin proof systems where the verifiers are two-way finite automata with quantum and classical states (2QCFAs) communicating with the provers classically. Our protocols use only rational-valued quantum transitions and run in double-exponential expected time. Moreover, the member strings are accepted with probability 1 (i.e., perfect-completeness). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_21020 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | QIP $ \subseteq $ AM(2QCFA) Yakaryılmaz, Abuzer Quantum Physics Computational Complexity Formal Languages and Automata Theory The class of languages having polynomial-time classical or quantum interactive proof systems ($\mathsf{IP}$ or $\mathsf{QIP}$, respectively) is identical to $\mathsf{PSPACE}$. We show that $\mathsf{PSPACE}$ (and so $\mathsf{QIP}$) is subset of $\mathsf{AM(2QCFA)}$, the class of languages having Arthur-Merlin proof systems where the verifiers are two-way finite automata with quantum and classical states (2QCFAs) communicating with the provers classically. Our protocols use only rational-valued quantum transitions and run in double-exponential expected time. Moreover, the member strings are accepted with probability 1 (i.e., perfect-completeness). |
| title | QIP $ \subseteq $ AM(2QCFA) |
| topic | Quantum Physics Computational Complexity Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2508.21020 |