On Perfect Completeness for QMA
| dc.creator | Aaronson, Scott | |
| dc.date | 2008-06-03 | |
| dc.date | 2008-08-23 | |
| dc.date.accessioned | 2026-07-07T09:57:46Z | |
| dc.date.available | 2026-07-07T09:57:46Z | |
| dc.description | Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with one-sided 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 they are different. 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 in ZQEXP. | |
| dc.description | 9 pages. To appear in Quantum Information & Computation | |
| dc.identifier | https://arxiv.org/abs/0806.0450 | |
| dc.identifier | http://arxiv.org/abs/0806.0450 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/167465 | |
| dc.subject | Quantum Physics | |
| dc.title | On Perfect Completeness for QMA | |
| dc.type | text |