一种改进的量子Grover算法  

An Improved Quantum Grover Algorithm

作　　者：周立志[1] 李飞[2] 郑宝玉[2] 

机构地区：[1]南京邮电大学通信与信息工程学院,江苏南京210003 [2]南京邮电大学信号处理与传输研究院,江苏南京210003

出　　处：《南京邮电大学学报（自然科学版）》2011年第2期27-30,共4页Journal of Nanjing University of Posts and Telecommunications：Natural Science Edition

基　　金：教育部博士点基金(BJ206006)资助项目

摘　　要：Grover提出的量子算法,在2n个元素的无序数据库中搜索到m个目标解,其搜索时间复杂度为O(2～(1/2)n/m)。但是当目标解m>N/4时,搜索的成功概率迅速下降,且当m=N/2时,算法失效。提出了一种改进算法,当m>N/4时,仅用一次搜索就能以不低于98.01%的成功概率搜索到目标解。The algorithm proposed by Grover solves the unsorted database search problem with computation complexity of O（√2^n/m）,where the size of database is N = 2^n and there is m target solutions. However, the successful probability of searching decreases rapidly, when the target solutions m is greater than N/d, And the algorithm is disabled when m is equal to N/2. This paper presents an improved Groverg algorithm, which can find the object with the successful probability at least 98.01% with one step when m is greater than N/4.

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

分 类 号：TN911[电子电信—通信与信息系统]