文献类型：期刊文章

作　　者：陈汉武[1] 高越[1] 张军[2]

机构地区：[1]东南大学计算机科学与工程学院,南京210096 [2]江苏海事职业技术学院信息工程系,南京211170

出　　处：《东南大学学报（自然科学版）》

基　　金：国家自然科学基金资助项目(61170321);高等学校博士学科点专项科研基金资助项目(20110092110024)

年　　份：2015

卷　　号：45

期　　号：4

起止页码：647-651

语　　种：中文

收录情况：AJ、BDHX、BDHX2014、CAS、CSA、CSA-PROQEUST、CSCD、CSCD2015_2016、EI(收录号：20153201119752)、IC、INSPEC、JST、MR、RCCSE、SCOPUS、ZGKJHX、ZMATH、核心刊

摘　　要：为了提高经典K-近邻算法的效率,引入量子计算理论,将Grover算法中的Oracle算子以及相位估计算法嵌入经典K-近邻算法,提出一种量子K-近邻算法.该算法首先将样本点和待分类点的向量信息制备成量子叠加态,采用可逆的量子控制交换门并行计算待分类点和样本点的相似度,然后利用相位估计算法将相似度信息存储到量子比特中,最后使用Grover算法一次性搜索出最相似的k个点.对嵌入的量子计算部分的理论分析结果表明,量子K-近邻算法可以明显降低经典计算复杂度,且提出的算法在已有算法计算复杂度O(RkM)的基础上,再次带来了k值的二次加速O(RkM),其中R为Oracle算子的执行次数,M为样本全局个数.

关 键 词：机器学习  K-近邻算法 量子算法

分 类 号：TP387]