自HHL提出的经典线性系统求解量子算法以及Kerenidis和Prakash随后提出的量子推荐系统算法以来，实现重要机器学习任务的可证明的量子指数加速一直是研究的核心目标。这些算法最初被认为是实现量子指数加速的强大候选者，但排除类似经典改进的下界一直未能出现。在Tang的一项突破性工作中，这种经典下界进展缓慢的原因得到了明确解释。具体而言，她给出了量子推荐系统算法的经典对应版本，将量子优势降低为单纯的多项式复杂度。她的方法非常通用，并被称为受量子启发的经典算法。自那时起，几乎所有最初声称的量子机器学习指数加速都被新的受量子启发的经典算法降级为多项式复杂度。从当前的研究状况来看，我们尚不清楚是否可以期望对于任何自然的机器学习任务实现量子指数加速。在这项工作中，我们展示了在输入矩阵条件良好且具有稀疏行和列的基本线性系统求解问题上，量子算法与受量子启发的经典算法之间首次可证明的指数分离。

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 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.