Quantum machine learning algorithms could provide significant speed-ups over their classical counterparts; however, whether they could also achieve good generalization remains unclear. Recently, two quantum perceptron models which give a quadratic improvement over the classical perceptron algorithm using Grover's search have been proposed by Wiebe et al. arXiv:1602.04799 . While the first model reduces the complexity with respect to the size of the training set, the second one improves the bound on the number of mistakes made by the perceptron. In this paper, we introduce a hybrid quantum-classical perceptron algorithm with lower complexity and better generalization ability than the classical perceptron. We show a quadratic improvement over the classical perceptron in both the number of samples and the margin of the data. We derive a bound on the expected error of the hypothesis returned by our algorithm, which compares favorably to the one obtained with the classical online perceptron. We use numerical experiments to illustrate the trade-off between computational complexity and statistical accuracy in quantum perceptron learning and discuss some of the key practical issues surrounding the implementation of quantum perceptron models into near-term quantum devices, whose practical implementation represents a serious challenge due to inherent noise. However, the potential benefits make correcting this worthwhile.
翻译:Quantum 机器学习算法可以大大加快其古典对应方的进度; 但是, 它们能否实现良好的概括化仍然不清楚。 最近, Wiebe 等人 ARXiv: 1602. 04799 提出了两个量子透视模型,这些模型对使用 Grover 搜索的古典透视算法进行了二次改进。 尽管第一个模型降低了培训成套方法的复杂程度,但第二个模型提高了关于透视器错误数目的界限。 在本文中,我们引入了一种混合量子透视算法,其复杂性比古典透视法低,普及能力也更好。 我们在样本数量和数据差值方面都对古典透视算法提出了二次改进。 我们根据我们的算法的预期误差得出了一个界限,与古典的在线透视仪相比,我们使用数字实验来说明量子透视系统学习的计算复杂程度和统计准确度之间的利差。 我们讨论了围绕古典透视谱的经典透视法应用的一些关键实际问题。