The class of languages recognized by a syntactic BQP machine with deterministic polynomial advice that depends only on the input length, such that the output is correct with probability 2/3 when the advice is good.
Can also be defined as the class of problems solvable by a nonuniform family of polynomial-size quantum circuits, just as P/poly is the class solvable by a nonuniform family of polynomial-size classical circuits.
Referred to with a variety of other ad hoc names, including BQP/poly on occassion.
Contains BQP/qlog, and is contained in BQP/qpoly.
Does not contain ESPACE [NY03].
Is to BQP/mpoly as ∃BPP is to MA. Namely, the BQP machine is required to give some answer with probability at least 2/3 even if the advice is bad. Even though BQP/mpoly is a more natural class, BQP/poly follows the standard definition of advice as a class operator [KL82].
Contained in BQP/mpoly and contains BQP/log.
Same as BQP/mpoly except that the advice is O(log n) bits instead of a polynomial number.
Strictly contained in BQP/qlog [NY03].
Same as BQP/mlog except that the advice is quantum instead of classical.
Strictly contains BQP/mlog [NY03].
Contained in BQP/mpoly.
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].
Same as BQP/mpoly, except that the machine only gets to make nonadaptive queries to whatever oracle it might have.
Defined in [NY03b], where it was also shown that P is not contained in BQPtt/poly relative to an oracle.
If PP/poly = P/poly then PP is contained in P/poly. Indeed this is true with any syntactically defined class in place of PP. An implication is that any unrelativized separation of BQP/qpoly from BQP/mpoly would imply that PP does not have polynomial-size circuits.
Same as PromiseBPP, but for BQP instead of BPP.
If PromiseBQP = PromiseP then BQP/mpoly = P/poly.
Has the same relation to UL as P/poly does to P.
Equals NL/poly [RA00]. (A corollary is that UL/poly is closed under complement).
Note that in UL/poly, the witness must be unique even for bad advice. UL/mpoly (as in BQP/mpoly) is a more natural definition, but this is a moot distinction here because [RA00] show that they both equal NL/poly.