quant-phApr 8, 2026
SaveExponential quantum advantage in processing massive classical data
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 , a -size quantum machine can succeed in time using quantum oracle sketching. In contrast, we prove that any classical machine, even with exponentially larger size , cannot solve the same task unless given time superpolynomial in . 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 -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 with quantum oracle sketching. Upon receiving each classical sample , we apply a multi-controlled phase gate . With samples, the resulting random unitary channel approximates the phase oracle of to error in diamond distance. This allows us to instantiate oracle queries in any quantum query algorithm that extracts the desired property of . (b) Numerical experiments benchmarking the number of samples needed to approximate various oracle queries to 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 to denote the domain size of Boolean functions, the dimension of vectors, and the dimension of square matrices. 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 -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 [ 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 ; 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 . 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 on IMDb, and 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 situation levels, each has time scale . Random variables within the same box are IID conditioned on their shared latent situations. (b) The model of classical learning algorithms with size (i.e., possible configurations) and sample complexity . The computation path when the algorithm is given a sequence of data is highlighted in blue. (c) The model of quantum learning algorithms with size and sample complexity . Upon receiving a sequence of data , the algorithm applies a series of quantum channels 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 . We build the phase oracle of using multi-controlled phase gates with control patterns given by and phase values given by from the data. samples guarantee 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. samples guarantee approximation in diamond distance of any quantum algorithm that makes queries to the oracle , its inverse , or the controlled versions .
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 as noisy encodings . The task is to estimate some property of the oracle using random query data of the noisy encoding that depends on the current situation which changes with time scale . (b) Visualization of the information flow during the learning process of a classical learning algorithm that has memory size and sample complexity . The information flow between the two situations is bounded by the number of situation changes times , 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 , while upper bounded by its ignorance of the information flow within the learning algorithm. This leads to the sample-space lower bound .
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 . Our results show that a small quantum machine with size can solve this task with samples, whereas any classical machine with exponentially larger size cannot solve the task unless it uses a sample size at least super-polynomial in .
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 , and use them to predict labels of new samples. A sample is the feature vector of a review and its label (positive or negative). A canonical way of binary classification is the support vector machine (SVM), which is trained on the high-dimensional data matrix and label vector and produces a decision boundary represented by a weight vector that classifies new samples. Our results show that a small quantum machine with size can solve this task with samples, whereas any classical machine with exponentially larger size cannot solve the task unless it uses a sample size at least super-polynomial in .
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 (e.g., via frequency counting of -mer representations). A sample is the feature vector 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 and produces a principal component vector that represents the most important feature combination. We obtain the low dimension representation of a sample by projecting it onto the principal component . Our results show that a small quantum machine with size can solve this task with samples, whereas any classical machine with exponentially larger size cannot solve the task unless it uses a sample size at least super-polynomial in .