The Power of Unentangled Quantum Proofs With Non-Negative Amplitudes | Quantum Colloquium

In this talk, we will explore entanglement from the lens of computational complexity by considering quantum generalizations of NP with multiple unentangled quantum proofs, the so-called QMA(2) and variants. The complexity of QMA(2) is known to be closely connected to a variety of problems such as deciding if a state is entangled and several classical optimization problems. However, determining the complexity of QMA(2) is a longstanding open problem, and only the trivial complexity bounds QMA <= QMA(2) <= NEXP are known.

More precisely, we will discuss the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote QMA+(2). In this setting, we are able to design proof verification protocols for (increasingly) hard problems both using logarithmic size quantum proofs and having a constant probability gap in distinguishing yes from no instances. In particular, we design global protocols for small set expansion (SSE), unique games (UG), and PCP verification. By virtue of this constant gap, we can "scale up" some of these results to obtain the characterization QMA+(2)= NEXP.

Panel discussion: Scott Aaronson (University of Texas at Austin), Fernando Granha Jeronimo (IAS), and Aram Harrow (MIT)