# Potential and limitations of random Fourier features for dequantizing quantum machine learning

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 42 references that are in the map.
- First posted on arXiv 20 Sep 2023.

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

- [Variational Quantum Algorithms](https://mlsanity.com/paper/2012.09265/) (2020)
- [The effect of data encoding on the expressive power of variational quantum machine learning models](https://mlsanity.com/paper/2008.08605/) (2020)
- [Parameterized quantum circuits as machine learning models](https://mlsanity.com/paper/1906.07682/) (2019)
- [Supervised quantum machine learning models are kernel methods](https://mlsanity.com/paper/2101.11020/) (2021)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [Quantum machine learning beyond kernel methods](https://mlsanity.com/paper/2110.13162/) (2021)
- [Encoding-dependent generalization bounds for parametrized quantum circuits](https://mlsanity.com/paper/2106.03880/) (2021)
- [On the Error of Random Fourier Features](https://mlsanity.com/paper/1506.02785/) (2015)
- [Exploiting symmetry in variational quantum machine learning](https://mlsanity.com/paper/2205.06217/) (2022)
- [Group-Invariant Quantum Machine Learning](https://mlsanity.com/paper/2205.02261/) (2022)
- [Expressive power of tensor-network factorizations for probabilistic modeling, with applications from hidden Markov models to quantum machine learning](https://mlsanity.com/paper/1907.03741/) (2019)
- [Classical surrogates for quantum learning models](https://mlsanity.com/paper/2206.11740/) (2022)
- [Optimal Rates for Random Fourier Features](https://mlsanity.com/paper/1506.02155/) (2015)
- [Input Redundancy for Parameterized Quantum Circuits](https://mlsanity.com/paper/1901.11434/) (2019)
- [Shadows of quantum machine learning](https://mlsanity.com/paper/2306.00061/) (2023)
- [Lower and Upper Bounds on the VC-Dimension of Tensor Network Models](https://mlsanity.com/paper/2106.11827/) (2021)

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

- [Does provable absence of barren plateaus imply classical simulability?](https://mlsanity.com/paper/2312.09121/) (2023)
- [On the relation between trainability and dequantization of variational quantum learning models](https://mlsanity.com/paper/2406.07072/) (2024)
- [On fundamental aspects of quantum extreme learning machines](https://mlsanity.com/paper/2312.15124/) (2023)
- [On the expressivity of embedding quantum kernels](https://mlsanity.com/paper/2309.14419/) (2023)
- [A Comparative Analysis of Adversarial Robustness for Quantum and Classical Machine Learning Models](https://mlsanity.com/paper/2404.16154/) (2024)
- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [Artificial intelligence for representing and characterizing quantum systems](https://mlsanity.com/paper/2509.04923/) (2025)
- [Double descent in quantum kernel methods](https://mlsanity.com/paper/2501.10077/) (2025)
- [Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits](https://mlsanity.com/paper/2408.12199/) (2024)
- [Opportunities and limitations of explaining quantum machine learning](https://mlsanity.com/paper/2412.14753/) (2024)
- [Spectral Bias in Variational Quantum Machine Learning](https://mlsanity.com/paper/2506.22555/) (2025)
- [Prospects for quantum advantage in machine learning from the representability of functions](https://mlsanity.com/paper/2512.15661/) (2025)
- [Spectral methods: crucial for machine learning, natural for quantum computers?](https://mlsanity.com/paper/2603.24654/) (2026)
- [Prospects of Privacy Advantage in Quantum Machine Learning](https://mlsanity.com/paper/2405.08801/) (2024)
- [On the similarity of bandwidth-tuned quantum kernels and classical kernels](https://mlsanity.com/paper/2503.05602/) (2025)
- [Demonstration of Efficient Predictive Surrogates for Large-scale Quantum Processors](https://mlsanity.com/paper/2507.17470/) (2025)
- [Non-variational supervised quantum kernel methods: a review](https://mlsanity.com/paper/2604.07896/) (2026)
- [Enhancing the Scalability of Classical Surrogates for Real-World Quantum Machine Learning Applications](https://mlsanity.com/paper/2508.06131/) (2025)
- [Theory and interpretability of Quantum Extreme Learning Machines: a Pauli-transfer matrix approach](https://mlsanity.com/paper/2602.18377/) (2026)
- [Optimal algorithmic complexity of inference in quantum kernel methods](https://mlsanity.com/paper/2604.15214/) (2026)
- [Connecting phases of matter to the flatness of the loss landscape in analog variational quantum algorithms](https://mlsanity.com/paper/2506.13865/) (2025)
- [Mitigating Bias in Low-SNR Financial Reinforcement Learning via Quantum Representations](https://mlsanity.com/paper/2606.10448/) (2026)

## Abstract (arXiv)

Quantum machine learning is arguably one of the most explored applications of near-term quantum devices. Much focus has been put on notions of variational quantum machine learning where parameterized quantum circuits (PQCs) are used as learning models. These PQC models have a rich structure which suggests that they might be amenable to efficient dequantization via random Fourier features (RFF). In this work, we establish necessary and sufficient conditions under which RFF does indeed provide an efficient dequantization of variational quantum machine learning for regression. We build on these insights to make concrete suggestions for PQC architecture design, and to identify structures which are necessary for a regression problem to admit a potential quantum advantage via PQC based optimization.