Class Description

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

Linked From

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

More about...


EESPACE: Double-Exponential Space With Linear Exponent

Equals DSPACE(22O(n)).

Is not contained in BQP/qpoly [NY03].

More about...


EXP/poly: Exponential Time With Polynomial-Size Advice

The class of decision problems solvable in EXP with the help of a polynomial-length advice string that depends only on the input length.

Contains BQP/qpoly [Aar04b].

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


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.

More about...


YQP*/poly: YQP* With Polynomial-Size Advice

Equal to BQP/qpoly [AD14].

More about...