Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.08462 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909608860188672 |
|---|---|
| author | Say, A. C. Cem |
| author_facet | Say, A. C. Cem |
| contents | Quantum Merlin-Arthur proof systems are believed to be stronger than both their classical counterparts and ``stand-alone'' quantum computers when Arthur is assumed to operate in $Ω(\log n)$ space. No hint of such an advantage over classical computation had emerged from research on smaller space bounds, which had so far concentrated on constant-space verifiers. We initiate the study of quantum Merlin-Arthur systems with space bounds in $ω(1) \cap o(\log n)$, and exhibit a problem family $\mathcal{F}$, whose yes-instances have proofs that are verifiable by polynomial-time quantum Turing machines operating in this regime. We show that no problem in $\mathcal{F}$ has proofs that can be verified classically or is solvable by a stand-alone quantum machine in polynomial time if standard complexity assumptions hold. Unlike previous examples of small-space verifiers, our protocols require only subpolynomial-length quantum proofs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_08462 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Short and useful quantum proofs for sublogarithmic-space verifiers Say, A. C. Cem Computational Complexity Quantum Merlin-Arthur proof systems are believed to be stronger than both their classical counterparts and ``stand-alone'' quantum computers when Arthur is assumed to operate in $Ω(\log n)$ space. No hint of such an advantage over classical computation had emerged from research on smaller space bounds, which had so far concentrated on constant-space verifiers. We initiate the study of quantum Merlin-Arthur systems with space bounds in $ω(1) \cap o(\log n)$, and exhibit a problem family $\mathcal{F}$, whose yes-instances have proofs that are verifiable by polynomial-time quantum Turing machines operating in this regime. We show that no problem in $\mathcal{F}$ has proofs that can be verified classically or is solvable by a stand-alone quantum machine in polynomial time if standard complexity assumptions hold. Unlike previous examples of small-space verifiers, our protocols require only subpolynomial-length quantum proofs. |
| title | Short and useful quantum proofs for sublogarithmic-space verifiers |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2505.08462 |