PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909377361870848 |
|---|---|
| author | Aaronson, Scott Grewal, Sabee Iyer, Vishnu Marshall, Simon C. Ramachandran, Ronak |
| author_facet | Aaronson, Scott Grewal, Sabee Iyer, Vishnu Marshall, Simon C. Ramachandran, Ronak |
| contents | We define and study a variant of QMA (Quantum Merlin Arthur) in which Arthur can make multiple non-collapsing measurements to Merlin's witness state, in addition to ordinary collapsing measurements. By analogy to the class PDQP defined by Aaronson, Bouland, Fitzsimons, and Lee (2014), we call this class PDQMA. Our main result is that PDQMA = NEXP; this result builds on the PCP theorem and complements the result of Aaronson (2018) that PDQP/qpoly = ALL. While the result has little to do with quantum mechanics, we also show a more "quantum" result: namely, that QMA with the ability to inspect the entire history of a hidden variable is equal to NEXP, under mild assumptions on the hidden-variable theory. We also observe that a quantum computer, augmented with quantum advice and the ability to inspect the history of a hidden variable, can solve any decision problem in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_02543 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements Aaronson, Scott Grewal, Sabee Iyer, Vishnu Marshall, Simon C. Ramachandran, Ronak Quantum Physics Computational Complexity We define and study a variant of QMA (Quantum Merlin Arthur) in which Arthur can make multiple non-collapsing measurements to Merlin's witness state, in addition to ordinary collapsing measurements. By analogy to the class PDQP defined by Aaronson, Bouland, Fitzsimons, and Lee (2014), we call this class PDQMA. Our main result is that PDQMA = NEXP; this result builds on the PCP theorem and complements the result of Aaronson (2018) that PDQP/qpoly = ALL. While the result has little to do with quantum mechanics, we also show a more "quantum" result: namely, that QMA with the ability to inspect the entire history of a hidden variable is equal to NEXP, under mild assumptions on the hidden-variable theory. We also observe that a quantum computer, augmented with quantum advice and the ability to inspect the history of a hidden variable, can solve any decision problem in polynomial time. |
| title | PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2403.02543 |