Grover量子搜索算法的改进

摘要：

　　Grover提出的量子算法，在2n个元素的无序数据库中搜索到M个目标解，其搜索时间的复杂度为O(√2n/M)。但是，当目标解M<N/4时一次迭代成功概率较低；当M>N/4时搜索的成功概率迅速下降；当M=N/2时，算法失效。本文提出了两种改进算法，当M<N/4时能显著提高搜索概率；当M>N/4时，仅用一次搜索就能以不低于98.01％的成功概率搜索到目标解。

关键词： Grover算法 量子并行计算 算法改进 相位旋转

作者: 张海雄 李飞

作者单位: 南京邮电大学通信与信息工程学院，南京，210003

会议类型: 国内会议

会议名称: 第23届全国计算机新科技与计算机教育学术会议

会议地点: 兰州

会议语种:中文

页码: 295-299

在线出版日期: 2012-08-03（万方平台首次上网日期，不代表论文的发表时间）