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.
The class of problems solvable by a semantic BPP machine with O(log n) advice bits that depend only on the input length n. If the advice is good, the output must be correct with probability at least 2/3. If it is bad, the machine must provide some answer with probability at least 2/3. See the discussion for BQP/poly.
Contained in BPP/mlog.
Same as BQP/poly except that the advice is O(log n) bits instead of a polynomial number.
Contained in BQP/mlog.
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].