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 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.