Short answer: In 2018 Ewin Tang published a classical algorithm for recommendation systems that matches a quantum algorithm by Kerenidis and Prakash to within a polynomial factor. As a consequence, the paper says that quantum algorithm does not give an exponential speedup over classical algorithms. The result is theoretical and holds under stated assumptions about how the input data is stored.
What was the specific algorithmic breakthrough?
The core contribution is a classical analogue to the quantum recommendation system proposed by Kerenidis and Prakash. That quantum algorithm was previously believed to be one of the strongest candidates for provably exponential speedups in quantum machine learning. Tang’s work provides a classical alternative that operates on an m by n matrix. The algorithm requires a data structure supporting certain l2-norm sampling operations. It outputs an l2-norm sample from a rank-k approximation of the input matrix, in time polynomial in k and logarithmic in the matrix size. This complexity is only polynomially slower than the corresponding quantum algorithm.
Does the quantum algorithm still have an advantage?
No, not in the context of this specific recommendation task. The existence of the classical algorithm implies that Kerenidis and Prakash’s quantum algorithm does not in fact give an exponential speedup over classical algorithms. The classical method achieves a complexity that is polynomially related to the quantum method, rather than exponentially worse. The paper presents this as a challenge to the earlier belief about this specific task.
How does the classical method compare to previous classical systems?
The paper says that, under strong input assumptions, the classical recommendation system resulting from Tang’s algorithm produces recommendations exponentially faster than previous classical systems. Earlier classical systems for this task ran in time linear in the matrix dimensions. The new algorithm reduces this dependence to a logarithmic dependence on the matrix size. The paper reports this as an improvement over the linear-time prior systems. The speedup is exponential relative to those older classical baselines, even though the new classical algorithm is only polynomially slower than the quantum algorithm.
What are the technical prerequisites and limitations?
The algorithm is not universally applicable without specific data structures. It requires the input matrix to be stored in a data structure that supports certain l2-norm sampling operations. The speedup over previous classical systems is conditional on "strong input assumptions." Without these specific structural and input conditions, the exponential speedup over older classical methods may not hold. The work focuses on the theoretical complexity bounds and the existence of the algorithm. It does not claim operational deployment or commercial availability. In a blog post, the author says the core sampling ideas are "super simple" and aims to build intuition for quantum researchers.
FAQ
What did Tang's paper show?
A classical analogue to Kerenidis and Prakash's quantum recommendation algorithm, which had been believed to be one of the strongest candidates for provably exponential speedups in quantum machine learning.
How fast is the classical algorithm?
It runs in time polynomial in the rank k and logarithmic in the matrix size, which the paper says is only polynomially slower than the quantum algorithm.
Does the quantum algorithm still give an exponential speedup?
According to the paper, no. As a consequence of the classical result, Kerenidis and Prakash's algorithm does not give an exponential speedup over classical algorithms.
What assumptions does it need?
The matrix must be stored in a data structure supporting certain l2-norm sampling operations. The speedup over earlier classical systems holds under strong input assumptions.
Does this mean quantum machine learning has no advantage?
No. The paper is about this specific recommendation task. It makes no claim about other problems and describes no deployment.
All field notes