Shannon entropy estimation in data streams exhibits an exponential quantum space advantage over classical streaming algorithms.
Exponential quantum advantage in processing massive classical data
6 Pith papers cite this work. Polarity classification is still indexing.
6
Pith papers citing it
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.
fields
quant-ph 6years
2026 6representative citing papers
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.
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.
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 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.
Adiabatic solver slightly outperforms shortcut when solution norm unknown; shortcut significantly better for non-Hermitian matrices when norm known.
citing papers explorer
-
Exponential quantum space advantage for Shannon entropy estimation in data streams
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
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.
-
Block-encodings as programming abstractions: The Eclipse Qrisp BlockEncoding Interface
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.
-
Measuring Accuracy and Energy-to-Solution of Quantum Fine-Tuning of Foundational AI Models
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
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
Adiabatic solver slightly outperforms shortcut when solution norm unknown; shortcut significantly better for non-Hermitian matrices when norm known.