Exponential separations between classical and quantum learners
- URL: http://arxiv.org/abs/2306.16028v1
- Date: Wed, 28 Jun 2023 08:55:56 GMT
- Title: Exponential separations between classical and quantum learners
- Authors: Casper Gyurik and Vedran Dunjko
- Abstract summary: We discuss how subtle differences in definitions can result in significantly different requirements and tasks for the learner to meet and solve.
We present two new learning separations where the classical difficulty primarily lies in identifying the function generating the data.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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.
Related papers
- Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem [70.42372213666553]
The No-Free-Lunch (NFL) theorem quantifies problem- and data-independent generalization errors regardless of the optimization process.
We categorize a diverse array of quantum learning algorithms into three learning protocols designed for learning quantum dynamics under a specified observable.
Our derived NFL theorems demonstrate quadratic reductions in sample complexity across CLC-LPs, ReQu-LPs, and Qu-LPs.
We attribute this performance discrepancy to the unique capacity of quantum-related learning protocols to indirectly utilize information concerning the global phases of non-orthogonal quantum states.
arXiv Detail & Related papers (2024-05-12T09:05:13Z) - Information-theoretic generalization bounds for learning from quantum data [5.0739329301140845]
We propose a general mathematical formalism for describing quantum learning by training on classical-quantum data.
We prove bounds on the expected generalization error of a quantum learner in terms of classical and quantum information-theoretic quantities.
Our work lays a foundation for a unifying quantum information-theoretic perspective on quantum learning.
arXiv Detail & Related papers (2023-11-09T17:21:38Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
The anticipated applications of quantum computers span across science and industry.
We present a survey of several potential application areas of quantum algorithms.
We outline the challenges and opportunities in each area in an "end-to-end" fashion.
arXiv Detail & Related papers (2023-10-04T17:53:55Z) - Statistical Complexity of Quantum Learning [32.48879688084909]
This article reviews the complexity of quantum learning using information-theoretic techniques.
We focus on data complexity, copy complexity, and model complexity.
We highlight the differences between quantum and classical learning by addressing both supervised and unsupervised learning.
arXiv Detail & Related papers (2023-09-20T20:04:05Z) - ShadowNet for Data-Centric Quantum System Learning [188.683909185536]
We propose a data-centric learning paradigm combining the strength of neural-network protocols and classical shadows.
Capitalizing on the generalization power of neural networks, this paradigm can be trained offline and excel at predicting previously unseen systems.
We present the instantiation of our paradigm in quantum state tomography and direct fidelity estimation tasks and conduct numerical analysis up to 60 qubits.
arXiv Detail & Related papers (2023-08-22T09:11:53Z) - Quantum data learning for quantum simulations in high-energy physics [55.41644538483948]
We explore the applicability of quantum-data learning to practical problems in high-energy physics.
We make use of ansatz based on quantum convolutional neural networks and numerically show that it is capable of recognizing quantum phases of ground states.
The observation of non-trivial learning properties demonstrated in these benchmarks will motivate further exploration of the quantum-data learning architecture in high-energy physics.
arXiv Detail & Related papers (2023-06-29T18:00:01Z) - 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) - A didactic approach to quantum machine learning with a single qubit [68.8204255655161]
We focus on the case of learning with a single qubit, using data re-uploading techniques.
We implement the different proposed formulations in toy and real-world datasets using the qiskit quantum computing SDK.
arXiv Detail & Related papers (2022-11-23T18:25:32Z) - On establishing learning separations between classical and quantum
machine learning with classical data [0.0]
We discuss the challenges of finding learning problems that quantum learning algorithms can learn much faster than any classical learning algorithm.
We study existing learning problems with a provable quantum speedup to distill sets of more general and sufficient conditions.
These checklists are intended to streamline one's approach to proving quantum speedups for learning problems, or to elucidate bottlenecks.
arXiv Detail & Related papers (2022-08-12T16:00:30Z) - 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)
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.