Return to Question

In the oracle query model quantum computers can provably achieve a quadratic speed-up over any classical randomized computer [Grover, BBBV].

Are similar speed-ups provably possible for higher levels of the polynomial hiearchy or even PSPACE or EXP? (i.e. for classes that require single-exponentially many queries classically.)

Note that for larger classes "scaling Grover up an exponential" to NEXP gives $2^{2^n}$ vs. $2^{2^{n-1}}$ queries.

In the oracle query model quantum computers can provably achieve a quadratic speed-up over any classical randomized computer [Grover, BBBV].

Are similar speed-ups provably possible for higher levels of the polynomial hiearchy or even PSPACE or EXP? (i.e. for classes that require single-exponentially many queries classically.)

Note, that I'm not asking for superpolynomial speed-ups. Quadratic is fine. Can I get quadratic speed-up e.g. for finding a satisfying assignment to some quantified formular $\forall x \exists y\; \varphi(x,y)$?

Note that for larger classes "scaling Grover up an exponential" to NEXP gives $2^{2^n}$ vs. $2^{2^{n-1}}$ queries.