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 SBP, except that f is a nonnegative-valued GapP function rather than a #P function.
Defined in [Vya03], where the following was also shown:
Kuperberg ([Kup09]) showed that A0PP = SBQP.
The class of problems for which the task is to output a quantum certificate for a QMA problem, when such a certificate exists. Thus, the desired output is a quantum state.
Defined in [JWB03], where it is also shown that state preparation for 3-local Hamiltonians is FQMA-complete. The authors also observe that, in contrast to the case of FNP versus NP, there is no obvious reduction of FQMA problems to QMA problems.
The class of decision problems solvable by a Merlin-Arthur protocol, which goes as follows. Merlin, who has unbounded computational resources, sends Arthur a polynomial-size purported proof that the answer to the problem is "yes." Arthur must verify the proof in BPP (i.e. probabilistic polynomial-time), so that
Defined in [Bab85].
An alternative definition requires that if the answer is "yes," then there exists a proof such that Arthur accepts with certainty. However, the definitions with one-sided and two-sided error can be shown to be equivalent (see [FGM+89]).
Contains NP and BPP (in fact also ∃BPP), and is contained in AM and in QMA.
There exists an oracle relative to which BQP is not in MA [Wat00].
Equals NP under a derandomization assumption: if E requires exponentially-sized circuits, then PromiseBPP = PromiseP, implying that MA = NP [IW97].
Shown in [San07] that MA/1 (that is, MA with 1 bit of advice) does not have circuits of size for any . In the same paper, the result was used to show that MA/1 cannot be solved on more than a fraction of inputs having length by any circuit of size . Finally, it was shown that MA does not have arithmetic circuits of size .
The class of decision problems solvable by a QTM in polynomial time such that a particular '|Accept>' state has nonzero amplitude at the end of the computation, if and only if the answer is 'yes.' Since it has an exact amplitude condition, NQP has the same technical caveats as EQP. Or it would, except that it turns out to equal coC=P [FGH+98].
Defined in [ADH97].
Contrast with QMA.
The class of decision problems solvable by an NP machine such that
Defined in [Gil77].
PP is closed under union and intersection [BRS91] (this was an open problem for 14 years). More generally, PPP[log] = PP. Even more generally, PP is closed under polynomial-time truth-table reductions, or even k-round reductions for any constant k [FR96].
Contains PNP[log] [BHW89] and QMA (see [MW05]). However, there exists an oracle relative to which PP does not contain Δ2P [Bei94].
BPP [KST+89b] and even BQP [FR98] and YQP* [Yir24] are low for PP: i.e., PPBQP = PP.
APP is PP-low [Li93].
For a random oracle A, PPA is strictly contained in PSPACEA with probability 1 [ABF+94].
For any fixed k, there exists a language in PP that does not have circuits of size nk [Vin04b].
Indeed, there exists a language in PP that does not even have quantum circuits of size nk with quantum advice [Aar06] and [Yir24].
By contrast, there exists an oracle relative to which PP has linear-size circuits [Aar06].
PP can be generalized to the counting hierarchy CH.
The class of decision problems solvable by a P machine, that can make O(log n) queries to a QMA oracle (where n is the length of the input).
Defined in [Amb14].
Estimating local observables [Amb14], [GY16] and local correlation functions [GY16] against ground states of local Hamiltonians is PQMA[log]-complete.
Estimating local observables remains PQMA[log]-complete even on 2D physical systems and on the 1D line [GPY19].
PQMA[log] is contained in PP [GY16].
The class of decision problems solvable by a P machine that can make a polynomial number of non-adaptive queries to a QMA oracle.
Same as QMA, except now the witness is a pure state, and the verifier can directly obtain the probability that any one of a polynomial number of observables of the witness, if measured, would equal 1. (In the usual model, by contrast, one can only sample an observable.) Without the pure state restriction, this class is SuperQMA.
Defined in [KR24] whose complete problem is the pure state marginal problem. It is known to be QMA-hard but contained in PSPACE and QMA(2). Surprisingly, it is unknown whether this class equals SuperQMA = QMA.
The class of decision problems for which a "yes" answer can be verified by a public-coin quantum AM protocol, as follows. Arthur generates a uniformly random (classical) string and sends it to Merlin. Merlin responds with a polynomial-size quantum certificate, on which Arthur can perform any BQP operation. The completeness and soundness requirements are the same as for AM.
Defined by Marriott and Watrous [MW05].
Contains QMA and is contained in QIP[2] and BP•PP (and therefore PSPACE).
The class of decision problems for which a "yes" answer can be verified by a quantum computer with access to a classical proof. Also known as the subclass of of QMA with classical witnesses. Defined in [AN02].
Called MQA by Watrous [Wat09].
Contains MA, and is contained in QMA.
Given a black-box group G and a subgroup H, the problem of testing non-membership in H has polynomial QCMA query complexity [AK06].
See [AK06] for a "quantum oracle separation" between QCMA and QMA. No classical oracle separation between QCMA and QMA is currently known.
The problem GROUND STATE CONNECTIVITY, which intuitively asks whether a local Hamiltonian's ground space has an "energy barrier", is QCMA-complete [GS15]. Roughly: Given a local Hamiltonian H and ground states v and w, is there a polynomial-length sequence of local unitary operations mapping v to w, such that each intermediate state encountered remains in the ground space of H?
The class of decision problems such that a "yes" answer can be verified by a quantum interactive proof. Here the verifier is a BQP (i.e. quantum polynomial-time) algorithm, while the prover has unbounded computational resources (though cannot violate the linearity of quantum mechanics). The prover and verifier exchange a polynomial number of messages, which can be quantum states. Thus, the verifier's and prover's states may become entangled during the course of the protocol. Given the verifier's algorithm, we require that
Let QIP[k] be QIP where the prover and verifier are restricted to exchanging k messages (with the prover going last).
Defined in [Wat99], where it was also shown that PSPACE is in QIP[3].
Subsequently [KW00] showed that for all k>3, QIP[k] = QIP[3] = QIP.
QIP is contained in EXP [KW00].
QIP = IP = PSPACE [JJUW09]; thus quantum computing adds no power to single-prover interactive proofs.
QIP(1) is more commonly known as QMA.
Same as QMA, except now the verifier can directly obtain the probability that a given observable of the certificate state, if measured, would equal 1. (In the usual model, by contrast, one can only sample an observable.)
Defined in [AR03], where it was also shown that QMA-plus = QMA. Sometimes referred to as SuperQMA.
Same as QMA, except now the witness must contain a state with non-negative amplitudes in the computational basis.
This class is sensitive to completeness-soundness gap, as proved in [BFM23]: At some constant gap, it is equal to QMA; at another constant gap, it is equal to NEXP.
Defined in [JW23].
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].
Same as QMA except that for a "yes" instance, there exists a state that is accepted with probability 1.
Defined in [Bra06]. It was shown there that Quantum k-SAT is QMA1-complete for any . It was also shown there that Quantum 2-SAT is in P.
This result was later improved in [GN13] where it was shown that Quantum 3-SAT is QMA1-complete.
Same as QMA except that the quantum proof has O(log n) qubits instead of a polynomial number.
Is contained in PSPACE/poly [Aar06b].
The class of problems for which there exists a BQP machine M such that:
In other words, it's the same as QRG(k) for , the class of problems that admit quantum interactive proofs with competing provers in which there's no communication from the verifier back to the provers. QRG(1) is the quantum version of RG(1).
Defined in [JW09], where it was shown that QRG(1) is contained in PSPACE .
QRG(1) trivially contains QMA (and indeed PQRG(1)).
QRG(1) is trivially contained in QRG(2) (and hence PSPACE).
Is to YPP as BQP is to BPP, and QMA is to MA. The machine is now a quantum computer and the advice is a quantum state |ψ_n>.
Contains BQP and YPP, and is contained in QMA and BQP/qpoly.
