Exponential quantum advantage in processing massive classical data

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

quant-phApr 8, 2026

Exponential quantum advantage in processing massive classical data

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

Organizations: California Institute of Technology, Pasadena, California 91125, USA · Google Quantum AI, Venice, California 90291, USA · Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA · Oratomic, Pasadena, California 91125, USA

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 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.

Figures & tables

Figure 1: Overview of quantum advantage in processing massive classical data. (a) We prove that a quantum computer can outperform exponentially larger classical machines in a wide range of classical data processing tasks, including solving linear systems, classification, and dimension reduction. (b) Our quantum algorithm enables coherent quantum queries to the noisy and evolving classical world. (c) For various classical data processing tasks with problem size $N$ , a $\mathrm{poly}(\log N)$ -size quantum machine can succeed in $\tilde{O}(N)$ time using quantum oracle sketching. In contrast, we prove that any classical machine, even with exponentially larger size $O(N^{0.99})$ , cannot solve the same task unless given time superpolynomial in $N$ . This exponential quantum advantage relies only on the principle of quantum superposition, independent of any computational complexity conjectures.

Figure 2: Evidence for quantum advantages in real-world datasets from numerical simulation. We perform binary classification and dimension reduction for (a) sentiment analysis of movie reviews from the Internet Movie Database (IMDb) [ 142 ] and (b) single-cell RNA sequencing analysis of peripheral blood mononuclear cells (PBMC) [ 207 ] . We compare the machine size required to reach a certain prediction performance using different families of classical (C) and quantum (Q) algorithms, including quantum oracle sketching (orange), quantum algorithms using QRAM (gray), classical sparse-matrix algorithms (gray), and classical streaming algorithms (blue [ 195 ] , green [ 116 ] , magenta [ 182 ] , and purple [ 8 ] ). For each algorithm, we truncate the retained information to plot the trade-off between machine size and performance, with standard error indicated by the shaded region. Machine size is defined as the maximal number of fundamental memory units consumed throughout the entire computation: logical qubits for quantum and floating-point numbers for classical. Performance is quantified by the $5$ -fold cross validation accuracy averaged over random category pairs for classification, and by the explained variance relative to the untruncated baseline for dimension reduction. More details are given in Appendix A .

Figure 3: Access the classical world in superposition with quantum oracle sketching. (a) An example of making quantum coherent query to a Boolean function using its classical data $(x,f(x))$ with quantum oracle sketching. Upon receiving each classical sample $(x,f(x))$ , we apply a multi-controlled phase gate $\exp(i\theta\ketbra{x}),\theta\propto f(x)$ . With $M=\Theta(N/\epsilon)$ samples, the resulting random unitary channel approximates the phase oracle $O:\ket{x}\to(-1)^{f(x)}\ket{x}$ of $f$ to $\epsilon$ error in diamond distance. This allows us to instantiate oracle queries in any quantum query algorithm that extracts the desired property of $f$ . (b) Numerical experiments benchmarking the number of samples $M$ needed to approximate various oracle queries to $\epsilon$ operator norm error of the expected unitary, which upper bounds the diamond distance error up to constants, as a proxy. We consider oracles of Boolean functions, state preparation unitaries of any vectors, and the sparse matrix element and index oracles of any sparse matrices. We use $N$ to denote the domain size of Boolean functions, the dimension of vectors, and the dimension of square matrices. $N_{\mathrm{nnz}}$ represents the number of non-zero elements in a sparse matrix. The solid lines represent the fitted sample complexity scaling, with fitted parameters and root-mean-squared relative errors (RMS rel. err.) listed.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Evidence for quantum advantages in additional real-world datasets from numerical simulation. We perform binary classification and dimension reduction for (a) topic analysis of posts from 20 newsgroups [ 110 ] and (b) chemical compound data for Thrombin binding [ 196 ] . We compare the machine size required to reach a certain prediction performance using different families of classical (C) and quantum (Q) algorithms, including quantum oracle sketching (orange), quantum algorithms using QRAM (gray), classical sparse-matrix algorithms (gray), and classical streaming algorithms (blue [ 195 ] , green [ 116 ] , magenta [ 182 ] , and purple [ 8 ] ). For each algorithm, we truncate the retained information to plot the trade-off between machine size and performance, with standard error indicated by the shaded region. Machine size is defined as the maximal number of fundamental memory units consumed throughout the entire computation: logical qubits for quantum and floating-point numbers for classical. Performance is quantified by the

5

-fold cross validation accuracy averaged over random category pairs for classification, and by the explained variance relative to the untruncated baseline for dimension reduction. More details are given in Appendix A .

Figure 5: Additional experiments with oblivious sketches. Top row: terminal performance achieved under designated machine sizes in classification (LS-SVM) and dimension reduction (PCA) on IMDb and PBMC68k, using different oblivious randomized sketching methods: uniform coordinate subsampling, feature hashing, and signed sparse JL transforms with sparsity

s_{\mathrm{JL}}=1,2,4,8

[ 116 ] . For all oblivious sketches, we use the truncated feature dimension as a conservative estimate of their machine size. The orange diamond marks the terminal performance of quantum oracle sketching. Bottom row: performance difference of different sketches from feature hashing at equal machine size, plotted in the symmetric log scale, where the axis is linear within

\pm 1\%

; shaded regions indicate standard error.

Figure 6: Additional experiments with adaptive streaming algorithms. Terminal classification accuracy achieved under designated machine sizes on IMDb and PBMC68k, using adaptive streaming algorithms trained on a stream of uniformly random training samples: Active-set Weight-Median Sketch (AWM-Sketch, magenta) [ 182 ] and MISSION (purple) [ 8 ] , along with feature hashing baselines obtained from the exact LS-SVM solutions (dashed blue) and by streaming stochastic gradient descent (solid blue). The orange diamond marks the terminal performance of quantum oracle sketching. The difference from exact feature hashing is plotted in the symmetric log scale, where the axis is linear within

\pm 5\%

. Differences are evaluated at equal measured machine size by interpolating the feature hashing baseline, since the measured register counts of the adaptive algorithms can sit slightly below the designated sizes due to integer divisions. Shaded regions indicate standard error.

Figure 7: Convergence of streaming algorithms to the terminal solution at fixed machine size. Example training dynamics of feature-hashing stochastic gradient descent at machine sizes

D^{\prime}=8192,65536

on IMDb, and

D^{\prime}=4096,32768

on the PBMC68k pair of the two largest cell-type classes (CD8+ Cytotoxic T versus CD8+/CD45RA+ Naive Cytotoxic). Each curve represents one repetition with an independent random seed, showing the training ridge loss function relative to the exact minimizer of the same problem under feature hashing on the left axis in log scale, and the held-out accuracy relative to the same exact solution on the right axis, as functions of the number of processed samples in units of effective passes over the training set. As the hashed ridge loss is strictly convex, the exact solution, plotted in dashed lines, is its unique global minimum and the streaming implementation can only converge to it from above.

Figure 8: Overview of the models of data access and computation. (a) Illustration of the tree structure of a hierarchical data generation process with $l$ situation levels, each has time scale $T_{1},\ldots,T_{l}$ . Random variables within the same box are IID conditioned on their shared latent situations. (b) The model of classical learning algorithms with size $S$ (i.e., $2^{S}$ possible configurations) and sample complexity $M$ . The computation path when the algorithm is given a sequence of data $z_{0},\ldots,z_{M-1}$ is highlighted in blue. (c) The model of quantum learning algorithms with size $S$ and sample complexity $M$ . Upon receiving a sequence of data $z_{0},\ldots,z_{M-1}$ , the algorithm applies a series of quantum channels $C^{0}_{z_{0}},\ldots,C^{M-1}_{z_{M-1}}$ and measures the final state to compute the outcome.

Figure 9: Schematic overview of quantum oracle sketching. (a) Illustration of quantum oracle sketching for Boolean function data $(x,f(x)),f:[N]\to\{0,1\}$ . We build the phase oracle $O=\sum_{x}(-1)^{f(x)}\outerproduct{x}{x}$ of $f$ using multi-controlled phase gates with control patterns given by $x$ and phase values given by $f(x)$ from the data. $M=\Theta(N/\epsilon)$ samples guarantee $\epsilon$ approximation of the phase oracle in diamond distance. We generalize this to accommodate noisy and correlated data inputs with generic data structures including state preparation unitaries of any vectors and block encodings of sparse matrices. (b) We use quantum oracle sketching to load data into a quantum computer and instantiate the oracle queries in any quantum algorithm. $M=\Theta(NQ^{2}/\epsilon)$ samples guarantee $\epsilon$ approximation in diamond distance of any quantum algorithm that makes $Q$ queries to the oracle $O$ , its inverse $O^{\dagger}$ , or the controlled versions $cO,cO^{\dagger}$ .

Figure 10: Overview of the classical hardness proof strategy. (a) Illustration of the Noisy Oracle Property Estimation (NOPE) task. We encode the truth table of an oracle $o\in\{0,1\}^{N}$ as noisy encodings $Y^{(0)},Y^{(1)}$ . The task is to estimate some property of the oracle $o$ using random query data of the noisy encoding $(x,Y^{(\alpha)}_{x},\alpha)$ that depends on the current situation $\alpha$ which changes with time scale $N$ . (b) Visualization of the information flow during the learning process of a classical learning algorithm that has memory size $S$ and sample complexity $M$ . The information flow between the two situations is bounded by the number of situation changes $O(M/N)$ times $S$ , the communicated number of bits per situation change. (c) Reduction from query algorithms to learning algorithms. We construct a query algorithm that calculates the desired oracle property by simulating a learning algorithm that solves the corresponding NOPE task. The query algorithm fakes data samples to feed into the learning algorithm and occasionally queries the oracle to update its data forging strategy. The number of queries it makes is lower bounded by the classical query complexity $Q_{C}$ , while upper bounded by its ignorance of the information flow within the learning algorithm. This leads to the sample-space lower bound $MS\geq\Omega(NQ_{C})$ .

Figure 11: Overview of the linear system task. We illustrate the linear system task with a particular real-world application scenario in power grid analysis. In power grid analysis, samples are obtained by performing measurements on a power grid to read off the impedance values and the voltage values of random locations that are changing dynamically. We may want to estimate the heat dissipation of some critical junctions, given by a quadratic form of the current. This reduces to solving a high-dimensional linear system $A\vec{x}=\vec{b}$ . Our results show that a small quantum machine with size $\mathrm{poly}(\log N)$ can solve this task with $\tilde{O}(N)$ samples, whereas any classical machine with exponentially larger size $O(N^{0.99})$ cannot solve the task unless it uses a sample size at least super-polynomial in $N$ .

Figure 12: Overview of the binary classification task. We illustrate the binary classification task with a particular real-world application scenario in sentiment analysis of movie reviews. We collect positive and negative reviews of movies from users, encode them into feature vectors $\vec{x}_{i}\in\mathbb{R}^{D}$ , and use them to predict labels of new samples. A sample is the feature vector of a review $\vec{x}_{i}$ and its label $y_{i}$ (positive or negative). A canonical way of binary classification is the support vector machine (SVM), which is trained on the high-dimensional data matrix $X\in\mathbb{R}^{N\times D}$ and label vector $\vec{y}$ and produces a decision boundary represented by a weight vector $\vec{w}\in\mathbb{R}^{D}$ that classifies new samples. Our results show that a small quantum machine with size $\mathrm{poly}(\log D)$ can solve this task with $\tilde{O}(N)$ samples, whereas any classical machine with exponentially larger size $O(D^{0.99})$ cannot solve the task unless it uses a sample size at least super-polynomial in $N$ .

Figure 13: Overview of the dimension reduction task. We illustrate the dimension reduction task with a particular real-world application scenario in single cell RNA sequencing (scRNA-seq). We conduct RNA sequencing experiments to obtain gene sequences in cell samples, which are represented as feature vectors $\vec{x}_{i}\in\mathbb{R}^{D}$ (e.g., via frequency counting of $k$ -mer representations). A sample is the feature vector $\vec{x}_{i}$ of a single RNA sequence. A canonical way of dimension reduction is principal component analysis (PCA), which is performed on the high-dimensional data matrix $X\in\mathbb{R}^{N\times D}$ and produces a principal component vector $\vec{w}\in\mathbb{R}^{D}$ that represents the most important feature combination. We obtain the low dimension representation $\xi(\vec{x})$ of a sample $\vec{x}$ by projecting it onto the principal component $\vec{w}$ . Our results show that a small quantum machine with size $\mathrm{poly}(\log D)$ can solve this task with $\tilde{O}(N)$ samples, whereas any classical machine with exponentially larger size $O(D^{0.99})$ cannot solve the task unless it uses a sample size at least super-polynomial in $N$ .

Explore similar work

May 13, 2026quant-ph

Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm

Quantum machine learning (QML) aims to accelerate machine learning tasks by exploiting quantum computation. Previous work studied a QML algorithm for selecting sparse subnetworks from large shallow neural networks. Instead of directly solving an optimization problem over a large-scale network, this algorithm constructs a sparse subnetwork by sampling hidden nodes from an optimized probability distribution defined using the ridgelet transform. The quantum algorithm performs this sampling in time

O(D)

in the data dimension

D

, whereas a naive classical implementation relies on handling exponentially many candidate nodes and hence takes

\exp[O(D)]

time. In this work, we construct and analyze a quantum-inspired fully classical algorithm for the same sampling task. We show that our algorithm runs in time

O(\operatorname{poly}(D))

, thereby removing the exponential dependence on

D

from the previous classical approach. Numerical simulations show that the proposed sampler achieves empirical risk comparable to exact sampling from the optimized distribution and substantially lower than sampling from the non-optimized uniform distribution, while also exhibiting exponentially improved runtime scaling compared with the conventional classical implementation. These successful dequantization results show that sparse subnetwork selection via optimized sampling can be achieved classically with polynomial data-dimension scaling on conventional computers without quantum hardware, providing an alternative to the existing quantum algorithm.

Natsuto Isogai, Hayata Yamasaki, Sho Sonoda +1

The University of Tokyo · RIKEN AIP

Quantum Machine Learning Quantum Annealing Neural Network Lotteries

Ask PDF

May 27, 2026cs.CV

Do We Really Need Quantum Machine Learning?: A Multidimensional Empirical Study

The rapid growth of computer vision and increasingly complex image recognition tasks has exposed fundamental computational limitations of classical machine learning models, motivating the exploration of quantum computing as an emerging new paradigm. This paper presents a comprehensive benchmarking study of classical and quantum machine learning models for image recognition on the MNIST handwritten digit dataset, evaluating both traditional models, a Classical Support Vector Machine (CSVM) and a Quantum Support Vector Machine (QSVM), and deep neural network models, a Classical Convolutional Neural Network (CCNN) and a Quantum Convolutional Neural Network (QCNN), across four performance dimensions: classification accuracy, computational runtime, parameter count, and memory requirements. Experiments are conducted as functions of both feature dimensionality and sample size, and across CPU and GPU execution environments, providing a controlled, multidimensional comparison to address gaps in prior work. For the SVM-based models, QSVM consistently outperforms CSVM in accuracy, reaching

\sim

0.90 versus

\sim

0.85 at 1,000 samples, with a higher computational cost. A feature count of 10 qubits and a sample size in the range of 200 -- 500 emerge as practical operating points that balance accuracy and runtime. For the neural network models, CCNN and QCNN achieve comparable classification accuracy, both exceeding 0.96 at 64 features and 60,000 samples, yet QCNN offers substantially superior parameter and memory efficiency, requiring

\sim

94% fewer parameters and

\sim

75% less memory than CCNN at higher feature counts, while incurring higher runtime. Across both model families, quantum models consistently outperform classical models by greater margins in accuracy as feature dimensionality or sample size increases.

Sudip Vhaduri, Ryan Gammon, Sayanton Dibbo

Department of Computer Science, University of Alabama, AL 35487 · Clemson University

Quantum Machine Learning Quantum Kernels Mnist Computational Cost

Ask PDF

Sep 20, 2026quant-ph

Comparative Study of Quantum and Classical Machine Learning Models in Binary Classification

A potential path forward is Quantum Machine Learning (QML), which aims to leverage quantum computing in conjunction with classical machine learning to enhance computing efficiency and the expressiveness of models. In this paper, two different quantum classifiers - Variational Quantum Classifier (VQC) and Quantum Kernel Support Vector Machine (QSVM) - are compared with three classical classifiers as baseline classifiers - Logistic Regression, Support Vector Machine (SVM), and a Multi-Layer Perceptron (MLP) - on the Breast Cancer Wisconsin dataset. The quantum circuits were created in the PennyLane framework and simulated on a classical backend. However, in terms of accuracy, classical Logistic Regression performed better with an accuracy of 97.8%, classical SVM and QSVM with an accuracy of 95.6% each, although the Quantum VQC achieved a lower accuracy of 88.9% and had a recall of 100% for the benign class, though it correctly identified only 12 of the 17 malignant cases (a malignant-class recall of approximately 70.6%). The drawback of quantum models is the higher training time; however, since the quantum circuit needs to be classically simulated, the quantum SVM took 23.29 seconds compared to less than 0.01 seconds for the classical linear models. These results indicate that for small structured datasets, classifiers based on quantum computing have not yet surpassed well-tuned classical counterparts. In some respects (e.g., benign-class recall), they perform competitively, though not on malignant-class recall, where the VQC in particular performed worse than the classical baselines, which is worth further investigation on real quantum computers.

Anand Kumar Mishra, Ramanuj Awasthi

School of Engineering & Technology (UIET), CSJM University, Kanpur, Uttar Pradesh, India

Quantum Machine Learning Quantum Kernels Support Vector Machines

Ask PDF