Class Description

PQP: Probabilistic Quantum Polynomial-Time

The class of decision problems solvable in polynomial time by a quantum Turing machine, with less than 1/2 probability of error.Similar to BQP in definition, but without bounded error.

Defined in [Wat09], where it shown to be equivalent to PP.

Equals PP and therefore PP^BPP [KST+89b] as well as PostBQP [Aar05b].

Linked From

No class.