# Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 40 references that are in the map.
- First posted on arXiv 11 Apr 2023.

## Builds on (most cited first, 10 of 10)

- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions](https://mlsanity.com/paper/1811.00414/) (2018)
- [Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension](https://mlsanity.com/paper/1811.04909/) (2018)
- [Revisiting dequantization and quantum advantage in learning tasks](https://mlsanity.com/paper/2112.00811/) (2021)
- [Quantum-Inspired Support Vector Machine](https://mlsanity.com/paper/1906.08902/) (2019)
- [An improved quantum-inspired algorithm for linear regression](https://mlsanity.com/paper/2009.07268/) (2020)
- [Quantum-Inspired Classical Algorithms for Singular Value Transformation](https://mlsanity.com/paper/1910.05699/) (2019)
- [A Quantum-inspired Classical Algorithm for Separable Non-negative Matrix Factorization](https://mlsanity.com/paper/1907.05568/) (2019)
- [A Quantum-inspired Algorithm for General Minimum Conical Hull Problems](https://mlsanity.com/paper/1907.06814/) (2019)

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

- [Hybrid Quantum--Classical Machine Learning Potential with Variational Quantum Circuits](https://mlsanity.com/paper/2508.04098/) (2025)
- [Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm](https://mlsanity.com/paper/2605.13979/) (2026)
- [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)

Several quantum algorithms for linear algebra problems, and in particular quantum machine learning problems, have been "dequantized" in the past few years. These dequantization results typically hold when classical algorithms can access the data via length-squared sampling. In this work we investigate how robust these dequantization results are. We introduce the notion of approximate length-squared sampling, where classical algorithms are only able to sample from a distribution close to the ideal distribution in total variation distance. While quantum algorithms are natively robust against small perturbations, current techniques in dequantization are not. Our main technical contribution is showing how many techniques from randomized linear algebra can be adapted to work under this weaker assumption as well. We then use these techniques to show that the recent low-rank dequantization framework by Chia, Gily'en, Li, Lin, Tang and Wang (JACM 2022) and the dequantization framework for sparse matrices by Gharibian and Le Gall (STOC 2022), which are both based on the Quantum Singular Value Transformation, can be generalized to the case of approximate length-squared sampling access to the input. We also apply these results to obtain a robust dequantization of many quantum machine learning algorithms, including quantum algorithms for recommendation systems, supervised clustering and low-rank matrix inversion.