On Perfect Completeness for QMA

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

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.
9 pages. To appear in Quantum Information & Computation

Keywords

Quantum Physics

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/167465

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0806.0450
 http://arxiv.org/abs/0806.0450

Collections

arXiv