What are the bounds on quantum speedups under the various models of complexity? How big or small can they be?

Under the query model, my understanding is that the lower bound is $\Omega(\sqrt{N})$ as discussed in BBBV97 and established by Grover's algorithm. The upper bound is established by Forrelation, as shown by Aaronson and Ambainis. Using these, we can then define a quantum speedup as:


where $C$ is some appropriately selected classical algorithm, $Q$ our quantum algorithm, and the quantum speedup is bounded by $\Omega(\sqrt{N}) \le S \le {\Omega(\sqrt{N}/ \log N)}$.

Do we have similar bounds on quantum speedups under other models of complexity (e.g. gate, sample, space)? If so, references to the papers establishing these bounds would be great.

  • 2
    $\begingroup$ arxiv.org/pdf/2004.13231.pdf seems relevant $\endgroup$ – user1936752 Oct 21 '20 at 20:18
  • $\begingroup$ @user1936752 Thanks for sharing this, this actually brings up a point that may have been an oversight in my question. The Forrelation upper bound is with respect to a random classical algorithm, but the paper you linked provides a quartic rather than quadratic lower bound (as I indicated was due to Grover's algorithm), but is specifically with resepect to a deterministic classical algorithm. Can we draw equivalence between the deterministic v. random case? Am I making an apples to oranges comparison if I use Grover's as a lower bound? Are they only equivalent if P=BPP as has been conjectured? $\endgroup$ – Greenstick Oct 22 '20 at 23:28
  • $\begingroup$ Sorry, I'm not familiar enough with complexity to answer you but perhaps someone else here will! $\endgroup$ – user1936752 Oct 22 '20 at 23:29
  • $\begingroup$ No worries, thanks for sharing the paper! $\endgroup$ – Greenstick Oct 22 '20 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.