# Arbitrary Polynomial Separations in Trainable Quantum Machine Learning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 121 references that are in the map.
- First posted on arXiv 13 Feb 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Show and Tell: A Neural Image Caption Generator](https://mlsanity.com/paper/1411.4555/) (2014)
- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Barren plateaus in quantum neural network training landscapes](https://mlsanity.com/paper/1803.11173/) (2018)
- [Quantum Machine Learning](https://mlsanity.com/paper/1611.09347/) (2016)
- [The Loss Surfaces of Multilayer Networks](https://mlsanity.com/paper/1412.0233/) (2014)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [Sustainable AI: Environmental Implications, Challenges and Opportunities](https://mlsanity.com/paper/2111.00364/) (2021)
- [Connecting ansatz expressibility to gradient magnitudes and barren plateaus](https://mlsanity.com/paper/2101.02138/) (2021)
- [Theory of overparametrization in quantum neural networks](https://mlsanity.com/paper/2109.11676/) (2021)
- [The Landscape of Empirical Risk for Non-convex Losses](https://mlsanity.com/paper/1607.06534/) (2016)
- [Effect of barren plateaus on gradient-free optimization](https://mlsanity.com/paper/2011.12245/) (2020)
- [Does provable absence of barren plateaus imply classical simulability?](https://mlsanity.com/paper/2312.09121/) (2023)
- [The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine](https://mlsanity.com/paper/1904.02214/) (2019)
- [Continuous-variable quantum neural networks](https://mlsanity.com/paper/1806.06871/) (2018)
- [On the Quantum versus Classical Learnability of Discrete Distributions](https://mlsanity.com/paper/2007.14451/) (2020)
- [Group-Invariant Quantum Machine Learning](https://mlsanity.com/paper/2205.02261/) (2022)
- [Enhancing Generative Models via Quantum Correlations](https://mlsanity.com/paper/2101.08354/) (2021)
- [Trainability barriers and opportunities in quantum generative modeling](https://mlsanity.com/paper/2305.02881/) (2023)
- [On Learning Rates and Schr"odinger Operators](https://mlsanity.com/paper/2004.06977/) (2020)
- [Faster Matrix Multiplication via Asymmetric Hashing](https://mlsanity.com/paper/2210.10173/) (2022)
- [Accelerated Gradient Methods for Nonconvex Optimization: Escape Trajectories From Strict Saddle Points and Convergence to Local Minima](https://mlsanity.com/paper/2307.07030/) (2023)
- [Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model](https://mlsanity.com/paper/2311.14123/) (2023)
- [Contextual Semantics: From Quantum Mechanics to Logic, Databases, Constraints, and Complexity](https://mlsanity.com/paper/1406.7386/) (2014)
- [Contextuality Analysis of Impossible Figures](https://mlsanity.com/paper/2008.04053/) (2020)

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

- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [Entanglement-induced provable and robust quantum learning advantages](https://mlsanity.com/paper/2410.03094/) (2024)
- [Quantum Theory and Application of Contextual Optimal Transport](https://mlsanity.com/paper/2402.14991/) (2024)
- [Let the Quantum Creep In: Designing Quantum Neural Network Models by Gradually Swapping Out Classical Components](https://mlsanity.com/paper/2409.17583/) (2024)
- [Quantum-Inspired Contextual Learning for Sparse-Ring Fraud Detection in Dynamic Transaction Graphs](https://mlsanity.com/paper/2607.09704/) (2026)

## Abstract (arXiv)

Recent theoretical results in quantum machine learning have demonstrated a general trade-off between the expressive power of quantum neural networks (QNNs) and their trainability; as a corollary of these results, practical exponential separations in expressive power over classical machine learning models are believed to be infeasible as such QNNs take a time to train that is exponential in the model size. We here circumvent these negative results by constructing a hierarchy of efficiently trainable QNNs that exhibit unconditionally provable, polynomial memory separations of arbitrary constant degree over classical neural networks -- including state-of-the-art models, such as Transformers -- in performing a classical sequence modeling task. This construction is also computationally efficient, as each unit cell of the introduced class of QNNs only has constant gate complexity. We show that contextuality -- informally, a quantitative notion of semantic ambiguity -- is the source of the expressivity separation, suggesting that other learning tasks with this property may be a natural setting for the use of quantum learning algorithms.