Grover 量子搜索算法的改进 课件

Grover量子搜索算法的改进2013.5.24之陶兴亮、王乐我们知道，对于一个未加整理的具有N个元素的数据库，如果用经典的搜索算法至少需要N/2步才可以搜索到指定的记录，为了加速上述问题的搜索过程，1996年Grover提出了一种量子搜索算法，而如果使用该Grover搜索算法则可以将算法复杂度从O(N)降低到O()，显然这种算法起到了起到了对经典算法的二次加速作用，从而显著提高了搜索的效率。N假设在N个元素的搜索空间进行搜索。现不直接搜索元素，而是给每个元素指定0~N-1的标记，假设存在N=，于是标记可以存储在n个比特中。进一步假设搜索问题恰有M个解，1=M=N，搜索问题可方便地表示为输入为x的函数f(x)，其中x的取值从0~N-1。若x是搜索问题的一个解，则f(x)=1；若x不是搜索问题的解，则f(x)=0；n2建立一个n比特量子寄存器和一个1比特的寄存器，在第一个寄存器中创建个基本量子态：|0,…,|,我们可以通过H门来实现。首先对第一个寄存器初始化|0,…0，然后利用算子作用，有|φ是所有基本量子状态的等幅度组合。n2n2nH10|1)21|0|()0|(0,...,0||NinnninHH表示n个H门并行运算nH011|100|111121H第二个寄存器初始化可以设置为|1，经过哈达玛门作用后，将存储|—=(|0-|1)/量子态。现在定义函数f:{0,…,N-1}-{0,1}，此函数的作用如下：再定义如下公正运算：2)(if0ii,1值是要查找的如果检测到的，其他情况0)(||)|(|fifjijiU其中|i代表第一个寄存器,i的值域是{0,…-1},j代表第二个寄存器，j的值域是{0,1}，表示模2加，很容易得到以下推导：其中n2||)1(2)(1||)(||2)1|(|)0|(|)|(|)(iifiifiiUiUiUiffff)(1if00,1,0iiii由于对第二个寄存器不产生影响，我们定义第一个寄存器状态在作用后用来表示，则作用的输出可以表示为fUfU1|fU||)1(1)|(|1)|(|||10)(101iNiUNUNiifNiff是各个基本失态的组合，但是对于搜索态，他的值是负值，而其他的基失却是正值，就是说待搜索态用负值做了标记。这个获得的结果可以表达为：量子并行处理，可以同时“看到”所有的量子状态，待搜索态用负号标记。但是量子信息不能用经典的方法简单获得，所以下一步我们要做的首先是提高待搜索态的振幅，同时减小其他态的振幅，即增加测量时获得搜索态的概率，减小非搜索得到的概率。1|HHHH。。。。。。。。。。。。。。。GGGH0|0|1|1|G|in|2|G|Grover算法的量子线路实现图中G称为Grover算子，它是由一系列的操作算子运算组成，包括Oracle算子（简写成O算子）、哈达玛算子H、条件相移算子。I|00|2由于Grover算子可以用图表示如下：IHIHnn||2)|00|2(21|0|21|0|。。。。。。。。。fUOracleI||2|G|1|||其中算子G的处理复杂度是，算子称为倒置因子。由于这里的就是带搜索状态，也是一个基态，由于基失之间是相互正交的，所以有：)(NOI||201|22||in0|i0|ini21|0前图中的，同时利用上面已经得出的公式，我们可以得到如下公式：这个状态是第一个寄存器经过一次G作用后的存储状态，第二个寄存器内容仍没有改变为|-。G算子作用使得在量子态方向的振幅增加，表明在方向上的概率增大。1|0220201|22|212|22||22|2)|22)(|||2(|)||2(|iiiIInnnnnnG0|i0|i从这里可以看出对执行了一次旋转I||21.2几何角度理解Grover算法用下图来描述，前者是开始状态，后者是搜索解。在这个图中我们可以看到向量，它们之间的夹角小于90度。由于，如果n很大，这个角度会很接近90度。0||i和0|i|||GG||fLU0||i和ni2/1|0证明Grover算子可看作由开始向量到搜索问题解所张成的二维空间中的一个旋转。我们假设表示所有搜索问题解的集合，共M解，表示所有非搜索问题解的集合，定义归一化状态如下：初向量将属于张成的空间，O算子运算对定义的平面上的向量进行了一次反射倒置因子也执行定义平面上的一次反射，即旋转。两个反射的积也是一个旋转，所以G算子作用一次是一个旋转。对于所有k次Grover算子操作，状态将留在定义的平面上。'x''xxMxMNxx|1||1|'|||NMNMN||和||和|||)||(babaO||和||kG||和若令,则可进一步将G运算表示为反复应用Grover算子，把状态向量旋转接近，此时在计算基中的任一个观测将以很高的概率产生输出，即获得待搜索解。NMN2cos|2)12(sin|2)12(cos||23sin|23cos||2sin|2cos|kkGGk||1.3Grover算法存在的问题由于前面有其中，现记则有,因为每次迭代相位旋转弧度，则要迭代次,现在令搜索解的成功概率为xMxMNxx|1|,|1|'|||NMNMNarcsin2/,/NM|2/sin|2/cos|2)/)/((arccosNMCI|arcsin)12sin(|arcsin)12cos(|))arcsin2/()((arccosRRCIR|2)arcsin)12(sin(RP因迭代步数通过R的取整得到，所以迭代步数每个取值对应λ的一个小区间，且随着λ增大，迭代步数减小，成功概率降低。如下表：迭代步数λ范围最小概率最小概率时λ值00.500001~1.0000000.50.510.146447~0.5000010.5000010.50000120.066988~0.1464470.8535540.14644730.038061~0.0669880.9330160.06698840.024472~0.0380610.9619450.03806150.017038~0.0244720.9755300.02447260.012537~0.0170380.9829720.01703870.009608~0.0125370.9874760.01253780.007597~0.0096080.9904020.00960890.006156~0.0075970.9924180.007597…………由右下图可见，算法仅在若干离散点处的成功概率为1，并且随着λ的增大，成功概率迅速下降,直至失败。不同迭代步数下的最小成功概率及对应的λ值如左下图，可知，当迭代步数从十进一步减小(λ0.005)时，算法的最小成功概率迅速下降；当λ=0.5时，最小成功概率降低到0.5，当迭代步数等于0时，算法失效。因此当λ较大时，算法成功率迅速下降正是Grover算法存在的主要问题。成功概率标记态数与状态总数比值M/N1010120151050上半部分是最小成功概率下半部分是最小成功概率对应的M/N迭代步数最小成功概率对应的M/N上节讲诉了Grover算法存在的问题，这个问题引起了国内外学者的广泛关注，到目前为止，围绕着如何提高Grover算法的成功概率，国内外学者进行了很多有益的探索，先后提出了多种Grover算法的改进措施。这些改进措施的基本思想，大多都是通过改变最初Grover迭代中的相移来构造新的迭代算子，以提高算法的成功概率。有关国内外的研究情况，可以参阅教材30~32页，下面我们来讲诉基于π/2的相位旋转的改进算法。2.1基于π/2的相位旋转的改进算法我们认为基本Grover算法存在问题的主要原因在于：Grover算法的两次相位旋转大小相同，都等于π。显然，这样的相位旋转的结果是：调用一次Grover算法迭代，使系统状态的相位增加弧度，且最初的|φ需要旋转才能进入|β状态。随着λ的增加，当其较大时，仅有极少数的取值才满足近似为整数，因而导致了成功概率的下降。为此，首先将其搜索过程中的两次相位旋转由固定值π推广为任意值，然后通过搜索两次相位旋转大小与获得正确结果概率之间的关系，来确定新的相位匹配条件。沿着这样的一种思路，根据推导结果，我们提出新的相位匹配条件：让两次相位旋转大小相等（都等于π/2），而方向相反。arcsin2arccos)arcsin2/(arccosR为将两次相位旋转由固定值π推广为任意值，不妨把Grover算法的两个相移算子写成外积形式，即进一步，通过将以上两式中的“2”改写成“”，而第二式的“-1”改写成“”，上面两式可推广为其中当α=β=π时，下面两式和上面两式等效。IVIUmMmm||2||21)1(ieieIeeVeIUiimMmmi||)1(||)1(1----（a）根据量子力学的基本假设：一个封闭的量子系统的演化由一个酋变换来刻画。下面来证明（a）中两式的酋性。定理1：由（a）定义的算子都是酋算子。证明：的第二式也是酋算子所以其共轭转置为。）中的第一式是酋算子因此，（其共轭转置为)(||)1(||)1(||)1)(1(||)1(|,|)1(a||)1)(1(||)e2(-||)1(|,|)1(1-1-i1-1aIIeeeeeeeeVVIeeVeVIeeeIUUeIUeIUiiiiiiiiiiimMmmiimMmmimMmmimMmmi定理2：当λ1/3时，取α=-β=π/2，只需一次搜索，可使搜索的成功概率。证明：设为M个要搜索的目标量子态，，则系统初始态可表示为27/25~PM|,...,|,|21}|,...,|,{|21M]|))1)(((|))(([1|)||)1((||||1||)(|)||(1|)()(^^~^kiiijiiiiijkijkKMeeeMNjMNeeeMNNIeeVkNejNUakjN中两式对其酋变换，应用对于上式方括号中的第一项、第二项分别为非解集和解集，也就是说，它们分别对应着。为方便起见，记第二项为，则搜索的成功概率P为将其中的N和M用λ表示，可得比较b式和有以下结论：~~sincos和iiiMeeeMNp)1)(()(2||pM）（时，上式可简化为当b-----------58-42/-)1(3)cos()1(2)cos()22()cos)(cos264(23~3222323PP2)arcsin)12(sin(RP27/25)6/5()13/1(,13/133/1)2;3/101~~~~~