Class Description

EESPACE: Double-Exponential Space With Linear Exponent

Equals DSPACE(22O(n)).

Is not contained in BQP/qpoly [NY03].

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