Shannon entropy estimation in data streams exhibits an exponential quantum space advantage over classical streaming algorithms.
Exponential quantum advantage in processing massive classical data
9 Pith papers cite this work. Polarity classification is still indexing.
9
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.
citation-role summary
background 2
baseline 1
citation-polarity summary
fields
quant-ph 9years
2026 9representative citing papers
Lie group diffusion models combine a discrete circuit skeleton selector with continuous diffusion on SU(2) ≃ S³ to synthesize hardware-aware quantum circuits, outperforming baselines on three-qubit Hamiltonian simulation targets.
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 subspace methods are extended to Lindblad open quantum systems and demonstrated on a Kerr resonator for estimating the Liouvillian gap in cat qubit regimes.
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.
Hybrid quantum-classical neural network reduces overall normalized RMSE by 24.4% versus classical ANN when predicting six electrical targets for AlGaN/GaN MIS-HEMTs on 468 experimental devices from 17 process splits.
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.
-
Lie Group Diffusion Models for Hardware-Aware Quantum Circuit Synthesis
Lie group diffusion models combine a discrete circuit skeleton selector with continuous diffusion on SU(2) ≃ S³ to synthesize hardware-aware quantum circuits, outperforming baselines on three-qubit Hamiltonian simulation targets.
-
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.
-
Real-time Krylov Diagonalisation for Open Quantum Systems
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
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.
-
Hybrid Classical-Quantum Neural Networks for Multi-Characteristic Co-Optimization of Recessed-Gate AlGaN/GaN MIS-HEMTs
Hybrid quantum-classical neural network reduces overall normalized RMSE by 24.4% versus classical ANN when predicting six electrical targets for AlGaN/GaN MIS-HEMTs on 468 experimental devices from 17 process splits.
-
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.