Exponential quantum advantage in processing massive classical data
Haimeng Zhao, Alexander Zlokapa, Hartmut Neven, Ryan Babbush, John Preskill, Jarrod R. McClean, Hsin-Yuan Huang
Abstract
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 validate 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.
AI Impact Assessments
(3 models)Scientific Impact Assessment
1. Core Contribution
This paper addresses one of the most fundamental open problems in quantum computing: whether quantum machines can provide exponential advantages for processing classical data. The authors prove that a polylogarithmic-size quantum computer can perform classification, dimension reduction, and linear system solving on massive classical datasets, whereas any classical machine achieving comparable performance requires exponentially larger memory. The key innovation is quantum oracle sketching, an algorithm that constructs coherent quantum queries from streaming classical data samples by applying incremental quantum rotations on the fly—each sample is processed once and immediately discarded. This elegantly resolves the long-standing tension between quantum algorithms' need for coherent oracle access and the classical nature of real-world data, without requiring QRAM. Combined with interferometric classical shadows for efficient readout, the framework enables end-to-end construction of compact classical models from massive data.
2. Methodological Rigor
The paper is exceptionally rigorous, with a 144-page appendix containing detailed proofs. The theoretical framework rests on several pillars:
3. Potential Impact
Broad applicability: Unlike prior quantum advantages restricted to contrived or specialized problems, this work targets genuinely ubiquitous tasks—SVMs, PCA, and linear systems—that underpin machine learning, scientific computing, and data analysis across industries.
Memory wall relevance: The results directly address the "memory wall" problem in modern computing, where memory capacity has become the primary bottleneck (growing 410× slower than model parameters). This positions quantum computing as a solution to a pressing practical constraint.
Paradigm shift for quantum ML: The paper effectively rebuts widespread skepticism about quantum advantages for classical data by demonstrating that (1) QRAM is unnecessary, (2) noisy/correlated data can be handled, (3) dequantized algorithms still retain exponential space advantages, and (4) the readout bottleneck is solvable via interferometric classical shadows.
Fundamental physics implications: The authors frame their results as a test of quantum mechanics at the complexity frontier—experimental confirmation would probe the physical reality of exponentially large Hilbert spaces, analogous to Bell inequality tests for nonlocality.
4. Timeliness & Relevance
The paper arrives at a critical juncture: quantum error correction is becoming practical, memory constraints dominate AI scaling, and the field has been seeking concrete, broadly applicable quantum advantages beyond cryptanalysis and simulation. The work directly addresses the community's need for provable, practical quantum utility.
5. Strengths
6. Limitations & Considerations
7. Overall Assessment
This is a landmark contribution that fundamentally advances our understanding of quantum advantages for classical data processing. The combination of algorithmic innovation (quantum oracle sketching), rigorous unconditional lower bounds, and practical demonstrations on real datasets represents a rare achievement in quantum computing research. The work opens a genuinely new frontier by establishing that memory-efficient classical data processing is a natural domain of quantum advantage.
Generated Apr 10, 2026
Comparison History (261)
Paper 2 claims a provable exponential quantum advantage in a broadly applicable domain—classical data processing and machine learning—validated on real-world datasets (RNA sequencing, sentiment analysis) with modest qubit requirements. This addresses a fundamental open problem with wide cross-disciplinary impact and practical near-term relevance. Paper 1 offers a valuable but narrower contribution on trainability-simulability trade-offs in variational ansätze, primarily relevant to the quantum computing subfield. Paper 2's breadth, real-world demonstrations, and foundational significance give it substantially higher potential impact.
Paper 1 addresses a fundamental open problem—broadly applicable quantum advantage in classical data processing and ML—with rigorous complexity-theoretic proofs and real-world validation on genomics and NLP tasks using few qubits. Its claims of exponential advantage persisting even if BPP=BQP would be transformative across computing and ML if correct. Paper 2 is an elegant, rigorous experimental advance in chiral quantum optics with clear physical significance, but its impact is more confined to quantum simulation/optics communities. Paper 1's potential breadth and timeliness in the quantum-ML debate give it higher estimated impact, contingent on validity.
Paper 1 addresses a fundamental open problem in quantum computing—provable, broadly applicable quantum advantage for classical data processing—with rigorous complexity-theoretic proofs and real-world validation. Its claims of exponential advantage in machine learning could reshape the field and answer a longstanding theoretical question. Paper 2 presents a solid engineering advance in cryogenic control achieving 99.9% fidelity, but this is incremental progress on a known bottleneck with fidelity already near community standards. Paper 1's potential breadth, theoretical significance, and demonstrated applications give it substantially higher impact potential, assuming its bold claims withstand scrutiny.
Paper 1 claims an exponential quantum advantage for massive classical-data ML with polylog-size quantum resources, addresses core bottlenecks (data loading/readout), provides complexity-theoretic separations, and includes real-world validation on prominent datasets—all highly novel, timely, and broadly impactful across quantum computing, ML, and complexity theory. Paper 2 is methodologically strong and practically relevant for QEC, but its impact is more specialized to fault-tolerance/noise modeling. Overall, Paper 1 has greater potential breadth and headline-level significance if its assumptions and empirical demonstrations hold.
Paper 1 resolves a fundamental bottleneck in quantum machine learning by proving an exponential quantum advantage for classical data processing using only ~60 logical qubits. Its ability to circumvent the classical data loading issue has profound theoretical implications and massive cross-disciplinary applicability in big data and AI. While Paper 2 is a significant hardware achievement for quantum sensing, Paper 1's foundational algorithmic breakthrough offers a much broader scientific and technological impact, representing a paradigm shift in how quantum computers might outperform classical systems in real-world ML tasks.
Paper 1 addresses a fundamental open problem—broadly applicable quantum advantage for classical data processing and machine learning—with rigorous complexity-theoretic proofs and real-world validation (RNA sequencing, sentiment analysis). Its claim of exponential advantage persisting even if BPP=BQP is striking and could reshape quantum ML. Its breadth touches complexity theory, ML, and foundations of quantum mechanics. Paper 2 is a strong, methodologically rigorous advance in NQS simulation of 3D dynamics, but its impact is more confined to computational many-body physics. Paper 1's potential cross-field significance and foundational implications give it higher estimated impact.
Paper 2 likely has higher scientific impact: it claims an exponential, broadly applicable quantum advantage for massive classical-data tasks, provides complexity-theoretic separations, and proposes techniques (quantum oracle sketching + classical shadows) aimed at overcoming key practical bottlenecks (data loading/readout), with validations on real datasets. If correct, it influences quantum computing, ML, complexity theory, and experimental tests of quantum mechanics. Paper 1 is a strong engineering advance toward scalable photonic quantum tech, but its demonstrated efficiency is extremely low and the impact is more incremental and domain-specific compared with the potential cross-field, foundational implications of Paper 2.
Paper 2 likely has higher scientific impact because it demonstrates a major experimental scalability milestone (11,000 trapped atoms) with a practical, enabling hardware innovation (single metasurface tweezer generation) that can be adopted across atomic/AMO platforms, directly advancing near-term quantum computing roadmaps. Its methodological rigor is anchored in a clear, measurable achievement and characterization. Paper 1 is highly novel and broad in scope, but relies on strong theoretical advantage claims plus application demos whose real-world impact depends on assumptions about quantum data access and near-term implementability.
Paper 2 addresses a fundamental open problem in quantum computing—provable, broadly applicable quantum advantage on classical data. It combines rigorous complexity-theoretic proofs with real-world validation (RNA sequencing, sentiment analysis) and requires only ~60 logical qubits, making it timely and impactful across ML, data science, and quantum foundations. Paper 1 is elegant and novel for motional cat-state engineering in tweezers, but its impact is narrower, confined to a specific platform and near-term proof-of-principle. Paper 2's breadth, theoretical depth, and demonstrated applicability to massive datasets suggest substantially higher potential impact.
Paper 1 addresses a fundamental open problem in quantum computing—proving broadly applicable quantum advantage on classical data—with rigorous complexity-theoretic guarantees and validation on real-world datasets (RNA sequencing, sentiment analysis) using few qubits. If correct, this has transformative breadth across machine learning and quantum computing. Paper 2 presents an intriguing polaritonic result violating N-scaling, relevant to room-temperature quantum tech, but is narrower in scope and requires stronger validation of extraordinary claims. Paper 1's combination of provable advantage, broad applicability, and near-term feasibility gives it higher potential impact.