量子搜寻算法

《量子搜寻算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、量子随机行走与量子随机行走搜索算法专业：物理学姓名：边志浩学号：131555摘要：量子计算与量子信息的研究可以追溯到几十年前,但真正引起广泛关注是在20世纪90年代中期。这期间发现了Shor快速因子分解算法和Grover搜索算法,这两类算法展示了量子计算机从根本上超越经典计算机的计算能力。近年来,量子随机行走正逐渐开始引起人们重视,这是因为一方面,量子随机行走可以看作是经典随机行走在量子系统上的一种自然推广,另一方面,量子随机行走能够应用于构造有效的量子算法。关键字：量子计算，量子搜寻算法，量子随机行走前言量子计

2、算机从速度上对经典计算机有本质的超越,许多在经典计算机中无法“有效”解决的问题在量子计算机下能得到有效解决。这里的“有效”、“非有效”是根据算法复杂性理论从数学上精确定义的。粗略的说,有效算法解决问题需要的时间是问题规模的多项式;相反,非有效算法需要超多项式(典型情况是指数)时间。1985年,DavidDeutsch提出了一个量子算法,用来说明量子计算机确实可能从计算能力上超过那些经典计算机。随后十年内许多人努力改进Deutsch令人瞩目的初步结果,这些努力到1994年PeterShor展示两个极其重要的问题——

3、寻找质数因子问题和解决所谓离散对数问题——可以用量子计算机有效解决时达到顶点。这方面研究受到广泛关注的原因是人们仍相信这两个问题在经典计算机上没有有效解法。Shor的结果是量子计算机比Turing机,甚至概率Turing机更为强大的有力证据。量子计算机功能强大的进一步的证据出现在1996年,LovGrover证明另一个重要问题——在没有结构的搜索空间上进行搜索的问题——在量子计算机上可以被加速。虽然Grover搜索算法没有达到Shor算法那样明显的加速,但搜索方法的广泛适用性引起人们对Grover搜索算法相当的关

4、注。量子随机行走算法是近几年来开始为人们所注意的另一种量子算法。由于经典随机行走在许多计算问题中都有应用,人们希望能够将它应用到量子计算机上。本文首先介绍了经典的随即行走和量子随即行走，通过比较几率分布得出了两者发散速度的不同，然后基于量子随机行走的发散速度快，我们提出了一种搜寻算法，即量子随机行走搜索算法,它与Grover搜索算法有着相同的搜索速度。有助于进一步了解量子随机行走搜索算法与Grover搜索算法之间的区别和差异,并对量子搜索算法的实际应用有一定的理论指导意义。一、经典随机行走经典随机行走是量子随机行

5、走的基础，它可以用图G(V,E)来表示,其中V是顶点集,E是边集。每一条边可以用它所连接的点表示,即e=(vi,v07)。当(vi,v0)E且(v0,vi)E时,我们说这个图是无向的。经典随机行走的一个重要参量是(独立于时间的)变换矩阵M,矩阵元Mij表示从顶点vi到顶点vj的跃迁几率。只有当一对顶点通过一条边连通时这个几率不为0,即Mij0iffe=(vi,vj)E(1)若M的非零矩阵元可以表示为Mij=1/d，则称这个行走是无偏的,其中di是顶点vi的度(即与顶点vi关联的边的数目)。若图上所有顶点都有相同的

6、度(d),则称这个图是正则的。在某一时刻t,经典随机行走的状态由各顶点viV的几率分布P(v,t)描述。这个几率分布在每次变换矩阵M作用后都会发生相应的变化,P(v,t)=MtP(v,0)(2)若G是连通的,即任意两个顶点通过一系列边都相互连接,则行走将趋于稳定分布,且这个分布不依赖于初态P(v,0)。若G是正则的,则每个顶点的稳定分布是均衡的。随机行走稳定分布的收敛性质可以通过混合时间(mixingtime)来描述,其定义如下,MC=min{T

7、t>T:‖P(v,t)-‖tV<}(3)它表示某个分布达到与稳定分

8、布只差任意小距离所需要的时间。这里我们用总偏差距离作为距离测度,即‖p1-p2‖tV=(4)还有一些量也可以用来描述经典随机行走的收敛性质,例如命中时间(hittingtime),即一对顶点(v0,v1),从v0出发第一次到达v1所经历的时间。这些量决定着许多基于经典随机行走的算法的行为特性。经典随机行走是理论计算科学的基础之一,作为算法工具,它在许多计算问题中都有应用,例如,可以应用随机行走来解决S-T连通性问题。这是一个经典计算科学问题,假设有无向图G(V,E),点集V的大小为

9、V

10、,研究两个顶点s和t是否连

11、通。标准的图形搜索算法需要搜遍所有的顶点,所需的时间与边数呈线性关系。但当计算机内存有限无法搜遍所有顶点时,可以用随机行走来解决这个问题。由顶点s出发,每一步计算机以相等的概率选择一条边行走到下一个顶点,若最终走到t,则s与t连通,若在T=

12、V

13、3步后未能到达t,则计算机认为s与t不连通。对于一个点集大小为

14、V

15、的图形,由于从图上任意点出发在

16、V

17、3步内到达图上任意点的几