# An Improved Classical Singular Value Transformation for Quantum Machine Learning

arXiv: https://arxiv.org/abs/2303.01492 · HTML: https://mlsanity.com/paper/2303.01492/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2023.

## Built on by (most cited first, 5 of 5)

- [Quantum-Inspired Machine Learning: a Survey](https://mlsanity.com/paper/2308.11269/) (2023)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [Krylov Methods are (nearly) Optimal for Low-Rank Approximation](https://mlsanity.com/paper/2304.03191/) (2023)
- [An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems](https://mlsanity.com/paper/2411.02087/) (2024)
- [A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features](https://mlsanity.com/paper/2609.10729/) (2026)

## Abstract (arXiv)

We study quantum speedups in quantum machine learning (QML) by analyzing the quantum singular value transformation (QSVT) framework. QSVT, introduced by [GSLW, STOC'19, arXiv:1806.01838], unifies all major types of quantum speedup; in particular, a wide variety of QML proposals are applications of QSVT on low-rank classical data. We challenge these proposals by providing a classical algorithm that matches the performance of QSVT in this regime up to a small polynomial overhead. We show that, given a matrix A ∈ mathbbCm× n, a vector b ∈ mathbbCn, a bounded degree-d polynomial p, and linear-time pre-processing, we can output a description of a vector v such that |v - p(A) b| ≤ varepsilon|b| in widetildeO(d11 |A|F4 / (varepsilon2 |A|4 )) time. This improves upon the best known classical algorithm [CGLLTW, STOC'20, arXiv:1910.06151], which requires widetildeO(d22 |A|F6 /(varepsilon6 |A|6 ) ) time, and narrows the gap with QSVT, which, after linear-time pre-processing to load input into a quantum-accessible memory, can estimate the magnitude of an entry p(A)b to varepsilon|b| error in widetildeO(d|A|F/(varepsilon |A|)) time. Our key insight is to combine the Clenshaw recurrence, an iterative method for computing matrix polynomials, with sketching techniques to simulate QSVT classically. We introduce several new classical techniques in this work, including (a) a non-oblivious matrix sketch for approximately preserving bi-linear forms, (b) a new stability analysis for the Clenshaw recurrence, and (c) a new technique to bound arithmetic progressions of the coefficients appearing in the Chebyshev series expansion of bounded functions, each of which may be of independent interest.