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.
Like QPH, but the provers may entangle their earlier proofs with their later proofs.
Defined in [GY24], and was shown to collapse to QRG(1).
The hierarchy collapses even with a polynomial number of rounds, whereas PH with polynomial rounds equals PSPACE.
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].