# Exponential quantum advantage in processing massive classical data

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 210 references that are in the map.
- First posted on arXiv 8 Apr 2026.

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

- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Does provable absence of barren plateaus imply classical simulability?](https://mlsanity.com/paper/2312.09121/) (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)
- [Quantum Machine Learning: A Hands-on Tutorial for Machine Learning Practitioners and Researchers](https://mlsanity.com/paper/2502.01146/) (2025)
- [Generative quantum advantage for classical and quantum problems](https://mlsanity.com/paper/2509.09033/) (2025)
- [Memory-Sample Lower Bounds for Learning Parity with Noise](https://mlsanity.com/paper/2107.02320/) (2021)
- [Quantum Transformer: Accelerating model inference via quantum linear algebra](https://mlsanity.com/paper/2402.16714/) (2024)
- [A quantum algorithm for training wide and deep classical neural networks](https://mlsanity.com/paper/2107.09200/) (2021)
- [A unifying framework for differentially private quantum algorithms](https://mlsanity.com/paper/2307.04733/) (2023)
- [Streaming Complexity of SVMs](https://mlsanity.com/paper/2007.03633/) (2020)
- [Explainable quantum regression algorithm with encoded data structure](https://mlsanity.com/paper/2307.03334/) (2023)
- [Multi-Pass Streaming Lower Bounds for Approximating Max-Cut](https://mlsanity.com/paper/2503.23404/) (2025)
- [A Generalized Quantum Branching Program](https://mlsanity.com/paper/2307.11395/) (2023)

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

- [Optimal algorithmic complexity of inference in quantum kernel methods](https://mlsanity.com/paper/2604.15214/) (2026)
- [Measuring Accuracy and Energy-to-Solution of Quantum Fine-Tuning of Foundational AI Models](https://mlsanity.com/paper/2605.02798/) (2026)
- [Lie Group Diffusion Models for Hardware-Aware Quantum Circuit Synthesis](https://mlsanity.com/paper/2606.29636/) (2026)
- [Block-encodings as programming abstractions: The Eclipse Qrisp BlockEncoding Interface](https://mlsanity.com/paper/2604.18276/) (2026)
- [QAP-Router: Tackling Qubit Routing as Dynamic Quadratic Assignment with Reinforcement Learning](https://mlsanity.com/paper/2605.12365/) (2026)
- [Quantum-classical hybrid models based on error correction for time series forecasting](https://mlsanity.com/paper/2606.15213/) (2026)
- [When AI meets quantum information: A comprehensive review](https://mlsanity.com/paper/2607.00365/) (2026)
- [Classical Limits of Spectral Filtering in Quantum Generative Models](https://mlsanity.com/paper/2608.14169/) (2026)
- [A Hybrid Quantum Neural Network to Analyse Big Experimental Powder X-ray Diffraction Data](https://mlsanity.com/paper/2609.22376/) (2026)
- [Quantum Diffusion Models for Medical Image Analysis](https://mlsanity.com/paper/2609.31070/) (2026)
- [Quantum Computing for Network Security Classification: Near-Term Classification and Long-Term Memory Efficiency](https://mlsanity.com/paper/2609.36479/) (2026)

## Abstract (arXiv)

Broadly applicable quantum advantage, particularly in classical data processing and machine learning, has been a fundamental open problem. In this work, we prove that a small quantum computer of polylogarithmic size can perform large-scale classification and dimension reduction on massive classical data by processing samples on the fly, whereas any classical machine achieving the same prediction performance requires exponentially larger size. Furthermore, classical machines that are exponentially larger yet below the required size need superpolynomially more samples and time. We provide evidence for these quantum advantages in real-world applications, including single-cell RNA sequencing and movie review sentiment analysis, demonstrating four to six orders of magnitude reduction in size with fewer than 60 logical qubits. These quantum advantages are enabled by quantum oracle sketching, an algorithm for accessing the classical world in quantum superposition using only random classical data samples. Combined with classical shadows, our algorithm circumvents the data loading and readout bottleneck to construct succinct classical models from massive classical data, a task provably impossible for any classical machine that is not exponentially larger than the quantum machine. These quantum advantages persist even when classical machines are granted unlimited time or if BPP = BQP, and rely only on the correctness of quantum mechanics. Together, our results establish machine learning on classical data as a broad and natural domain of quantum advantage and a fundamental test of quantum mechanics at the complexity frontier.