An Improved Classical Singular Value Transformation for Quantum Machine Learning

Quantum machine learning (QML) has shown great potential to produce killer applications of quantum computers by introducing the possibility of large quantum speedups for computationally intensive linear algebra tasks. The quantum singular value transformation (QSVT), introduced by Gily\'en, Su, Low and Wiebe, is a unifying framework to obtain QML algorithms. We provide a classical algorithm that matches the performance of QSVT, up to a small polynomial overhead. In particular, given a bounded matrix $A\in\mathbb{C}^{m\times n}$, a vector $b\in\mathbb{C}^{n}$, and a bounded degree-$d$ polynomial $p$, QSVT can output a measurement from the state $|p(A)b\rangle$ in $O(d\|A\|_F )$ time. We show that for any $\epsilon >0$, we can output a vector $v$ such that $\|v-p(A)b\|\le\epsilon$ in $O(d^9\|A\|_F^4/\epsilon^2)$ time after linear-time pre-processing. This improves upon the best known classical algorithm [CGL+'20], which requires $O(d^{22}\|A\|_F^6/\epsilon^6)$ time. Instantiating our algorithm with different polynomials, we obtain fast quantum-inspired algorithms for regression/matrix inversion, recommendation systems and Hamiltonian simulation. We improve upon several recent papers specialized to specific problems, including [CGL+'20,SM'21,GST'22,CCH+'22} for regression, and [Tan'19,CGL+'20,CCH+'22] for recommendation systems. Our key insight is to combine the Clenshaw recurrence, an iterative method for computing matrix polynomials, with sketching techniques to simulate QSVT classically. The tools we introduce include (a) a non-oblivious matrix sketch for approximately preserving bi-linear forms, (b) a non-oblivious asymmetric approximate matrix product sketch based on $\ell_2^2$ sampling, (c) a new stability analysis for the Clenshaw recurrence, and (d) a new technique to bound arithmetic progressions of the coefficients appearing in the Chebyshev expansion of bounded functions.