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.
We study gap amplification of the class 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 for some small constant gap, it is equal to QMA(2) for larger constant gap. This is in stark contrast to 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/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 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 QMAR(2) denotes 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 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.
Stoquasticity, originating in sign-problem-free physical systems, gives rise to StoqMA, introduced by Bravyi, Bessen, and Terhal (2006), a quantum-inspired intermediate class between MA and AM. Unentanglement similarly gives rise to QMA(2), introduced by Kobayashi, Matsumoto, and Yamakami (CJTCS 2009), which generalizes QMA to two unentangled proofs and still has only the trivial NEXP upper bound. In this work, we initiate a systematic study of the power of unentanglement without destructive interference via StoqMA(2), the class of unentangled stoquastic Merlin--Arthur proof systems. Beyond its complexity-theoretic interest, StoqMA(2) is connected to the optimality of non-negative tensor optimization algorithms. We highlight:
1. NP⊆StoqMA(2) with O(n)-qubit proofs and completenes 1−2−polylog(n). Conversely, the Sum-of-Squares algorithm of Barak, Kelner, and Steurer (STOC 2014) gives an exponential-time upper bound for StoqMA(2). Our tightened analysis shows the optimality of our protocol and the BKS algorithm under ETH.
2. For logarithmic-size proofs, NP⊆StoqMA(2)log with completeness 1−O(n−2) and vanishing gap, while StoqMA(2)log⊆MA. Consequently, quantum-inspired randomness enables exponentially shorter unentangled proofs even under the assumption MA=NP.
3. For StoqMA(2)1, the parameter dependence in the general ETH-optimal time bound can be exponentially improved, or the bound achieved simultaneously with polynomial space.
Our lower bounds are obtained by stoquastizing the short-proof QMA(2) protocols using distribution testing techniques. Our upper bounds for the nearly perfect completeness case are proved via our rectangular closure testing framework.
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) ⊆ NEXP.
Quantum entanglement is a fundamental property of quantum mechanics and it serves as a basic resource in quantum computation and information. Despite its importance, the power and limitations of quantum entanglement are far from being fully understood. Here, we study entanglement via the lens of computational complexity. This is done by studying quantum generalizations of the class NP with multiple unentangled quantum proofs, the so-called QMA(2) and its variants. The complexity of QMA(2) is known to be closely connected to a variety of problems such as deciding if a state is entangled and several classical optimization problems. However, determining the complexity of QMA(2) is a longstanding open problem, and only the trivial complexity bounds ⊆ (2) ⊆ are known.
The quantum PCP conjecture is one of the major open problems in quantum complexity theory. It has resisted attack in part because many primitives used in the proof of the classical PCP theorem, such as locality-preserving gap amplification and alphabet reduction, have no obvious quantum analogues due to quantum no-cloning. Locality-preserving gap amplification is a procedure that takes as input a local Hamiltonian problem instance and produces a new instance with a larger promise gap, without increasing the locality of the Hamiltonian, and instead moderately increasing its local qudit dimension. Obtaining this kind of control over the locality during gap amplification is critical to the success of many known strategies for proving the classical PCP theorem. In this work, we put forth the first known viable template for quantum locality-preserving gap amplification, and we prove that our procedure amplifies the combinatorial gap of local Hamiltonians. Our work introduces a new framework for reasoning about quantum gap amplification in terms of fault-tolerant computation, and illuminates a route toward importing one of the central ingredients in classical PCPs into the quantum setting. In particular, we build upon ideas from the recent classical PCP of Bafna--Minzer--Vyas based on high-dimensional expanders, and the circuit-to-Hamiltonian construction of Anshu--Breuckmann--Nguyen, in addition to several recent advances in quantum coding theory.
In QMA(2), two computationally unbounded provers submit unentangled quantum witnesses to a polynomial-time quantum verifier. We ask whether allowing limited shared entanglement between the two provers changes the power of QMA(2). To this end, we formalize QMA(2;h), a variant in which the provers initially share h EPR pairs, as suggested by Aaronson, Beigi, Drucker, Fefferman, and Shor (ToC~2009). We show that polynomially many shared EPR pairs give the provers no cheating advantage: QMA(2)⊆QMA(2;h) for h=poly(n). For logarithmically many pairs, the power of QMA(2) remains unchanged, strengthening this inclusion to QMA(2)=QMA(2;h) for h=O(logn). Finally, we introduce a variant that also allows classical communication between the provers when preparing the witnesses. This setting is particularly revealing for logarithmic-size witnesses: assuming NP⊈BQP, we show that superlogarithmically many shared EPR pairs strictly reduce the model's computational power.