  Despite years of effort, the quantum machine learning community has only been
able to show quantum learning advantages for certain contrived
cryptography-inspired datasets in the case of classical data. In this note, we
discuss the challenges of finding learning problems that quantum learning
algorithms can learn much faster than any classical learning algorithm, and we
study how to identify such learning problems. Specifically, we reflect on the
main concepts in computational learning theory pertaining to this question, and
we discuss how subtle changes in definitions can mean conceptually
significantly different tasks, which can either lead to a separation or no
separation at all. Moreover, we study existing learning problems with a
provable quantum speedup to distill sets of more general and sufficient
conditions (i.e., ``checklists'') for a learning problem to exhibit a
separation between classical and quantum learners. These checklists are
intended to streamline one's approach to proving quantum speedups for learning
problems, or to elucidate bottlenecks. Finally, to illustrate its application,
we analyze examples of potential separations (i.e., when the learning problem
is build from computational separations, or when the data comes from a quantum
experiment) through the lens of our approach.
