Unconditional proofs of quantumness between small-space machines
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908976572006400 |
|---|---|
| author | Say, A. C. Cem Gezer, M. Utkan |
| author_facet | Say, A. C. Cem Gezer, M. Utkan |
| contents | A proof of quantumness is a protocol through which a classical machine can test whether a purportedly quantum device, with comparable time and memory resources, is performing a computation that is impossible for classical computers. Existing approaches to provide proofs of quantumness depend on unproven assumptions about some task being impossible for machines of a particular model under certain resource restrictions. We study a setup where both devices have space bounds $\mathit{o}(\log \log n)$. Under such memory budgets, it has been unconditionally proven that probabilistic Turing machines are unable to solve certain computational problems. We formulate a new class of problems, and show that these problems are polynomial-time solvable for quantum machines, impossible for classical machines, and have the property that their solutions can be "proved" by a small-space quantum machine to a classical machine with the same space bound. These problems form the basis of our newly defined protocol, where the polynomial-time verifier's verdict about the tested machine's quantumness is not conditional on an unproven weakness assumption. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_02662 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Unconditional proofs of quantumness between small-space machines Say, A. C. Cem Gezer, M. Utkan Computational Complexity Formal Languages and Automata Theory Quantum Physics A proof of quantumness is a protocol through which a classical machine can test whether a purportedly quantum device, with comparable time and memory resources, is performing a computation that is impossible for classical computers. Existing approaches to provide proofs of quantumness depend on unproven assumptions about some task being impossible for machines of a particular model under certain resource restrictions. We study a setup where both devices have space bounds $\mathit{o}(\log \log n)$. Under such memory budgets, it has been unconditionally proven that probabilistic Turing machines are unable to solve certain computational problems. We formulate a new class of problems, and show that these problems are polynomial-time solvable for quantum machines, impossible for classical machines, and have the property that their solutions can be "proved" by a small-space quantum machine to a classical machine with the same space bound. These problems form the basis of our newly defined protocol, where the polynomial-time verifier's verdict about the tested machine's quantumness is not conditional on an unproven weakness assumption. |
| title | Unconditional proofs of quantumness between small-space machines |
| topic | Computational Complexity Formal Languages and Automata Theory Quantum Physics |
| url | https://arxiv.org/abs/2412.02662 |