Exponential quantum advantage in processing massive classical data

arXiv:2604.07639 · quant-ph, cs.AI, cs.CC, cs.IT, cs.LG, math.IT · Submitted 2026-04-08 · Read on arXiv

quant-ph, cs.AI, cs.CC, cs.IT, cs.LG, math.IT

Submitted: 2026-04-08

Updated: 2026-10-01

Comments: 169 pages, including 10 pages of main text and 13 figures. Code available at https://github.com/haimengzhao/quantum-oracle-sketching

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Sample Complexity — 109× in this paper · explained in 15 episodes
• Block Encoding — 60× in this paper · explained in 4 episodes
• Query Complexity — 49× in this paper · explained in 2 episodes
• Sparsity — 26× in this paper · explained in 4 episodes
• Noisy Oracle Property Estimation — 16× in this paper
• Regularization — 16× in this paper · explained in 3 episodes
• BQP — 13× in this paper · explained in 2 episodes
• Accuracy — 12× in this paper · explained in 1 episode
• Trace — 9× in this paper · explained in 2 episodes
• Ancilla Qubits — 8× in this paper · explained in 1 episode
• Foundations of Computer Science — 8× in this paper
• Quantum Circuits — 6× in this paper · explained in 2 episodes
• Benchmark — 5× in this paper · explained in 2 episodes
• Entanglement — 5× in this paper · explained in 4 episodes
• Trace Distance — 5× in this paper · explained in 3 episodes
• Hilbert Space — 4× in this paper · explained in 2 episodes
• Principal Component Analysis (PCA) — 4× in this paper · explained in 4 episodes
• Sample Efficiency — 4× in this paper · explained in 4 episodes
• Benchmarking — 3× in this paper · explained in 3 episodes
• Shadow Tomography — 3× in this paper · explained in 4 episodes
• Spectral Gap — 3× in this paper · explained in 5 episodes
• Transformer — 3× in this paper · explained in 2 episodes
• Adam — 2× in this paper · explained in 2 episodes
• Degeneracy — 2× in this paper · explained in 3 episodes
• Generative Model — 2× in this paper · explained in 2 episodes
• Generative Models — 2× in this paper · explained in 2 episodes
• Sample Complexity Scaling — 2× in this paper · explained in 2 episodes
• Catastrophic Forgetting — 1× in this paper · explained in 5 episodes
• Consistency — 1× in this paper · explained in 3 episodes
• Curse of Dimensionality — 1× in this paper · explained in 6 episodes
• Differentially Private — 1× in this paper · explained in 3 episodes
• Distillation — 1× in this paper · explained in 2 episodes
• Feature Selection — 1× in this paper · explained in 4 episodes
• Generalization — 1× in this paper · explained in 13 episodes
• Hybrid Approach — 1× in this paper · explained in 4 episodes
• Loss Function — 1× in this paper · explained in 2 episodes
• Redundancy — 1× in this paper · explained in 2 episodes
• Regret — 1× in this paper · explained in 3 episodes
• Robustness — 1× in this paper · explained in 5 episodes
• Scaling Laws — 1× in this paper · explained in 4 episodes
• Transformer Models — 1× in this paper · explained in 2 episodes
• Unified Framework — 1× in this paper · explained in 5 episodes

Sources

• The Grand Challenge of Quantum Applications
• Quantum measurements and the Abelian Stabilizer Problem
• The Need for Structure in Quantum Speedups
• A distillation-teleportation protocol for fault-tolerant QRAM
• Does provable absence of barren plateaus imply classical simulability?
• On the relation between trainability and dequantization of variational quantum learning models
• Exponential separations between classical and quantum learners
• Generative quantum advantage for classical and quantum problems
• Quantum Machine Learning: A Hands-on Tutorial for Machine Learning Practitioners and Researchers
• Scaling Laws for Neural Language Models
• Streaming Complexity of SVMs
• Realization of a Quantum Streaming Algorithm on Long-lived Trapped-ion Qubits
• Demonstrating an unconditional separation between quantum and classical information resources
• Quantum computing and the entanglement frontier
• On Query-to-Communication Lifting for Adversary Bounds
• Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
• Quantum Computing Enhanced Sensing
• A quantum algorithm to solve nonlinear differential equations
• Small quantum computers and large classical data sets
• Preconditioned quantum linear system algorithm

Related papers

• Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
• Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
• Polynomial-time classical and quantum simulation of quantum impurity models
• Theory of quantum-enhanced interferometry with general Markovian light sources
• A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
• Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity