量子K-近邻算法

• 作者: 张军 陈汉武 高越
• 来源期刊: 东南大学学报（自然科学版）
• 学科: 工学
• 关键词: 机器学习 K-近邻算法 量子算法
• 年，卷（期）: 2015,（4）
• 页码范围: 647-651
• 页数: 5页
• 分类号: TP387
• 字数: 4905字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-0505.2015.04.006

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张军	江苏海事职业技术学院信息工程系	25	63	4.0	6.0
2	陈汉武	东南大学计算机科学与工程学院	67	442	12.0	17.0
3	高越	东南大学计算机科学与工程学院	1	5	1.0	1.0