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...
| Հիմնական հեղինակ: | |
|---|---|
| Այլ հեղինակներ: | |
| Ձևաչափ: | Հոդված |
| Լեզու: | en_US |
| Հրապարակվել է: |
Association for Computing Machinery (ACM)
2017
|
| Առցանց հասանելիություն: | http://hdl.handle.net/1721.1/109480 https://orcid.org/0000-0003-1333-4045 |
| Ամփոփում: | 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. |
|---|