第2卷第1期 智能系统学报 Vol.2№1 2007年2月 CAAI Transactions on Intelligent Systems Fcb.2007 一种Grover量子搜索算法的改进策略 李盼池2，李士勇 (1.哈尔滨工业大学航天学院，黑龙江哈尔滨150001：2.大庆石油学院计算机系，黑龙江大庆163318) 摘要：在使用Grover量子搜索算法对给定规模的数据库搜索时，随着搜索目标数的增加，获得正确结果的概率大 幅度下降.分析了出现这种现象的原因，提出了一种基于新的相位匹配条件的改进策略.在新的相位匹配条件中，使 2次相位旋转的大小相等方向相反.当要搜索的目标数目多于记录总数的1/3时，应用改进后的算法只需一步搜索， 能以至少25/27的概率得到全部搜索目标.实验证明这种策略是有效的 关键词：Grover算法；相位匹配；量子搜索；量子计算 中图分类号：TP18文献标识码：A文章编号：16734785(2007)01-003505 An improved measure in Grover quantum searching algorithm LI Panchi',LI Shi-yong' (1.School of Astronautics,Harbin Institute of Technology,Harbin 150001,China:2.Department of Computer Science, Daqing Petroleum Institute,Daqing 163318,China) Abstract:When the current Grover algorithm is applied to search some objects in an unsorted quantum da- tabase,the probability of correct objects usually falls with the increase of the searched objects.The reason for this problem is analyzed in this paper,and an improved measure based on the new phase matching con- dition is proposed.In the new phase matching condition,the amplitudes of two phase rotations are the same and the directions of two phase rotations are contrary.When the objects are more than one third of the total items,with the new phase matching condition,all objects can be found by at least 25/27 of the probability and by the only one Grover iteration.The validity of the improved measure is proved by experi- ment. Keywords:Grover algorithm;phase matching;quantum searching;quantum computing Grover量子搜索算法I和Shor大数质因子分 龙桂鲁等人提出了新的Grover量子搜索算法中的 解算法是2个最著名的量子算法.对于在无序数相位匹配条件1，认为搜索算法中的2次相位取反 据库中搜索若干特定目标时，Grover算法可以对许 可以改为任意的相位旋转，但需满足2次相位旋转 多（虽不是全部）启发式搜索的经典算法起到实质性 的大小和方向均相同.在算法的推广方面，文献[6] 的二次加速作用；Grover算法在搜索时忽略搜索元 考察了系统基态概率幅取任意初始分布时的 素的性质，而把注意力放在那些元素的指标（对应0 Grover算法；文献[7]考察了系统取任意初始混合 ~N-1的数字)上，因此具有很强的通用性).由 态时的Grover算法，文献[8]将Grover算法看作一 于这2个特点，Grover算法引起了人们广泛关注. 个动态系统，详细分析了系统取任意纯态时，算法的 自1996年Grover算法首次提出以来，人们对于该 各项性能.在算法的应用方面，文献[9]将该算法和 算法的研究主要集中在改进、推广和应用3个方面. 神经网络相融合提出一种量子联想记忆模型，与传 在算法的改进方面，Grover在文献[4]中指出，算法 统的Hopfield记忆模型相比，该模型的存储容量具 中的Walsh-Hadamard变换可由任意酉算子代替， 有指数级的扩充；文献[10]对上述模型作了推广，提 收稿日期：20060518. 出了一种基于分布式查询的量子联想记忆模型等. 基金项目：国家自然科学基金资助项目(50138010) 此外，Grover算法也存在自身的缺陷.当搜索 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 2 卷第 1 期 智 能 系 统 学 报 Vol. 2 №. 1 2007 年 2 月 CAA I Transactions on Intelligent Systems Feb. 2007 一种 Grover 量子搜索算法的改进策略 李盼池1 ,2 ,李士勇1 (1. 哈尔滨工业大学 航天学院 ,黑龙江 哈尔滨 150001 ;2. 大庆石油学院 计算机系 ,黑龙江 大庆 163318) 摘 要 :在使用 Grover 量子搜索算法对给定规模的数据库搜索时 ,随着搜索目标数的增加 ,获得正确结果的概率大 幅度下降. 分析了出现这种现象的原因 ,提出了一种基于新的相位匹配条件的改进策略. 在新的相位匹配条件中 ,使 2 次相位旋转的大小相等方向相反. 当要搜索的目标数目多于记录总数的 1/ 3 时 ,应用改进后的算法只需一步搜索 , 能以至少 25/ 27 的概率得到全部搜索目标. 实验证明这种策略是有效的. 关键词 : Grover 算法 ;相位匹配 ;量子搜索 ;量子计算 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2007) 0120035205 An improved measure in Grover quantum searching algorithm L I Pan2chi 1 ,2 , L I Shi2yong 1 (1. School of Astronautics , Harbin Institute of Technology , Harbin 150001 , China ; 2. Department of Computer Science , Daqing Petroleum Institute , Daqing 163318 , China) Abstract : When t he current Grover algorithm is applied to search some objects in an unsorted quant um da2 tabase , the probability of correct objects usually falls wit h t he increase of the searched objects. The reason for t his problem is analyzed in t his paper , and an improved measure based on t he new p hase matching con2 dition is proposed. In t he new p hase matching condition , t he amplit udes of two p hase rotations are t he same and t he directions of two p hase rotations are contrary. When t he objects are more t han one t hird of t he total items , wit h t he new p hase matching condition , all objects can be found by at least 25/ 27 of t he probability and by the only one Grover iteration. The validity of the improved measure is proved by experi2 ment. Keywords : Grover algorit hm ; p hase matching ; quant um searching ; quant um comp uting 收稿日期 :2006205218. 基金项目 :国家自然科学基金资助项目(50138010) . Grover 量子搜索算法[ 1 ]和 Shor 大数质因子分 解算法[2 ]是 2 个最著名的量子算法. 对于在无序数 据库中搜索若干特定目标时 , Grover 算法可以对许 多(虽不是全部) 启发式搜索的经典算法起到实质性 的二次加速作用 ; Grover 算法在搜索时忽略搜索元 素的性质 ,而把注意力放在那些元素的指标 (对应 0 ～N - 1 的数字) 上 ,因此具有很强的通用性[3 ] . 由 于这 2 个特点 , Grover 算法引起了人们广泛关注. 自 1996 年 Grover 算法首次提出以来 ,人们对于该 算法的研究主要集中在改进、推广和应用 3 个方面. 在算法的改进方面 , Grover 在文献[ 4 ]中指出 ,算法 中的 Walsh2Hadamard 变换可由任意酉算子代替 ; 龙桂鲁等人提出了新的 Grover 量子搜索算法中的 相位匹配条件[5 ] ,认为搜索算法中的 2 次相位取反 可以改为任意的相位旋转 ,但需满足 2 次相位旋转 的大小和方向均相同. 在算法的推广方面 ,文献[ 6 ] 考察 了 系 统 基 态 概 率 幅 取 任 意 初 始 分 布 时 的 Grover 算法 ;文献[ 7 ]考察了系统取任意初始混合 态时的 Grover 算法 ;文献[8 ]将 Grover 算法看作一 个动态系统 ,详细分析了系统取任意纯态时 ,算法的 各项性能. 在算法的应用方面 ,文献[ 9 ]将该算法和 神经网络相融合提出一种量子联想记忆模型 ,与传 统的 Hopfield 记忆模型相比 ,该模型的存储容量具 有指数级的扩充 ;文献[ 10 ]对上述模型作了推广 ,提 出了一种基于分布式查询的量子联想记忆模型等. 此外 , Grover 算法也存在自身的缺陷. 当搜索