The geometry of quantum computation

Abstract

Whether the class 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 oracle relative to which QMA\neqQMA_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}.