量子K-近邻算法

摘要：

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

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

所属期刊栏目：45

分类号：TP387(计算技术、计算机技术)

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

在线出版日期：2015-09-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：647-651