论文标题
量子$ k $ - 最近的邻居算法
Quantum $k$-nearest neighbors algorithm
论文作者
论文摘要
最简单，最有效的古典机器学习算法之一是$ k $ - 最初的邻居算法（$ k $ nn），它通过从一组$ m $ train状态下找到最近的邻居来对未知的测试状态进行分类。在这里，我们提出了一个基于Fidelity作为相似性度量的经典$ k $ nn $ nn $ -nn $ -nn $ nn $ -nn $ k $ nn（q $ k $ nn）$ - $的量子类似物。我们表明，Q $ K $ nn算法可以简化为量子$ k $ -maxima算法的实例，因此，Q $ K $ nn的查询复杂性是$ O（\ sqrt {km}）$。此减少的非平凡任务是编码测试状态与所有火车状态之间的保真度信息，作为量子状态的振幅。将此幅度编码的信息转换为数字格式，使我们能够有效地比较它们，从而完成降低。与经典的$ k $ nn和现有的量子$ k $ nn算法不同，提出的算法可以直接用于量子数据上，从而绕过昂贵的过程，例如量子状态层析成像。例如，我们显示了该算法在纠缠分类和量子状态歧视中的适用性。
One of the simplest and most effective classical machine learning algorithms is the $k$-nearest neighbors algorithm ($k$NN) which classifies an unknown test state by finding the $k$ nearest neighbors from a set of $M$ train states. Here we present a quantum analog of classical $k$NN $-$ quantum $k$NN (Q$k$NN) $-$ based on fidelity as the similarity measure. We show that Q$k$NN algorithm can be reduced to an instance of the quantum $k$-maxima algorithm, hence the query complexity of Q$k$NN is $O(\sqrt{kM})$. The non-trivial task in this reduction is to encode the fidelity information between the test state and all the train states as amplitudes of a quantum state. Converting this amplitude encoded information to a digital format enables us to compare them efficiently, thus completing the reduction. Unlike classical $k$NN and existing quantum $k$NN algorithms, the proposed algorithm can be directly used on quantum data thereby bypassing expensive processes such as quantum state tomography. As an example, we show the applicability of this algorithm in entanglement classification and quantum state discrimination.
