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 条

[11]

Bennett C.H., Logical reversibility of computation, IBM Journal of Research and Development, 17, 6, pp. 525-532, (1973)

[12]

Buhrman H., Cleve R., Watrous J., Et al., Quantum fingerprinting, Physical Review Letters, 87, 16, pp. 167902-01-167902-04, (2001)

[13]

Brassard G., H∅yer P., Mosca M., Et al., Quantum amplitude amplification and estimation, Quantum Computation & Information, pp. 53-74, (2000)

[14]

Durr C., Heiligman M., H∅yer P., Et al., Quantum Query Complexity of Some Graph Problems, pp. 481-493, (2004)

[15]

Durr C., H∅yer P., A quantum algorithm for finding the minimum, (1996)

[16]

Boyer M., Brassard G., H∅yer P., Et al., Tight bounds on quantum searching, (1996)

[17]

Arya S., Mount D.M., Netanyahu N.S., Et al., An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM, 45, 6, pp. 891-923, (1998)

[18]

Li Q., Jiang J., Quantum k nearest neighbor algorithm, Systems Engineering and Electronics, 30, 5, pp. 940-943, (2008)

← 1 2 →