5
$\begingroup$

I would like to know if there are known quantum algorithms that provide a double exponential advantage compared to the best known classical algorithms.

More precisely, if the characteristics of the problem to simulate depend on an integer $n$, the quantum computer requires a number of gates polynomial in $n$ while the classical computer requires $\exp(\exp(P(n))$ gates where $P(n)$ is a polynome.

If there doesn't exist such an algorithm, is there some general proof that shows that a double exponential speedup is impossible with quantum computers?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
12
$\begingroup$

Classical computers can simulate quantum computers with an exponential overhead. Thus, there cannot be a doubly exponential speedup (unless maybe in some blackbox setting, cf Deutsch-Jozsa).

Improve this answer
$\endgroup$
12
  • 2
    $\begingroup$ If you don't count the time it takes to run the oracle (as an actual circuit), but count queries to the oracle, the story can be different -- at least in principle. E.g., in DJ & in a setting where you want a deterministic outcome and have deterministic classical computation, you need $2^n/2-1$ queries classically, but only one query quantumly. So the speedup -- in terms of queries to a black-box function -- is "as big as you wish", in some sense. --- I'm pretty sure you can get rid of this even in an oracle setting with suitable conditions, which is why I wrote "maybe". $\endgroup$
    – Norbert Schuch
    Commented Apr 10, 2022 at 13:54
  • 1
    $\begingroup$ @user253751 If $O(n)$ is exponentially faster than $O(2^n)$, then probably $O(1)$ vs $O(2^n)$ is something more than exponentially faster. $\endgroup$
    – eugenhu
    Commented Apr 11, 2022 at 12:52
  • 2
    $\begingroup$ @user253751 ? I'm not sure I understand, I thought the question you were asking Norbert was if Deutsch-Jozsa algorithm didn't count as more than "double exponential". I don't know if "speedup" is a commonly defined thing, but the question seems like it's saying a $O(f(n))$ algorithm vs $O(g(n))$ algorithm has $h$ speedup if $h(f(n))=g(n)$, or something like that. $\endgroup$
    – eugenhu
    Commented Apr 11, 2022 at 13:03
  • 1
    $\begingroup$ @user253751 Wait, in the D-J case, $f(n)=1$ for the quantum query complexity and $g(n)=2^n$ for the classical query complexity, there is no $h(x)$ that satisfies $h(f(n))=g(n)$ right? I don't see how it is $h(x)=x$. $\endgroup$
    – eugenhu
    Commented Apr 11, 2022 at 13:21
  • 2
    $\begingroup$ @user253751 Yes.. I didn't mean to start an extended discussion about this, so I'll just leave it at that unless you want to move this to a chat. $\endgroup$
    – eugenhu
    Commented Apr 11, 2022 at 13:28
2
$\begingroup$

There is a super exponential query reduction for a quantum algorithm that solves SEARCH WITH ADVICE problem for a power law advice distribution with average-case query complexity O(1) as N tends to infinity.Link to paper

Improve this answer
$\endgroup$

Your Answer

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

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