# Learning with Optimized Random Features: Exponential Speedup by Quantum Machine Learning without Sparsity and Low-Rank Assumptions

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Apr 2020.

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

- [On the expressivity of embedding quantum kernels](https://mlsanity.com/paper/2309.14419/) (2023)
- [Fock State-enhanced Expressivity of Quantum Machine Learning Models](https://mlsanity.com/paper/2107.05224/) (2021)
- [Consensus-based Distributed Quantum Kernel Learning for Speech Recognition](https://mlsanity.com/paper/2409.05770/) (2024)
- [Stochastic Gradient Line Bayesian Optimization for Efficient Noise-Robust Optimization of Parameterized Quantum Circuits](https://mlsanity.com/paper/2111.07952/) (2021)
- [Quantum Ridgelet Transform: Winning Lottery Ticket of Neural Networks with Quantum Computation](https://mlsanity.com/paper/2301.11936/) (2023)
- [Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learning](https://mlsanity.com/paper/2106.09028/) (2021)
- [Advantage of Quantum Machine Learning from General Computational Advantages](https://mlsanity.com/paper/2312.03057/) (2023)
- [Quantum diffusion map for nonlinear dimensionality reduction](https://mlsanity.com/paper/2106.07302/) (2021)
- [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)

Kernel methods augmented with random features give scalable algorithms for learning from big data. But it has been computationally hard to sample random features according to a probability distribution that is optimized for the data, so as to minimize the required number of features for achieving the learning to a desired accuracy. Here, we develop a quantum algorithm for sampling from this optimized distribution over features, in runtime O(D) that is linear in the dimension D of the input data. Our algorithm achieves an exponential speedup in D compared to any known classical algorithm for this sampling task. In contrast to existing quantum machine learning algorithms, our algorithm circumvents sparsity and low-rank assumptions and thus has wide applicability. We also show that the sampled features can be combined with regression by stochastic gradient descent to achieve the learning without canceling out our exponential speedup. Our algorithm based on sampling optimized random features leads to an accelerated framework for machine learning that takes advantage of quantum computers.