第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><ml. 7) 2(1-y2c0s(a+月+ U,=(1-e9)|φ><+e81 31-少2+P 8) 在普通Grover算法中，a=B=.根据量子力学基本 当a=-f=/2时，上式取得极大值： 假设1：一个封闭量子系统的演化由一个酉变换来 P=Pax=4R.8P+5入 9) 刻画.关于算子7)、(8)的酉性，提出如下定理 比较式6)和式9)有以下结论： 定理1由式7)、8)定义的算子都是酉算子 1)当0<A<1/3时，户<P: 2)当A=1/3时，P=P: 证明令U=1-1-e>< 3)当1/3<入<1时，P>P. Pv3c<1≥P1-6=25/27.(证毕) 则U*=1--e)∑1n><1 由定理2，改进后算法的2个相移算子式7)、8)具 体化为 UU=1-2-e-el><l+ 0=11-><. 10) 1.ey1.e9(><)=1 Us=1+i动lφ><φ1-i1. (11) 因此，由式7)描述的算子是酉算子 改进前后成功搜索的概率曲线如图2所示 令V=1-e|><9+e1 则V=1-e川><有+e1 10 P v*V=1-e)(1-e)川><+ P 1-e)e9p><+ ei81-e川φ><9+ee1=I. p0.5 因此，由式(8)描述的算子是酉算子.（证毕） 一。一改进前 关于a、B的匹配，文献[51指出，只有在满足 ◆一改进后 a=B时量子搜索才能成功.经过研究认为这个结论 λ1入：50.5 5/61.0 在入较大时是不必要的.在入较大时，给出的相位匹 λ1=0.14645A=0.85356 配条件可表述为如下定理 x=0.25A=1/3乃=25/27 定理2当入>1/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<入<1时，改进后的算 法明显优于普通Grover算法. 1=太j>+k习 2.2改进后的算法相位旋转的直观图示 对于引中>，应用式)得 关于改进后Grover搜索算法的相位旋转，给出 了一种直观的几何表示，见图3. 1>=j>+1k> 图中荆>√a>√B>含义见式5)：0为式10) 对于1中>，应用式(8)，整理后得 描述的相移算子：G为式I1)描述的相移算子：G为 |币>=(1-e)|φ><1+e1)|中>= |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 > <τm | . (7) Us = (1 - e iβ ) | < > < <| + e iβ I. (8) 在普通 Grover 算法中 ,α=β=π. 根据量子力学基本 假设[3 ] :一个封闭量子系统的演化由一个酉变换来 刻画. 关于算子(7) 、(8) 的酉性 ,提出如下定理. 定理 1 由式(7) 、(8) 定义的算子都是酉算子. 证明 令 U = I - (1 - e iα ) ∑ M m =1 | τm > <τm | . 则 U + = I - (1 - e - iα ) ∑ M m =1 | τm > <τm | . U + U = I - (2 - e iα - e - iα ) ∑ M m = 1 | τm > <τm | + (1 - e iα ) (1 - e - iα ) ( ∑ M m =1 | τm > <τm | ) 2 = I. 因此 ,由式(7) 描述的算子是酉算子. 令 V = (1 - e iβ ) | <> < <| + e iβ I . 则 V = (1 - e iβ ) | <> < <| + e - iβ I. V + V = (1 - e - iβ ) (1 - e iβ ) | <> < <| + (1 - e - iβ ) e iβ | <> < <| + e - iβ (1 - e iβ ) | <> < <| + e - iβ e iβ I = I. 因此 ,由式(8) 描述的算子是酉算子. (证毕) 关于α、β的匹配 , 文献 [ 5 ]指出 , 只有在满足 α=β时量子搜索才能成功. 经过研究认为这个结论 在λ较大时是不必要的. 在λ较大时 ,给出的相位匹 配条件可表述为如下定理. 定理 2 当λ> 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β ) | < > < <| + e iβ 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 <λ< 1/ 3 时 , ŽP < P; 2) 当λ= 1/ 3 时 , ŽP = P; 3) 当 1/ 3 <λ< 1 时 , ŽP > P. ŽP1/ 3 <λ<1 ≥ŽPλ=5/ 6 = 25/ 27. (证毕) 由定理 2 ,改进后算法的 2 个相移算子式(7) 、(8) 具 体化为 O = I - (1 - i) ∑ M m =1 | τm > <τm . (10) Us = (1 + i) | < > < <| - i I. (11) 改进前后成功搜索的概率曲线如图 2 所示. 图 2 Grover 算法改进前后成功搜索概率对比 Fig12 Comparison of Successful research probability curve between general Grover algorithm and improved ones 从图 2 可以看出 ,当 1/ 3 <λ< 1 时 ,改进后的算 法明显优于普通 Grover 算法. 212 改进后的算法相位旋转的直观图示 关于改进后 Grover 搜索算法的相位旋转 ,给出 了一种直观的几何表示 ,见图 3. 图中| <> 、|α> 、|β> 含义见式(5) ; O 为式(10) 描述的相移算子; G为式(11) 描述的相移算子; GŽ 为 |α> 、|β> 面上的投影算子;θ= arcsin λ;θ„= arcsin 第 1 期 李盼池 ,等 :一种 Grover 量子搜索算法的改进策略 ·37 ·