改进的Grover量子搜索算法  

Improved Grover's quantum searching algorithm

作　　者：杨舒晴[1,2] 邓梓杨 李渤 YANG Shuqing;DENG Ziyang;LI Bo(School of Software Engineering,Jiangxi University of Science and Technology,Nanchang 330013,China;School of Information Engineering,Nanchang University,Nanchang 330031,China;School of Software Engineering,East China University of Technology,Nanchang 330013,China;School of Information Management, Jiangxi University of Finance and Economics,Nanchang 330000,China)

机构地区：[1]江西理工大学软件学院,江西南昌330013 [2]南昌大学信息工程学院,江西南昌330031 [3]东华理工大学软件学院,江西南昌330013 [4]江西财经大学信息管理学院,江西南昌330000

出　　处：《南昌大学学报（理科版）》2017年第6期581-584,共4页Journal of Nanchang University(Natural Science)

基　　金：江西省自然科学基金资助项目(20132BAB201044);江西省高等学校科技落地基金资助项目(KJLD12071)

摘　　要：通过分析发现,经典的Grover算法在目标项个数为总搜索项个数的一半时迭代会失效,为此提出一种扩大搜索空间的改进Grover算法1,该算法在目标项个数未知的情况下自适应的调整迭代次数,可以有效避免算法失效;此外针对Grover算法在多次迭代后目标解的概率仍有可能达不到1的情况,提出了改进的Grover算法2。当目标项个数M和待搜索项个数N已知时,针对M/N>1/4的情况,对量子位进行了扩充,在一定情况下该算法只需迭代一次即可以100%的概率得到目标解。Noting that the classical Grover's algorithm will fail when the number of targets is half of the total number of searches,an improved Grover algorithm 1 was proposed in this paper to enlarge the search space.In the case of unknown number of objects,this algorithm can adjust iteration times adaptively and avoid the failure of the algorithm effectively.In addition,in view of the probability of the target item smaller than 1 by using Grover algorithm after multiple iterations,an improved Grover algorithm 2 was proposed.When the number M of target items and the number N of items to be searched are known,the qubit was extended under M/N>1/4,and the algorithm under certain condition needs only one iteration to obtain the target solution with probability 1.

关 键 词：GROVER算法 量子搜索算法 等权叠加态 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP387A[自动化与计算机技术—计算机科学与技术]