基于自适应相位旋转的Grover量子搜索算法  

Grover’s Quantum Search Algorithm Based on Adaptive Phase Rotation

作　　者：李盼池[1,2] 李士勇[1] 

机构地区：[1]哈尔滨工业大学控制科学与工程系,哈尔滨150001 [2]大庆石油学院计算机与信息技术学院,大庆163318

出　　处：《系统仿真学报》2009年第12期3557-3560,共4页Journal of System Simulation

基　　金：国家自然科学基金(60773065)

摘　　要：在使用Grover量子搜索算法对给定规模的无序数据库搜索时,随着搜索目标数的增加,获得正确结果的概率大幅度下降。分析了出现这种现象的原因,研究了算法中的Grover叠代过程,提出了一种新的自适应相位旋转策略。应用这一策略,当搜索目标数超过目标总数的(3-5^(1/2))/8时,只需两步搜索;当搜索目标数超过目标总数的1/4时,只需一步搜索,即可获得恒等于1的成功概率。实验表明新相位旋转策略是有效的。When the Grover＇s algorithm is applied to search an unordered database, the success probability usually decreases with the increase of marked items. The reason for this phenomenon was analyzed, the Grover iteration was studied, and a new adaptive phase rotation was proposed. With application of the new phase rotation, when the fraction of marked items is a rational number in range （3 - √5） / 8 to 1/4, the success probability is equal to 1 after two Grover iterations; and when the fraction of marked items is greater than 1/4, the success probability is equal to 1 after the only one Grover iteration. The effectiveness of the new phase rotation is verified by a search example.

关 键 词：量子计算 量子搜索 GROVER算法 相位旋转 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]