8
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ I should point out the Grover's search has an exponential in the running time, and for the equivalent classical algorithm. It only has a polynomial, not exponential speedup. $\endgroup$
    – DaftWullie
    May 9 at 13:25
  • 1
    $\begingroup$ My two cents: maybe a definition along the lines of there is an exponential advantage if for some polynomial $P$, the following holds: $$N_Q(n)=\mathcal{O}\left(\log\left(P\left(N_C(n)\right)\right)\right)$$ I find your question quite interesting! $\endgroup$ May 9 at 13:26
  • $\begingroup$ @DaftWullie Thank you for the comment. I have heard that Grover can be applied for RSA but I am a bit ignorant about its performances (I had in mind Shor algo in my text). In your comment did you mean that applying Grover to break RSA only provides a polynomial speedup (hence it is less effective than Shor which provides exp speedup, for this specific problem). $\endgroup$ May 9 at 16:42
  • 1
    $\begingroup$ @TristanNemoz Thanks! That could also be a well-motivated definition indeed! There are however other examples that I would consider "legitimate" that are outside of this definition. For instance $N_Q(n)=e^{\log(n)^a}$ where $a$ is some constant and $N_{Cl}=e^{n}$. I would somehow be tempted to say that there is an exponential speedup here (in a less trivial manner than the example in my text) and I don't think it fits in your suggestion. We can probably generalize a bit what you suggest in order to include such examples. But overall of course all this is subjective and I am wondering if a[...] $\endgroup$ May 9 at 17:07
  • 1
    $\begingroup$ @MarcoFellous-Asiani I don't mean specifically RSA (as you say, Shor is more appropriate in that case). There is a standard problem, which is basically searching an unsorted database. If it has $N=2^n$ entries, to find the one I'm interested in, classically I have to look at every entry to be certain of finding it. Grover's search required $O(\sqrt{N})$ queries only. $\endgroup$
    – DaftWullie
    May 10 at 7:03

2 Answers 2

2
+25
$\begingroup$

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)}$$

$\endgroup$
5
  • $\begingroup$ Hello. Thank you for your answer. Do you have a reference in which the definition you proposed is clearly stated? Since I wrote this question I actually found a talk in which the definition I used is also considered (look at my edit). My suspicion now is that there is not a universal definition on which everyone agrees. $\endgroup$ May 15 at 15:38
  • 1
    $\begingroup$ @MarcoFellous-Asiani I don't have a source but that's what it is understood to be. The definition doesn't really have anything to do with quantum computers but rather complexity theory in computer science in general. Universally it is agreed that Grover provides a quadratic speed up and not an exponential one for reasons I explained above. As I and many others have pointed out by your definition this assumption doesn't hold which is why that definition is not correct. $\endgroup$
    – Dani007
    May 15 at 20:15
  • $\begingroup$ I am coming back a bit late on this question but I am not sure this definition works in general. A first reason is that it is an equality (we could have some prefactor), but I am not sure it works even if we change the definition in big-O or big-Omega. For instance, if $N_C(n)=\exp(Pol_C(n))$ and $N_Q(n)=Pol_Q(n)$ ($Pol_Q,Pol_Q$ mean "some polynome"). $N_C/b^{N_Q}=\exp(Pol_C(n)-\ln(b) Pol_Q(n))$. We see that depending on the exact $Pol_Q$ and $Pol_C$, the ratio can either converge or diverge, whatever $b$ we choose. $\endgroup$ Aug 12 at 10:22
  • 1
    $\begingroup$ @MarcoFellous-Asiani The definition I gave was "you can write the runtime of one as an exponential function of the other". So I'm not sure how the example you gave is a counter-example since you're using different polynomials ($Poly_C$ and $Poly_Q$). It's important to note $b^n$ is not in the same asymptotic family as $b^{n^2}$. Since $b^{n^2}= (b^n)^n$ is an exponential of an exponential. $\endgroup$
    – Dani007
    Aug 13 at 15:35
  • $\begingroup$ Sorry my example was confusing, you are right. But consider $N_Q(n)=n^2$ and $N_C(n)=\exp(n)$. Wouldn't we expect to call naturally call it an exponential speedup (because the speed goes from polynomial to exponential) while we cannot write it $N_C(n)=b^{N_Q(n)}$? For instance, according to your definition I am not sure we would call Shor algorithm as providing an exponential speedup. $\endgroup$ Aug 16 at 15:59
2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thank you for your answer. Would you have some reference in which this general definition is provided? Thanks a lot. $\endgroup$ May 16 at 9:23
  • $\begingroup$ I was trying to formalise an intuition; can’t find a quantum-related source so quickly. You can look at the literature on Blum’s speedup theorem. They talk about speedups in this way. $\endgroup$
    – shashvat
    May 16 at 9:32
  • $\begingroup$ It seems that this paper has yet another interpretation of polynomial speedup, which excludes scaling altogether: arxiv.org/pdf/2011.04149.pdf It would be interesting to look at these three definitions of speedup, where they are used, and where confusions arise. $\endgroup$
    – shashvat
    May 16 at 13:43
  • 1
    $\begingroup$ I think that this paper you refer to uses a definition of speedup which agrees both with your definition and mine. This is because they compare $M^d$ operations classically with $M$ quantum. I would call it a polynomial speedup because the ratio of the two is polynomial (and you would also call it a polynomial speedup with your definition). $\endgroup$ May 17 at 6:48
  • 1
    $\begingroup$ I believe that your definition does not allow to distinguish power of polynomes because you ask $T_C(n) \in \Omega(f(T_Q(n))$. A lot of different powers could match. In my definition I could just ask that the ratio of the quantities grows as $\sim c n^2$ for some constant $c$ (I slightly extend my proposal). $\endgroup$ May 17 at 6:54

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.