This class is a generalization of BQP where one is allowed to perform measuresments without collapsing the wavefunction.[ABFL14]
Unlike, BQP this is likely to be a not physically realizable class.
Contains SZK and thus contains graph isomorphism.
There is an oracle relative to which BQP is not equal to PDQP and an oracle relative to which NP is not contained in PDQP.
PDQP can perform unordered searches faster than BQP.
Compare DQP.
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.
Defined in the conference version of [ABFL14]. Same as PDQP.