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.

本文探讨如何找到一些学习问题，量子学习算法可以在其中证明比经典学习算法快速得多，还具有物理意义的应用，例如，在凝聚态物理和高能物理中表现出来的数据。