See QIP for definition.
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 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.
A quantum analog of SZK (or more precisely HVSZK).
Arthur is a BQP (i.e. quantum) verifier who can exchange quantum messages with Merlin. So Arthur and Merlin's states may become entangled during the course of the protocol.
Arthur's "view" of his interaction with Merlin is taken to be the sequence of mixed states he has, over all steps of the protocol. The zero-knowledge requirement is that each of these states must have trace distance at most (say) 1/10 from a state that Arthur could prepare himself (in BQP), without help from Merlin. Arthur is assumed to be an honest verifier.
Defined in [Wat02], where the following was also shown:
Subsequently, [Wat09b] showed that honest-verifier and general-verifier quantum statistical zero-knowledge are equivalent.
There exists an oracle relative to which QSZK does not contain UP ∩ coUP, and a random oracle relative to which QSZK does not contain UP [MW18].
Same as MIP*[2,1], but with the further restriction that both provers send only a single bit to the verifier, and the verifier's output is a function of the exclusive-OR of those bits. There should exist 0<a<b<1 such that if the answer is "yes", then for some responses of the provers the verifier accepts with probability at least b, while if the answer is "no", then for all responses of the provers the verifier accepts with probability at most a.
Defined by [CHT+04], whose motivation was a connection to the Bell and CHSH inequalities of quantum physics.
XOR-MIP*[2,1] is contained in NEXP [CHT+04].
XOR-MIP*[2,1] is contained in QIP[2] [Weh06]