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.
Literally, the class of ALL languages.
ALL is a gargantuan beast that's been wreaking havoc in the Zoo of late.
First [Aar04b] observed that PP/rpoly (PP with polynomial-size randomized advice) equals ALL, as does PostBQP/qpoly (PostBQP with polynomial-size quantum advice).
Then [Raz05] showed that QIP/qpoly, and even IP(2)/rpoly, equal ALL.
Nor is it hard to show that MAEXP/rpoly = ALL.
Also, per [Aar18], PDQP/qpoly = ALL.
On the other hand, even though PSPACE contains PP, and EXPSPACE contains MAEXP, it's easy to see that PSPACE/rpoly = PSPACE/poly and EXPSPACE/rpoly = EXPSPACE/poly are not ALL.
So does ALL have no respect for complexity class inclusions at ALL? (Sorry.)
It is not as contradictory as it first seems. The deterministic base class in all of these examples is modified by computational non-determinism after it is modified by advice. For example, MAEXP/rpoly means M(AEXP/rpoly), while (MAEXP)/rpoly equals MAEXP/poly by a standard argument. In other words, it's only the verifier, not the prover or post-selector, who receives the randomized or quantum advice. The prover knows a description of the advice state, but not its measured values. Modification by /rpoly does preserve class inclusions when it is applied after other changes.
The class of decision problems for which a "yes" answer can be verified by an interactive proof. Here a probabilistic polynomial-time verifier sends messages back and forth with an all-powerful prover. They can have polynomially many rounds of interaction. Given the verifier's algorithm, at the end:
Defined in [GMR89], with the motivation of providing a framework for the introduction of zero-knowledge proofs (see the class ZK). Interestingly, the power of general interactive proof systems is not decreased if the verifier is only allowed random queries (i.e., it merely tosses coins and sends any outcome to the prover). The latter model, known as the Arthur-Merlin (or public-coin) model was introduced independently (but later) in [Bab85], and a strong equivalent (which preserves the number of rounds) is proved in [GS86]. Often, it is required that the prover can convince the verifier to accept correct assertions with probability 1; this is called perfect completeness.However, the definitions with one-sided and two-sided error can be shown to be equivalent (see [FGM+89]).
First demonstration to the power of interactive proofs was given by showing that for graph nonisomorphism (a problem not known in NP) has such proofs [GMW91]. Five years later is was shown thatIP contains PH [LFK+90], and indeed (this was discovered only a few weeks later) equals PSPACE [Sha90]. On the other hand, coNP is not contained in IP relative to a random oracle [CCG+94].
The verifier for PSPACE only uses logarithmic space when given two way, read only access to its randomness. On the other hand, given only read once access to its randomness, a log space verifier can only verify languages in P [Sha90]. Further, a log space verifier with read once access to its randomness can verifier any language in P [GKR15]. See BPL vs BP•L for a comparison between read once and read multiple access to randomness.
See QIP for definition.
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.
The class of decision problems for which a "yes" answer can be verified by a public-coin quantum MAM protocol, as follows. Merlin sends a polynomial-size quantum state to Arthur. Arthur then flips some classical coins (in fact, he only has to flip one without loss of generality) and sends the outcome to Merlin. At this stage Arthur is not yet allowed to perform any quantum operations. Merlin then sends Arthur another quantum state. Finally, Arthur performs a BQP operation on both of the states simultaneously, and either accepts or rejects. The completeness and soundness requirements are the same as for AM. Also, Merlin's messages might be entangled.
Defined by Marriott and Watrous [MW05], who also showed that QMAM = QIP(3) = QIP.
Hence QMAM equals PSPACE.
The quantum generalization of MIP, and the multi-prover generalization of QIP.
A quantum multi-prover interactive proof system is the same as a classical one, except that all messages and verifier computations are quantum. As in MIP, there is no communication among the provers; however, the provers share unlimited prior entanglement. The number of provers and number of rounds can both be polynomial in n.
Defined in [KM02].
Shown to be equal to MIP* in [RUV12], and thus RE [JNVWY20].
QMIP contains NEXP simply because MIP* contains NEXP [IV12]. Since we know that NEXP = QMIPne, this tells us that giving the provers unlimited prior entanglement does not make the class less powerful.
Same as QRG(2), except that now the verifier can process the yes-prover's answer before preparing the no-prover's question.
Defined in [GW05], where it was also shown that SQG contains QIP.
SQG is contained in EXP [Gut05].
SQG is trivially contained in QRG(4) (and hence EXP).
SQG trivially contains QRG(2) (and hence PSPACE).
SQG is contained in PSPACE [GW10]. Hence SQG = QRG(2) = RG(2) = PSPACE and the addition of quantum information, combined with the ability of the verifier to process the one prover's answer before preparing the other prover's question, has no effect on the complexity of two-turn (one-round) zero-sum games.