[BFM24] Quantum Merlin-Arthur and Proofs Without Relative Phase

Authors: Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha | Venue: ITCS 2024 | Source

Abstract

We study QMA+, a variant of QMA where quantum proofs are restricted to have non-negative amplitudes (i.e., no relative phase between basis states). We show:

• QMA+ with a constant completeness-soundness gap of (2/3, 1/3) equals NEXP.
• QMA+ with a different constant gap equals QMA.

This shows that relative phase is at least as important a source of power in quantum proofs as entanglement, since QMA(2) (two unentangled proofs) ⊆ NEXP. Removing relative phase is therefore a drastic restriction that collapses the class all the way to NEXP, far above QMA. The result also implies that QMA with a non-collapsing measurement equals NEXP (a result later proved directly in [BM25]).