论文标题
通过使用经典数据建立古典和量子机学习之间的学习分离
On establishing learning separations between classical and quantum machine learning with classical data
论文作者
论文摘要
尽管经过多年的努力，但在经典数据的情况下，Quantum机器学习社区只能显示某些人为加密启发的数据集的量子学习优势。在本说明中，我们讨论了发现学习问题的挑战，即量子学习算法可以比任何经典学习算法更快地学习，并研究如何识别此类学习问题。具体来说，我们反思了与此问题有关的计算学习理论中的主要概念，并讨论定义的微妙变化在概念上意味着显着不同的任务，这可能会导致分离或根本没有分离。此外，我们以可证明的量子加速研究现有的学习问题，以提炼一组更一般和充分的条件（即``清单''），以表现出学习问题，以表现出经典学习者和量子学习者之间的分离。这些清单旨在简化一个人的方法来证明学习问题或阐明瓶颈的量子加速。最后，为了说明其应用，我们分析了潜在分离的示例（即，当学习问题是从计算分离中或数据来自量子实验时）通过我们的方法的镜头进行分析。
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.
