Class Description

BQP/mpoly: BQP With Polynomial-Size Deterministic Merlin-Like Advice

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].

Linked From

BQP/poly: BQP With Polynomial-Size Karp-Lipton Advice

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.

More about...


BQP/mlog: BQP With Logarithmic-Size Deterministic Merlin-Like Advice

Same as BQP/mpoly except that the advice is O(log n) bits instead of a polynomial number.

Strictly contained in BQP/qlog [NY03].

More about...


BQP/qlog: BQP With Logarithmic-Size Quantum Advice

Same as BQP/mlog except that the advice is quantum instead of classical.

Strictly contains BQP/mlog [NY03].

Contained in BQP/mpoly.

More about...


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...


BQPtt/poly: BQP/mpoly With Truth-Table Queries

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.

More about...


PP/poly: Nonuniform PP

Contains BQP/qpoly [Aar04b].

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.

More about...


PromiseBQP: Promise-Problem BQP

Same as PromiseBPP, but for BQP instead of BPP.

If PromiseBQP = PromiseP then BQP/mpoly = P/poly.

More about...


UL/poly: Nonuniform UL

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.

More about...