On perfect completeness for QMA
Scott T. Aaronson · Quantum Information and Computation · 2009
Whether the class QMA (Quantum Merlin Arthur)\ is equal to QMA_1, 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" relative to which QMA eq QMA_1. 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 \subseteq ZQEXP.