Quantum K-nearest neighbor algorithm

被引：5

作者：

Chen, Hanwu ^{[1
]}

Gao, Yue ^{[1
]}

Zhang, Jun ^{[2
]}

机构：

[1] School of Computer Science and Engineering, Southeast University, Nanjing

[2] Department of Information and Engineering, Jiangsu Maritime Institute, Nanjing

来源：

Dongnan Daxue Xuebao (Ziran Kexue Ban)/Journal of Southeast University (Natural Science Edition) | 2015年 / 45卷 / 04期

关键词：

K-nearest neighbor algorithm; Machine learning; Quantum algorithm;

D O I：

10.3969/j.issn.1001-0505.2015.04.006

中图分类号：

学科分类号：

摘要：

A novel quantum K-nearest neighbor algorithm is designed to improve the efficiency by introducing the theory of quantum computation and embedding the Oracle operator of Grover algorithm and the phase estimation algorithm in classic K-nearest neighbor algorithm. In the proposed algorithm, the vector information of sample points and to-be-classified points is prepared to be quantum superposition, and quantum reversible c-swap gate is used to parallel compute the similarity. Then the similarity is stored in qubit by using quantum phase estimation, and the k most similar points are found once by the Grover algorithm. Through theoretical analysis of the embedded quantum computing, the results show that the quantum K-nearest neighbor algorithm can significantly reduce the computational complexity of classical algorithms and the proposed algorithm runs faster than other existing algorithms (O(RkM1/2)) with the k value of the second acceleration O(R(kM)1/2) for solving the same problem. Wherein R represents Oracle execution times and M is global number of samples. ©, 2015, Southeast University. All right reserved.

引用

页码：647 / 651

页数：4

共 18 条

[1]

Beckmann B., Kriegel H.P., Schneider R., Et al., The R<sup>*</sup>-tree: an efficient and robust access method, 9th ACM SIGMOD International Conference on Management of Data, pp. 322-331, (1990)

[2]

White D.A., Jain R., Similarity indexing with the SS-tree, Proceedings of the Twelfth International Conference on Data Engineering, pp. 516-523, (1996)

[3]

Katayama N., Satoh S., The SR-tree: an index structure for high-dimensional nearest neighbor queries, SIGMOD Record, 26, 2, pp. 369-380, (1997)

[4]

Goodsell G., On finding p-th nearest neighbours of scattered points in two dimensions for small p, Computer Aided Geometric Design, 17, 4, pp. 387-392, (2000)

[5]

Piegl L.A., Tiller W., Algorithm for finding all k nearest neighbors, Computer-Aided Design, 34, 2, pp. 167-172, (2002)

[6]

Han K.H., Kim J.H., Genetic quantum algorithm and its application to combinatorial optimization problem, Proceedings of the 2000 Congress on Evolutionary Computation, 2, pp. 1354-1360, (2000)

[7]

Lloyd S., Mohseni M., Rebentrost P., Quantum principal component analysis, Nature Physics, 10, 9, pp. 631-633, (2014)

[8]

Lloyd S., Mohseni M., Rebentrost P., Quantum algorithms for supervised and unsupervised machine learning, (2013)

[9]

Aimeur E., Brassard G., Gambs S., Quantum speed-up for unsupervised learning, Machine Learning, 90, 2, pp. 261-287, (2013)

[10]

Wiebe N., Kapoor A., Svore K., Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning, (2014)

← 1 2 →