Class Description

YQP: Yaroslav BQP

Is to YPP as BQP is to BPP, and QMA is to MA. The machine is now a quantum computer and the advice is a quantum state |ψ_n>.

Contains BQP and YPP, and is contained in QMA and BQP/qpoly.

Linked From

BQP/qpoly: BQP With Polynomial-Size Quantum Advice

The class of problems solvable by a BQP machine that receives a quantum state ψn as advice, which depends only on the input length n.

As with BQP/mpoly, the acceptance probability does not need to be bounded away from 1/2 if the machine is given bad advice. (Thus, we are discussing the class that [NY03] call BQP/*Qpoly.) Indeed, such a condition would make quantum advice unusable, by a continuity argument.

Does not contain EESPACE [NY03].

[AD14] showed that BQP/qpoly = YQP/poly.

There exists an oracle relative to which BQP/qpoly does not contain NP [Aar04b].

A classical oracle separation between BQP/qpoly and BQP/mpoly is presently unknown, but there is a quantum oracle separation [AK06]. An unrelativized separation is too much to hope for, since it would imply that PP is not contained in P/poly.

Contains BQP/mpoly.

Does not contain PP unless CH collapses [Aar06],[Yir24].

More about...


YQP*: Yaroslav BQP star

Is to YQP as YP* is to YP [AD14].

Is contained in APP, and so is low for PP [Yir24].

More about...