# Prospects for quantum advantage in machine learning from the representability of functions

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 73 references that are in the map.
- First posted on arXiv 17 Dec 2025.

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

- [Variational Quantum Algorithms](https://mlsanity.com/paper/2012.09265/) (2020)
- [Power of data in quantum machine learning](https://mlsanity.com/paper/2011.01938/) (2020)
- [The effect of data encoding on the expressive power of variational quantum machine learning models](https://mlsanity.com/paper/2008.08605/) (2020)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [Supervised quantum machine learning models are kernel methods](https://mlsanity.com/paper/2101.11020/) (2021)
- [Barren Plateaus in Variational Quantum Computing](https://mlsanity.com/paper/2405.00781/) (2024)
- [Quantum machine learning beyond kernel methods](https://mlsanity.com/paper/2110.13162/) (2021)
- [Does provable absence of barren plateaus imply classical simulability?](https://mlsanity.com/paper/2312.09121/) (2023)
- [Classical surrogates for quantum learning models](https://mlsanity.com/paper/2206.11740/) (2022)
- [Quantum Convolutional Neural Networks are Effectively Classically Simulable](https://mlsanity.com/paper/2408.12739/) (2024)
- [Shadows of quantum machine learning](https://mlsanity.com/paper/2306.00061/) (2023)
- [Exponential separations between classical and quantum learners](https://mlsanity.com/paper/2306.16028/) (2023)
- [On the relation between trainability and dequantization of variational quantum learning models](https://mlsanity.com/paper/2406.07072/) (2024)
- [Potential and limitations of random Fourier features for dequantizing quantum machine learning](https://mlsanity.com/paper/2309.11647/) (2023)
- [Tensor network approaches for learning non-linear dynamical laws](https://mlsanity.com/paper/2002.12388/) (2020)
- [Minimizing low-rank models of high-order tensors: Hardness, span, tight relaxation, and applications](https://mlsanity.com/paper/2210.11413/) (2022)

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

- [A PAC-Bayesian approach to generalization for quantum models](https://mlsanity.com/paper/2603.22964/) (2026)
- [Theory and interpretability of Quantum Extreme Learning Machines: a Pauli-transfer matrix approach](https://mlsanity.com/paper/2602.18377/) (2026)
- [Quantum Reservoir Computing: Recent Advances and Future Directions](https://mlsanity.com/paper/2607.18552/) (2026)
- [Cautious optimism for deep parameterized quantum circuits](https://mlsanity.com/paper/2607.21409/) (2026)

## Abstract (arXiv)

Demonstrating quantum advantage in machine learning tasks requires navigating a complex landscape of proposed models and algorithms. To bring clarity to this search, we introduce a framework that connects the structure of parametrized quantum circuits to the mathematical nature of the functions they can actually learn. Within this framework, we show how fundamental properties, like circuit depth and non-Clifford gate count, directly determine whether a model's output leads to efficient classical simulation or surrogation. We argue that this analysis uncovers common pathways to dequantization that underlie many existing simulation methods. More importantly, it reveals critical distinctions between models that are fully simulatable, those whose function space is classically tractable, and those that remain robustly quantum. This perspective provides a conceptual map of this landscape, clarifying how different models relate to classical simulability and pointing to where opportunities for quantum advantage may lie.