An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems

Achieving a provable exponential quantum speedup for an important machine learning task has been a central research goal since the seminal HHL quantum algorithm for solving linear systems and the subsequent quantum recommender systems algorithm by Kerenidis and Prakash. These algorithms were initially believed to be strong candidates for exponential speedups, but a lower bound ruling out similar classical improvements remained absent. In breakthrough work by Tang, it was demonstrated that this lack of progress in classical lower bounds was for good reasons. Concretely, she gave a classical counterpart of the quantum recommender systems algorithm, reducing the quantum advantage to a mere polynomial. Her approach is quite general and was named \emph{quantum-inspired classical} algorithms. Since then, almost all the initially exponential quantum machine learning speedups have been reduced to polynomial via new quantum-inspired classical algorithms. From the current state-of-affairs, it is unclear whether we can hope for exponential quantum speedups for any natural machine learning task. In this work, we present the first such provable exponential separation between quantum and quantum-inspired classical algorithms for the basic problem of solving a linear system when the input matrix is well-conditioned and has sparse rows and columns.

A major goal in quantum machine learning is to find important learning problems where quantum computers are provably exponentially faster than classical ones. Early algorithms for solving linear systems and recommender systems seemed to offer such speedups. However, later work by Tang showed that the recommender-system speedup could largely be matched by a new kind of classical algorithm inspired by the quantum method. This led to a broad program of “quantum-inspired” classical algorithms, which has since reduced most proposed exponential quantum machine-learning advantages to only polynomial ones. As a result, it has remained unclear whether natural machine-learning problems can truly admit exponential quantum speedups over the best known quantum-inspired classical methods. In this work, we give the first provable exponential separation of this kind. We show that quantum algorithms can be exponentially faster than quantum-inspired classical algorithms for the fundamental task of solving well-conditioned sparse linear systems.