2026-08-07T13:05:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19537 2024-03-06T11:04:15Z ddc:004 open_access

Quantum Merlin-Arthur and Proofs Without Relative Phase Bassirian, Roozbeh Fefferman, Bill Marwaha, Kunal quantum complexity QMA(2) PCPs We study a variant of QMA where quantum proofs have no relative phase (i.e. non-negative amplitudes, up to a global phase). If only completeness is modified, this class is equal to QMA [Grilo et al., 2014]; but if both completeness and soundness are modified, the class (named QMA+ by Jeronimo and Wu [Jeronimo and Wu, 2023]) can be much more powerful. We show that QMA+ with some constant gap is equal to NEXP, yet QMA+ with some other constant gap is equal to QMA. One interpretation is that Merlin’s ability to "deceive" originates from relative phase at least as much as from entanglement, since QMA(2) ⊆ NEXP. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Roozbeh Bassirian and Bill Fefferman and Kunal Marwaha 2024 Is Part Of LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2024.9 urn:nbn:de:0030-drops-195370 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.9 eng https://creativecommons.org/licenses/by/4.0/legalcode