改进的量子搜索算法在grove算法中的应用

改进的量子搜索算法在grove算法中的应用

0经典算法的应用自20世纪90年代提出以来，该算法迅速发表，解决了许多困难的算法。从计算复杂性理论到通信保密技术，从基础研究到日常生活的经济和人民生活，它具有广阔的应用前景。费曼1权益的概率在量子系统中,每一个n位量子比特表示的量子态|ψ〉都可以看作是2|ψ〉可以由2其中,c将基态分为两个部分———目标态|α〉和非目标态|β〉:其中,N=2则:则|ψ〉可以写成:如图1所示,Grover的两个反射把|ψ〉变换成:每次Grover迭代就相当于增加2θ,从而测得β〉的概率增加。K次迭代后,2相位旋转改进算法到目前为止,围绕如何提高Grover算法的成功概率,国内外的学者进行了很多有益的探索,先后提出了很多改进措施,如基于π/2相位旋转改进算法,自适应相位旋的Grover算法,基于固定相位旋转的Grover算法2.1基于/2条件的个相移算子Grover算法中的两次相位旋转大小相同,都等于π。这样相位旋转的结果是:调用一次Grover迭代,使系统状态相位增加将Grover算法的两个相移算子写成外积形式,即将Grover算子作用于系统态|φ〉,整理的测量目标态的概率为当α=-β=π/2时,式(10)简化为由式(11)有如下结论:(1)当0<λ<1/3时态,改进算法的成功概率低于Grover算法成功概率。(2)当λ=1/3时,改进算法的成功概率等于Grover算法的成功概率。(3)当1/3<λ<1时,改进算法的成功概率高于基本Grover算法的成功概率。最低的成功概率为25/27。2.2基于自适应相位旋转的算法根据相关文献,Grover算法的搜索引擎可描述为旋转相位α的确定直接关系到算法的搜索效率。基于自适应相位旋转改进算法的基本思想是:α的大小根据搜索目标数M和状态总数N的比值λ=M/N来自适应确定。(1)当1/4≤λ≤1,时,存在唯一确定的α=arccos((2λ-1)/2λ),只需一次Grover迭代,搜索成功概率P=1。2.3基于改进算法的计算及搜索迭代次数埃及亚历山大大学Younes于2007年4月提出了基于固定相位的旋转的Grover算法由以上几个改进算法可知,这些改进算法的出发点都是提高原始Grover算法的成功概率。经过理论计算和模拟仿真,这些改进算法的计算量相比于Grover算法没有降低,甚至有所提高。在λ=M/N<0.001时Grover算法的搜索迭代次数仍然相当可观。如何在保证成功概率的基础上,降低Grover算法的迭代次数,是本文的出发点。3本文改进了算法分析3.1gro经营算法目前提出的各种改进算法,都是在如何进一步提高算法的搜索成功概率上进行研究探讨,很少有学者对如何进一步降低算法的计算量进行研究。Grover算法是一种用于大规模数据库搜索的算法。当数据规模很大时,Grover算法的计算量也是很大的,这时如何进一步降低算法的复杂度?本文提出了一种改进型算法,该算法能够在保证搜索成功概率93%以上,将计算量降低到约为原来算法的1/3。3.2种标态和非目标态第1步同样先应用WalshHadamard变换作用在|000…0〉上,状态初始化:将系统态分为目标态和非目标态两部分,在定义归一化状态后,非目标态为:目标态为:从而初始态|ψ〉可以表示成:第2步对|ψ〉运用Grover算子变换,记变换后的态为第3步参考U可以证明U第4步重复执行算子O,U第5步测量,经过上述迭代后,目标态的概率幅达到最大,测量时最有可能获得要搜索的目标态。当用O,U3.3基于改进算法和groper算法的迭代次数比较在量子系统中,所有的变换都必须是幺正变换。改进算法中的O算子显然是幺正算子。对于U对于本改进算法,初态|ψ〉旋转改进算法比Grover算法迭代次数节省了次。在[0,0.001]区间,改进算法和Grover算法的成功概率比较如图4所示。改进算法和Grover算法的迭代次数比较如图5所示。由以上的理论推导过程可知,改进算法在[0,0.001]区间内,在保证搜索的成功概率在0.99以上的同时,能够降低迭代的次数至约等于基本Grover算法的1/3。4基于数据库的方法利用本文改进算法和Grover算法对一个数据库(数据库大小为2由表1可知,该改进型算法在[0,0.001]区间上能明显降低计算量,且能将搜索的成功概率保持在0.93以上。5基于改进算法的groper算法仿真依照量子并行计算的优势,在遍历搜索问题中运用Grover算法可以大大减少搜索的运算次数。本文对进一步降低Grover算法进行了探索,并提出了改进算法