An Improved Classical Singular Value Transformation for Quantum Machine Learning

Understand

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 \in \mathbb{C}^{m\times n}$, a vector $b \in \mathbb{C}^{n}$, 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\| \leq \varepsilon\|b\|$ in $\widetilde{\mathcal{O}}(d^{11} \|A\|_{\mathrm{F}}^4 / (\varepsilon^2 \|A\|^4 ))$ time.