[jaddood]

From the paper,

> The only difference between Theorem 1 and its quantum equivalent in [13] is that the quantum algorithm has no ε approximation factors (so ε=0 and 1/ε does not appear in the runtime). Thus, we can say that our algorithm performs just as well, up to polynomial slowdown and ε approximation factors.

With ε being the accepted margin of error, theorem 1 being the algorithm produced by Tang, and [13] being a reference to Kerenidis and Prakash's quantum algorithm kept here in the quote for fidelity of quoting.

This means that this algorithm is not really a substitue for the quantum algorithm because it will require a level of error to be accepted (something which might work in recommendation engines, but not necessarily outside that context) and it still has polynomial slowdown over the quantum algorithm. One thing to note is that not all quantum algorithms will perform exponenttially better than their classical counterparts. Particularily, some quantum search algorithms perform only quadratically better than the classical search algorithms. This means that even if an exponential speedup was not achieved by quantum computers, (which it still is because of the ε factor meaning they don't give the same results) it is expected that they still achieve polynomial speedup as they do in this case.

In conclusion, stating that this algorithm threatens the prospects of quantum computation is probably an exageration.