Are provable quantum speed-ups possible for classes larger than NP?

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

Answer 1

I wasn't sure what you were asking in Rev 1 of the question, but in Rev 4 you've added a more precise question that I can answer:

Can I get quadratic speed-up e.g. for finding a satisfying assignment to some quantified formular $\forall x \exists y\; \varphi(x,y)$?

Before that question can be answered, we have to make the model precise. We can think of Grover's algorithm as solving the following problem: $\exists x\; \varphi(x)$? In this model you only have access to $\varphi(\cdot)$ through an oracle who will evaluate it at any input you like.

So another way of thinking of the same problem is that Grover's algorithm evaluates the following formula: $\varphi(1) \vee \varphi(2) \vee \ldots \vee \varphi(N)$. And this can be done in $O(\sqrt{N})$ queries, where it would need $N$ queries (deterministically) and $\Omega(N)$ (bounded-error) classically.

Similarly, $\forall x \exists y\; \varphi(x,y)$ can be written as a formula using only AND, OR and NOT over the variables $\varphi(i)$. In fact, it is a formula in which every variable appears exactly once (such formulas are called "read-once").

A very general result in quantum algorithms says that any read-once formula over the gate set {AND, OR, NOT} over $N$ variables can be evaluated in $O(\sqrt{N})$ queries. This result has a long history, beginning with generalizations of Grover's algorithm to handle bounded-error inputs, a breakthrough result of Farhi, Goldstone, and Gutmann (Scott Aaronson's blog post), a beautiful connection with span programs, an SDP characterization of quantum query complexity, etc.

The final $O(\sqrt{N})$ bound for any read-once formula over that gate set is from "Reichardt, B.: Reflections for quantum query algorithms. In: 22nd SODA. (2011) 560–569"

This almost answers the quantum part of your question, unless I've misunderstood it. However the classical query complexity of read-once formulas isn't well understood, so I can't tell you whether you always get a provable quadratic speed up or not.

Sometimes you do get a quadratic speedup, as in Grover's algorithm. If the formula is balanced and each gate has fanin 2, i.e., if it looks like $\forall x_1 \exists x_2 \forall x_3 \ldots \varphi(x_1, \ldots x_n)$, then the best classical algorithm, which happens to be a zero-error randomized algorithm, needs $O(N^{0.753})$ queries, so it's not really a quadratic speedup.

Answer 2

For total functions it is impossible to achieve more than a polynomial separation (i.e. $D(f) = O(Q^6(f))$) in the quantum query model, for more info see this cstheory blog post. With promise problems, you can have exponential seperations between the quantum and classical query complexity. However, classical query complexity is sometimes very deceptive in its correspondence to complexity classes; as are partial functions in general. If you don't allow promise problems, you can't get exponential separations and your relevance to the big classes is questionable. You can never expect more than an exponential seperation, because a quantum algorithm can be simulated by a classical computer with exponential overhead (actually, in PSPACE so looking above that is dubious).