The class of questions that can be answered by a QTM that answers yes, no, or "maybe". If the correct answer is yes, then P[no] = 0, and vice-versa; and the probability of maybe is at most 1/2. Since some of the probabilities have to vanish, ZQP has the same technical caveats as EQP.
Defined independently in [BW03] and in [Nis02].
Contains EQP and ZBQP and is contained in BQP. Equals RQP ∩ coRQP. There is an oracle such that ZQPZQP is larger than ZQP [BW03]; c.f. with ZBQP.
The class of questions that can be answered by a QTM that accepts with probability 0 when the true answer is no, and accepts with probability at least 1/2 when the true answer is yes. Since one of the probabilities has to vanish, RQP has the same technical caveats as EQP.
Contains ZQP and RBQP, and is contained in BQP.
Defined as RBQP ∩ coRBQP. Equivalently, the class of problems in NP ∩ coNP such that both positive and negative witnesses are in FBQP.
For example, the language of square-free numbers is in ZBQP, because factoring is in FBQP and a factorization can be certified in ZPP (indeed in P, by [AKS02]).
Unlike EQP or ZQP, ZBQP would generalize ZPP in practice if quantum computers existed, in the sense that it provides proven answers.
Contains ZPP and is contained in RBQP and ZQP. Also, ZBQPZBQP = ZBQP. Defined here to clarify EQP and ZQP.