Grover量子搜索算法的改进

Grover量子搜索算法的改进2020/1/10之陶兴亮、王乐2003年，英国伯明翰大学Younes提出了一种使用局部扩散算子的搜索算法，该算法中算子的均值反转操作仅在系统的一个局部子空间上执行。理论推导和实验证明，该算法比基本Grover算法具有更优良的性能，尤其适用于多目标搜索。对于在N个元素中寻找M个目标的搜索，其成功概率至少为84.72%。对于拥有个元素的无序数据搜索，一步迭代搜索的实施过程可分为4步，如下图所示。nN20|0|0|0|fUYHHH….……N量子比特1qubit工作空间测量)/(MNO具体步骤如下：(1)准备存储器。准备一个所有量子位处于|0态的n+1位作为Oracle算子的工作空间。此时系统状态为(2)寄存器初始化。对于前n位量子位施加H门变换，将系统状态变为个状态的均匀叠加态，即(3)应用Oracle识别搜索问题的解，并将识别结果存储在附加量子比特中，即(4)局部扩散。首先定义一个局部扩散算子Y，将其用于n+1位量子比特系统中，该算子可描述为其中向量|0的长度为fU0|0||0nWn20|)|1(|)(|1001NiniNWIHW)())(|(|1102difiNWNiIHIIHYnn)|00|2(122nNP下面考虑将Y应用于具有P个基本状态的量子系统的情况。为便于叙述，该量子系统可以重写为其中当k为偶数时，当k为奇数时。应用Y后该量子系统变为10|Pkkk101010)1|(|)0|(||NjjNjjPkkjjkkjkj101010101010)1|(|)0|)(|2(||)|00|(2|))|00|2(()|(NjNjjjPkkPkknnPkknnPkkjjakkIHIHkIHIIHkY其中是子空间的幅度均值。上述结果表明，应用局部扩散算子Y的结果只是在子空间上执行均值翻转，而对于子空间，仅仅只是改变幅度的符号。记为所有搜索问题的解集，为所有非解的集合，由d式描述的系统状态可以描述为101NjjN10)0|(|Njjj10)0|(|Njjj10)1|(|Njjj1i2i1011022)1|(|1)0|(|1NjNjiNiNW将Y作用于后，系统状态更新为记均值为，经计算上式各系数为：2|W)()1|(|)0|(|)0|(|1011101110213eicibiaWNjNjNj1a)/()(1NNMN幅度。之前具有算子扩散对应的状态在应用局部应该指出，幅度且满足0b)(1)(1;2;12121212111111YfMcMbaMNNcbNa(5)测量。经过一步迭代搜索之后，搜索的成功概率为1e)()(4)(8)(5))1())(2(()()1()1(s21)1(ns32222121)1(snsPPaMNPNMNMNMNNNMNMcbMP式得根据失败的概率为当Oracle算子和局部扩算算子Y作用于系统状态时，就构成了迭代算法。如前所述，系统在一次迭代之后的状态如e式，经过二次迭代后，系统更新情况如下：应用Oracle算子后，将具有概率幅的目标态概率幅交换后，系统可描述为应用局部扩散算子Y作用后系统状态变为记，经过计算上式中各系数分别为fUfU11cb和1011101110214)1|(|)0|(|)0|(|NjNjNjibiciaW1012101210225)1|(|)0|(|)0|(|NjNjNjicibiaWNMcaMN/))((11211122122;2;2bccbaa21222222)2(21222222)2())(())(()()()(:bbMNcbMNaMNPbbMcbMPnss系统搜索的成功概率为同理，三次迭代后系统状态变为232332332231013101310236710121012102256;2;2a,/))(()1|(|)0|(|)0|(||)1|(|)0|(|)0|(||bccbaNMcaMNibiciaWYWibiciaWUWNjNjNjNjNjNjf经计算上式各系数为记系统搜索的成功的概率为综上所述，经过q=2次迭代之后，系统状态可描述为记。计算上式中各态系数可用递推算式22323323)3(22232323)3())(())(()()()(bbMNcbMNaMNPbbMcbMPnss101101102)1|(|)0|(|)0|(|NjqNjqNjqqicibiaW11)1(,/1,/1qqqcyyaNsNMysccbcgsybsbcbysasaaaqqqqqqqq101101101;0;)(2;;2)12(;;2系统的搜索的成功概率是当q=2时，将g式改为解上述的迭代方程可得2122)(21222)q())(())(()()()(qqqqqqnsqqqqsbbMNcbMNaMNPbbMcbMPsccbcsybsbbybysasaayaqqqqqqq1011021021;0;2;;2)12(;;2)sinsin()sin)1sin(()sinsinsin)1sin((qscqsbqqsaqqq其中y=cosθ，0θ=π/2。由第二类切比雪夫多项式，上述三式可写为sin)1sin()(qyUq2212)(ns212)(s11)(cos))(cos1(;);(qqqqqqqqqqqqqUUPUUPsUcsUbUUsa系统搜索的成功概率为且满足1sinsin)sin)sin1(sinsin)sin1((sin1)sincossinsin(cossin1)sin)1sin(cos2sin)1((sinsin1)(2)()()(2222222222222222222222)()q(qqqqqqqqqqbcMNcbNaMNcbMPPqqqqqqqqnss为确定以高概率获得一个搜索目标所需要的迭代步数，Younes给出了如下定理。定理：若使得成功概率=1，其中是第二类切比雪夫多项式，y=cosθ且0θ=π/2，则所需迭代步数为。证明：))(cos1(212)(sqqqUUP)(yUq22或q22cos)2cos(0cos0)1)2(cos(cos0)1sin2sincos2(coscos20cos22sincos2cos2cos20cos22cos)22(ccos1sin)1(sin1)sinsinsin)1(sin)(cos1(,sin)1(sin)()(2222222qqqqqqqqqqqosqqqqqyUyU或或上述关系可写为经过简单的三角运算，或成功概率可写为的定义式由NMqMNqNMNMNMNMy2222,2212sin1cos，通常向下取整表示为考虑到迭代步数为整数。时，。当的由基本Grover算法经过q次迭代后的成功概率为为：需要的迭代次数其中次迭代后成功概率为算法经过需要的迭代次数其中;2/0;/1cos)sinsinsin)1(sin)(cos1(q4q;2/0;/sin)12(sin2222qs22NMqqPYounesMNNMqPGqsNMq22