Class Description

RQP: One-sided Error Extension of EQP

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.

Linked From

RBQP: Strict Quantum RP

The class of problems in NP whose witnesses are in FBQP. For example, the set of square-free numbers is in coRBQP using only the fact that factoring is in FBQP. (Even without a proof that the factors are prime, the factorization proves that there is a square divisor.)

Contains RP and ZBQP, and is contained in BQP and RQP. Defined here to clarify EQP; see also ZBQP.

More about...


ZQP: Zero-Error Extension Of EQP

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.

More about...