A polylog-sized quantum computer achieves exponential advantage over classical machines in classification and dimension reduction of massive classical data using quantum oracle sketching combined with classical shadows.
Exponential separations between classical and quantum learners
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
abstract
Despite significant effort, the quantum machine learning community has only demonstrated quantum learning advantages for artificial cryptography-inspired datasets when dealing with classical data. In this paper we address the challenge of finding learning problems where quantum learning algorithms can achieve a provable exponential speedup over classical learning algorithms. We reflect on computational learning theory concepts related to this question and discuss how subtle differences in definitions can result in significantly different requirements and tasks for the learner to meet and solve. We examine existing learning problems with provable quantum speedups and find that they largely rely on the classical hardness of evaluating the function that generates the data, rather than identifying it. To address this, we present two new learning separations where the classical difficulty primarily lies in identifying the function generating the data. Furthermore, we explore computational hardness assumptions that can be leveraged to prove quantum speedups in scenarios where data is quantum-generated, which implies likely quantum advantages in a plethora of more natural settings (e.g., in condensed matter and high energy physics). We also discuss the limitations of the classical shadow paradigm in the context of learning separations, and how physically-motivated settings such as characterizing phases of matter and Hamiltonian learning fit in the computational learning framework.
citation-role summary
background 1
citation-polarity summary
fields
quant-ph 4roles
background 1polarities
background 1representative citing papers
A provable exponential quantum-classical learning separation is established for predicting expectation values of time-evolved quantum states under unknown low-intersection Hamiltonians, assuming BQP ⊄ P/poly.
A single-qubit quantum reinforcement learning agent solves CartPole faster than classical networks and quantifies shot-count versus control-frequency requirements for real-time closed-loop control on NISQ hardware, including direct electronics programming to reduce latency.
Extends Fano bounds to sufficiency of low conditional entropy and defines a quantum entanglement task for infinite-dimensional systems with bounds via maximal singlet fraction of finite-dimensional approximations.
citing papers explorer
-
Exponential quantum advantage in processing massive classical data
A polylog-sized quantum computer achieves exponential advantage over classical machines in classification and dimension reduction of massive classical data using quantum oracle sketching combined with classical shadows.
-
Provable learning separation for predicting time-evolution of quantum many-body systems
A provable exponential quantum-classical learning separation is established for predicting expectation values of time-evolved quantum states under unknown low-intersection Hamiltonians, assuming BQP ⊄ P/poly.
-
Towards Real-time Control of a CartPole System on a Quantum Computer
A single-qubit quantum reinforcement learning agent solves CartPole faster than classical networks and quantifies shot-count versus control-frequency requirements for real-time closed-loop control on NISQ hardware, including direct electronics programming to reduce latency.
-
On the coherent extension of some Fano-type learning bounds
Extends Fano bounds to sufficiency of low conditional entropy and defines a quantum entanglement task for infinite-dimensional systems with bounds via maximal singlet fraction of finite-dimensional approximations.