[tsucres]

The paper [1] states:

> There is a classical algorithm whose output distribution is O(ε)-close in total variation distance to the distribution given by l2-norm sampling from the ith row of a low- rank approximation D of A in query and time complexity [O(poly-func)] where δ is the probability of failure.

So the classical algorithm would give a "sufficiently close" approximation of what the QML would output? The article doesn't mention this at all. Is it fair to compare a quantum algorithm with an equivalent classical approximation algorithm?

From the quanta magazine article:

> Computer scientists had considered [the recommendation problem] to be one of the best examples of a problem that’s exponentially faster to solve on quantum computers — making it an important validation of the power of these futuristic machines. Now Tang has stripped that validation away.

Has he really?

[1] https://arxiv.org/pdf/1807.04271.pdf

[sheroze]

> As a consequence, we show that Kerenidis and Prakash’s quantum machine learning (QML) algorithm, one of the strongest candidates for provably exponential speedups in QML, does not, in fact, give an exponential speedup over classical algorithms.

The comparison is fair and the author is giving a metric to compare the algorithms too.

[HelloNurse]

The quantum algorithm is exact if it works, the new classical algorithm is negligibly worse at a negligibly higher cost.

Even if there's a formal difference, practical performance is what matters when discussing useful real-world applications as motivating examples for new and expensive technology.