<p>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 <a href="http://cstheory.blogoverflow.com/2011/07/quantum-query-complexity/" rel="nofollow noreferrer">cstheory blog post</a>. 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 <a href="https://cstheory.stackexchange.com/questions/7413/trade-off-between-time-and-query-complexity">partial functions in general</a>. 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).</p>

CC BY-SA 3.0
2012-10-08T07:11:09.907Z
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?
blk
CC BY-SA 3.0
2012-10-08T07:15:31.643Z
@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.
Artem Kaznatcheev
CC BY-SA 3.0
2012-10-07T22:59:05.197Z
2012-10-07T22:59:05.197Z
2017-04-13T12:32:28.167Z
Artem Kaznatcheev
<p>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:</p>

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

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

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

<p>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").</p>

<p>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 (<a href="http://www.scottaaronson.com/blog/?p=207">Scott Aaronson's blog post</a>), a beautiful connection with span programs, an SDP characterization of quantum query complexity, etc. </p>

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

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

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

CC BY-SA 3.0
2012-10-08T19:19:28.203Z
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.
blk
CC BY-SA 3.0
2012-10-08T19:58:48.223Z
@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.
Robin Kothari
CC BY-SA 3.0
2012-10-08T18:39:45.067Z
2012-10-08T18:39:45.067Z
Robin Kothari
<p>In the oracle query model quantum computers can provably achieve a quadratic speed-up over any classical randomized computer [Grover, BBBV]. </p>

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

<p>Note, that I'm <em>not</em> 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)$? </p>

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

<cc.complexity-theory><reference-request><quantum-computing><query-complexity>
Are provable quantum speed-ups possible for classes larger than NP?
blk
# Are provable quantum speed-ups possible for classes larger than NP?

(Asked by: username_0 on 2012-10-07)

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.

**Tags:** cc.complexity-theory, reference-request, quantum-computing, query-complexity

---

## 2 answers

### Answer by username_2 on 2012-10-08. Score: 6 | Accepted answer

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](http://www.scottaaronson.com/blog/?p=207)), 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.: Reﬂections 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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: @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.  

---

### Answer by username_1 on 2012-10-07. Score: 6

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](http://cstheory.blogoverflow.com/2011/07/quantum-query-complexity/). 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](https://cstheory.stackexchange.com/questions/7413/trade-off-between-time-and-query-complexity). 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).

> **Comments:**
> **username_0**: 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?  
> **username_1**: @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.  

---

