第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 算法也存在自身的缺陷. 当搜索
·36· 智能系统学报 第2卷 目标大于数据库记录数的1/4时，搜索成功的概率 1.2 Grover算法成功搜索的概率 快速降低，当搜索的目标大于数据库记录数的一半 令1a>为N·M个非解均匀迭加态的归一化 时，搜索失效.已有改进措施均不能解决这一问题， 状态，B>为M个解均匀迭加态的归一化状态.则 针对这一问题，文中从分析算法中旋转相位的匹配 初态中>可在a>和B>张成的空间中表示为 条件入手，提出了改进措施.该措施使搜索过程中2 I>=cos(a>+sin(B>. (5) 次相位旋转的大小相等，方向相反.应用改进后的算 式中：t=arcsin经过R次Grover调用后，初态 法，当搜索目标数较多时，只需一步搜索，即可获得 变为 很高的成功概率，并且随搜索目标数的增加，这种高 G>=cos(2R+1)arcsiina>+ 概率变化很小 sin((2R+1)arcsinB>. 1普通Grover算法及存在问题 因此，Grover算法成功搜索的概率为 1.1 Grover算法简介 P=sin2((2R+1)arcsin 6) 假设在N个元素的搜索空间中进行搜索，为方 概率曲线如图1所示。 便起见，假定N=2”,于是元素指标可以存储在n个 量子比特中.假设搜索问题恰有M个解Ω={5，互， ,Tw,1M≤N Grover算法的初始状态为n个量子比特的均 0.5 匀迭加态 0.0 10.25 0.5 1.0 其中记号“9>”称为Dirac记号，它在量子力学中表 示状态，另外记号“1a>和 a:=0.14645B=0.85356 |>和的外积，其实质是一个描述量子态演化的酉 图1普通Grover算法成功搜索概率曲线 算子.搜索过程包括以下4个步骤 Fig 1 The successful research probability curve 1)目标态取反中>=O> of general Grover algorithm 0=1-21>=|H1$>. 0.50.因此，普通Grover算法搜索成功概率在入= 式中：H=上11 0.25时达到最大，之后迅速下降，在入=0.5时降到 21. 最低点.之后R=0,算法失效，成功搜索的概率变为 3)执行条件相移： 入所以，普通Grover搜索算法在A>0.25之后，不 1$>=210> 再适用 4)应用Hadamard变换：>=Ho14> 出现这种现象的原因在于：算法1)、3)中2次 由Hadamard门性质，将2)、3)、4)3步结合的 相移的大小相等均为)；方向相同均正向).根据 效果为 文献3]，这样的相位旋转结果是：调用一次Grover Us=2|中>正向旋转0=2 aresin瓜当0≤1.25 记1=兴对于上述4步.调用次数R为 时，将使|>逐渐逼近1B>;当入>0.25时，将使|中 >迅速偏离B> R=CI arccos 4) 2 arcsin月 2 Grover算法的改进策略 式中：CI(x)表示取最接近实数x的整数，按习惯将 根据前节对普通Grover量子搜索算法存在问 一半向下取整.因此，至多经过R次Grover调用， 题的分析，可首先将其搜索过程中的2次相位旋转 即能以至少1/2的概率搜索到问题的M个解 由固定值π推广为任意值，然后通过探索2次相位 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
目标大于数据库记录数的 1/ 4 时 ,搜索成功的概率 快速降低 ,当搜索的目标大于数据库记录数的一半 时 ,搜索失效. 已有改进措施均不能解决这一问题. 针对这一问题 ,文中从分析算法中旋转相位的匹配 条件入手 ,提出了改进措施. 该措施使搜索过程中 2 次相位旋转的大小相等 ,方向相反. 应用改进后的算 法 ,当搜索目标数较多时 ,只需一步搜索 ,即可获得 很高的成功概率 ,并且随搜索目标数的增加 ,这种高 概率变化很小. 1 普通 Grover 算法及存在问题 111 Grover 算法简介 假设在 N 个元素的搜索空间中进行搜索 ,为方 便起见 ,假定 N = 2 n ,于是元素指标可以存储在 n 个 量子比特中. 假设搜索问题恰有 M 个解Ω= {τ1 ,τ2 , …,τM } ,1 ≤M ≤N . Grover 算法的初始状态为 n 个量子比特的均 匀迭加态 | = 1 N j ∑| Ω | j > + 1 N k∑∈Ω | k > . (1) 其中记号“| > ”称为 Dirac 记号 ,它在量子力学中表 示状态 ,另外记号“| α> 和 |β> 和的外积 ,其实质是一个描述量子态演化的酉 算子. 搜索过程包括以下 4 个步骤. 1) 目标态取反 :| = O| <> . O = I - 2 ∑ M m =1 | τm > = | H á n | . 式中 : H á n = 1 2 n 1 1 1 - 1 á n . 3) 执行条件相移 : | = (2 | 0 > . 4) 应用 Hadamard 变换 :| = H á n | 由 Hadamard 门性质 ,将 2) 、3) 、4) 3 步结合的 效果为 Us = 2 | 为 N - M 个非解均匀迭加态的归一化 状态;|β> 为 M 个解均匀迭加态的归一化状态. 则 初态| <> 可在|α> 和|β> 张成的空间中表示为 | = cos( t) | α > + sin ( t) | β > . (5) 式中 :t = arcsin λ. 经过 R 次 Grover 调用后 ,初态 变为 G R | = cos(2 R + 1) arcsiin λ| α > + sin ( (2 R + 1) arcsin λ) | β > . 因此 , Grover 算法成功搜索的概率为 P = sin 2 ( (2 R + 1) arcsin λ) . (6) 概率曲线如图 1 所示. 图 1 普通 Grover 算法成功搜索概率曲线 Fig11 The successful research probability curve of general Grover algorithm 113 Grover 算法存在问题及分析 由式(4) 、(6) 可知 ,当λ∈(01146 45 , 0150) 时 , R = 1 ; Pλ= 01146 45 = 01853 56 ; Pλ= 0125 = 1100 ; Pλ= 0150 = 0150. 因此 ,普通 Grover 算法搜索成功概率在λ= 0125 时达到最大 ,之后迅速下降 ,在λ= 015 时降到 最低点. 之后 R = 0 ,算法失效 ,成功搜索的概率变为 λ. 所以 ,普通 Grover 搜索算法在λ> 0125 之后 ,不 再适用. 出现这种现象的原因在于 :算法 1) 、3) 中 2 次 相移的大小相等(均为π) ;方向相同(均正向) . 根据 文献[3 ] ,这样的相位旋转结果是 :调用一次 Grover 搜索 ,使| <> 正向旋转θ= 2arcsin λ. 当 0 ≤λ≤0125 时 ,将使| <> 逐渐逼近|β> ;当λ> 0125 时 ,将使| 迅速偏离|β> . 2 Grover 算法的改进策略 根据前节对普通 Grover 量子搜索算法存在问 题的分析 ,可首先将其搜索过程中的 2 次相位旋转 由固定值π推广为任意值 ,然后通过探索 2 次相位 ·36 · 智 能 系 统 学 报 第 2 卷
第1期 李盼池，等：一种Grover量子搜索算法的改进策略 ·37· 旋转的大小与获得正确结果的概率之间的关系，来 确定新的相位匹配条件.沿着这种思路，提出的新的 (Me"+e" 相位匹配条件是：2次相位旋转的大小相等（均等于 (NMe Me /2),而方向相反 令p=(N-M(ea9-e”+)+Me”,则成功搜索 2.1改进算法的相位匹配条件 的概率P为Mp2.整理后得 考察Grover算法的2个相移算子，写成一般形 P=(-4+6(cos a+cos+ 式为 (2R.2)c0s1a.月+ 0=1-1-e)ltm>P. Pv3c1/3时，取a=-B=/2,只需一 图2 Grover算法改进前后成功搜索概率对比 次搜索，获得正确结果的概率P25/27. Fig 2 Comparison of Successful research probability 证明设！互>，互>，m>为M个要搜索 curve between general Grover algorithm and improved ones 的目标量子态，P={,互，…w.则系统初始状态 可表示为 从图2可以看出，当1/3+k习 2.2改进后的算法相位旋转的直观图示 对于引中>，应用式)得 关于改进后Grover搜索算法的相位旋转，给出 了一种直观的几何表示，见图3. 1>=j>+1k> 图中荆>√a>√B>含义见式5)：0为式10) 对于1中>，应用式(8)，整理后得 描述的相移算子：G为式I1)描述的相移算子：G为 |币>=(1-e)|φ>= |a>JB>面上的投影算子：0=arcsin:0=arcsin 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
旋转的大小与获得正确结果的概率之间的关系 ,来 确定新的相位匹配条件. 沿着这种思路 ,提出的新的 相位匹配条件是 :2 次相位旋转的大小相等(均等于 π/ 2) ,而方向相反. 211 改进算法的相位匹配条件 考察 Grover 算法的 2 个相移算子 ,写成一般形 式为 O = I - (1 - e iα ) ∑ M m =1 | τm > 1/ 3 时 ,取α= - β=π/ 2 ,只需一 次搜索 ,获得正确结果的概率 P ≥25/ 27. 证明 设|τ1 > ,|τ2 > , …,|τm > 为 M 个要搜索 的目标量子态 ,Ω= {τ1 ,τ2 , …,τM } . 则系统初始状态 可表示为 | = 1 N j ∑| Ω | j > + k∑∈Ω | k > . 对于| <> ,应用式(7) 得 | ^ = j ∑| Ω 1 N | j > + k∑∈Ω e iα N | k > . 对于| ^<> ,应用式(8) ,整理后得 | = ( (1 - e iβ ) | = 1 N N j ∑| Ω ( M (e iα + e iβ - e i(α+β) + N - M) +| j > + k∑∈Ω ( ( N - M) (e i(α+β) - e iβ + 1) + Me iα ) | k > . 令 p = ( N - M) (e i(α+β) - e iβ + 1) + Me iα ,则成功搜索 的概率 P 为 M | p| 2 . 整理后得 P = ( - 4λ3 + 6λ2 - 2λ) (cosα+ cosβ) + (2λ3 - 2λ2 ) co s(α- β) + 2λ(1 - λ) 2 cos(α+β) + 3λ(1 - λ) 2 +λ3 . 当α= - β=π/ 2 时 ,上式取得极大值 : P = Pmax = 4λ3 - 8λ2 + 5λ. (9) 比较式(6) 和式(9) 有以下结论 : 1) 当 0 P. P1/ 3 、|α> 、|β> 含义见式(5) ; O 为式(10) 描述的相移算子; G为式(11) 描述的相移算子; G 为 |α> 、|β> 面上的投影算子;θ= arcsin λ;θ= arcsin 第 1 期 李盼池 ,等 :一种 Grover 量子搜索算法的改进策略 ·37 ·
·38· 智能系统学报 第2卷 R 1abab baba bab abba babb abab baba bbab). GGO$> 式中：a=-6:b=26+32i GO引克 表1目标学号及量子比特目标状态 Table 1 The target serial number and its quantum state 目标学号 目标状态 0 100001> 01p li> 1 3 100011> 2 4 100100> 图3改进后的算法相位旋转的直观图示 3 6 |00110> Fig 3 The sketch map of phase rotation for the 4 8 101000> improved Grover algorithm 9 101001> 4P-8+5入：i=J1.调用一次算法，相位旋转 6 11 101011> ).日图3直观示出了搜索过程中相位的变化情况. 13 101101> 2.3改进后的算法描述八 8 14 101110> 以入=1/3为分界点，分如下2种情况： 9 16 110000>≥ 1)若l/3 Step1用式10)，使！>中目标态的相位正向 11 19 |10011> 移动/2： 12 21 110101> 13 23 |10111> 18>=1-1-动∑l。> 14 24 111000> Step2用式11)，使！>正向旋转到>； 15 26 111010> 10>=(1+i边1φ>. 16 28 111100> Step3对中>实施测量. 17 29 111101> 3算例 18 31 111111> 某班有32名同学，学号n=0,1,…31.搜索学 号满足[号鬥的同学=0,113：1·7伪校 3)正确结果的概率 26 32 p=19 四舍五入取整算符.目标学号及对应量子比特状态 128w2 + 1282 =0.9875. 见表1. 作为对比，用普通Grover算法的搜索结果如下： 此算例中，N=32:M=19:A=0.5938.取5位 ①1$>=1-21> 量子比特即可满足搜索要求5量子比特均匀迭加 的初始状态>为 11-11-1-11-11-1-11-11- 4 1>= 500>+11>+…+131>) 1-11-11-1-11-11-1-11-11-1- 4 搜索过程如下： 11-1). ②>=(2φ> 川$>=(1-1-i动1.> (abab baba bbab abba babb abab baba 32N2 4方i, bbab). 2)川>=(1+川> 式中：a=-11:b=5. 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
图 3 改进后的算法相位旋转的直观图示 Fig13 The sketch map of phase rotation for the improved Grover algorithm 4λ3 - 8λ2 + 5λ;i = - 1. 调用一次算法 ,相位旋转 θ- θ. 图 3 直观示出了搜索过程中相位的变化情况. 213 改进后的算法描述 以λ= 1/ 3 为分界点 ,分如下 2 种情况 : 1) 若 1/ 3 中目标态的相位正向 移动π/ 2 ; | θ^ > = ( I - (1 - i) ∑ M m =1 | τm > Step2 用式(11) ,使| ^<> 正向旋转到| <> ; | θ > = ( (1 + i) | . Step3 对 ^<> 实施测量. 3 算 例 某班有 32 名同学 ,学号 n = 0 , 1 , …, 31. 搜索学 号满足 n = 5 k + 3 3 的同学. k = 0 ,1 …,18 ;[ ·]为按 四舍五入取整算符. 目标学号及对应量子比特状态 见表 1. 此算例中 , N = 32 ; M = 19 ;λ= 01593 8. 取 5 位 量子比特即可满足搜索要求. 5 量子比特均匀迭加 的初始状态| <> 为 | = 1 4 2 (| 0 > +| 1 > + …+| 31 >) . 搜索过程如下 : 1) | ^ = ( I - ( 1 - i) ∑ M m = 1 | τm > 1 4 2 (1i1i i1i1 ii1i 1ii1 i1ii 1i1i i1i1 ii1i) . 2) | <> = ( (1 + i) | <> . 1 128 2 ( abab baba bbab abba babb abab baba bbab) . 式中 : a = - 6 ; b = 26 + 32i. 表 1 目标学号及量子比特目标状态 Table 1 The target serial number and its quantum state k 目标学号 目标状态 0 1 | 00001 > 1 3 | 00011 > 2 4 | 00100 > 3 6 | 00110 > 4 8 | 01000 > 5 9 | 01001 > 6 11 | 01011 > 7 13 | 01101 > 8 14 | 01110 > 9 16 | 10000 > 10 18 | 10010 > 11 19 | 10011 > 12 21 | 10101 > 13 23 | 10111 > 14 24 | 11000 > 15 26 | 11010 > 16 28 | 11100 > 17 29 | 11101 > 18 31 | 11111 > 3) 正确结果的概率 P = 19 26 128 2 2 + 32 128 2 2 = 01987 5. 作为对比 ,用普通 Grover 算法的搜索结果如下 : ①| ^ = ( I - 2 ∑ M m = 1 | τm > 1 4 2 (1 - 1 1 - 1 - 1 1 - 1 1 - 1 - 1 1 - 1 1 - 1 - 1 1 - 1 1 - 1 - 1 1 - 1 1 - 1 - 1 1 - 1 1 - 1 - 1 1 - 1) . ②| <> = (2| <> . 1 32 2 ( abab baba bbab abba babb abab baba bbab) . 式中 : a = - 11 ; b = 5. ·38 · 智 能 系 统 学 报 第 2 卷
第1期 李盼池，等：一种Grover量子搜索算法的改进策略 ·39· ③正确结果的概率 [7]BIHAM E,KENIGSBERG D.Grover's quantum search 5 2 algorithm for an arbitrary initial mixed state [J].Physi- P=19 32 =0.2319. cal Review A,2002,66(6):2301.2304. [8]BIHAM O,SHAPIRA D,SHIMONI Y.Analysis of 4 结束语 Grover's quantum search algorithm as a dynamical system 针对目前Grover算法随着目标数增多，搜索概 [U].Physical Review A,2003,68(2):2326-2333. [9]VENTURA D,MARTIN EZ T.Quantum associative 率迅速下降直至算法失效的问题，文中提出了一种 memory [J ]Information Sciences,2000(124):273- 新的相位匹配策略，不同于文献[5]的结论，该策略 296. 使算法中2次相移大小相等方向相反.该策略较好 [10]EZHOV A,NIFANOVA A,VENTURA D.Quantum 地解决了目前Grover算法中存在的上述问题.算例 associative memory with distributed queries [J ]Infor- 证明，该策略是有效的.在搜索目标较多时如何进一 mation Sciences,2000(128):271-293. 步提高成功搜索的概率，以及如何将Grover量子搜 [11]李士勇，李盼池.基于实数编码和目标函数梯度的量子 索算法与梯度量子遗传算法川融合是下一步要解 遗传算法[U],哈尔滨工业大学学报，2006,38(8)： 决的问题 1216-1218 LI Shiyong,LI Panchi.A quantum genetic algorithm 参考文献： based on real encoding and gradient information of ob- [1]GROVER L K.A fast quantum mechanical algorithm for ject function [J].Journal of Harbin Institute of Tech- nology,2006,38(8):1216-1218 database search [A ]Proceedings of the 28th Annual 作者简介： ACM Symposium on the Theory of Computing [C]. 李盼池，男，1969年生，副教授，博 Pennsylvania,1996. 士研究生，主要研究方向为量子计算、 [2]SHOR P W.Algorithms for quantum computation:dis 智能优化算法及其在智能控制、智能信 crete logarithms and factoring [A].Proceedings of the 息处理、模式识别等方面的应用.发表 35th Annual Symposium on the Foundation of Computer 学术论文多篇。 Science [C].Los Alamitos,1994. [3]NIEL SEN M A,CHUANG IL.Quantum computation Email:lipanchi @vip.sina.com. and quantum information [M].London:Cambridge Uni- versity Press,2000. 李士勇，男，1943年生，教授，博士 [4]GROVER L K.Quantum computers can search rapidly 生导师，主要研究方向为模糊控制、神经 by using almost any transformation [J].Physical Review 控制、智能控制、智能优化算法，非线性 Letters,1998,80(29):4329-4332. 科学与复杂性科学等.中国自动化学会 5]LONG GL,LI Y S,ZHANG WL,et al.Phase matc- hing in quantum searching[J].Physics Letters A,1999, 智能自动化专业委员会委员，《计算机测 量与控制》编委.编著教材与专著共5 26(10):27-34. [6]BIHAM E,BIHAM O,BIRON D,et al.Grover's quam 部，在国内外发表学术论文120余篇。 E mail:Isy @hit.edu.cn tum search algorithm for an arbitrary initial amplitude distribution [J].Physical Review A,1999,60(4):2742 .2745. 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
③正确结果的概率 P = 19 5 32 2 2 = 01231 9. 4 结束语 针对目前 Grover 算法随着目标数增多 ,搜索概 率迅速下降直至算法失效的问题 ,文中提出了一种 新的相位匹配策略 ,不同于文献[ 5 ]的结论 ,该策略 使算法中 2 次相移大小相等方向相反. 该策略较好 地解决了目前 Grover 算法中存在的上述问题. 算例 证明 ,该策略是有效的. 在搜索目标较多时如何进一 步提高成功搜索的概率 ,以及如何将 Grover 量子搜 索算法与梯度量子遗传算法[ 11 ] 融合是下一步要解 决的问题. 参考文献 : [ 1 ] GROV ER L K. A fast quantum mechanical algorithm for database search [ A ]. Proceedings of the 28th Annual ACM Symposium on the Theory of Computing [ C ]. Pennsylvania , 1996. [2 ]SHOR P W. Algorithms for quantum computation : dis2 crete logarithms and factoring [ A ]. Proceedings of the 35th Annual Symposium on the Foundation of Computer Science [C]. Los Alamitos , 1994. [3 ]NIELSEN M A , CHUAN G I L. Quantum computation and quantum information [ M]. London : Cambridge Uni2 versity Press , 2000. [4 ] GROV ER L K. Quantum computers can search rapidly by using almost any transformation [J ]. Physical Review Letters ,1998 , 80 (29) : 4329 - 4332. [5 ]LON G G L , L I Y S , ZHAN G W L , et al. Phase matc2 hing in quantum searching [J ]. Physics Letters A ,1999 , 26 (10) :27 - 34. [6 ]BIHAM E , BIHAM O , BIRON D , et al. Grover’s quan2 tum search algorithm for an arbitrary initial amplitude distribution [J ]. Physical Review A ,1999 , 60 (4) : 2742 - 2745. [7 ]BIHAM E , KENIGSBERG D. Grover’s quantum search algorithm for an arbitrary initial mixed state [J ]. Physi2 cal Review A ,2002 ,66 (6) : 2301 - 2304. [8 ] BIHAM O , SHAPIRA D , SHIMONI Y. Analysis of Grover’s quantum search algorithm as a dynamical system [J ]. Physical Review A ,2003 , 68 (2) : 2326 - 2333. [ 9 ] V EN TURA D , MARTIN EZ T. Quantum associative memory [J ]. Information Sciences , 2000 ( 124) : 273 - 296. [10 ] EZHOV A , NIFANOVA A , V EN TURA D. Quantum associative memory with distributed queries [J ]. Infor2 mation Sciences ,2000 (128) : 271 - 293. [ 11 ]李士勇 , 李盼池. 基于实数编码和目标函数梯度的量子 遗传算法 [J ]. 哈尔滨工业大学学报 , 2006 , 38 ( 8) : 1216 - 1218. L I Shiyong , L I Panchi. A quantum genetic algorithm based on real encoding and gradient information of ob2 ject function [J ]. Journal of Harbin Institute of Tech2 nology ,2006 , 38 (8) : 1216 - 1218. 作者简介 : 李盼池 ,男 ,1969 年生 ,副教授 ,博 士研究生 ,主要研究方向为量子计算、 智能优化算法及其在智能控制、智能信 息处理、模式识别等方面的应用. 发表 学术论文多篇. E2mail : lipanchi @vip. sina. com. 李士勇 ,男 ,1943 年生 ,教授 ,博士 生导师 ,主要研究方向为模糊控制、神经 控制、智能控制、智能优化算法、非线性 科学与复杂性科学等. 中国自动化学会 智能自动化专业委员会委员《, 计算机测 量与控制》编委. 编著教材与专著共 5 部 ,在国内外发表学术论文 120 余篇. E2mail : lsy @hit. edu. cn 第 1 期 李盼池 ,等 :一种 Grover 量子搜索算法的改进策略 ·39 ·