论文标题
对纠缠数据集的禁止午餐定理的重新重新制定
Reformulation of the No-Free-Lunch Theorem for Entangled Data Sets
论文作者
论文摘要
无需午餐（NFL）定理是学习理论的著名结果，它限制了人们通过培训数据集学习功能的能力。随着Quantum机器学习的最新兴起，很自然地询问是否有NFL定理的量子类似物，这将限制量子计算机使用量子训练数据学习单一过程（函数的量子类似物）的能力。但是，在量子设置中，训练数据可以具有纠缠，而没有经典类似物的强烈相关性。在这项工作中，我们表明纠缠的数据集显然违反了（经典）NFL定理。这激发了一个重新制定，该重新构成了培训集中的纠缠程度。作为我们的主要结果，我们证明了一个量子NFL定理，从而通过纠缠降低了单一可学习性的基本限制。我们使用Rigetti的量子计算机来测试经典和量子NFL定理。我们的工作确定纠缠是量子机学习中的商品。
The no-free-lunch (NFL) theorem is a celebrated result in learning theory that limits one's ability to learn a function with a training data set. With the recent rise of quantum machine learning, it is natural to ask whether there is a quantum analog of the NFL theorem, which would restrict a quantum computer's ability to learn a unitary process (the quantum analog of a function) with quantum training data. However, in the quantum setting, the training data can possess entanglement, a strong correlation with no classical analog. In this work, we show that entangled data sets lead to an apparent violation of the (classical) NFL theorem. This motivates a reformulation that accounts for the degree of entanglement in the training set. As our main result, we prove a quantum NFL theorem whereby the fundamental limit on the learnability of a unitary is reduced by entanglement. We employ Rigetti's quantum computer to test both the classical and quantum NFL theorems. Our work establishes that entanglement is a commodity in quantum machine learning.
