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• 3 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•0 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•13 citations

PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements

Scott Aaronson, Sabee Grewal, Vishnu Iyer +2 more

We define and study a variant of QMA (Quantum Merlin Arthur) in which Arthur can make multiple non-collapsing measurements to Merlin's witness state, in addition to ordinary collapsing measurements. By analogy to the class PDQP defined by Aaronson, Bouland, Fitzsimons, and Lee (2014), we call this class PDQMA. Our main result is that PDQMA = NEXP; this result builds on the PCP theorem and complements the result of Aaronson (2018) that PDQP/qpoly = ALL. While the result has little to do with quantum mechanics, we also show a more "quantum" result: namely, that QMA with the ability to inspect the entire history of a hidden variable is equal to NEXP, under mild assumptions on the hidden-variable theory. We also observe that a quantum computer, augmented with quantum advice and the ability to inspect the history of a hidden variable, can solve any decision problem in polynomial time.

arXiv:2403.02543•Leibniz international proceedings in informatics•Mar 4, 2024•0 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.

Quantum Information and Computation•Jan 1, 2009•29 citations

PDQMA = DQMA = NEXP: QMA with Hidden Variables and Non-Collapsing Measurements

Scott Aaronson, Grewal, Sabee, Iyer, Vishnu +2 more

We define and study a variant of QMA (Quantum Merlin Arthur) in which Arthur can make multiple non-collapsing measurements to Merlin’s witness state, in addition to ordinary collapsing measurements. By analogy to the class PDQP defined by Aaronson, Bouland, Fitzsimons, and Lee (2014), we call this class PDQMA. Our main result is that PDQMA = NEXP; this result builds on the PCP theorem and complements the result of Aaronson (2018) that PDQP/qpoly = ALL. While the result has little to do with quantum mechanics, we also show a more "quantum" result: namely, that QMA with the ability to inspect the entire history of a hidden variable is equal to NEXP, under mild assumptions on the hidden-variable theory. We also observe that a quantum computer, augmented with quantum advice and the ability to inspect the history of a hidden variable, can solve any decision problem in polynomial time.

•Jan 1, 2025•0 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.
We define and study a variant of QMA (Quantum Merlin Arthur) in which Arthur can make multiple non-collapsing measurements to Merlin's witness state, in addition to ordinary collapsing measurements. By analogy to the class PDQP defined by Aaronson, Bouland, Fitzsimons, and Lee (2014), we call this class PDQMA. Our main result is that PDQMA = NEXP; this result builds on the PCP theorem and complements the result of Aaronson (2018) that PDQP/qpoly = ALL. While the result has little to do with quantum mechanics, we also show a more "quantum" result: namely, that QMA with the ability to inspect the entire history of a hidden variable is equal to NEXP, under mild assumptions on the hidden-variable theory. We also observe that a quantum computer, augmented with quantum advice and the ability to inspect the history of a hidden variable, can solve any decision problem in polynomial time.
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.
We define and study a variant of QMA (Quantum Merlin Arthur) in which Arthur can make multiple non-collapsing measurements to Merlin’s witness state, in addition to ordinary collapsing measurements. By analogy to the class PDQP defined by Aaronson, Bouland, Fitzsimons, and Lee (2014), we call this class PDQMA. Our main result is that PDQMA = NEXP; this result builds on the PCP theorem and complements the result of Aaronson (2018) that PDQP/qpoly = ALL. While the result has little to do with quantum mechanics, we also show a more "quantum" result: namely, that QMA with the ability to inspect the entire history of a hidden variable is equal to NEXP, under mild assumptions on the hidden-variable theory. We also observe that a quantum computer, augmented with quantum advice and the ability to inspect the history of a hidden variable, can solve any decision problem in polynomial time.