Exponential quantum advantage in processing massive classical data

• URL: http://arxiv.org/abs/2604.07639v1
• Date: Wed, 08 Apr 2026 22:55:59 GMT
• Title: Exponential quantum advantage in processing massive classical data
• Abstract summary: We prove that a small quantum computer of polylogarithmic size can perform large-scale classification and dimension reduction on massive classical data.<n>We validate these quantum advantages in real-world applications, including single-cell RNA sequencing and movie review sentiment analysis.
• Score: 35.39226386838022
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Machine learning with minimal use of quantum computers: Provable advantages in Learning Under Quantum Privileged Information (LUQPI) [3.3882078618429348]
  A quantum computer is used only as a feature extractor.<n>We formalize this model by adapting the classical framework of Learning Under Privileged Information.<n>We show that even such minimally involved quantum feature extraction, available only during training, can yield exponential quantum-classical separations.
  arXiv  Detail & Related papers  (2026-01-29T17:14:58Z)
• Distributed quantum machine learning via classical communication [0.7378853859331619]
  We present an experimentally accessible distributed quantum machine learning scheme that integrates quantum processor units via classical communication. Our results indicate that incorporating classical communication notably improves classification accuracy compared to schemes without communication.
  arXiv  Detail & Related papers  (2024-08-29T08:05:57Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• The curse of random quantum data [62.24825255497622]
  We quantify the performances of quantum machine learning in the landscape of quantum data. We find that the training efficiency and generalization capabilities in quantum machine learning will be exponentially suppressed with the increase in qubits. Our findings apply to both the quantum kernel method and the large-width limit of quantum neural networks.
  arXiv  Detail & Related papers  (2024-08-19T12:18:07Z)
• Exponential quantum advantages in learning quantum observables from classical data [1.9662978733004604]
  We prove quantum advantages for the physically relevant task of learning quantum observables from classical data.<n>Our results shed light on the utility of quantum computers for machine learning problems in the domain of quantum many body physics.
  arXiv  Detail & Related papers  (2024-05-03T11:58:43Z)
• A Quantum-Classical Collaborative Training Architecture Based on Quantum State Fidelity [50.387179833629254]
  We introduce a collaborative classical-quantum architecture called co-TenQu. Co-TenQu enhances a classical deep neural network by up to 41.72% in a fair setting. It outperforms other quantum-based methods by up to 1.9 times and achieves similar accuracy while utilizing 70.59% fewer qubits.
  arXiv  Detail & Related papers  (2024-02-23T14:09:41Z)
• Classical Verification of Quantum Learning [42.362388367152256]
  We develop a framework for classical verification of quantum learning. We propose a new quantum data access model that we call "mixture-of-superpositions" quantum examples. Our results demonstrate that the potential power of quantum data for learning tasks, while not unlimited, can be utilized by classical agents.
  arXiv  Detail & Related papers  (2023-06-08T00:31:27Z)
• Quantum Machine Learning: from physics to software engineering [58.720142291102135]
  We show how classical machine learning approach can help improve the facilities of quantum computers. We discuss how quantum algorithms and quantum computers may be useful for solving classical machine learning tasks.
  arXiv  Detail & Related papers  (2023-01-04T23:37:45Z)
• Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
  We present an approach where the quantum computation is supplemented by a classical result. Taking advantage of its anticipation also leads to a new type of quantum measurements, which we call anticipative. In an anticipative quantum measurement the combination of the results from classical and quantum computations happens only in the end.
  arXiv  Detail & Related papers  (2022-09-12T15:47:44Z)
• Power of data in quantum machine learning [2.1012068875084964]
  We show that some problems that are classically hard to compute can be easily predicted by classical machines learning from data. We propose a projected quantum model that provides a simple and rigorous quantum speed-up for a learning problem in the fault-tolerant regime.
  arXiv  Detail & Related papers  (2020-11-03T19:00:01Z)
• Space Complexity of Streaming Algorithms on Universal Quantum Computers [13.941598115553957]
  The space complexity of some data stream problems, such as PartialMOD and Equality, is investigated on universal quantum computers. The quantum algorithms for these problems are believed to outperform their classical counterparts.
  arXiv  Detail & Related papers  (2020-10-31T16:16:35Z)
• Quantum Deformed Neural Networks [83.71196337378022]
  We develop a new quantum neural network layer designed to run efficiently on a quantum computer. It can be simulated on a classical computer when restricted in the way it entangles input states.
  arXiv  Detail & Related papers  (2020-10-21T09:46:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.