Same as QMA, except that now the verifier is given two polynomial-size quantum certificates, which are guaranteed to be unentangled.
Defined in [KMY01].
In [BT09], the authored presented a QMAlog(2) (that is, the length of the certificates is logarithmic in the size of the problem -- see, e.g., QMAlog) protocol for 3-Coloring, with perfect completeness and 1-1/poly(n) soundness. Note that a similar construction for QMA is highly unlikely, since it would imply NP is contained in QMAlog=BQP. An analogous result, with constant soundness but with quadratic proof length was shown in [ABD+08]. It was shown shown there that a conjecture they call the Strong Amplification Conjecture implies that QMA(2) is contained in PSPACE. The authors also show that there exists no perfectly disentangler that can be used to simulate QMA(2) in QMA, though other approaches to showing QMA = QMA(2) may still exist.
It was shown in [HM13] that QMA(k) = QMA(2) for k >= 2. However we still do not know if QMA(2) = QMA. It was shown in [BCY11] that QMA(2) = QMA if the verifier is restricted to one-way LOCC protocols.
The best known unconditional upper bound is NEXP. If QMA(2)=NEXP, then QΣ2=QΠ2 (see QPH) (alternating quantifiers provide no additional power in the quantum setting) [GSSSY18]. If QCPH=QPH (quantum proofs provide no additional power in the presence of alternating quantifiers), then QMA(2) is in PPPPP [GSSSY18].
Approximating the minimal energy of a sparse Hamiltonian with respect to a separable state (which is known as the Separable Sparse Hamiltonian problem) is QMA(2)-complete [CS12]. This is in contrast to the Separable Local Hamiltonian problem which is in QMA [CS12].
The class of decision problems such that a "yes" answer can be verified by a 1-message quantum interactive proof. That is, a BQP (i.e. quantum polynomial-time) verifier is given a quantum state (the "proof"). We require that
QMA = QIP(1).
Defined in [Wat00], where it is also shown that group non-membership is in QMA.
Based on this, [Wat00] gives an oracle relative to which MA is strictly contained in QMA.
Kitaev and Watrous (unpublished) showed QMA is contained in PP (see [MW05] for a proof). Combining that result with [Ver92], one can obtain an oracle relative to which AM is not in QMA.
Kitaev ([KSV02], see also [AN02]) showed that the 5-Local Hamiltonians Problem is QMA-complete. Subsequently, Kempe and Regev [KR03] showed that even 3-Local Hamiltonians is QMA-complete. A subsequent paper by Kempe, Kitaev, and Regev [KKR04], has hit rock bottom (assuming P does not equal QMA), by showing 2-local Hamiltonians QMA-complete.
Compare to NQP.
If QMA = PP then PP contains PH [Vya03]. This result uses the fact that QMA is contained in A0PP.
Approximating the ground state energy of a system composed of a line of quantum particles is QMA-complete [AGK07].
See also: QCMA, QMA/qpoly, QSZK, QMA(2), QMA-plus.
Same as QMA(2), except now *each* witness must contain a state with non-negative amplitudes in the computational basis.
This class was defined in [JW23] as a possible approach to prove QMA(2) equals NEXP. QMA+(2) at some completeness-soundness gap is equal to QMA(2), but at another constant gap, it is equal to NEXP. As of 2025 this problem is still open.
See also QMA+.
A bounded-error quantum generalization of PH in which all proofs are un-entangled mixed quantum states, and the verifier is a quantum circuit. Note the utilization of mixed states is non-trivial, due to the presence of alternating quantifiers.
Defined in [GSSSY18].
Contains QMA(2).
Its second and third levels, QΣ2 and QΣ3, are contained in EXP and NEXP, respectively [GSSSY18].
In contrast to PH, it is open whether QΣ2=QΠ2 collapses QPH to its second level.