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?

$\endgroup$

2 Answers 2

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

$\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$ Apr 10 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
    Apr 11 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
    Apr 11 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
    Apr 11 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
    Apr 11 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

$\endgroup$

Your Answer

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

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