Exponential quantum advantage in processing massive classical data

Broadly useful quantum advantage, particularly in classical data processing and machine learning, has remained a fundamental open question. 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, whereas any classical machine requires exponentially larger size or superpolynomially more samples and time. We validate these advantages in real-world applications including movie review sentiment analysis and single-cell RNA sequencing, demonstrating four to six orders of magnitude reduction in model size with fewer than $60$ logical qubits. These advantages are enabled by quantum oracle sketching, an algorithm for accessing the classical world in quantum superposition using only classical data samples. Combined with classical shadows, our algorithm circumvents the data loading and readout bottleneck to construct succinct classical models from large-scale classical data, a task provably impossible for any classical machine that is not exponentially larger than the quantum machine. Our hardness proofs are information-theoretic and unconditional, persisting even when classical machines are granted unlimited time or when $\mathsf{BPP} = \mathsf{BQP}$. Together, our results establish machine learning on classical data as a broad and natural domain of quantum advantage, and simultaneously as a fundamental test of quantum mechanics at the complexity frontier.