Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2306.13247 · Leibniz international proceedings in informatics

Quantum Merlin-Arthur and Proofs Without Relative Phase

Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha

Published Jun 23, 2023• 13 citations
arXivHTMLPDF

Abstract

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 [arXiv:1410.2882]; but if both completeness and soundness are modified, the class (named QMA+ by Jeronimo and Wu) 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) $\subseteq$ NEXP.

DOI
10.4230/lipics.itcs.2024.9

Related papers

Near-Optimal Gap Amplification for Nonnegative Unentangled Quantum Proofs

Masayuki Miyamoto

We study gap amplification of the class $\mathsf{QMA}^{+}(2)$ characterized by unentangled quantum proofs whose amplitudes are nonnegative in the computational basis. This class was recently introduced by Jeronimo and Wu (STOC 2023), and its behavior depends sharply on the completeness-soundness gap: although it captures the power of $\mathsf{NEXP}$ for some small constant gap, it is equal to $\mathsf{QMA}(2)$ for larger constant gap. This is in stark contrast to $\mathsf{QMA}(2)$ where strong gap amplification is known due to the product test by Harrow and Montanaro (FOCS 2010, JACM 2013). In this paper, we prove for every completeness $c$ and soundness $s$ with $c-s=1/\mathrm{poly}(n)$, \[ \mathsf{NEXP} = \mathsf{QMA}^{+}(2,c,s) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14+\frac1{\mathrm{poly}(n)}\right). \] Our result gives a clean complexity phase transition for $\mathsf{QMA}^{+}(2)$ since we have \[ \mathsf{QMA}^{\mathbb R}(2) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14-\frac1{\mathrm{poly}(n)}\right), \] where $\mathsf{QMA}^{\mathbb R}(2)$ denotes $\mathsf{QMA}(2)$ with witnesses restricted to real amplitudes. Our amplification is thus optimal in the sense that a slight improvement of our soundness would have the collapse \[ \mathsf{QMA}^{\mathbb R}(2)=\mathsf{NEXP}. \] Our proof combines symmetric-subspace projections with the relation $\mathsf{QMA}^{+}(1)=\mathsf{NEXP}$ of Bassirian, Fefferman, and Marwaha (ITCS 2024). The main technical ingredient is a dimension-independent de Finetti theorem in Hilbert-Schmidt norm that applies when the number of registers under consideration grows logarithmically.

quant-pharXiv:2608.07986•Aug 11, 2026•0 citations

Quantum Merlin-Arthur with an Internally Separable Proof

Roozbeh Bassirian, Bill Fefferman, Itai Leigh +2 more

We find a modification to QMA where having one quantum proof is strictly less powerful than having two unentangled proofs, assuming EXP $\ne$ NEXP. This gives a new route to prove QMA(2) = NEXP that overcomes the primary drawback of a recent approach [arXiv:2402.18790 , arXiv:2306.13247] (QIP 2024). Our modification endows each proof with a form of *multipartite* unentanglement: after tracing out one register, a small number of qubits are separable from the rest of the state.

arXiv:2410.19152•Leibniz international proceedings in informatics•Oct 24, 2024•7 citations

Multi-Prover Quantum Merlin-Arthur Proof Systems with Small Gap

Attila Pereszlényi

This paper studies multiple-proof quantum Merlin-Arthur (QMA) proof systems in the setting when the completeness-soundness gap is small. Small means that we only lower-bound the gap with an inverse-exponential function of the input length, or with an even smaller function. Using the protocol of Blier and Tapp [arXiv:0709.0738], we show that in this case the proof system has the same expressive power as non-deterministic exponential time (NEXP). Since single-proof QMA proof systems, with the same bound on the gap, have expressive power at most exponential time (EXP), we get a separation between single and multi-prover proof systems in the 'small-gap setting', under the assumption that EXP is not equal to NEXP. This implies, among others, the nonexistence of certain operators called disentanglers (defined by Aaronson et al. [arXiv:0804.0802]), with good approximation parameters. We also show that in this setting the proof system has the same expressive power if we restrict the verifier to be able to perform only Bell-measurements, i.e., using a BellQMA verifier. This is not known to hold in the usual setting, when the gap is bounded by an inverse-polynomial function of the input length. To show this we use the protocol of Chen and Drucker [arXiv:1011.0716]. The only caveat here is that we need at least a linear amount of proofs to achieve the power of NEXP, while in the previous setting two proofs were enough. We also study the case when the proof-lengths are only logarithmic in the input length and observe that in some cases the expressive power decreases. However, we show that it doesn't decrease further if we make the proof lengths to be even shorter.

arXiv:1205.2761•May 12, 2012•27 citations

On perfect completeness for QMA

Scott Aaronson

Whether the class QMA (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" relative to which QMA \neq QMA_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.

arXiv:0806.0450•Quantum Information and Computation•Jan 1, 2009•45 citations

On Perfect Completeness for QMA

Scott Aaronson

Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with onesided 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 ≠ QMA1. 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 ⊆ ZQEXP.

•Jun 3, 2008•4 citations

On QMA protocols with two short quantum proofs

Francois Le Gall, Shota Nakagawa, Harumichi Nishimura

This paper gives a QMA (Quantum Merlin-Arthur) protocol for 3-SAT with two logarithmic-size quantum proofs (that are not entangled with each other) such that the gap between the completeness and the soundness is $\Omega(\frac{1}{n\polylog{n}})$. This improves the best completeness/soundness gaps known for NP-complete problems in this setting.

arXiv:1108.4306•Quantum Information and Computation•Jul 1, 2012•36 citations
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 [arXiv:1410.2882]; but if both completeness and soundness are modified, the class (named QMA+ by Jeronimo and Wu) 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) ⊆\subseteq⊆ NEXP.
We study gap amplification of the class QMA+(2)\mathsf{QMA}^{+}(2)QMA+(2) characterized by unentangled quantum proofs whose amplitudes are nonnegative in the computational basis. This class was recently introduced by Jeronimo and Wu (STOC 2023), and its behavior depends sharply on the completeness-soundness gap: although it captures the power of NEXP\mathsf{NEXP}NEXP for some small constant gap, it is equal to QMA(2)\mathsf{QMA}(2)QMA(2) for larger constant gap. This is in stark contrast to QMA(2)\mathsf{QMA}(2)QMA(2) where strong gap amplification is known due to the product test by Harrow and Montanaro (FOCS 2010, JACM 2013). In this paper, we prove for every completeness ccc and soundness sss with c−s=1/poly(n)c-s=1/\mathrm{poly}(n)c−s=1/poly(n), NEXP=QMA+(2,c,s)=QMA+(2,1−1poly(n),14+1poly(n)). \mathsf{NEXP} = \mathsf{QMA}^{+}(2,c,s) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14+\frac1{\mathrm{poly}(n)}\right). NEXP=QMA+(2,c,s)=QMA+(2,1−poly(n)1​,41​+poly(n)1​). Our result gives a clean complexity phase transition for QMA+(2)\mathsf{QMA}^{+}(2)QMA+(2) since we have QMAR(2)=QMA+(2,1−1poly(n),14−1poly(n)), \mathsf{QMA}^{\mathbb R}(2) = \mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14-\frac1{\mathrm{poly}(n)}\right), QMAR(2)=QMA+(2,1−poly(n)1​,41​−poly(n)1​), where QMAR(2)\mathsf{QMA}^{\mathbb R}(2)QMAR(2) denotes QMA(2)\mathsf{QMA}(2)QMA(2) with witnesses restricted to real amplitudes. Our amplification is thus optimal in the sense that a slight improvement of our soundness would have the collapse QMAR(2)=NEXP. \mathsf{QMA}^{\mathbb R}(2)=\mathsf{NEXP}. QMAR(2)=NEXP. Our proof combines symmetric-subspace projections with the relation QMA+(1)=NEXP\mathsf{QMA}^{+}(1)=\mathsf{NEXP}QMA+(1)=NEXP of Bassirian, Fefferman, and Marwaha (ITCS 2024). The main technical ingredient is a dimension-independent de Finetti theorem in Hilbert-Schmidt norm that applies when the number of registers under consideration grows logarithmically.
We find a modification to QMA where having one quantum proof is strictly less powerful than having two unentangled proofs, assuming EXP ≠\ne= NEXP. This gives a new route to prove QMA(2) = NEXP that overcomes the primary drawback of a recent approach [arXiv:2402.18790 , arXiv:2306.13247] (QIP 2024). Our modification endows each proof with a form of *multipartite* unentanglement: after tracing out one register, a small number of qubits are separable from the rest of the state.
This paper studies multiple-proof quantum Merlin-Arthur (QMA) proof systems in the setting when the completeness-soundness gap is small. Small means that we only lower-bound the gap with an inverse-exponential function of the input length, or with an even smaller function. Using the protocol of Blier and Tapp [arXiv:0709.0738], we show that in this case the proof system has the same expressive power as non-deterministic exponential time (NEXP). Since single-proof QMA proof systems, with the same bound on the gap, have expressive power at most exponential time (EXP), we get a separation between single and multi-prover proof systems in the 'small-gap setting', under the assumption that EXP is not equal to NEXP. This implies, among others, the nonexistence of certain operators called disentanglers (defined by Aaronson et al. [arXiv:0804.0802]), with good approximation parameters. We also show that in this setting the proof system has the same expressive power if we restrict the verifier to be able to perform only Bell-measurements, i.e., using a BellQMA verifier. This is not known to hold in the usual setting, when the gap is bounded by an inverse-polynomial function of the input length. To show this we use the protocol of Chen and Drucker [arXiv:1011.0716]. The only caveat here is that we need at least a linear amount of proofs to achieve the power of NEXP, while in the previous setting two proofs were enough. We also study the case when the proof-lengths are only logarithmic in the input length and observe that in some cases the expressive power decreases. However, we show that it doesn't decrease further if we make the proof lengths to be even shorter.
Whether the class QMA (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" relative to which QMA \neq QMA_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.