·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>和 a:=0.14645B=0.85356 |>和的外积，其实质是一个描述量子态演化的酉 图1普通Grover算法成功搜索概率曲线 算子.搜索过程包括以下4个步骤 Fig 1 The successful research probability curve 1)目标态取反中>=O> of general Grover algorithm 0=1-21><1 (2 1.3 Grover算法存在问题及分析 由式4)、16)可知，当入∈0.14645,0.50)时 式中：I为单位矩阵 R=1;P-a14645=0.85356;Pa-a25=1.00;P-a50= 2)应用Hadamard变换>=|H1$>. 0.50.因此，普通Grover算法搜索成功概率在入= 式中：H=上11 0.25时达到最大，之后迅速下降，在入=0.5时降到 21. 最低点.之后R=0,算法失效，成功搜索的概率变为 3)执行条件相移： 入所以，普通Grover搜索算法在A>0.25之后，不 1$>=210><01-01$> 再适用 4)应用Hadamard变换：>=Ho14> 出现这种现象的原因在于：算法1)、3)中2次 由Hadamard门性质，将2)、3)、4)3步结合的 相移的大小相等均为)；方向相同均正向).根据 效果为 文献3]，这样的相位旋转结果是：调用一次Grover Us=2|中><-1 (3) 搜索，使|>正向旋转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) 目标态取反 :| <1 > = O| <> . O = I - 2 ∑ M m =1 | τm > <τm | . (2) 式中 : I 为单位矩阵. 2) 应用 Hadamard 变换 :| <2 > = | H á n | <1 > . 式中 : H á n = 1 2 n 1 1 1 - 1 á n . 3) 执行条件相移 : | <3 > = (2 | 0 > < 0 | - I) | <2 > . 4) 应用 Hadamard 变换 :| <4 > = H á n | <3 > 由 Hadamard 门性质 ,将 2) 、3) 、4) 3 步结合的 效果为 Us = 2 | < > < <| - I. (3) 记λ= M N ,对于上述 4 步 ,调用次数 R 为 R = CI arccos λ 2arcsin λ . (4) 式中 :CI( x) 表示取最接近实数 x 的整数 ,按习惯将 一半向下取整. 因此 ,至多经过 R 次 Grover 调用 , 即能以至少 1/ 2 的概率搜索到问题的 M 个解. 112 Grover 算法成功搜索的概率 令|α> 为 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 卷