[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]).

BibTeX

Copy

@Inproceedings{ITCS:BasFefMar24,
  author = {Roozbeh Bassirian and Bill Fefferman and Kunal Marwaha},
  title = {Quantum Merlin-Arthur and Proofs Without Relative Phase},
  pages = {9:1--9:19},
  editor = {Venkatesan Guruswami},
  booktitle = {ITCS 2024: 15th Innovations in Theoretical Computer Science Conference},
  volume = {287},
  address = {Berkeley, CA, USA},
  month = {jan~30~--~feb~2},
  publisher = {Leibniz International Proceedings in Informatics (LIPIcs)},
  year = {2024},
  doi = {10.4230/LIPIcs.ITCS.2024.9},
}