PaperlayerView exact revision on arXiv

Source-linked AI summary

Exponential quantum advantage in processing massive classical data

Haimeng Zhao, Alexander Zlokapa, Hartmut Neven, Ryan Babbush, John Preskill, Jarrod R. McClean, Hsin-Yuan Huang

arXiv:2604.07639v1quant-phcs.AIcs.CCcs.ITcs.LG

TL;DR

The paper asks whether quantum computers can achieve broad advantages for classical data processing despite classical data-loading and readout constraints. It introduces quantum oracle sketching with interferometric classical shadows to process samples on the fly and construct compact models. The results establish exponential space advantages, with four- to six-order-of-magnitude memory savings demonstrated using fewer than 60 logical qubits.

  • Problem

    Existing quantum machine-learning approaches require coherent access to classical data, while QRAM imposes substantial memory and fault-tolerance overhead.

  • Method

    Quantum oracle sketching builds coherent quantum queries from streaming samples, and interferometric classical shadows enable efficient readout into compact classical models.

  • Results

    Four- to six-order-of-magnitude memory savings are demonstrated with fewer than 60 logical qubits across classification and dimension-reduction experiments.

  • Takeaways & Limitations

    Classical data processing and machine learning constitute a broad domain of exponential quantum advantage, with separations that persist under unlimited classical time or BPP=BQP.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper addresses whether quantum advantages extend beyond specialized tasks to classical data processing and machine learning. It proposes processing samples on the fly to obtain exponential space advantages for natural tasks, supported by real-world experiments.

  • Quantum advantage has remained difficult to establish broadly because prior compelling end-to-end benefits were concentrated in specialized tasks such as cryptanalysis and quantum simulation.
  • Classical data access conflicts with quantum algorithms that require coherent superposition access, while QRAM introduces substantial fault-tolerance, control, and memory overhead.
  • Streaming, sketching, and online learning reduce classical machine size by processing samples incrementally, but sacrifice prediction accuracy.
  • The paper asks whether small quantum machines can leverage quantum Hilbert-space dimensionality to outperform exponentially larger classical machines.
  • A poly(log N)-size quantum computer processes massive data samples on the fly for classification, dimension reduction, and linear-system solving, while comparable classical machines require exponentially larger size or superpolynomially more samples and time.
  • Experiments on movie reviews and single-cell RNA sequencing report four- to six-order-of-magnitude size reductions using fewer than 60 logical qubits.
  • Quantum oracle sketching constructs coherent queries from streaming samples, and classical shadows help produce compact classical models from massive data.

II. MAIN RESULTS

The main results establish quantum space and sample-efficiency advantages for linear systems, classification, and dimension reduction, including dynamic settings. Experiments compare quantum oracle sketching with classical and QRAM-based approaches using memory-size versus performance curves.

  • Linear systems: A quantum computer of poly(log N) size solves linear-system tasks using ˜O(N) samples, whereas an O(N 0.99)-size classical machine cannot.
  • Linear systems: Dynamic linear systems preserve the quantum ˜O(N)-sample bound, while O(N 0.99)-size classical machines require superpoly(N) samples.
  • Classification: A poly(log D)-size quantum computer solves binary classification with ˜O(N) samples, whereas an O(D0.99)-size classical machine cannot.
  • Classification: Dynamic classification retains ˜O(N) quantum sample complexity, while O(D0.99)-size classical machines require superpoly(N) samples.
  • Dimension reduction: A poly(log D)-size quantum computer solves dimension reduction with ˜O(N) samples, whereas an O(D0.99)-size classical machine cannot.
  • Dimension reduction: Dynamic dimension reduction retains ˜O(N) quantum sample complexity, while O(D0.99)-size classical machines require superpoly(N) samples.
  • Experiments: Figure 2 compares memory size with classification accuracy and explained variance across quantum oracle sketching, QRAM-based quantum, sparse-matrix classical, and streaming algorithms.
  • Experiments: Four to six orders of magnitude in memory savings are achieved with fewer than 60 logical qubits because quantum-oracle-sketching memory remains nearly constant while classical and QRAM-based requirements grow exponentially.

A. Quantum Oracle Sketching

Quantum oracle sketching converts streaming classical samples into coherent quantum queries without storing the full dataset. Its error scaling, extensions, and sample costs determine when this approach preserves quantum advantage.

  • Quantum oracle sketching applies incremental quantum rotations to fresh classical samples, enabling quantum query algorithms without full-dataset storage.
  • Generic randomized Hamiltonian simulation can require M ∼N^2 samples for one query, eliminating potential quantum advantage.
  • For Boolean phase oracles, sampled basis-state rotations accumulate coherently from uniformly drawn data samples.
  • Choosing τ = πN makes empirical sample frequencies approximate the target phase accumulation for the phase oracle.
  • The phase-oracle construction achieves ϵ ∼N/M error, so M = Θ(N/ϵ) samples suffice in diamond distance.
  • A Q-query algorithm with total error ϵ requires each oracle sketch to use error ϵ/Q, producing total sample complexity proportional to NQ^2/ϵ.
  • The framework handles noisy, correlated, and time-varying data, with repetition increasing sample complexity proportionally.
  • Extensions use QSVT and related techniques to construct state-preparation unitaries, sparse oracles, and matrix block encodings for broader data structures.

B. Interferometric Classical Shadows

The paper addresses quantum readout after data loading by developing interferometric classical shadows. This enables compact classical representations that preserve task-relevant information without exponentially large classical memory.

  • Interferometric classical shadows combine the Hadamard test with efficient readout to retain sign structures needed for applications such as SVM classification.
  • The resulting procedure compresses relevant classical-data information into a compact classical representation while preserving accuracy, which classical machines cannot achieve without exponentially larger memory.

C. Classical Hardness

The paper establishes classical hardness by reducing quantum space advantage to separations in noisy-oracle query complexity. This framework yields exponential space advantages and superpolynomial sample requirements for insufficiently large classical machines.

  • Hardness framework: The authors connect machine-size advantage to query-complexity separation through the Noisy Oracle Property Estimation task.NOPE estimates properties of Boolean functions from noisy query data.
  • Proof mechanism: The space lower bound is obtained by scattering useful information across blocks of noisy samples that small-memory machines must carry across boundaries.Communication-complexity arguments formalize this information-transfer bottleneck.
  • Space lower bound: A classical machine of size S must satisfy S ≥ Ω(QC/Q^2) to match a quantum machine’s sample usage for a NOPE task.Here Q and QC denote the quantum and classical query complexities.
  • Exponential separation: When QC is exponentially large and quantum queries have a super-quadratic advantage, the theorem implies exponential quantum space advantage.For QC = Θ(N) and Q = O(N^0.49), the classical memory lower bound is S ≥ Ω(N^0.02).
  • Sample complexity: Classical machines lacking sufficient space require superpolynomially more samples because they cannot track dynamically evolving data distributions.The result follows from a learning version of the XOR lemma and reductions to target applications.

IV. DISCUSSION

The discussion presents classical data processing and machine learning as a broad domain of exponential quantum advantage, enabled by compact quantum-derived models. The results include practical memory savings, sample-complexity advantages, and unconditional information-theoretic separation, while runtime remains an important boundary.

  • Scope and separation: The paper establishes exponential quantum advantage across linear systems, binary classification, and dimension reduction in classical data processing and machine learning.The claimed separation reaches the limit permitted by quantum mechanics because classical machines can store and simulate the full dataset with near-linear size.
  • Mechanism: Quantum oracle sketching and interferometric classical shadows circumvent data-loading and readout bottlenecks to construct exponentially compact classical models.The paper argues that these models efficiently extract task-relevant structure without violating the generic Holevo bound.
  • Empirical relevance: Fewer than 60 logical qubits yielded orders-of-magnitude memory savings in numerical experiments.The paper extrapolates that hundreds of logical qubits could outperform extremely large classical systems, while ignoring exponential runtime overhead.
  • Runtime and samples: Quantum oracle sketching gives super-polynomial sample-complexity advantage on dynamic tasks, while each sample’s subsequent processing takes only poly(log N) time.The overall runtime is dominated by Õ(N) data loading when each gate has constant degrees of freedom.
  • Future directions: The framework is proposed for extension to additional tasks including differential equations, optimization, signal processing, communication, and recommendation systems.These extensions are presented as opportunities rather than established results of this work.
  • Foundational scope: The space advantage is unconditional and persists with unbounded classical computation time or even if BPP = BQP.The argument relies on quantum superposition rather than computational-complexity conjectures.

Appendices

The appendices organize the paper into background and setup, theoretical foundations, and applications. They separately develop quantum algorithms, classical-hardness machinery, and application-specific demonstrations.

  • Roadmap: The appendices begin with a roadmap and organize the material into three themes for navigating the technical development.The roadmap directs readers to background, theory, and applications.
  • Background and setup: Section B covers related work and contributions, while Section C introduces the models of data access and computation.Together these sections establish the background and formal setup.
  • Theoretical foundations: Sections D and E provide theoretical foundations for processing massive classical data on small quantum computers.Section D develops quantum algorithms; Section E develops classical-hardness proofs.
  • Quantum algorithms: Section D introduces quantum oracle sketching for IID Boolean-function data, addresses decoherence, proves optimality, and extends the method to matrices and vectors.The section develops the algorithm from a simple setting to more general data structures.
  • Classical hardness: Section E introduces NOPE and its dynamic variant, proves their classical hardness, and connects them to applications.This supplies the lower-bound machinery used in the paper’s application results.

Applications.

The appendices support the paper’s applications with intuitive figures, numerical experiments, implementation resources, and rigorous proofs. Readers can choose routes emphasizing applications, algorithms, or complexity theory.

  • Applications: Section F applies the theoretical tools to linear systems, binary classification, and dimension reduction with self-contained introductions and quantum-advantage statements.Detailed proofs follow each application using the theoretical foundations.
  • Suggested reading: Figures 8–10 present application results, while Figures 5–7 explain the formal setup, quantum oracle sketching, and classical-hardness intuition.The figures are designed to provide intuitive understanding before technical details.
  • Reader routes: General readers are directed to Section F and Figures 2 and 4, algorithm designers to Section D and implementation templates, and theory readers to Sections C–E.The routes are tailored to applications, algorithm design, and rigorous proofs.
  • Numerical experiments: Figure 4 compares quantum oracle sketching with classical sparse-matrix, QRAM-based quantum, and classical streaming algorithms on topic analysis and Thrombin binding data.It varies dimension truncation and plots machine size against cross-validation accuracy or explained variance.
  • Notation: The appendices define asymptotic notation such as O, Ω, Θ, o, ω, and poly(N) for the theoretical statements.A tilde suppresses factors that scale polynomially with log f(N).
  • Experimental program: The numerical appendix first demonstrates exponential quantum space advantage in real-world datasets and then benchmarks quantum oracle sketching.The experiments cover the paper’s empirical validation program.

additional numerical experiments.

The paper combines quantum oracle sketching with classical shadows to build compact models from massive classical data without QRAM, and reports broad experimental validation alongside unconditional space-advantage results.

  • Numerical experiments: Four real-world datasets cover movie-review sentiment, single-cell RNA analysis, social-media topics, and pharmaceutical drug discovery.The datasets are standard benchmarks in their respective domains.
  • Data access: Quantum oracle sketching avoids QRAM by processing each classical sample once, discarding it immediately, and incrementally building coherent quantum queries.The scheme uses streaming samples rather than storing the full dataset.
  • Theoretical results: Exponential quantum space advantages persist with noisy data, and any super-quadratic query separation yields an exponential space advantage.The result is presented as applying to useful classical tasks, including settings where algorithms have only polynomial query speedups.
  • Readout: Interferometric classical shadows enable a completely classical model to predict sparse observables while preserving sign information needed for classification and dimension reduction.The method combines the Hadamard test with the offline prediction capability of classical shadows.
  • Theoretical results: The classical lower bound requires MS ≥ Ω(NQC), while quantum oracle sketching uses optimal sample complexity M = Θ(NQ2).These bounds connect classical memory and sample requirements to the target property's classical query complexity.
  • Computational model: The formal comparison uses classical branching programs and quantum branching programs that apply input-dependent quantum channels, with uniformity established for the constructed algorithms.The model is stronger than an online Turing machine, so the classical lower bounds carry over directly.

f. Low advantage leads to large sample complexity

The learning XOR lemma converts exponentially small prediction advantage across multiple instances into a superpolynomial sample-complexity requirement for classical learners with insufficient space.

  • Learning XOR lemma: The learning XOR lemma shows that predicting the XOR of L instances causes the advantage over random guessing to decay exponentially with L.The proof addresses repeated samples and dependencies between instances before applying the lemma.
  • Consequence: The resulting theorem establishes that low advantage at sample size τ forces a larger sample requirement for learners constrained to the same space.This is the bridge from exponentially decaying XOR advantage to sample-complexity blow-up.
  • Single-block hardness: A single-block hardness assumption limits classical success to 1/2+δ when space and sample complexity are insufficient.This bound is stated for randomized classical learners receiving IID samples from one of two distributions.
  • Hybrid argument: The hybrid argument partitions M samples into r blocks of size τ and bounds the total advantage by accumulating the per-block distinguishability.The construction uses r+1 hybrid distributions and an auxiliary learner with sample complexity τ.
  • Hybrid argument: The constructed learner preserves space complexity S while converting a high-success learner into one using τ samples with nontrivial advantage.Its success probability is at least 1/2 + 1/(6r).

g. Proof of Theorems E.27 and E.28

The proofs reduce dynamic NOPE hardness to application tasks and use the learning XOR lemma and sample-complexity blow-up to establish classical lower bounds for those tasks.

  • Proof strategy: The proof pipeline combines a distributional sample-space lower bound, a learning XOR lemma, and a low-advantage sample-complexity theorem.These tools are used to prove the classical hardness results for dynamic NOPE.
  • Theorem E.27: Theorem E.27 follows by applying the learning XOR lemma to a classical learner with insufficient space and bounded sample complexity.The reduction sets the amplified instance count and sample parameters using the lower-bound construction.
  • Theorem E.28: Theorem E.28 applies the low-advantage sample-complexity result to show that restricted-space classical learners require substantially more samples.The argument uses τ = T1N and an exponentially small advantage parameter.
  • Application reductions: The hardness construction uses Forrelation with the inner-product function as a noisy encoding and embeds a quantum circuit into application tasks.The target embeddings include linear-system solving, binary classification, and dimension reduction.
  • Application reductions: The reduction shows that solving the application tasks would solve dynamic NOPE, so the application tasks inherit its classical hardness.The argument connects the dynamic oracle problem to the paper’s application-level tasks.

a. Forrelation and inner product

The paper uses Forrelation and inner-product constructions to establish quantum–classical query separations and support embeddings into classical data-processing tasks. Realification preserves key matrix properties while enabling quantum-circuit constructions over real data.

  • Forrelation: Forrelation exhibits an O_ϵ(1) versus Ω(N^(1−ϵ)) quantum–classical query complexity separation for every constant ϵ > 0.The construction uses oracle distributions that a small quantum algorithm can distinguish, while classical algorithms require substantially more queries.
  • Forrelation: Forrelation distributions can be identified quantumly with log N + O(log log(1/η) + K) space and polynomially bounded query and gate complexity.The quantum procedure uses majority voting to amplify success probability.
  • Inner product: The inner-product noisy encoding function has discrepancy at most 2^(−b/2).This low-discrepancy property is established through an orthogonal-matrix argument.
  • Realification: Realification preserves norms, real parts of inner products, matrix products, inverses, singular values, norms, and condition numbers.It maps complex matrices and vectors into real ones while preserving the properties needed by the application embeddings.
  • Realification: Realification maps unitary quantum-circuit operations to orthogonal real operations on one additional qubit.The construction also maps computational-basis states to states with real components.
  • Application embedding: A quantum circuit can be embedded into a binary-classification dataset so that the classifier’s prediction determines the sign of a circuit output expectation value.The embedded prediction uses the sign of x^T(X^T X)^−1X^T y and requires no regularization.

e. Connect to dimension reduction

The paper connects quantum circuits to dimension reduction by embedding a circuit into a real PCA instance. The resulting principal-component projection can encode the circuit output while retaining controlled sparsity and spectral properties.

  • Dimension reduction: PCA reduces a data matrix to one dimension by projecting a test vector onto the top eigenvector of X^T X.The resulting scalar is the test vector’s one-dimensional representation.
  • Circuit embedding: A quantum circuit can be embedded into a data matrix so that approximating a sparse test vector’s principal-component projection to 1/poly(T, log(N)) error determines the circuit output.The construction provides a BQP-hardness connection for dimension reduction with a suitable guiding vector.
  • Circuit embedding: The PCA embedding uses a real dataset and a 1-sparse guiding vector, with the data matrix remaining symmetric and O(s)-sparse.The construction also specifies a spectral gap and overlap between the guiding vector and the principal component.
  • Circuit embedding: Padding the circuit with Θ(T) identity gates yields a guiding vector with constant overlap Θ(1) but sparsity O(T).This trades sparsity for stronger overlap with the principal component.
  • Linear-system connection: The linear-system application models power-grid measurements and estimates heat dissipation through a quadratic form after solving A x = b.The task uses a high-dimensional, sparse, well-conditioned system and random samples of matrix and vector entries.

b. Main results

The main results establish unconditional quantum advantages for high-dimensional linear-system tasks. Quantum oracle and state sketching let a polylogarithmic-size machine process streaming samples with polylogarithmic time per sample, while smaller classical machines require exponentially larger size or superpolynomially more samples.

  • Main theorem: Using Õ(RN) samples, a poly(log N)-size quantum machine solves the linear-system task with 1/poly(log N) error and high success probability.Its processing time per sample is poly(log N), whereas classical machines of o(N^(1−ζ)) size cannot achieve comparable performance with the same sample scale.
  • Dynamic setting: Classical machines of o(N^(1−ζ)) size require at least RN^ω(1) samples for dynamic linear systems.The quantum machine uses Õ(RN) samples under sufficient refreshing time and retains poly(log N) processing time per sample.
  • Main theorem: Theorems F.3 and F.4 establish unconditional exponential quantum advantages for linear-system solving.The result applies to a foundational task used across science and engineering.
  • Algorithm: The quantum algorithm combines quantum oracle sketching, quantum state sketching, quantum linear-system solving, and amplitude estimation.The sketching procedures instantiate the required matrix and state queries from streaming classical samples.
  • Complexity: When relevant parameters are poly(log N), the algorithm uses poly(log N) data-processing time per sample.The construction produces a classical estimate of the target quadratic form with probability at least 1 − δ.
  • Error control: The combined approximation errors satisfy E1 + E2 + E3 = δ/2.The three contributions arise from replacing ideal queries with approximate and sample-generated implementations.

d. Classical hardness

The paper establishes classical hardness results showing that matching the quantum machine’s performance requires exponentially larger classical space, while smaller classical machines may require superpolynomially more samples.

  • Linear systems: The hardness proofs embed quantumly difficult oracle problems into linear-system and learning-task data-generation processes.The constructions use K-Forrelation and noisy inner-product encodings to transfer oracle hardness to classical data-processing tasks.
  • Binary classification: For dynamic binary classification, classical machines with o(D^(1−ζ)) space require at least RN^ω(1) samples to achieve success probability at least 2/3.The dynamic task has refreshing time τ = O~(RN).

c. Quantum algorithm

The quantum algorithm processes high-dimensional data through quantum sketches rather than storing the full dataset, then uses quantum regression or ground-state preparation and classical shadows to produce predictions or reduced representations.

  • Binary classification: Quantum oracle sketching instantiates coherent data queries from streaming samples, while quantum state sketching prepares the required vector states.Each sample is processed once and the resulting quantum operations support the downstream algorithm.
  • Binary classification: For binary classification, a quantum ridge-regression solver prepares the normalized LS-SVM weight vector from the sketched data.The weight vector is |w⟩ = (X^T X + λI_D)^−1X^T y after normalization.
  • Complexity: The resulting quantum procedures use poly(log D) space and poly(log D) processing time per sample for the classification and dimension-reduction tasks.The classification theorem explicitly gives high success probability with approximately O~(RN) samples.
  • Binary classification: Interferometric classical shadows preserve sign information and enable predictions for many test vectors from a universal readout of the weight state.This extends ordinary shadow readout beyond estimating only squared overlaps.
  • Dimension reduction: For dimension reduction, the algorithm prepares the principal component as the ground state of H = −X^T X and reads it out with interferometric classical shadows.The smallest eigenvalue of H corresponds to the largest singular value of X.

b. Main results

The main results establish exponential quantum advantages for classification and dimension reduction on massive classical data, including dynamic settings, under explicit sample, error, and guiding-vector conditions.

  • Non-dynamic dimension reduction: A quantum machine with poly(log D) size solves dimension reduction using O~(RND^(1−χ)) samples, while smaller classical machines cannot match its error and success probability.The classical lower bound is o(D^((1−ζ)χ)) space for any constant ζ > 0.
  • Dynamic dimension reduction: Dynamic dimension reduction retains the quantum advantage with O~(RND^(1−χ)) samples when χ > 1/2, while smaller classical machines require superpolynomially more samples.The classical space threshold is o(D^((1−ζ)(2χ−1))).
  • Conclusion: The paper concludes that dimension reduction exhibits unconditional and exponential quantum advantage in both non-dynamic and dynamic formulations.The non-dynamic and dynamic claims are stated in Theorems F.21 and F.22.
  • Quantum algorithm: The dimension-reduction algorithm prepares the principal component through ground-state preparation and converts its quantum representation into classical predictions using interferometric shadows.It uses H = −X^T X, whose ground state is the principal component.
  • Guarantees: The quantum output is correct with probability at least 1 − δ after combining the algorithmic and query-instantiation error bounds.The total qubit count and per-sample processing time remain polylogarithmic under the stated conditions.
Loading 2604.07639v1…