Exponential quantum advantage in processing massive classical data

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

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.07639v1Apr 8, 2026quant-phcs.AIcs.CCcs.ITcs.LG

TL;DR

Broad quantum advantage in classical data processing remains an open question, with existing approaches relying on QRAM whose efficient realization is unclear. This paper introduces quantum oracle sketching and interferometric classical shadows, and proves exponential quantum space advantages across classical data tasks.

Problem
Whether quantum computers can provide broad advantages in classical data processing remains open, while existing QRAM-based approaches face unclear prospects for efficient, fault-tolerant realization.
Source: §2 · p. 21
Method
The paper combines quantum oracle sketching with interferometric classical shadows to address data-loading and readout bottlenecks.
Source: §IV · p. 9
Results
A poly(log N)-size quantum computer performs classification, dimension reduction, and linear-system solving, while classical machines require exponentially larger size or superpolynomially more samples and time.
Source: §I · p. 2
Takeaways & Limitations
Classical data processing and machine learning constitute a broad domain of exponential quantum advantage, extending quantum computation beyond specialized tasks.
Source: §IV · p. 8
Projections that devices with hundreds of logical qubits could outperform extremely large classical systems extrapolate the observed scaling while ignoring exponential runtime overhead.
Source: §IV · p. 9

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 introduction presents classical-data processing as a central test of whether quantum advantage can extend beyond specialized tasks. It claims exponential space advantages for large-scale data processing and learning, enabled by quantum oracle sketching of classical samples streamed on the fly.

I. INTRODUCTION

End-to-end quantum machine-learning advantage remains unclear because superposition access conflicts with classical data access; QRAM overhead, contrived tasks, dequantization, and difficult variational training fuel skepticism.The introduction situates this uncertainty within the broader search for quantum advantages beyond specialized tasks.Source: §I · p. 1
The introduction identifies a tension between machine size and data scale: streaming, sketching, and online learning process samples on the fly but sacrifice prediction accuracy as machine size shrinks.The motivating question is whether small quantum machines can predict better than exponentially larger classical machines.Source: §I · pp. 1–2
A poly(log N)-size quantum computer performs classification, dimension reduction, and linear system solving, while classical machines need exponentially larger size or superpolynomially more samples and time for the same performance.Figure 1 describes the quantum algorithm succeeding in ˜O(N) time and classical machines of size O(N^0.99) failing unless given superpolynomial time.Source: Figure 1 · p. 2, §I · p. 2
Quantum oracle sketching builds coherent queries from classical samples processed once and discarded; its sample requirement is quadratic in quantum queries, and this scaling is optimal under the Born rule.The samples incrementally build an approximate oracle for use within quantum algorithms.Source: §I · p. 2
Quantum oracle sketching handles noisy, correlated data with generic distributions and data structures, enabling state-preparation unitaries and matrix block encodings combined with classical-shadow readout.These methods construct compact, accurate classical models from massive data, which classical machines that are not exponentially larger cannot construct.Source: §I · p. 2
Six orders of magnitude less size than classical sparse-matrix and QRAM-based algorithms, and four orders less than classical streaming algorithms, are demonstrated with fewer than 60 logical qubits.The experiments cover movie-review sentiment analysis and single-cell RNA sequencing.Source: §I · p. 2, Figure 2 · p. 3
The results are information-theoretic and unconditional, persisting with unlimited classical time or if BPP = BQP, and depend only on the validity of quantum mechanics.The authors frame experimental confirmation or disproof as a test of quantum mechanics at the complexity frontier.Source: §I · p. 3

II. MAIN RESULTS

The section proves that polylogarithmic-size quantum computers can solve linear-system, classification, and dimension-reduction tasks from sampled classical data despite classical machine-size barriers. Numerical experiments report large memory advantages in real-world classification and dimension reduction.

Linear systems

˜O(N) samples let a poly(log N)-size quantum computer solve sparse, well-conditioned linear-system tasks, while classical size O(N^0.99) cannot; dynamically, that classical size requires superpoly(N) samples.For dynamic systems with τ = ˜O(N), the quantum machine still uses ˜O(N) samples; general repetition number R scales sample complexity linearly.Source: §II · p. 4

Classification

˜O(N) samples let a poly(log D)-size quantum computer classify N items with D-dimensional features, while classical size O(D^0.99) cannot; dynamically, that classical size requires superpoly(N) samples.The task predicts labels for sparse, classifiable test vectors under the LS-SVM decision rule; the dynamic dataset refreshes every τ = ˜O(N) samples while the rule remains approximately fixed.Source: §II · p. 4

Dimension reduction

˜O(N) samples let a poly(log D)-size quantum computer perform dimension reduction on N items with D features, while classical size O(D^0.99) cannot; dynamically, that classical size requires superpoly(N) samples.The task estimates test-vector representations using a guiding vector and a sparse, spectrally gapped dataset; the dynamic setting has τ = ˜O(N).Source: §II · p. 5

Numerical experiments

To achieve high performance, quantum oracle sketching requires nearly constant memory, while classical and QRAM-based approaches grow exponentially, yielding advantages of four to six orders of magnitude using fewer than 60 logical qubits.Source: §II · p. 5

Quantum oracle sketching

Quantum oracle sketching uses classical samples to approximate quantum oracle queries in superposition, with M = Θ(N/ϵ) samples approximating a Boolean-function phase oracle to ϵ diamond-distance error.The method applies a phase gate for each received sample and can instantiate oracle queries in quantum algorithms that extract properties of the function.Source: Figure 3 · p. 6

III. ORIGIN OF ADVANTAGE · A. Quantum Oracle Sketching

Quantum oracle sketching uses fresh classical samples to construct coherent quantum oracles without storing the dataset, enabling quantum query algorithms and classical outputs. For the phase oracle, its error scales as ϵ ∼ N/M rather than the generic ϵ ∼ N^2/M.

A. Quantum Oracle Sketching

The end-to-end method processes and discards each classical sample once, sketches oracle queries for quantum algorithms, then uses classical shadow tomography to extract outputs.This resolves the tension between coherent quantum queries and classical data access without storing the entire dataset.Source: A. Quantum Oracle Sketching · p. 6
Generic randomized Hamiltonian simulation has error ϵ ∼ N^2/M, requiring M ∼ N^2 samples for one query and eliminating potential quantum advantage.This contrasts with the phase-oracle sketch’s improved scaling.Source: A. Quantum Oracle Sketching · p. 6
For a Boolean phase oracle, setting τ = πN makes the random gate sequence approach the oracle as empirical frequencies concentrate around p(x) = 1/N.Each sample applies a small phase rotation to its corresponding basis state; inverse and controlled oracles follow by negating τ or controlling each gate.Source: A. Quantum Oracle Sketching · p. 7
Sketching Q oracle queries with total error ϵ incurs a necessary quadratic dependence on Q in sample complexity.The method allocates error ϵ/Q to each query, and the paper proves this sample complexity is optimal.Source: A. Quantum Oracle Sketching · p. 7
Quantum oracle sketching handles noisy and correlated data with time-varying features, multiplying sample complexity only by the data-generation repetition number R.The factor reflects needing R times more samples when each sample is repeated R times.Source: A. Quantum Oracle Sketching · p. 7
Extensions handle unknown or non-uniform distributions, arbitrary-vector state preparation, sparse oracles, and matrix block encodings, using QSVT and other techniques.These extensions involve non-orthogonal rotations and require more sophisticated variance analysis.Source: A. Quantum Oracle Sketching · p. 7
Across Boolean functions, unit vectors, and sparse matrices, empirical sample-complexity fits agreed with theory, with root-mean-squared relative errors all below 3%.The study used operator-norm error of the expected unitary as a proxy for diamond distance.Source: A. Quantum Oracle Sketching · p. 7

B. Interferometric Classical Shadows

Interferometric classical shadows combine the Hadamard test with classical shadow tomography to preserve sign information and produce an offline classical predictor. This compresses task-relevant information without sacrificing accuracy, a capability classical machines need exponentially larger memory to match.

B. Interferometric Classical Shadows

The interferometric classical shadow algorithm combines the Hadamard test with classical shadow tomography to retain sign structures needed for predictions such as SVM labels.The sign of the inner product between the weight vector and data vector determines the predicted label.Source: B. Interferometric Classical Shadows · p. 8
The method constructs a completely classical model that predicts for an arbitrary number of sparse test inputs.Source: B. Interferometric Classical Shadows · p. 8
The compact classical representation preserves accuracy, while classical machines require exponentially larger memory to achieve this compression; the result does not violate the Holevo bound.It exploits task structure to extract useful outputs efficiently.Source: B. Interferometric Classical Shadows · p. 8

C. Classical Hardness

The section establishes classical hardness by relating the memory needed to process noisy query data to classical-versus-quantum query complexity. It derives space and sample-complexity separations and transfers NOPE hardness to the paper’s target applications.

C. Classical Hardness

NOPE estimates a Boolean-function property from noisy queries; its classical query complexity QC measures the information a classical machine must extract, while scattered block data forces it to carry information across memory-boundary transitions.After M samples, a machine of size S carries at most S · O(M/N) bits across block boundaries, which must be at least QC to solve the task.Source: C. Classical Hardness · p. 8
At the quantum sample count, any classical machine solving a NOPE task with quantum query complexity Q and classical query complexity QC requires size at least Ω(QC/Q^2).The lower bound is proved using communication complexity tools [91] [94] and the quantum oracle sketching sample complexity M = Θ(NQ^2).Source: C. Classical Hardness · p. 8
For Forrelation, Q = O(1) and QC = Ω(N^(1−ζ)) for any constant ζ > 0, yielding a large classical–quantum space separation.More generally, when QC = Θ(N) and Q = O(N^0.49), the same-sample classical memory lower bound is S ≥ Ω(N^0.02).Source: C. Classical Hardness · p. 8
Insufficient-space classical machines require superpolynomially more samples, and reductions make the target prediction and representation tasks BQP-hard.A learning version of the XOR lemma [97–99] establishes the sample-complexity result; solving the target tasks would simulate the quantum circuit that solves NOPE.Source: C. Classical Hardness · p. 8

IV. DISCUSSION

The discussion presents classical data processing as a broad domain of exponential quantum advantage, enabled by quantum oracle sketching and interferometric classical shadows. It emphasizes the advantages’ practical scope, unconditional basis, and potential as a test of quantum mechanics.

IV. DISCUSSION

The work establishes exponential quantum advantage across linear systems, binary classification, and dimension reduction, reaching the limit allowed by quantum mechanics.A classical machine of ˜O(N) size can store the full dataset and simulate a poly(log N)-qubit computation with only poly(log N) space overhead.Source: §IV · pp. 8–9
Quantum oracle sketching and interferometric classical shadows overcome data-loading and readout bottlenecks to construct exponentially compact classical models from massive data.Their existence indicates that useful tasks such as classification and dimension reduction contain structure that can be extracted efficiently without violating the generic Holevo bound.Source: §IV · p. 9
Orders-of-magnitude memory savings were demonstrated with fewer than 60 logical qubits, while projections for hundreds of qubits ignore exponential runtime overhead.The discussion suggests such devices could outperform extremely large classical systems, barring unforeseen limitations to quantum mechanics.Source: §IV · p. 9
For dynamic tasks, the work establishes super-polynomial sample-complexity advantage; quantum oracle sketching takes ˜O(N) data-loading time but only poly(log N) time to process each subsequent sample.The algorithm is largely composed of commuting operations, suggesting potential parallelization through hardware-software co-design and optimized error-correction architectures.Source: §IV · p. 9
Quantum oracle sketching is a worst-case-guaranteed classical-to-quantum converter that may extend quantum advantages beyond linear systems, classification, and dimension reduction.The authors identify trainable or variational components, hybrid pipelines, differential equations, optimization, signal processing, communication, and recommendation systems as opportunities for extensions; exponential space advantage may follow from super-quadratic query separation.Source: §IV · p. 9
The space advantage is unconditional and information-theoretic, persists with unbounded classical computation or BPP = BQP, and can be experimentally tested at the complexity frontier [75].Such experiments would probe the physical reality of exponentially large Hilbert spaces [101].Source: §IV · p. 9

Appendices · Roadmap

The roadmap directs readers to the appendices’ numerical experiments, background and setup, and theoretical foundations for processing massive classical data on small quantum computers.

Roadmap

Section A contains additional numerical experiments and their details, while the remaining appendices are organized into three themes.Source: Roadmap · p. 17
Clicking a page-header number returns readers to the roadmap.Source: Roadmap · p. 17
Section B reviews related work and contributions, and Section C introduces the models of data access and computation.Source: Roadmap · p. 17
Sections D and E establish rigorous theoretical foundations for processing massive classical data on small quantum computers.Source: Roadmap · p. 17
Section D introduces quantum oracle sketching for IID Boolean-function data, addresses decoherence, and establishes the method’s optimality.It then extends the approach to more general data distributions and structures, including matrices and vectors.Source: Roadmap · p. 17
Section E introduces the Noisy Oracle Property Estimation task and its dynamic variant as machinery for proving classical hardness.Source: Roadmap · p. 17
Section E proves the tasks’ classical hardness and connects them to the applications.Source: Roadmap · p. 17

Applications. · Appendix A: Additional numerical experiments

The applications section presents accessible quantum-advantage results across linear systems, binary classification, and dimension reduction, while Appendix A expands the numerical experiments and algorithm benchmarking.

Applications.

Section F presents applications to linear systems, binary classification, and dimension reduction, with self-contained introductions, main quantum-advantage statements, and detailed proofs.The application introductions avoid quantum jargon and target a general audience.Source: Applications · p. 17
The suggested intuitive reading route starts with application results in Figures 8–10, then moves to the formal setup in Figure 5 and oracle-sketching overview in Figure 6.Figure 7 illustrates the intuition behind the classical hardness proofs.Source: Applications · p. 17
General readers are directed to Section F’s applications and their numerical support in Figures 2 and 4, with Section B supplying context on challenges and the approach.The suggested route is intended for general readers.Source: Applications · p. 17
Algorithm designers are directed to Section D, especially D 5 for linear algebra, and can use Section F’s quantum algorithms as application templates.A GitHub JAX implementation of quantum oracle sketching and QSVT supports GPU/TPU and automatic differentiation for variational training.Source: Applications · p. 17
Readers seeking rigorous proofs are directed to Section C’s formal setup, Sections D 4–D 5’s sample-complexity and variance analyses, and Section E’s classical lower bounds.The lower-bound contributions include sample-space bounds via simulation, a learning XOR lemma with derandomization, and BQP-hardness of useful applications.Source: Applications · p. 17
Figure 4 compares quantum oracle sketching with classical sparse-matrix, QRAM quantum, and classical streaming algorithms on newsgroup and thrombin classification and dimension-reduction tasks.Machine size counts logical qubits or classical floating-point numbers; performance uses 5-fold cross-validation accuracy and explained variance relative to the untruncated baseline, with standard errors shown. The experiments vary rare-feature filtering to plot the size-performance trade-off.Source: Figure 4 · p. 18

Appendix A: Additional numerical experiments

Appendix A expands the numerical experiments by covering real-world demonstrations in Figures 2 and 4 and quantum oracle sketching benchmarks in Figure 3.The appendix describes these as experiments presented in the main text.Source: additional numerical experiments · p. 18, Appendix A · p. 18

additional numerical experiments. … e. Proof of Theorem E.30

This section develops and analyzes quantum oracle sketching and related sample-based methods for classical-data learning, including correlated data, sparse-matrix access, and state preparation. It also presents supporting simulation and hardness arguments, numerical experiments, and related-work context.

additional numerical experiments.

Experiments span movie-review, single-cell RNA, social-media-topic, and drug-discovery datasets, evaluating binary classification and PCA-based dimension reduction.The datasets are IMDb, PBMC68k, 20Newsgroup, and Dorothea; classification uses five-fold LS-SVM accuracy, while dimension reduction measures relative explained variance of the first principal component.Source: additional numerical experiments · pp. 18–19
Feature truncation drops rare features according to a minimum document-frequency threshold, enabling a memory-consumption versus performance trade-off.The authors leave dataset-specific heuristics for future empirical evaluation.Source: additional numerical experiments · pp. 18–19
The oracle benchmarks test Boolean-function phase oracles, vector state-preparation unitaries, sparse matrix-element oracles, and sparse row-index oracles.They evaluate operator-norm errors for Boolean-function, matrix-element, and row-index oracles, and Euclidean-norm errors for vector state preparation.Source: additional numerical experiments · p. 20
All four quantum-oracle-sketching sample-complexity scalings in Figure 3 agree with theoretical predictions, with fitted root-mean-squared relative errors below 3%.The tests cover Boolean-function, vector, sparse-matrix-element, and sparse-row-index oracles.Source: additional numerical experiments · p. 20

Appendix B: Overview and related works

The related-work overview covers quantum data-processing algorithms, challenges to useful quantum advantage, classical space-efficient algorithms, and space lower-bound techniques.It also frames the results as improving existing quantum space advantages in streaming.Source: Appendix B · p. 20

1. Machine learning and quantum algorithms

Prior provable advantages for classical data often rely on contrived quantum or cryptographic tasks, while variational quantum methods face training and expressivity difficulties; this work targets realistic machine-learning tasks.The paper reports rigorously establishing exponential advantages across realistic classical machine-learning tasks and demonstrating them on real-world datasets.Source: §1 · p. 21

2. The challenging quest for quantum advantage

Quantum oracle sketching avoids QRAM’s general O(N) total-space cost, using poly(log N) total space to load classical data, with gate complexity ˜O(N) optimal up to logarithmic factors.The work also reports exponential space advantages persisting with noisy data and says any super-quadratic query separation yields an exponential space advantage.Source: §2 · pp. 21–22
Interferometric classical shadows preserve sign information for prediction and produce classical models from quantum data processing; the information-theoretic space advantages persist even if BPP = BQP.The paper says these models predict any number of sparse test data and are exponentially smaller than classical models that achieve the same task.Source: §2 · pp. 22–23

3. Memory-efficient algorithms and quantum space advantage

MS ≥ Ω(NQC) for classical learners and quantum sample complexity M = Θ(NQ2) imply S ≥ Ω(QC/Q2), proving exponential quantum space advantage for exponential classical query complexity and slightly greater than quadratic query advantage.For QC = Θ(N) and Q = O(N^0.49), the stated lower bound is S ≥ Ω(N^0.02).Source: §3 · p. 24
The learning XOR lemma bounds progress per repetition by 1/2log2 N = 1/superpoly(N), yielding a superpolynomial sample lower bound under constrained space.It combines derandomization with a hybrid argument for simultaneously solving log2 N independent NOPE instances; the results are instantiated with Forrelation.Source: §3 · p. 24
Embedding Forrelation NOPE transfers classical hardness to linear systems, binary classification, and dimension reduction.The constructions use matrix-inversion BQP-hardness for linear systems and a modified Feynman–Kitaev circuit Hamiltonian for dimension reduction.Source: §3 · p. 24

Appendix C: Models of data access and computation

The framework models data as hierarchical processes that include IID samples and time-varying, correlated features, and defines classical and quantum learning algorithms by size, sample, and time complexity.The paper states that its quantum algorithm works for any such process, while classical algorithms require exponentially larger size.Source: Appendix C · p. 25

1. Data generation processes

Hierarchical data generation represents multiple time scales through changing latent situations, allowing correlations while preserving the same marginal distribution for each sample.The full situation information may be included in each sample, though the quantum algorithm also extends to cases where it is unavailable.Source: §1 · p. 26

2. Classical learning algorithms

Classical learners are modeled as branching programs with at most 2S configurations per layer, and their lower bounds also apply to uniform, space-bounded computational models.The model measures machine size S and sample complexity M; it is stronger than online Turing machines with bounded space.Source: §2 · pp. 27–28

3. Quantum learning algorithms

Quantum learners process the same classical samples through input-dependent quantum channels on S qubits and output through a final measurement.The designed algorithms have program descriptions generable by a polynomial-time classical Turing machine, so they also fit uniform models.Source: §3 · p. 28

4. Properties of hierarchical data generation processes

Shared situations enhance sample correlation, and the repetition number RD is nonnegative and controls variance and quantum-oracle-sketching sample convergence.The refresh time characterizes the largest correlation time scale; samples separated by at least that interval are independent.Source: §1 · p. 27, §4 · p. 29
Correlation is non-decreasing with correlation depth, and the repetition-number bound applies from any starting time.For samples separated by s, the correlation depth satisfies K(t, t+s) ≤ K(1, 1+s), which underlies the starting-time result.Source: §4 · pp. 29–30
For hierarchical samples, the repetition number bounds the variance of sample frequencies and controls conditional drift, with the drift bound scaling as 1/M.The conditional-drift result applies after conditioning on previously processed samples; the bound is stated for a processing round of M samples.Source: §4 · pp. 31–32

Q O, O†, cO, cO†

Quantum oracle sketching constructs a Boolean-function phase oracle from random classical samples and uses it to estimate function properties.The described construction uses multi-controlled phase gates whose control patterns and phases come from the samples.Source: Appendix D · p. 34, Figure 6 · p. 34, Q O, O†, cO, cO† · p. 34

Appendix D: Quantum oracle sketching

Appendix D extends quantum oracle sketching to multi-bit outputs, correlated time-varying data, and unknown marginals, and introduces quantum state sketching for state preparation.The section also describes sparse-oracle and block-encoding primitives built from random matrix samples.Source: Appendix D · p. 34

a. Inequalities

Appendix D collects distance, entropy, and random-vector moment inequalities used in analyses of oracle and state sketching.These include a diamond/operator distance relation, a quantum Bretagnolle-Huber inequality for oracle-sketching optimality, and a quadratic-form moment bound for state-sketching error.Source: a. Inequalities · pp. 34, 36
The expected error from exchanging expectation and matrix exponentiation for a random diagonal matrix is related to the variance of its matrix elements, and the result can improve the qDrift error-bound constant [86].The analysis relies on the diagonal matrices commuting.Source: a. Inequalities · p. 37

b. Quantum singular value transform

QSVT implements polynomial transformations of a Hermitian matrix through query access to a unitary and its inverse, and the authors use it to apply threshold functions approximated by polynomials.The cited threshold approximation is even and approximates opposite signs on intervals separated by λ⋆.Source: b. Quantum singular value transform · pp. 37–38

2. Quantum oracle sketching for IID data

IID samples (xi, yi), with yi = f(xi), construct a phase oracle to ϵ error in diamond distance; for uniform p and t = Nπ, the construction yields the phase oracle.The gates are applied on the fly without storing data points, using ⌈log2(N)⌉ qubits rather than O(N) memory for QRAM-based storage.Source: §2 · p. 38

a. The apparent trap of decoherence

Generic qDrift analysis requires O(N^2) samples for one uniform-distribution phase-oracle query, while a classical algorithm can solve generic query problems with the same sample count and O(1) memory.The authors describe this as an apparent decoherence trap: generic-rotation bounds offer no quantum advantage, and O(N) samples leave large error.Source: a. The apparent trap of decoherence · p. 39

b. Evading decoherence

For uniform p and t = Nπ, concentration analysis gives O(N log N/ϵ2) samples, improving the O(N^2/ϵ) qDrift scaling in N but not in ϵ.The 1/ϵ2 dependence causes a cubic slowdown in query complexity when fresh samples are used for each oracle query.Source: b. Evading decoherence · p. 42
Variance-based mixing analysis improves the error dependence while recovering a pmax factor, enabling sample complexity to bypass O(N^2) and reach O(N).The authors give up a worst-case error bound and instead bound the random unitary channel’s error in expectation; each sample takes O(log N) processing time.Source: b. Evading decoherence · p. 42
Quantum oracle sketching simulates any Q-query algorithm using IID classical samples with at most quadratic sample slowdown, while preserving its space complexity and bounding data-processing time by its runtime.The quadratic slowdown is stated for the total number of samples; the constructed learning algorithm retains the original algorithm's space complexity.Source: b. Evading decoherence · p. 43, §3 · p. 44

3. Optimality

The quadratic sample slowdown is necessary and tight for incoherent random-sample access when p_max tQ ≥ 8πϵ.The lower-bound theorem assumes ϵ ∈ (0, 1/12); when p_max tQ < 8πϵ, an algorithm can use no samples and replace each query by the identity.Source: §3 · pp. 44–45

4. Extensions

The extensions cover multi-bit outputs, hierarchical non-IID data, and non-uniform unknown distributions; for uniform data, t = Nπ yields the desired phase oracle.These extensions build on constructing the unitary U(t) from random data samples.Source: §4 · p. 46

a. Multi-bit output

For multi-bit outputs, the improved construction avoids sampling overhead: with uniform p(x) = 1/N and t = Nπ, the phase oracle still takes O(N/ϵ) samples.A wasteful random-coordinate subsampling method would instead incur an additional factor b; the improved algorithm uses more information in each sample.Source: a. Multi-bit output · p. 47

b. Quantum oracle sketching for correlated data

For hierarchical correlated data, the per-query sample overhead is the repetition number R_D; with a uniform marginal and t = O(N), O(NR_D/ϵ) samples suffice.At t = Nπ, the alternating process needs O(N/ϵ) samples, whereas the repetitive process needs O(N^2/ϵ), which is unavoidable because seeing all N inputs takes Ω(N^2) samples.Source: b. Quantum oracle sketching for… · pp. 48–49
For correlated data, quantum oracle sketching bounds both variance and correlation-induced bias, while expected conditional diamond-distance errors accumulate additively.The expected conditional error is the appropriate measure for correlated data and reduces to the diamond error of the expected channel in the IID case.Source: b. Quantum oracle sketching for… · pp. 49–51

c. Unknown marginal distribution

For unknown, non-uniform marginals, QSVT thresholds rotation angles using one ancilla qubit; when pmax/pmin ≤ polylog(N) and pmin ≥ Ω(1/N), sample complexity remains ˜O(N).Learning and storing p(x) for every x may require exponentially large memory; the proposed approach avoids that requirement and has polylog(N) processing time per sample.Source: c. Unknown marginal distribution · p. 52

5. Linear algebra primitives

Quantum oracle sketching constructs sparse oracles and block encodings for sparse matrices, and prepares quantum states corresponding to arbitrary vectors.Source: §5 · p. 54

a. Linear algebra data

The linear-algebra data model treats matrix samples as random nonzero elements and vector samples as random components, with rectangular inputs handled by zero-padding embeddings.The construction assumes N is a power of two, achievable by padding to a dimension between N and 2N.Source: a. Linear algebra data · pp. 54–55

b. Sparse oracles

Quantum oracle sketching implements the standard sparse oracles for matrices with specified row and column sparsities.Source: b. Sparse oracles · p. 55
For s=polylogN, quantum oracle sketching implements sparse oracles using polylog(N) qubits and ˜O(RN/ϵ) samples.Processing each sample takes polylog(N, 1/ϵ) time; the guarantees also cover adjoint and controlled sparse element oracles.Source: b. Sparse oracles · p. 55
The sparse element oracle is built by accumulating sampled matrix-entry bits into phase oracles and converting them to XOR oracles.The proof invokes quantum oracle sketching on the streamed nonzero entries to implement the phase oracles.Source: b. Sparse oracles · p. 56

2 E[max

The sparse index-oracle construction uses cumulative counts, QSVT thresholding, and binary search to recover nonzero column indices; the column version follows by swapping rows and columns.The cumulative counter encodes C(i, l) − k in a phase, and QSVT maps its sign to the threshold bit used during the search.Source: b. Sparse oracles · pp. 56–57, §2 · pp. 60–61
The sparse index oracle is constructed from a cumulative counter oracle by writing the selected column index bit by bit, then erasing the k register with a second binary search.The resulting circuit uses 2n + ⌈log(sr)⌉ + 1 qubits and n + ⌈log(sr)⌉ ≤ 2n uses of the counter oracle.Source: §2 · pp. 62–63

c. Block encodings

Sparse-oracle conversion yields an ϵ-approximate block encoding of an s-sparse matrix using O(log(N) + b + log^2.5(1/ϵ)) qubits and polylog(N, 1/ϵ) processing time per sample.The construction uses the sparse index and element oracles and also applies to the inverse and controlled unitaries.Source: c. Block encodings · p. 63

d. Quantum state sketching

Block-encoding access alone can require ˜O(N^2) samples to prepare a computational-basis state, while quantum state sketching handles any vector with ˜O(N) samples.A Hadamard transform makes variance depend on the vector’s 2-norm, but under hierarchical data generation variance can blow up and bias can conflict with valid block encoding.Source: d. Quantum state sketching · pp. 64–66
Quantum state sketching prepares the state for any N-dimensional vector using ˜O(N) samples, O(log N) qubits, and polylog(N, 1/ϵ) processing time per sample.The construction also supports the inverse and controlled preparation unitaries.Source: d. Quantum state sketching · p. 65
O(log N)-wise independent random phases make the procedure efficient by decoupling data samples, controlling variance, and making b′ roughly flat with high probability.The seeded randomized Hadamard transform yields a roughly flat vector with probability at least 1 − δ.Source: d. Quantum state sketching · p. 66
The algorithm estimates ∥b∥2, applies seeded phase gates to samples on the fly, then uses block encoding, QSVT, and amplitude amplification to prepare |b⟩.The random seed is stored classically, while the phase function is computed efficiently; the final inverse transform recovers |b⟩ from |b′⟩.Source: d. Quantum state sketching · p. 68
With M′ = 4RN/δ samples, norm estimation succeeds with probability at least 1 − δ.The empirical estimate of ∥b∥2 is used to normalize later block encodings.Source: d. Quantum state sketching · pp. 68–69
With total sample complexity M = ˜O(RN/ϵ), the algorithm prepares a state O(ϵ)-close to |b⟩ with probability at least 1 − O(ϵ).The resulting overall error in trace distance is O(ϵ).Source: d. Quantum state sketching · p. 68
State unpreparation follows by inverting the state-preparation procedure, and controlled versions follow by controlling each gate, completing the proof of Theorem D.24.The preceding passage sets ϵ3 = δ = ϵ/10 in the sample-complexity calculation.Source: d. Quantum state sketching · p. 74

3. Sample-space lower bound

For NOPE, the sample-space product MS is lower-bounded by Ω(NQC), relating the required classical resources to the target property’s query complexity.The proof simulates a learner using forged samples and oracle queries; its query count is bounded by the learner’s information flow, while any query algorithm requires at least QC queries.Source: d. Quantum state sketching · p. 75, §3 · pp. 77–78

Appendix E: Classical hardness

Dynamic NOPE keeps the target property fixed while the oracle changes over time, yielding a super-polynomial sample requirement for classical machines slightly smaller than the sample-space bound demands.The hardness framework is intended to transfer to applications by reducing them to NOPE or dynamic NOPE.Source: Appendix E · p. 75

1. Noisy oracle property estimation

NOPE asks learners to estimate a Boolean oracle property from noisy samples, using a low-discrepancy encoding whose partial inputs reveal limited information about the oracle value.The framework establishes sample and space lower bounds for classical learners solving the task.Source: §1 · pp. 76–77

a. Preliminaries

Low discrepancy makes the noisy encoding obfuscating: a partial input cannot reveal much about its output, supporting the NOPE hardness construction.The encoding has discrepancy at most 2^-ηb for constant η > 0.Source: §1 · p. 76

2. Recap of classical learning algorithms

The hardness model tracks classical machine space S and sample complexity M, representing learners as branching programs and covering computational models weaker than this non-uniform model.The learner’s transcript records its state when the data-generation situation changes.Source: §2 · p. 77

a. Preliminaries

Parity-bias bounds across all nonempty subsets imply near-uniformity, while bounds only for subsets of size at least t imply H∞(Z)≥m−t log m−1.These are variants of Vazirani’s lemma [89], [92, Lemma 2.5] and its min-entropy formulation [92, Lemma 2.6].Source: a. Preliminaries · pp. 80–81
For sufficiently obfuscating encodings, structured guesses have marginals within 2^-γb total variation distance of guesses conditioned on a consistent oracle value.The uniform marginals lemma assumes b≥c log N and disc(g)≤2^-ηb.Source: a. Preliminaries · p. 82
A density-restoring partition supports maintaining dense guesses, and the dangerous-values lemma shows dangerous guesses are unlikely when the guesses are structured.The text motivates restoration because conditioning on the learning algorithm’s path can reduce guess density.Source: a. Preliminaries · pp. 83, 85

b. Simulation

For b≥c log N and disc(g)≤2^-ηb, any randomized classical learner using M≤2NTb samples admits a parallel decision-tree simulation with transcript distribution 2^-ηb/8-close in total variation.The tree receives any input o∈{0,1}^N; its output distribution is close to the learner’s transcript on data generated from D_N.Source: b. Simulation · p. 86
The simulation maintains dense rectangles of candidate noisy oracle encodings, generates fake data for the learner, and restores density by querying fixed oracle coordinates when needed.It tracks error-accumulation quantities and halts if they exceed specified thresholds.Source: b. Simulation · p. 86

c. Simulation is correct

The simulated transcript is 2^-ηb/8-close in total variation to the classical learner’s transcript when M ≤ 2NTb.The proof establishes this by comparing the simulation with an ideal encoding and using the bound on the number of situation changes.Source: c. Simulation is correct · p. 90

d. Simulation does not query too much

Density restoration decreases deficiency by at least ηb|Iji|/6920 per queried block, and summing the deficiency accounting yields a bound on total query complexity.The argument starts from zero deficiency and accounts for the learner’s transcript probabilities and density-restoring queries.Source: d. Simulation does not query too much · p. 91

e. Proof of Theorem E.2

The proof of Theorem E.2 considers any randomized classical learner with space S and sample complexity M, reducing randomized learners to deterministic ones by fixing their random bits.The learner’s input form is I = [N]×{0, 1}b ×{0, 1}.Source: b. Simulation · p. 86, e. Proof of Theorem E.2 · p. 91
The proof of Theorem E.2 turns a learner’s transcript into a query algorithm with query complexity O(MS/(Tb)) and the same δ-error guarantee.A transcript approximation followed by a union-bound argument yields the query algorithm’s correctness guarantee.Source: e. Proof of Theorem E.2 · pp. 91–92

4. Bootstrap with one more time scale

Dynamic NOPE estimates a fixed binary property while the oracle changes over time, and its target is the parity of the properties of L sampled oracles.The construction adds a second time scale and makes the target parity depend on L oracle properties.Source: §4 · pp. 92–93
With insufficient memory, classical learners cannot do much better than random guessing on one dynamic NOPE block; achieving at least 2/3 success requires super-polynomially many samples.The single-block hardness result applies under the theorem’s stated query-complexity and encoding assumptions.Source: §4 · p. 93

a. Distributional sample-space lower bound

The distributional sample-space lower bound adapts the NOPE argument to random oracles by replacing worst-case query complexity with distributional query complexity.It reduces a learner’s transcript to a query algorithm that predicts the property on an oracle drawn from the relevant distribution.Source: a. Distributional sample-space lower… · pp. 93–94

b. Learning XOR Lemma

Under the single-instance success cap, the learning XOR lemma bounds a classical learner’s success on the XOR task by 1/2 + (2δ)^(L/2).The lemma concerns L instances with randomly sampled labels and allows the learner to correlate its work across instances.Source: b. Learning XOR Lemma · pp. 94–95

c. Derandomization

Derandomizing the instance labels preserves success while increasing space by ⌈log L⌉ and samples to T1NL, using a fixed round-robin label order.The constructed learner selects a random label for each chunk and processes the corresponding N samples.Source: c. Derandomization · p. 95

d. Derandomized learning XOR lemma

For interleaved instances, the derandomized XOR lemma uses a communication-game analysis to bound success while accounting for correlations between instances.The construction addresses the interleaved data order inherent in randomly sampled instance labels.Source: d. Derandomized learning XOR lemma · pp. 95–96
Each individual problem instance has expected conditional bias at most 2δ under the communication protocol.The proof argues that greater bias would yield a learner with space T1LS and sample complexity T1N that predicts the instance bit with probability above 1/2+δ.Source: d. Derandomized learning XOR lemma · p. 97
Conditioned on any final blackboard content, each instance’s data are independent of the other instances’ data.This conditional-independence property lets the proof treat the instance bits as independent after observing the protocol transcript.Source: d. Derandomized learning XOR lemma · pp. 98–99
For independent random bits, the XOR bias equals the product of their biases, so bias is dampened exponentially across instances.The stated two-bit identity is bias(X1 ⊕X2) = bias(X1)bias(X2).Source: d. Derandomized learning XOR lemma · p. 98

e. Proof of Theorem E.30

p_succ ≤ 1/2+(2δ)^L/2 for the original learner, by reducing it to an ordered-data learner and applying Theorem E.32.The reduction preserves success probability while increasing space from S to S+⌈log L⌉ and sample complexity from T1N to T1NL.Source: e. Proof of Theorem E.30 · p. 99

f. Low advantage leads to large sample complexity

The section uses the learning XOR lemma’s exponentially decaying prediction advantage to derive a sample-complexity lower bound through a hybrid argument. It shows that a learner succeeding with many samples would imply a learner with the same space and only τ samples that has nontrivial advantage.

f. Low advantage leads to large sample complexity

The learning XOR lemma says prediction advantage for a single γ ∈{0, 1}^L instance decays exponentially with L, motivating the translation of low advantage into larger sample complexity.The section identifies a hybrid argument as the means of making that translation.Source: f. Low advantage leads to large sample… · p. 99
Any same-space learner succeeding with M samples at probability at least 2/3 implies a τ-sample learner succeeds with probability at least 1/2 + 1/(6⌈M/τ⌉).The implication is obtained by constructing a learner on one τ-sample block; thus, if τ-sample success is bounded by 1/2+δ, the many-sample learner must be inconsistent with that bound whenever 1/(6⌈M/τ⌉) exceeds δ.Source: f. Low advantage leads to large sample… · pp. 99–100
The hybrid construction replaces blocks of τ samples one at a time and uses an adjacent pair of hybrids to build a τ-sample learner from the many-sample learner.It pads the sample count to M′=rτ, where r=⌈M/τ⌉, and feeds the target block between blocks drawn from D1 and D0.Source: f. Low advantage leads to large sample… · p. 100

g. Proof of Theorems E.27 and E.28 · 5. Connect to applications

The first section proves classical hardness and sample-complexity results for dynamic NOPE. The next connects dynamic NOPE to application tasks by constructing and embedding a quantum circuit whose hardness transfers to those tasks.

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

Theorem E.27’s classical single-block hardness proof combines a distributional sample-space lower bound with the learning XOR lemma.The proof considers a randomized classical learner that solves dynamic NOPE with probability at least 2/3.Source: g. Proof of Theorems E.27 and E.28 · p. 101
Theorem E.28’s proof applies the low-advantage sample-complexity blow-up result to establish its sample-complexity conclusion.The passage identifies the low-advantage result as Theorem E.37 and says this concludes the proof of Theorem E.28.Source: g. Proof of Theorems E.27 and E.28 · p. 101

5. Connect to applications

The application framework aims to connect dynamic NOPE to tasks including solving linear systems, binary classification, and dimension reduction.The section also names other application tasks explored later.Source: §5 · p. 101
The framework first focuses on Forrelation [95] and develops a distributional version of it.It takes the inner product function as the noisy encoding function.Source: §5 · p. 101
The section shows that inner product is a good noisy encoding function and proves useful lemmas for connecting dynamic NOPE to applications.Source: §5 · p. 101
An efficient quantum circuit for dynamic NOPE is embedded into linear-system solving, binary classification, and dimension reduction, transferring dynamic NOPE’s hardness to these tasks.The full application hardness proofs are deferred to Section F.Source: §5 · p. 101

a. Forrelation and inner product … d. Connect to binary classification

This section develops the Forrelation and inner-product ingredients for dynamic NOPE, constructs a compact quantum circuit, and connects quantum circuits to sparse, well-conditioned linear systems and least-squares SVM classification, whose predictions can encode circuit output observables.

a. Forrelation and inner product

Forrelation exhibits a quantum-classical query-complexity separation: quantum complexity is Oε(1), while classical complexity is Ω(N^(1−ε)), for any arbitrarily small constant ε > 0.The classical distributional query complexity for identifying pγ remains the same as that in Theorem E.39 up to a factor of K.Source: a. Forrelation and inner product · p. 102
The inner-product noisy encoding function has discrepancy disc(g)≤2^-b/2.This supplies the low-discrepancy encoding used with Forrelation.Source: a. Forrelation and inner product · pp. 103–104

b. Quantum circuit for dynamic NOPE

The circuit uses log N + O(log log N) space and returns B with success probability at least 0.9 when its first (ancilla) qubit is measured; its gate complexity is O(log^3 N log log N) and query complexity is O(log^2 N log log N).All other qubits are in the |0⟩ state.Source: b. Quantum circuit for dynamic NOPE · pp. 105, 107

c. Connect to linear systems

The circuit embedding yields a real, symmetric O(s)-sparse linear system with operator norm ∥A∥≤1 and condition number κ≤4T.The embedding is used to connect circuit execution to the hardness of solving a linear system.Source: c. Connect to linear systems · p. 107
The linear-systems construction yields a real symmetric O(s)-sparse matrix with condition number κ≤4T.Source: c. Connect to linear systems · pp. 107–108

d. Connect to binary classification

A size-T quantum circuit embeds into an unregularized least-squares SVM with D=N and a sparse test vector, whose prediction determines sgn(⟨ψ|Z1|ψ⟩).This establishes BQP hardness of binary classification.Source: d. Connect to binary classification · p. 109
The embedding uses 48T′2^n real samples and features and a 4-sparse test vector; its training matrix is O(s)-sparse, has norm ≤1, and condition number κ≤4T′.Source: d. Connect to binary classification · p. 110

e. Connect to dimension reduction … c. Quantum algorithm

This section develops dimension reduction through a circuit-to-PCA embedding and presents linear-system applications of quantum oracle sketching, including static and dynamic systems and quadratic-form estimation. It also describes a quantum-query instantiation using sample-built random unitaries, with total error δ/2 and output distribution δ/2-close in total variation to the ideal algorithm’s output.

e. Connect to dimension reduction

PCA projects a test vector onto the top eigenvector; the circuit embedding makes its 1D representation sufficient to determine a quantum circuit’s output, establishing BQP-hardness given a good guiding vector.The construction uses a sparse test vector and a sparse guiding vector with good overlap with the principal component.Source: e. Connect to dimension reduction · p. 111

Appendix F: Applications

Quantum oracle sketching applies end-to-end to linear systems, binary classification, and dimension reduction; at equal sample counts, classical machines need exponentially larger size, and undersized machines need super-polynomially more samples dynamically.The applications section states that the classical size lower bound applies across these tasks, while the dynamic sample lower bound applies when classical machines lack sufficient size.Source: Appendix F · p. 114

a. Problem formulation

The task estimates a normalized quadratic form of the linear-system solution from random nonzero matrix entries and vector components, rather than writing down the full solution.The formulation assumes poly(log N) matrix sparsity and condition number, and an efficiently measurable matrix defining the quadratic form.Source: a. Problem formulation · pp. 115–116

b. Main results

With ˜O(RN) samples, poly(log N)-size quantum machines attain 1/poly(log N) error; classical machines of size o(N^(1−ζ)) cannot attain constant error and success above 1/2+1/N^ω(1).The quantum machine also has high success probability and poly(log N) processing time per sample.Source: b. Main results · p. 116
At τ=˜O(RN), poly(log N)-size quantum machines solve dynamic systems using ˜O(RN) samples, while classical machines sized o(N^(1−ζ)) require at least RN^ω(1) samples.The classical lower bound applies to machines achieving constant error and success probability at least 2/3; quantum processing time per sample is poly(log N).Source: b. Main results · pp. 116–117

c. Quantum algorithm

Quantum oracle and state sketching instantiate quantum linear-system-solver queries to estimate efficiently measurable quadratic forms, with poly(log N) processing time per sample under polylogarithmic parameter bounds.The method combines quantum oracle sketching, quantum state sketching, a quantum linear-system solver, and amplitude estimation.Source: c. Quantum algorithm · p. 117
It replaces block-encoding and state-preparation queries with sample-built random unitaries, using coefficient data for A and bias data for |b⟩.The algorithm discards bias data for the block-encoding queries and coefficient data for the state-preparation queries.Source: c. Quantum algorithm · p. 119
The instantiated query algorithm has total error E1 + E2 + E3 = 3 · δ/6 = δ/2, leaving its output distribution δ/2-close in total variation to θ̂0.The output is a classical random variable.Source: c. Quantum algorithm · p. 119

d. Classical hardness … b. Main results

The section formulates static and dynamic binary-classification tasks and establishes their classical hardness through a reduction from dynamic NOPE to a sparse linear system. It then presents exponential quantum advantages for these tasks, while outlining prediction and sample-complexity limits for smaller classical machines.

d. Classical hardness

The hardness reduction embeds a dynamic-NOPE quantum circuit into a sparse linear system whose normalized quadratic form encodes the oracle bit, so a classical solver would decide that bit.The constructed systems are symmetric, O(1)-sparse, and have condition number O(log^3 N log log N).Source: d. Classical hardness · pp. 119–121
With ˜O(RN) samples, classical learners need Ω(N^(1−ζ)) space to solve the static linear-system task with error 0.03 and success above 1/2 + 1/N^ω(1), for any constant ζ > 0.The hardness follows from Theorem F.7; the first ˜O(RN) samples of the constructed dynamic task also form valid non-dynamic data.Source: d. Classical hardness · pp. 119, 121
For dynamic linear systems, classical learners with space o(N^(1−ζ)) require super-polynomially many samples to achieve error 0.03 and success probability at least 2/3, for any constant ζ > 0.The task has repetition number R and refreshing time τ = ˜O(RN).Source: d. Classical hardness · pp. 119, 121

2. Binary classification

Binary classification predicts labels of unseen feature vectors; the section uses least-squares SVM and characterizes tractability by sparsity, regularized condition number, and test-vector margin.The stated regime has very large sample count N and feature dimension D, while the task remains sparse, well-conditioned, and classifiable.Source: §2 · pp. 123–124

a. Problem formulation

The classification formulation allows hierarchical sampling of sparse feature-vector entries and their labels with bounded repetition, and asks for predictions on all properly normalized sparse, classifiable test vectors.The sampling process may be arbitrary subject to the specified form; the stated results also generalize to partial feature vectors or random, possibly unmatched labels.Source: a. Problem formulation · p. 124
The tasks classify sparse, classifiable test vectors using sparse, well-conditioned normalized features; the dynamic variant allows training data to refresh while test labels remain fixed.The dynamic setup uses bounded repetition and refreshing time, with a fixed classification rule across training sets.Source: a. Problem formulation · p. 125

b. Main results

With ˜O(RN) samples, a poly(log D)-size quantum machine classifies with high success probability, while classical machines of size o(D^(1−ζ)) cannot exceed success probability 1/2 + 1/N^{ω(1)}; quantum processing takes poly(log D) time per sample.The classical size bound holds for any constant ζ > 0.Source: b. Main results · p. 125
For dynamic classification with refreshing time τ = ˜O(RN), a poly(log D)-size quantum machine succeeds with ˜O(RN) samples, whereas classical machines of size o(D^(1−ζ)) need at least RN^{ω(1)} samples to reach probability 2/3.Quantum processing takes poly(log D) time per sample; the classical size bound holds for any constant ζ > 0.Source: b. Main results · p. 126
Together, Theorems F.11 and F.12 establish unconditional exponential quantum advantages for binary classification.Source: b. Main results · p. 126

c. Quantum algorithm … a. Problem formulation

This section develops quantum and classical formulations for high-dimensional SVM classification and dimension reduction, including a quantum algorithm using sketching, ridge regression, and classical shadows and definitions of static and dynamic dimension-reduction tasks. It also proves classical hardness results for binary classification and contrasts quantum processing with classical sample and size requirements.

c. Quantum algorithm

Quantum oracle and state sketching instantiate a ridge-regression solver, while interferometric classical shadows produce a classical representation of its weight vector for predicting test labels.Theorem F.13 implies the quantum algorithm parts of Theorems F.11 and F.12.Source: c. Quantum algorithm · pp. 126–128
The ridge-regression solver uses O(log(max{N,D}) + log(κreg)) qubits and O(κreg log(κreg) log(κreg/ϵ)) gates and queries.It prepares the normalized ridge-regression weight vector from X and y.Source: c. Quantum algorithm · p. 127
Interferometric classical shadows preserve the sign of ⟨x|w⟩ in reusable classical data, addressing the limitation that measuring |x⟩⟨x| reveals only its squared magnitude.The standard Hadamard test obtains sign information but does not provide a universal classical shadow for predicting on many later test vectors.Source: c. Quantum algorithm · p. 127

d. Classical hardness

Classical learners using the quantum algorithms’ sample count need size Ω(D^(1−ζ)) to beat random guessing, while dynamic-task learners of size o(D^(1−ζ)) need superpolynomially many samples.These hardness results follow by reducing dynamic Noisy Oracle Property Estimation to binary classification.Source: d. Classical hardness · p. 130
The hardness construction embeds dynamic NOPE into binary classification by making a fixed sparse test vector’s label encode the oracle property.It uses K-Forrelation as the oracle property and an inner product as the noisy encoding.Source: d. Classical hardness · p. 130
A poly(log D)-size quantum machine solves dimension reduction with ˜O(N) samples, while a classical machine of size O(D^0.99) needs at least super-polynomially many samples in N.The paper says this classical hardness, together with the quantum algorithm result, completes the quantum-advantage claims.Source: d. Classical hardness · pp. 132, 134

3. Dimension reduction

Dimension reduction is framed as one-dimensional PCA: project test vectors onto the top covariance eigenvector, under sparse-data, spectral-gap, and constant-quality guiding-vector conditions.The spectral gap separates the principal component from competing modes, while the guiding vector supplies an initial estimate with constant overlap.Source: §3 · pp. 134–135

a. Problem formulation

The static task estimates, to additive error ϵ, the one-dimensional representations of any-size sets of sparse test vectors using samples from a sparse, gapped dataset with repetition bounded by R.The task assumes a guiding vector of quality χ; the data-generation process may be arbitrary subject to the stated requirements.Source: a. Problem formulation · pp. 135–136
The dynamic task estimates fixed test-vector representations to 2ϵ error as the training matrix changes every τ steps, with each matrix sparse, gapped, and similarly represented.The data process has repetition at most R and refreshing time τ, and the guiding vector must have quality at least χ across the matrices.Source: a. Problem formulation · p. 136

b. Main results · c. Quantum algorithm · d. Classical hardness

This section establishes quantum advantages for static and dynamic dimension reduction, presenting the quantum algorithms alongside NOPE-based classical-hardness results; it also describes a non-dynamic result with an improved space-bound exponent under a different data-generation process.

b. Main results

With ˜O(RND^(1−χ)) samples, a poly(log D)-size quantum machine solves dimension reduction at 1/poly(log D) error, while classical machines of size o(D^((1−ζ)χ)) cannot.The classical lower bound holds for any constant ζ > 0 and success probability above 0.67; quantum per-sample processing time is poly(log D).Source: b. Main results · p. 136
For χ > 1/2, a poly(log D)-size quantum machine solves dynamic dimension reduction with ˜O(RND^(1−χ)) samples, whereas classical size o(D^((1−ζ)(2χ−1))) requires RN^ω(1) samples.The classical lower bound applies to algorithms achieving 1/poly(log D) error and success probability at least 2/3; quantum per-sample processing time is poly(log D).Source: b. Main results · p. 137

c. Quantum algorithm

The quantum algorithm prepares the principal component as the ground state of −X^T X, then uses interferometric classical shadows to output classical 1D predictions for test vectors.It combines quantum oracle sketching, quantum state sketching, and ground-state preparation; the guiding vector’s overlap with the principal component supports that preparation.Source: c. Quantum algorithm · pp. 137–138

d. Classical hardness

The classical hardness proof embeds dynamic NOPE into dimension reduction, encoding the oracle property in a fixed sparse test vector’s 1D representation so any classical solver can solve NOPE.The construction uses K-Forrelation as the oracle property and the inner product as the noisy encoding function.Source: d. Classical hardness · p. 140
A different data-generation process based on the distributional sample-space lower bound (Theorem E.29) improves the non-dynamic dimension-reduction exponent from 2χ−1 to χ; quantum advantages are proved for both dynamic and non-dynamic settings.Source: d. Classical hardness · pp. 142–144
The hardness reduction generates matching training samples online, preserving the learner’s space and success probability while reducing source samples by a factor of T3.For Theorem F.26, the corresponding reduction uses R repetitions and M′ = M/R source samples.Source: d. Classical hardness · p. 144
For a guiding vector of constant quality χ ∈ (0, 1], any randomized classical learner using ˜O(RND1−χ) samples cannot solve dimension reduction with error ϵ = Θ(1/ log2(N)) and success probability more than 0.67.Source: d. Classical hardness · p. 143