On perfect completeness for QMA
Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with onesided error, has been an open problem for years. This note helps to explain why the problem is difficult, by using ideas from real analysis to give a "quantum oracle" relative to which QMA ≠ QMA1. As a byproduct...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2017
|
| Online Access: | http://hdl.handle.net/1721.1/109480 https://orcid.org/0000-0003-1333-4045 |
| _version_ | 1826217100079792128 |
|---|---|
| author | Aaronson, Scott |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Aaronson, Scott |
| author_sort | Aaronson, Scott |
| collection | MIT |
| description | Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with onesided error, has been an open problem for years. This note helps to explain why the problem is difficult, by using ideas from real analysis to give a "quantum oracle" relative to which QMA ≠ QMA1. As a byproduct, we find that there are facts about quantum complexity classes that are classically relativizing but not quantumly relativizing, among them such "trivial" containments as BQP ⊆ ZQEXP. |
| first_indexed | 2024-09-23T16:58:19Z |
| format | Article |
| id | mit-1721.1/109480 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:58:19Z |
| publishDate | 2017 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1094802022-10-03T09:31:28Z On perfect completeness for QMA Aaronson, Scott Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Aaronson, Scott Aaronson, Scott Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with onesided error, has been an open problem for years. This note helps to explain why the problem is difficult, by using ideas from real analysis to give a "quantum oracle" relative to which QMA ≠ QMA1. As a byproduct, we find that there are facts about quantum complexity classes that are classically relativizing but not quantumly relativizing, among them such "trivial" containments as BQP ⊆ ZQEXP. 2017-05-31T20:37:34Z 2017-05-31T20:37:34Z 2009-01 Article http://purl.org/eprint/type/SubmittedJournalArticle 1533-7146 http://hdl.handle.net/1721.1/109480 Aaronson, Scott. "On perfect completeness for QMA." Quantum Information & Computation 9:1 (January 2009), pp. 81-89. https://orcid.org/0000-0003-1333-4045 en_US http://dl.acm.org/citation.cfm?id=2021261 Quantum Information & Computation Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Association for Computing Machinery (ACM) S. Aaronson |
| spellingShingle | Aaronson, Scott On perfect completeness for QMA |
| title | On perfect completeness for QMA |
| title_full | On perfect completeness for QMA |
| title_fullStr | On perfect completeness for QMA |
| title_full_unstemmed | On perfect completeness for QMA |
| title_short | On perfect completeness for QMA |
| title_sort | on perfect completeness for qma |
| url | http://hdl.handle.net/1721.1/109480 https://orcid.org/0000-0003-1333-4045 |
| work_keys_str_mv | AT aaronsonscott onperfectcompletenessforqma |