[1]陈汉武,高越,张军.量子K-近邻算法[J].东南大学学报(自然科学版),2015,45(4):647-651.[doi:10.3969/j.issn.1001-0505.2015.04.006]
　Chen Hanwu,Gao Yue,Zhang Jun.Quantum K-nearest neighbor algorithm[J].Journal of Southeast University (Natural Science Edition),2015,45(4):647-651.[doi:10.3969/j.issn.1001-0505.2015.04.006]
点击复制

量子K-近邻算法()
分享到：

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
45
期数:
2015年第4期
页码:
647-651
栏目:
计算机科学与工程
出版日期:
2015-07-20

文章信息/Info

Title:
Quantum K-nearest neighbor algorithm
作者:
陈汉武1; 高越1; 张军2
1东南大学计算机科学与工程学院, 南京210096; 2江苏海事职业技术学院信息工程系, 南京211170
Author(s):
Chen Hanwu1;  Gao Yue1;  Zhang Jun2
1School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
2Department of Information and Engineering, Jiangsu Maritime Institute, Nanjing 211170, China
关键词:
机器学习;  K-近邻算法;  量子算法
Keywords:
machine learning;  K-nearest neighbor algorithm;  quantum algorithm
分类号:
TP387
DOI:
10.3969/j.issn.1001-0505.2015.04.006
摘要:
为了提高经典K-近邻算法的效率,引入量子计算理论,将Grover算法中的Oracle算子以及相位估计算法嵌入经典K-近邻算法,提出一种量子K-近邻算法.该算法首先将样本点和待分类点的向量信息制备成量子叠加态,采用可逆的量子控制交换门并行计算待分类点和样本点的相似度,然后利用相位估计算法将相似度信息存储到量子比特中,最后使用Grover算法一次性搜索出最相似的k个点.对嵌入的量子计算部分的理论分析结果表明,量子K-近邻算法可以明显降低经典计算复杂度,且提出的算法在已有算法计算复杂度O(RkM1/2)12的基础上,再次带来了k值的二次加速O(R(kM)1/2)12,其中R为Oracle算子的执行次数,M为样本全局个数.
Abstract:
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/212))with the k value of the second acceleration O(R(kM)1/212)for solving the same problem. Wherein R represents Oracle execution times and M is global number of samples.

参考文献/References:

[1] Beckmann B, Kriegel H P, Schneider R, et al. The R*-tree: an efficient and robust access method[C]//9th ACM SIGMOD International Conference on Management of Data. Atlantic City, NY,USA, 1990: 322-331.
[2] White D A, Jain R. Similarity indexing with the SS-tree[C]//Proceedings of the Twelfth International Conference on Data Engineering. New Orleans, LA, USA, 1996: 516-523.
[3] Katayama N, Satoh S. The SR-tree: an index structure for high-dimensional nearest neighbor queries[J]. SIGMOD Record, 1997, 26(2): 369-380.
[4] Goodsell G. On finding p-th nearest neighbours of scattered points in two dimensions for small p[J]. Computer Aided Geometric Design, 2000, 17(4): 387-392.
[5] Piegl L A, Tiller W. Algorithm for finding all k nearest neighbors[J]. Computer-Aided Design, 2002, 34(2): 167-172.
[6] Han K H, Kim J H. Genetic quantum algorithm and its application to combinatorial optimization problem[C]//Proceedings of the 2000 Congress on Evolutionary Computation. San Diego, CA, USA, 2000, 2: 1354-1360.
[7] Lloyd S, Mohseni M, Rebentrost P. Quantum principal component analysis[J]. Nature Physics, 2014, 10(9): 631-633.
[8] Lloyd S, Mohseni M, Rebentrost P. Quantum algorithms for supervised and unsupervised machine learning[J/OL]. Eprint arXiv, 2013.http://arxiv.org/pdf/1307.0411v2.pdf.
[9] Aïmeur E, Brassard G, Gambs S. Quantum speed-up for unsupervised learning[J]. Machine Learning, 2013, 90(2): 261-287.
[10] Wiebe N, Kapoor A, Svore K. Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning[J/OL]. Eprint arXiv, 2014.http://arxiv.org/pdf/1401.2142v2.pdf.
[11] Bennett C H. Logical reversibility of computation[J]. IBM Journal of Research and Development, 1973, 17(6): 525-532.
[12] Buhrman H, Cleve R, Watrous J, et al. Quantum fingerprinting[J]. Physical Review Letters, 2001, 87(16): 167902-01-167902-04.
[13] Brassard G, Høyer P, Mosca M, et al. Quantum amplitude amplification and estimation[J]. Quantum Computation & Information, 2000:53-74.
[14] Dürr C, Heiligman M, Høyer P, et al. Quantum query complexity of some graph problems[M]//Automata, Languages and Programming. Berlin: Springer, 2004: 481-493.
[15] Dürr C, Høyer P. A quantum algorithm for finding the minimum[J/OL]. LANL e-print, 1996.http://arxiv.org/pdf/quant-ph/9607014.pdf.
[16] Boyer M, Brassard G, Høyer P, et al. Tight bounds on quantum searching[J/OL]. arXiv Preprint, 1996.http://arxiv.org/pdf/quant-ph/9605034v1.pdf.
[17] Arya S, Mount D M, Netanyahu N S, et al. An optimal algorithm for approximate nearest neighbor searching fixed dimensions[J]. Journal of the ACM, 1998, 45(6): 891-923.
[18] 李强,蒋静坪.量子K最近邻算法[J].系统工程与电子技术,2008,30(5):940-943.
　　Li Qiang, Jiang Jingping. Quantum k nearest neighbor algorithm[J]. Systems Engineering and Electronics, 2008, 30(5): 940-943.(in Chinese)

备注/Memo

备注/Memo:
收稿日期: 2014-12-29.
作者简介: 陈汉武(1955—),男,博士,教授,博士生导师,hanwu_chen@163.com.
基金项目: 国家自然科学基金资助项目(61170321)、高等学校博士学科点专项科研基金资助项目(20110092110024).
引用本文: 陈汉武,高越,张军.量子K-近邻算法[J].东南大学学报:自然科学版,2015,45(4):647-651. [doi:10.3969/j.issn.1001-0505.2015.04.006]
更新日期/Last Update: 2015-07-20