arxiv: 2604.07639 · v1 · submitted 2026-04-08 · 🪐 quant-ph · cs.AI· cs.CC· cs.IT· cs.LG· math.IT

Recognition: unknown

Exponential quantum advantage in processing massive classical data

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

Authors on Pith no claims yet

Pith reviewed 2026-05-10 17:05 UTC · model grok-4.3

classification 🪐 quant-ph cs.AIcs.CCcs.ITcs.LGmath.IT

keywords quantum advantagemachine learningquantum oracle sketchingclassical shadowsclassificationdimension reductionclassical data processing

0 comments

The pith

A small quantum computer of polylog size can classify and reduce dimensions of massive classical data on the fly, while any classical machine needs exponentially larger size.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that polylog-sized quantum computers can handle large-scale classification and dimension reduction on massive classical datasets by processing samples on the fly. This is achieved through quantum oracle sketching, which provides superposition access to the data from random classical samples, combined with classical shadows to build succinct models. In contrast, classical machines require exponentially larger size to match the prediction performance, and those that are still too small need superpolynomially more samples and time. The quantum advantage is validated on real tasks including single-cell RNA sequencing and movie review sentiment analysis, showing four to six orders of magnitude size reduction with under 60 logical qubits. The separation holds even with unlimited classical time or if BPP equals BQP, depending only on the correctness of quantum mechanics.

Core claim

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

What carries the argument

Quantum oracle sketching, an algorithm that grants quantum superposition access to classical data using only random classical samples, combined with classical shadows to construct succinct models.

If this is right

Quantum machines of polylog size match classical performance on massive data tasks.
Classical machines require an exponential increase in size to achieve the same results.
Classical machines below the size threshold need superpolynomial extra samples and time.
The separation applies to practical tasks such as RNA sequencing and sentiment analysis.
The advantage persists even if classical machines have unlimited time or if BPP equals BQP.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

This approach could enable practical quantum use in big-data machine learning without full quantum data loading overhead.
It positions classical-data machine learning as a concrete test domain for quantum advantage in near-term devices.
The sketching technique might extend to other data-intensive fields like genomics or large-scale statistical modeling.
If the procedure works efficiently in practice, it could encourage development of hybrid quantum-classical pipelines for data analysis.

Load-bearing premise

The quantum oracle sketching procedure can be realized with random classical samples to grant superposition access to the data without incurring the standard loading and readout costs.

What would settle it

A classical algorithm that achieves equivalent prediction performance and succinct models on the same massive datasets using only polynomial size and sample overhead would disprove the claimed exponential separation.

Figures

Figures reproduced from arXiv: 2604.07639 by Alexander Zlokapa, Haimeng Zhao, Hartmut Neven, Hsin-Yuan Huang, Jarrod R. McClean, John Preskill, Ryan Babbush.

**Figure 2.** Figure 2: FIG. 2 [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Figure 3: FIG. 3 [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

**Figure 4.** Figure 4: FIG. 4 [PITH_FULL_IMAGE:figures/full_fig_p018_4.png] view at source ↗

**Figure 5.** Figure 5: FIG. 5 [PITH_FULL_IMAGE:figures/full_fig_p025_5.png] view at source ↗

**Figure 6.** Figure 6: FIG. 6 [PITH_FULL_IMAGE:figures/full_fig_p034_6.png] view at source ↗

**Figure 7.** Figure 7: FIG. 7 [PITH_FULL_IMAGE:figures/full_fig_p075_7.png] view at source ↗

**Figure 8.** Figure 8: FIG. 8 [PITH_FULL_IMAGE:figures/full_fig_p114_8.png] view at source ↗

**Figure 9.** Figure 9: FIG. 9 [PITH_FULL_IMAGE:figures/full_fig_p123_9.png] view at source ↗

**Figure 10.** Figure 10: FIG. 10 [PITH_FULL_IMAGE:figures/full_fig_p134_10.png] view at source ↗

read the original abstract

Broadly applicable quantum advantage, particularly in classical data processing and machine learning, has been a fundamental open problem. In this work, we prove that a small quantum computer of polylogarithmic size can perform large-scale classification and dimension reduction on massive classical data by processing samples on the fly, whereas any classical machine achieving the same prediction performance requires exponentially larger size. Furthermore, classical machines that are exponentially larger yet below the required size need superpolynomially more samples and time. We validate these quantum advantages in real-world applications, including single-cell RNA sequencing and movie review sentiment analysis, demonstrating four to six orders of magnitude reduction in size with fewer than 60 logical qubits. These quantum advantages are enabled by quantum oracle sketching, an algorithm for accessing the classical world in quantum superposition using only random classical data samples. Combined with classical shadows, our algorithm circumvents the data loading and readout bottleneck to construct succinct classical models from massive classical data, a task provably impossible for any classical machine that is not exponentially larger than the quantum machine. These quantum advantages persist even when classical machines are granted unlimited time or if BPP=BQP, and rely only on the correctness of quantum mechanics. Together, our results establish machine learning on classical data as a broad and natural domain of quantum advantage and a fundamental test of quantum mechanics at the complexity frontier.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper claims exponential quantum size advantage for classical data classification and reduction via quantum oracle sketching from random samples, but the separation depends on whether that sketching truly avoids scaling costs.

read the letter

The paper claims that a small quantum computer can achieve exponential size advantage over classical ones when doing classification and dimension reduction on massive classical data sets. It does this by processing random samples on the fly with a new method called quantum oracle sketching, combined with classical shadows. The new element is this sketching algorithm that supposedly lets the quantum machine access the data in superposition using only classical samples, bypassing traditional loading bottlenecks. They demonstrate it on single-cell RNA sequencing and movie review sentiment analysis, reporting size reductions of four to six orders of magnitude with under 60 logical qubits. The argument that the advantage persists even under BPP=BQP is also a clear point in their favor. The paper handles the connection to practical applications reasonably well and grounds the claims in both theory and examples. The math appears to draw from established tools like classical shadows without reinventing basics. Where it is softer is in the precise accounting for the sketching step. The exponential separation assumes that the procedure delivers succinct models without hidden costs that grow with data size, and that no classical method can achieve similar performance with non-exponential resources. If the sample complexity or circuit requirements turn out to scale in ways that classical learners could also use, the gap narrows. The full error analysis and lower bound details would need careful review to confirm there are no loopholes. This work is for quantum information theorists and ML researchers exploring quantum advantages in data-heavy tasks. Readers who follow complexity results in quantum computing would get the most from it, as it tries to establish a broad domain for such advantages. It deserves a serious referee because the claim is significant and the construction is original, even if revisions are likely needed on the resource bounds.

Referee Report

2 major / 2 minor

Summary. The manuscript claims to prove that a polylogarithmic-sized quantum computer can perform large-scale classification and dimension reduction on massive classical data by processing random samples on the fly via quantum oracle sketching combined with classical shadows, while any classical machine achieving identical prediction performance must be exponentially larger in size (and even exponentially larger classical machines require superpolynomially more samples and time). It further asserts empirical validation on real-world tasks including single-cell RNA sequencing and movie-review sentiment analysis, with 4-6 orders of magnitude size reduction using fewer than 60 logical qubits, and states that the advantage holds even if BPP=BQP.

Significance. If the proof and resource accounting hold, the result would establish machine learning on classical data as a broad, natural domain of quantum advantage and a complexity-theoretic test of quantum mechanics. The claimed parameter-free separation from classical complexity bounds, together with the empirical demonstrations on practical datasets, would be a substantial contribution; the persistence of the advantage under the assumption BPP=BQP is a particularly strong feature.

major comments (2)

[quantum oracle sketching procedure] The exponential separation rests on the quantum oracle sketching procedure granting superposition access to arbitrary classical data from random samples without incurring standard loading or readout costs that scale with data dimension. The manuscript asserts this circumvents the bottleneck and enables succinct models, but provides neither the full derivation of the procedure nor explicit bounds on circuit depth, sample complexity, or effective model size (see the description of quantum oracle sketching and its combination with classical shadows). Without these, the claimed separation from any classical machine cannot be verified.
[proof of classical lower bound] The classical lower-bound argument—that any classical machine achieving the same prediction performance requires exponentially larger size—is load-bearing for the central claim yet lacks a complete, self-contained proof or reduction in the main text. The abstract states the result holds even with unlimited classical time, but the precise complexity-theoretic assumption and the handling of post-processing costs are not detailed enough to assess internal consistency.

minor comments (2)

[empirical validation] The empirical sections should include explicit baselines, exact metrics for the reported 4-6 orders of magnitude size reduction, and data-exclusion criteria for the single-cell RNA and sentiment-analysis experiments to allow independent verification.
[model construction] Notation for the succinct classical models constructed via classical shadows should be clarified with respect to the input data dimension and the polylog qubit count to avoid ambiguity in the resource comparison.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive feedback. The two major comments identify areas where the presentation can be strengthened for clarity and verifiability. We address each point below and will revise the manuscript accordingly.

read point-by-point responses

Referee: [quantum oracle sketching procedure] The exponential separation rests on the quantum oracle sketching procedure granting superposition access to arbitrary classical data from random samples without incurring standard loading or readout costs that scale with data dimension. The manuscript asserts this circumvents the bottleneck and enables succinct models, but provides neither the full derivation of the procedure nor explicit bounds on circuit depth, sample complexity, or effective model size (see the description of quantum oracle sketching and its combination with classical shadows). Without these, the claimed separation from any classical machine cannot be verified.

Authors: We agree that explicit bounds and a self-contained derivation will make the separation easier to verify. In the revised manuscript we will add a dedicated subsection that derives the quantum oracle sketching procedure from first principles, including the circuit construction that achieves superposition access from random classical samples. We will state the circuit depth (polylogarithmic in the data dimension), the sample complexity (logarithmic in the dimension for the sketching step), and the resulting effective model size after combination with classical shadows. These additions will directly show how the procedure avoids dimension-dependent loading and readout costs while preserving the exponential separation. revision: yes
Referee: [proof of classical lower bound] The classical lower-bound argument—that any classical machine achieving the same prediction performance requires exponentially larger size—is load-bearing for the central claim yet lacks a complete, self-contained proof or reduction in the main text. The abstract states the result holds even with unlimited classical time, but the precise complexity-theoretic assumption and the handling of post-processing costs are not detailed enough to assess internal consistency.

Authors: We accept that the lower-bound argument requires a more explicit, self-contained treatment in the main text. In the revision we will insert a complete proof (or a clearly labeled reduction) that any classical model achieving the same prediction accuracy must be exponentially larger in size. The argument is information-theoretic and concerns minimum model size (space), so it holds even when classical machines are granted unlimited time; post-processing costs are accounted for by showing they cannot reduce the required size below the exponential threshold. We will also state the precise complexity assumption (standard, and the separation survives even if BPP = BQP) and confirm that the abstract claim is consistent with the proof. revision: yes

Circularity Check

0 steps flagged

No circularity: proof relies on external quantum mechanics and complexity separation

full rationale

The paper's core derivation is a mathematical proof establishing an exponential separation between a polylog-sized quantum device using oracle sketching plus classical shadows and any classical machine achieving equivalent performance. This rests on standard quantum mechanics assumptions and complexity-theoretic lower bounds rather than any self-referential definition, fitted parameter renamed as prediction, or load-bearing self-citation chain. Empirical validation on RNA sequencing and sentiment data serves only as illustration and does not enter the proof. No equation or step reduces to its own inputs by construction; the result is independent of the paper's own fitted values or prior author ansatzes.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on the correctness of quantum mechanics and the functionality of the newly introduced quantum oracle sketching procedure; no numerical free parameters are mentioned in the abstract.

axioms (1)

domain assumption Correctness of quantum mechanics
The abstract states that the advantages rely only on the correctness of quantum mechanics.

invented entities (1)

quantum oracle sketching no independent evidence
purpose: Accessing the classical world in quantum superposition using only random classical data samples
New algorithmic primitive introduced to circumvent data loading and readout bottlenecks.

pith-pipeline@v0.9.0 · 5572 in / 1339 out tokens · 74696 ms · 2026-05-10T17:05:56.093839+00:00 · methodology

discussion (0)

Forward citations

Cited by 8 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Exponential quantum space advantage for Shannon entropy estimation in data streams
quant-ph 2026-04 unverdicted novelty 8.0

Shannon entropy estimation in data streams exhibits an exponential quantum space advantage over classical streaming algorithms.
QAP-Router: Tackling Qubit Routing as Dynamic Quadratic Assignment with Reinforcement Learning
quant-ph 2026-05 unverdicted novelty 7.0

QAP-Router models qubit routing as dynamic QAP and applies RL with a solution-aware Transformer to cut CNOT counts by 12-30% versus industry compilers on real circuit benchmarks.
Real-time Krylov Diagonalisation for Open Quantum Systems
quant-ph 2026-05 unverdicted novelty 7.0

Real-time Krylov subspace methods are extended to Lindblad open quantum systems and demonstrated on a Kerr resonator for estimating the Liouvillian gap in cat qubit regimes.
Block-encodings as programming abstractions: The Eclipse Qrisp BlockEncoding Interface
quant-ph 2026-04 unverdicted novelty 6.0

The Eclipse Qrisp BlockEncoding interface provides high-level programming abstractions for block-encodings, enabling easier implementation of quantum algorithms such as QSVT, matrix inversion, and Hamiltonian simulation.
Real-time Krylov Diagonalisation for Open Quantum Systems
quant-ph 2026-05 unverdicted novelty 5.0

Real-time Krylov subspace methods are adapted to Lindblad open systems and used to extract the Liouvillian gap of a two-photon-driven Kerr resonator in the cat-qubit regime.
Measuring Accuracy and Energy-to-Solution of Quantum Fine-Tuning of Foundational AI Models
quant-ph 2026-05 conditional novelty 5.0

Trapped-ion quantum fine-tuning of AI models shows linear energy scaling and 24% better classification error than classical logistic regression or SVM baselines, with a projected energy break-even at 34 qubits.
Unitaria: Quantum Linear Algebra via Block Encodings
quant-ph 2026-05 accept novelty 4.0

Unitaria is a new open-source Python library that provides a high-level, composable interface for block encodings in quantum computing, enabling automatic circuit generation and classical simulation-based verification.
Constant Factor Analysis of Optimal Quantum Linear Solvers in Practice
quant-ph 2026-04 unverdicted novelty 4.0

Adiabatic solver slightly outperforms shortcut when solution norm unknown; shortcut significantly better for non-Hermitian matrices when norm known.

Reference graph

Works this paper leans on

183 extracted references · 31 canonical work pages · cited by 7 Pith papers · 3 internal anchors

[1]

Quantum mechanical computers

Richard P Feynman. Quantum mechanical computers. Foundations of physics , 16(6):507--531, 1986

1986
[2]

Algorithms for quantum computation: discrete logarithms and factoring

Peter W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science , pages 124--134. Ieee, 1994

1994
[3]

Babbush, R

Ryan Babbush, Robbie King, Sergio Boixo, William Huggins, Tanuj Khattar, Guang Hao Low, Jarrod R McClean, Thomas O'Brien, and Nicholas C Rubin. The grand challenge of quantum applications. arXiv preprint arXiv:2511.09124 , 2025

work page arXiv 2025
[4]

Beyond NISQ : The megaquop machine

John Preskill. Beyond NISQ : The megaquop machine. ACM Transactions on Quantum Computing , 6(3):1--7, 2025

2025
[5]

Quantum measurements and the Abelian Stabilizer Problem

Alexei Kitaev. Quantum measurements and the abelian stabilizer problem. arXiv preprint quant-ph/9511026 , 1995

work page internal anchor Pith review arXiv 1995
[6]

Universal quantum simulators

Seth Lloyd. Universal quantum simulators. Science , 273(5278):1073--1078, 1996

1996
[7]

The need for structure in quantum speedups

Scott Aaronson and Andris Ambainis. The need for structure in quantum speedups. arXiv preprint arXiv:0911.0996 , 2009

work page arXiv 2009
[8]

Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T

Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, and et al. Quantum Algorithms: A Survey of Applications and End-to-end Complexities . Cambridge University Press, 2025

2025
[9]

Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

Andr \'a s Gily \'e n, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing , pages 193--204, 2019

2019
[10]

Grand unification of quantum algorithms

John M Martyn, Zane M Rossi, Andrew K Tan, and Isaac L Chuang. Grand unification of quantum algorithms. PRX Quantum , 2(4):040203, 2021

2021
[11]

Quantum machine learning

Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature , 549(7671):195--202, 2017

2017
[12]

Read the fine print

Scott Aaronson. Read the fine print. Nature Physics , 11(4):291--293, 2015

2015
[13]

Quantum random access memory

Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Physical Review Letters , 100(16):160501, 2008

2008
[14]

Resilience of quantum random access memory to generic noise

Connor T Hann, Gideon Lee, SM Girvin, and Liang Jiang. Resilience of quantum random access memory to generic noise. PRX Quantum , 2(2):020311, 2021

2021
[15]

A distillation- teleportation protocol for fault-tolerant qram,

Alexander M Dalzell, Andr \'a s Gily \'e n, Connor T Hann, Sam McArdle, Grant Salton, Quynh T Nguyen, Aleksander Kubica, and Fernando GSL Brand \ a o. A distillation-teleportation protocol for fault-tolerant QRAM . arXiv preprint arXiv:2505.20265 , 2025

work page arXiv 2025
[16]

QRAM: A survey and critique

Samuel Jaques and Arthur G Rattew. QRAM: A survey and critique . Quantum , 9:1922, 2025

1922
[17]

Is quantum advantage the right goal for quantum machine learning? PRX Quantum , 3(3):030101, 2022

Maria Schuld and Nathan Killoran. Is quantum advantage the right goal for quantum machine learning? PRX Quantum , 3(3):030101, 2022

2022
[18]

Cerezo, Martin Larocca, Diego Garc´ ıa-Mart´ ın, N

Marco Cerezo, Martin Larocca, Diego Garc \' a-Mart \' n, Nelson L Diaz, Paolo Braccia, Enrico Fontana, Manuel S Rudolph, Pablo Bermejo, Aroosa Ijaz, Supanut Thanasilp, et al. Does provable absence of barren plateaus imply classical simulability? or, why we need to rethink variational quantum computing. arXiv preprint arXiv:2312.09121 , 2023

work page arXiv 2023
[19]

On the relation between trainability and dequantization of variational quantum learning models

Elies Gil-Fuster, Casper Gyurik, Adri \'a n P \'e rez-Salinas, and Vedran Dunjko. On the relation between trainability and dequantization of variational quantum learning models. arXiv preprint arXiv:2406.07072 , 2024

work page arXiv 2024
[20]

Entanglement-induced provable and robust quantum learning advantages

Haimeng Zhao and Dong-Ling Deng. Entanglement-induced provable and robust quantum learning advantages. npj Quantum Information , 11(1):127, 2025

2025
[21]

A quantum machine learning algorithm based on generative models

Xun Gao, Z-Y Zhang, and L-M Duan. A quantum machine learning algorithm based on generative models. Science advances , 4(12):eaat9004, 2018

2018
[22]

Enhancing generative models via quantum correlations

Xun Gao, Eric R Anschuetz, Sheng-Tao Wang, J Ignacio Cirac, and Mikhail D Lukin. Enhancing generative models via quantum correlations. Physical Review X , 12(2):021037, 2022

2022
[23]

Interpretable quantum advantage in neural sequence learning

Eric R Anschuetz, Hong-Ye Hu, Jin-Long Huang, and Xun Gao. Interpretable quantum advantage in neural sequence learning. PRX Quantum , 4(2):020338, 2023

2023
[24]

Arbitrary polynomial separations in trainable quantum machine learning

Eric R Anschuetz and Xun Gao. Arbitrary polynomial separations in trainable quantum machine learning. Quantum , 10:1976, 2026

1976
[25]

Quantum-classical separations in shallow-circuit-based learning with and without noises

Zhihan Zhang, Weiyuan Gong, Weikang Li, and Dong-Ling Deng. Quantum-classical separations in shallow-circuit-based learning with and without noises. Communications Physics , 7(1):290, 2024

2024
[26]

A rigorous and robust quantum speed-up in supervised machine learning

Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. A rigorous and robust quantum speed-up in supervised machine learning. Nature Physics , 17(9):1013--1017, 2021

2021
[27]

Exponential separations between classical and quantum learners

Casper Gyurik and Vedran Dunjko. Exponential separations between classical and quantum learners. arXiv preprint arXiv:2306.16028 , 2023

work page arXiv 2023
[28]

Huang, M

Hsin-Yuan Huang, Michael Broughton, Norhan Eassa, Hartmut Neven, Ryan Babbush, and Jarrod R McClean. Generative quantum advantage for classical and quantum problems. arXiv preprint arXiv:2509.09033 , 2025

work page arXiv 2025
[29]

A quantum-inspired classical algorithm for recommendation systems

Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing , pages 217--228, 2019

2019
[30]

Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions

Ewin Tang. Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions. Physical Review Letters , 127(6):060503, 2021

2021
[31]

Quantum machine learning without any quantum

Ewin Tang. Quantum machine learning without any quantum . University of Washington, 2023

2023
[32]

A variational eigenvalue solver on a photonic quantum processor

Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Al \'a n Aspuru-Guzik, and Jeremy L O’brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications , 5(1):4213, 2014

2014
[33]

The theory of variational hybrid quantum-classical algorithms

Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Al \'a n Aspuru-Guzik. The theory of variational hybrid quantum-classical algorithms. New Journal of Physics , 18(2):023023, 2016

2016
[34]

Variational quantum algorithms

Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. Variational quantum algorithms. Nature Reviews Physics , 3(9):625--644, 2021

2021
[35]

Challenges and opportunities in quantum machine learning

Marco Cerezo, Guillaume Verdon, Hsin-Yuan Huang, Lukasz Cincio, and Patrick J Coles. Challenges and opportunities in quantum machine learning. Nature Computational science , 2(9):567--576, 2022

2022
[36]

Quantum machine learning: A hands-on tutorial for machine learning practitioners and researchers,

Yuxuan Du, Xinbiao Wang, Naixu Guo, Zhan Yu, Yang Qian, Kaining Zhang, Min-Hsiu Hsieh, Patrick Rebentrost, and Dacheng Tao. Quantum machine learning: A hands-on tutorial for machine learning practitioners and researchers. arXiv preprint arXiv:2502.01146 , 2025

work page arXiv 2025
[37]

Barren plateaus in quantum neural network training landscapes

Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature Communications , 9(1):4812, 2018

2018
[38]

Cost function dependent barren plateaus in shallow parametrized quantum circuits

Marco Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J Coles. Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nature Communications , 12(1):1791, 2021

2021
[39]

Noise-induced barren plateaus in variational quantum algorithms

Samson Wang, Enrico Fontana, Marco Cerezo, Kunal Sharma, Akira Sone, Lukasz Cincio, and Patrick J Coles. Noise-induced barren plateaus in variational quantum algorithms. Nature Communications , 12(1):6961, 2021

2021
[40]

Barren plateaus in variational quantum computing

Martin Larocca, Supanut Thanasilp, Samson Wang, Kunal Sharma, Jacob Biamonte, Patrick J Coles, Lukasz Cincio, Jarrod R McClean, Zo \"e Holmes, and Marco Cerezo. Barren plateaus in variational quantum computing. Nature Reviews Physics , pages 1--16, 2025

2025
[41]

Quantum variational algorithms are swamped with traps

Eric R Anschuetz and Bobak T Kiani. Quantum variational algorithms are swamped with traps. Nature Communications , 13(1):7760, 2022

2022
[42]

Scaling Laws for Neural Language Models

Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08361 , 2020

work page internal anchor Pith review Pith/arXiv arXiv 2001
[43]

Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity

William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. Journal of Machine Learning Research , 23(120):1--39, 2022

2022
[44]

Ai and memory wall

Amir Gholami, Zhewei Yao, Sehoon Kim, Coleman Hooper, Michael W Mahoney, and Kurt Keutzer. Ai and memory wall. IEEE Micro , 44(3):33--39, 2024

2024
[45]

Energy and policy considerations for deep learning in nlp

Emma Strubell, Ananya Ganesh, and Andrew McCallum. Energy and policy considerations for deep learning in nlp. In Proceedings of the 57th annual meeting of the association for computational linguistics , pages 3645--3650, 2019

2019
[46]

Exponential scaling of single-cell rna-seq in the past decade

Valentine Svensson, Roser Vento-Tormo, and Sarah A Teichmann. Exponential scaling of single-cell rna-seq in the past decade. Nature Protocols , 13(4):599--604, 2018

2018
[47]

a hnemann, Johannes K \

David L \"a hnemann, Johannes K \"o ster, Ewa Szczurek, Davis J McCarthy, Stephanie C Hicks, Mark D Robinson, Catalina A Vallejos, Kieran R Campbell, Niko Beerenwinkel, Ahmed Mahfouz, et al. Eleven grand challenges in single-cell data science. Genome biology , 21(1):31, 2020

2020
[48]

Benchmarking principal component analysis for large-scale single-cell rna-sequencing

Koki Tsuyuzaki, Hiroyuki Sato, Kenta Sato, and Itoshi Nikaido. Benchmarking principal component analysis for large-scale single-cell rna-sequencing. Genome biology , 21(1):9, 2020

2020
[49]

A roadmap for hep software and computing r&d for the 2020s

HEP Software Foundation, Johannes Albrecht, Antonio Augusto Alves Jr, Guilherme Amadio, Giuseppe Andronico, Nguyen Anh-Ky, Laurent Aphecetche, John Apostolakis, Makoto Asai, Luca Atzori, et al. A roadmap for hep software and computing r&d for the 2020s. Computing and software for big science , 3(1):7, 2019

2019
[50]

B\' e jar Alonso and others (Eds.)

I. B\' e jar Alonso and others (Eds.). High-Luminosity Large Hadron Collider (HL-LHC): Technical design report . Technical Report CERN-2020-010, CERN, Geneva, 2020

2020
[51]

Search for narrow resonances in dijet final states at s= 8 tev with the novel cms technique of data scouting

Vardan Khachatryan, Albert M Sirunyan, Armen Tumasyan, Wolfgang Adam, E Asilar, Thomas Bergauer, Johannes Brandstetter, Erica Brondolin, Marko Dragicevic, Janos Er \"o , et al. Search for narrow resonances in dijet final states at s= 8 tev with the novel cms technique of data scouting. Physical Review Letters , 117(3):031802, 2016

2016
[52]

The square kilometre array

Peter E Dewdney, Peter J Hall, Richard T Schilizzi, and T Joseph LW Lazio. The square kilometre array. Proceedings of the IEEE , 97(8):1482--1496, 2009

2009
[53]

Data streams: Algorithms and applications

Shanmugavelayutham Muthukrishnan et al. Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science , 1(2):117--236, 2005

2005
[54]

The space complexity of approximating the frequency moments

Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. In Proceedings of the twenty-eighth annual ACM symposium on theory of computing , pages 20--29, 1996

1996
[55]

Probabilistic counting algorithms for data base applications

Philippe Flajolet and G Nigel Martin. Probabilistic counting algorithms for data base applications. Journal of computer and system sciences , 31(2):182--209, 1985

1985
[56]

Finding repeated elements

Jayadev Misra and David Gries. Finding repeated elements. Science of computer programming , 2(2):143--152, 1982

1982
[57]

An improved data stream summary: the count-min sketch and its applications

Graham Cormode and Shan Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms , 55(1):58--75, 2005

2005
[58]

Sketching as a tool for numerical linear algebra

David P Woodruff et al. Sketching as a tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science , 10(1--2):1--157, 2014

2014
[59]

Numerical linear algebra in the streaming model

Kenneth L Clarkson and David P Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the forty-first annual ACM symposium on theory of computing , pages 205--214, 2009

2009
[60]

Streaming complexity of svms

Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, and David P Woodruff. Streaming complexity of svms. arXiv preprint arXiv:2007.03633 , 2020

work page arXiv 2007
[61]

Memory limited, streaming pca

Ioannis Mitliagkas, Constantine Caramanis, and Prateek Jain. Memory limited, streaming pca. Advances in neural information processing systems , 26, 2013

2013
[62]

Online learning and online convex optimization

Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning , 4(2):107--194, 2025

2025
[63]

Bounds for the quantity of information transmitted by a quantum communication channel

Alexander Semenovich Holevo. Bounds for the quantity of information transmitted by a quantum communication channel. Problemy Peredachi Informatsii , 9(3):3--11, 1973

1973
[64]

Space-bounded quantum complexity

John Watrous. Space-bounded quantum complexity. Journal of Computer and System Sciences , 59(2):281--326, 1999

1999
[65]

On the complexity of simulating space-bounded quantum computations

John Watrous. On the complexity of simulating space-bounded quantum computations. computational complexity , 12(1):48--84, 2003

2003
[66]

Exponential separation of quantum and classical online space complexity

Fran c ois Le Gall. Exponential separation of quantum and classical online space complexity. In Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures , pages 67--73, 2006

2006
[67]

The space complexity of recognizing well-parenthesized expressions in the streaming model: the index function revisited

Rahul Jain and Ashwin Nayak. The space complexity of recognizing well-parenthesized expressions in the streaming model: the index function revisited. IEEE Transactions on Information Theory , 60(10):6646--6668, 2014

2014
[68]

A quantum advantage for a natural streaming problem

John Kallaugher. A quantum advantage for a natural streaming problem. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 897--908. IEEE, 2022

2021
[69]

Exponential quantum space advantage for approximating maximum directed cut in the streaming model

John Kallaugher, Ojas Parekh, and Nadezhda Voronova. Exponential quantum space advantage for approximating maximum directed cut in the streaming model. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1805--1815, 2024

2024
[70]

How to design a quantum streaming algorithm without knowing anything about quantum computing

John Kallaugher, Ojas Parekh, and Nadezhda Voronova. How to design a quantum streaming algorithm without knowing anything about quantum computing. In 2025 Symposium on Simplicity in Algorithms (SOSA) , pages 9--45. SIAM, 2025

2025
[71]

Exponential quantum communication advantage in distributed inference and learning

Dar Gilboa, Hagay Michaeli, Daniel Soudry, and Jarrod McClean. Exponential quantum communication advantage in distributed inference and learning. Advances in Neural Information Processing Systems , 37:30425--30473, 2024

2024
[72]

Realization of a quantum streaming algorithm on long-lived trapped-ion qubits

Pradeep Niroula, Shouvanik Chakrabarti, Steven Kordonowy, Niraj Kumar, Sivaprasad Omanakuttan, Michael A Perlin, MS Allman, JP Campora III, Alex Chernoguzov, Samuel F Cooper, et al. Realization of a quantum streaming algorithm on long-lived trapped-ion qubits. arXiv preprint arXiv:2511.03689 , 2025

work page arXiv 2025
[73]

Demonstrating an unconditional separation between quantum and classical information resources

William Kretschmer, Sabee Grewal, Matthew DeCross, Justin A Gerber, Kevin Gilmore, Dan Gresh, Nicholas Hunter-Jones, Karl Mayer, Brian Neyenhuis, David Hayes, et al. Demonstrating an unconditional separation between quantum and classical information resources. arXiv preprint arXiv:2509.07255 , 2025

work page internal anchor Pith review arXiv 2025
[74]

Predicting many properties of a quantum system from very few measurements

Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics , 16(10):1050--1057, 2020

2020
[75]

Preskill, Quantum computing and the entanglement frontier, arXiv preprint arXiv:1203.5813 (2012)

John Preskill. Quantum computing and the entanglement frontier. arXiv preprint arXiv:1203.5813 , 2012

work page arXiv 2012
[76]

On the problem of hidden variables in quantum mechanics

John S Bell. On the problem of hidden variables in quantum mechanics. Reviews of Modern physics , 38(3):447, 1966

1966
[77]

Proposed experiment to test local hidden-variable theories

John F Clauser, Michael A Horne, Abner Shimony, and Richard A Holt. Proposed experiment to test local hidden-variable theories. Physical Review Letters , 23(15):880, 1969

1969
[78]

Bell's theorem

John F Clauser and Abner Shimony. Bell's theorem. experimental tests and implications. Reports on Progress in Physics , 41(12):1881, 1978

1978
[79]

Learning word vectors for sentiment analysis

Andrew Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies , pages 142--150, 2011

2011
[80]

Massively parallel digital transcriptional profiling of single cells

Grace XY Zheng, Jessica M Terry, Phillip Belgrader, Paul Ryvkin, Zachary W Bent, Ryan Wilson, Solongo B Ziraldo, Tobias D Wheeler, Geoff P McDermott, Junjie Zhu, et al. Massively parallel digital transcriptional profiling of single cells. Nature Communications , 8(1):14049, 2017

2017

Showing first 80 references.