A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features
Not on the map. Why?
Abstract (arXiv)
Quantum-inspired classical algorithms have dequantized several quantum machine learning routines by replacing quantum linear-algebra subroutines with classical counterparts. However, the sampler based on quantum singular value transformation (QSVT) for learning with optimized random features is not covered by existing dequantization frameworks, because the matrix to be inverted is not itself available through sampling access. In this work, we develop a classical algorithm to address this type of quantum-advantage candidate. Our method samples heavy indices, reduces the transformation to a small principal block, and outputs a sparse classical representation with operator-norm guarantees. Applying this method dequantizes the sampler for optimized random features, giving a classical sampler with prescribed accuracy and polynomially related runtime. These results show that the factorization underlying a quantum block encoding can itself provide sufficient classical structure even when sampling-and-query access to the composite matrix is unavailable.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 19 of its 36 references that are in the map. First posted on arXiv 9 Sep 2026.
Builds on
19 of 36 references.
References · 19
- 2020A rigorous and robust quantum speed-up in supervised machine learningcited by 271
- 2015On the Equivalence between Kernel Quadrature Rules and Random Feature Expansionscited by 138
- 2017Quantum machine learning: a classical perspectivecited by 95
- 2018Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guaranteescited by 71
- 2016Quantum Recommendation Systemscited by 70
- 2018A quantum-inspired classical algorithm for recommendation systemscited by 70
- 2019Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learningcited by 37
- 2023Exponential separations between classical and quantum learnerscited by 26
- 2015Quantum assisted Gaussian process regressioncited by 17
- 2022On establishing learning separations between classical and quantum machine learning with classical datacited by 15
- 2018Quantum-inspired sublinear classical algorithms for solving low-rank linear systemscited by 12
- 2020Learning with Optimized Random Features: Exponential Speedup by Quantum Machine Learning without Sparsity and Low-Rank Assumptionscited by 9
7 more
- 2019Random Fourier Features via Fast Surrogate Leverage Weighted Samplingcited by 8
- 2019On Sampling Random Features From Empirical Leverage Scores: Implementation and Theoretical Guaranteescited by 5
- 2023Quantum Ridgelet Transform: Winning Lottery Ticket of Neural Networks with Quantum Computationcited by 5
- 2023An Improved Classical Singular Value Transformation for Quantum Machine Learningcited by 5
- 2023Advantage of Quantum Machine Learning from General Computational Advantagescited by 4
- 2019Quantum-Inspired Classical Algorithms for Singular Value Transformationcited by 3
- 2023Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithmscited by 3
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2026Towards Surrogate Based Dequantization of Quantum Reinforcement Learning
- 2023Potential and limitations of random Fourier features for dequantizing quantum machine learning
- 2021Revisiting dequantization and quantum advantage in learning tasks
- 2024On the relation between trainability and dequantization of variational quantum learning models
- 2026Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm
- 2025Quantum Data Encoding and Variational Algorithms: A Framework for Hybrid Quantum Classical Machine Learning
- 2022Quantum Sparse Coding
- 2026Canonical quantization of neurons