A rigorous definition for an exponential quantum advantage

Question

Let's assume that we have an algorithmic problem to solve. This problem takes an integer $n$ as input to describe it and provides as output a bit string providing the answer we are expecting.

For some tasks, such as factoring, quantum computers are expected to provide an exponential advantage, meaning that the best-known classical algorithms required to solve the task will require "exponentially more" operations than the quantum computer as a function of the input $n$ (which in this case is typically the size in bits of the encryption key).

My question is about a precise and rigorous definition of this "exponentially more" operations.

I would expect to say "there is an exponential quantum advantage" if the ratio $N_C(n)/N_Q(n)=\Omega(e^{Poly(n)})$ for $Poly(n)$ some polynome in $n$ (where $N_C(n)$ is the number of classical operations and $N_Q(n)$ the number of quantum operations).

A trivial example is for instance $N_Q(n)=Poly_Q(n)$ and $N_C(n)=e^{Poly_C(n)}$ where $Poly_Q$ and $Poly_C$ are some polynomes in $n$. However the following example would also fall in the same class (and I don't know if people call this "exponential advantage" as well):

$$N_C(n)=e^{n}, N_Q(n)=e^{0.999*n} \Rightarrow N_C(n)/N_Q(n)=e^{0.001 n}$$

My doubts about defining it as an exponential advantage are that (i) both algorithms grow exponentially as a function of the input $n$, (ii) that two very tiny differences in the polynome would still make the quantum computer exponentially more efficient. Finally (iii), I have never seen a classical/quantum comparison in which both algorithms grow exponentially as a function of $n$ (typically the quantum algo is polynomial while the classical is exponential as a function of the input in all the examples that I have seen).

Now, of course, there is some degree of freedom in choosing the input and we can probably always redefine the problem in such a manner that both classical & quantum grow exponentially as a function of "some" parameter. Finally, "tiny" differences grow "big" at infinity so (ii) is not really a valid point. But still, I find this little example a bit "disturbing" and that's why I am not sure if people still call it "exponential advantage".

My questions in summary

1. Is there a widely accepted definition of exponential quantum advantage? If so, where is a good reference in which it is written?
2. If according to this definition my last example doesn't fit in, why would that be the case (said differently, every definition has a motivation. I would expect my last example to be an exponential advantage but if it appears it doesn't fit the definition I would like to understand what motivates this definition then).

[edit] I actually found a ref in which the definition I used here seems to be used but I don't know if all the community agrees on that. Look at 6mn58s of this video.

Answer 1

The right definition in most Quantum Computing has to be: Algorithm Q has an $f$-ial speedup over Algorithm C if the running times $T_Q(n)$ and $T_C(n)$ satisfy $T_C(n) \in \Omega(f(T_Q(n))$

where $f$ is something like a quadratic, cubic, quartic, exponential, etc. function.

Consider the case of a Brute force classical SAT algorithm ($O(2^n)$) and a Grover SAT search ($O((\sqrt{2})^n)$). The community calls this a quadratic speedup. On your definition this would be an exponential speedup.

Edit: After a discussion with a colleague I'm not sure that this is everyone's clear intuition and the definition provided by OP, and the talk that is linked, plus some discussion in the comments have led me to believe that there is some confusion about what it means to provide an exponential / polynomial /etc. speedup.

Answer 2

The definition you provided isn't the correct definition. In computer science, time complexity refers to how the runtime of an algorithm scales with respect to your problem size. When we talk about a quantum exponential advantage, we mean that if a classical computer can solve the problem in a certain number of steps, a quantum computer can solve an exponentially larger instance of the same problem in an asymptotically similar number of steps. Is this the case with your definition? In the example you provided, even doubling the problem size makes the quantum computer slower than the classical one, let alone exponentiating the problem size!

The definition you provided is more like "how many times faster will one algorithm finish than the other given the same problem size, as a function of the problem size?" which is also an important question, for example, amplitude amplification provides a quadratic speedup over classical search which means as you increase the size of the problem the advantage becomes larger and larger, with 100 you get 10 times the speed up but with 1,000,000,000,000 you get a 1,000,000 time speed up, and if you choose to set $N = 2^n$ you get an exponential advantage with your definition. But is the algorithm/approach itself fundamentally exponentially more efficient when you take the problem size out of it? Take the following classical example of searching in a sorted list:

"Look at every single element in the worst case" - Linear search

"Look at a logarithmic number of elements in the worstcase" - Binary search

From the wording alone you can see that the algorithm or the approach itself is fundementally more efficient than the other in an exponential way. In other words, you can write the runtime of one as an exponential function of the other. Which motivates the following definition, there is an exponential quantum advantage if:

$$\exists \> b\in \mathbb{R_{>1}} \>\> s.t. \>\>N_C(n) = b^{N_Q(n)}$$