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.


2 Answers 2


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.

  • $\begingroup$ Thanks! That's what I wanted to know. One more detail: is the number of quantifiers required to be constant or may it grow polynomially with the input? In other words, is it correct to interpret your answer as follows: quantum query algorithms can solve the PSPACE-complete QBF-SAT problem in O(N^0.5) queries, whereas any randomized needs O(N^0.753) queries. $\endgroup$
    – blk
    Oct 8, 2012 at 19:19
  • $\begingroup$ @blk: The number of quantifiers need not be a constant, as in the last example where the final quantifier would be $\forall x_n$ or $\exists x_n$ depending on the parity of $n$. Your interpretation about QBF-SAT is correct if you interpret it as the query version of QBF-SAT, i.e., where you aren't given a formula $\varphi$, but must instead query a black box to get its output on any input. $\endgroup$ Oct 8, 2012 at 19:58

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

  • $\begingroup$ I'm not asking for superpolynomial speed-ups. Quadratic is fine. Can I get quadratic speed-ups for finding a satisfying assignment to e.g. some for-all there-exists quantified formular? $\endgroup$
    – blk
    Oct 8, 2012 at 7:11
  • 4
    $\begingroup$ @blk Grower's algorithm applies to anything that needs to be searched. So for each x search over y for an example, then with this nested search over all x for a counter-example... I don't think I understand your question anymore. Are you just asking when searching applies? Because anytime search is the best strategy you know, then you can use Grover's search to get a quadratic speed up. $\endgroup$ Oct 8, 2012 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.