# Are there quantum algorithms showing a double exponential advantage?

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?

• 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". Apr 10 at 13:54
• @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. Apr 11 at 12:52
• @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. Apr 11 at 13:03
• @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$. Apr 11 at 13:21