Relation Between Quantum Advantage in Supervised Learning and Quantum Computational Advantage

The widespread use of machine learning has raised the question of quantum supremacy for supervised learning as compared to quantum computational advantage. In fact, a recent work shows that computational and learning advantages are, in general, not equivalent, i.e., the additional information provid...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on quantum engineering 2024, Vol.5, p.1-17
Main Authors: Perez-Guijarro, Jordi, Pages-Zamora, Alba, Fonollosa, Javier R.
Format: Article
Language:English
Subjects:
Algorithms
Cognitive tasks
Complexity theory
Cost function
Equivalence
Machine learning
Prime factorization problem
quantum advantage
Quantum algorithm
quantum machine learning
Supervised learning
Training
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The widespread use of machine learning has raised the question of quantum supremacy for supervised learning as compared to quantum computational advantage. In fact, a recent work shows that computational and learning advantages are, in general, not equivalent, i.e., the additional information provided by a training set can reduce the hardness of some problems. This article investigates under which conditions they are found to be equivalent or, at least, highly related. This relation is analyzed by considering two definitions of learning speed-up: one tied to the distribution and another that is distribution-independent. In both cases, the existence of efficient algorithms to generate training sets emerges as the cornerstone of such conditions, although, for the distribution-independent definition, additional mild conditions must also be met. Finally, these results are applied to prove that there is a quantum speed-up for some learning tasks based on the prime factorization problem, assuming the classical intractability of this problem.
ISSN:2689-1808
2689-1808
DOI:10.1109/TQE.2023.3347476