基于绝热演化的量子搜索算法研究

来源 :华中科技大学 | 被引量 : 0次 | 上传用户:milin1215
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
基于传统量子线路模型的Shor大整数因子分解算法、Grover无序数据库量子搜索算法以及求解线性方程组的量子算法等均展现出量子计算机的强大计算能力。然而,事实证明设计量子的算法是一个极具挑战性的难题。2000年左右,一种崭新的量子计算模型被提出来—绝热量子计算模型。其基于量子物理中的绝热定理,属于连续时间演化模型,该方案的主要思想可以概括为:让量子系统处于一个容易制备初始状态,将所求问题的解编码对应至系统的末态,让整个量子系统封闭地按照预先选定的某一个路径进行绝热演化,这样经过适当的时间之后,测量系统的末态将以很大的概率得到所要求问题的解。其中的演化时间便由绝热定理来估计。经研究发现,最初的绝热模型用来实现Grover搜索时相对于经典搜索算法并没有优势而言。针对这一问题,一种称为局部绝热的量子搜索算法被提出来,其性能与Grover算法相当。最近,一种介于这两种算法之间称为部分绝热算法的框架由Tulsi提出,一方而其继承了全局绝热算法的与生俱来的抵抗量子噪声的能力,但同时其仍可提供二次加速的功能。基于部分绝热演化的量子搜索算法已经被设计出来并进行了初步的研究。由于绝热搜索算法的演化路径是算法性能的核心要素之,这里首先就两类非线性路径以一类特殊的搜索问题为例进行了研究,即当需查找的元素与量子系统的初态正交时,具有一般化形式的非线性路径会失效—时间复杂度为无穷大,并不可以暂时增加量子系统能量而带来时间复杂度的降低;具有驱动哈密顿量形式的非线性路径仍然能以一种物理上实现时相应复杂度的增加而保证其常数量级的时间复杂度的优势。但同时这里研究发现,以保持系统在整个演化过程中能量为零、形式上可认为是增加了驱动哈密顿量的非线性路径一种变体的绝热路径导入的绝热算法,在解决同一搜索问题时时问复杂度仍然为无穷大。这些研究表明非线性演化路径的优越性与局限性。其次,文中对量子搜索问题进行了抽象,得出一种能在全局绝热演化框架下仍能提供二次加速功效的新系统哈密顿量,并将之推广到可以提供任意时间复杂度功能的哈密顿量,分析了在绝热演化过程中伴随系统的能量变化方式,并与非线性绝热演化以及局部绝热演化方式进行了比较,给出伴随此演化过程能量变化的物理机理。局部绝热演化运用至同一问题时,很明显可以得到二次加速的效果。对这一抽象搜索问题,文中研究发现在部分地Tulsi给出的原先部分绝热演化系统哈密顿量需满足的条件这一前提下,仍然可以运用部分绝热算法而得到二次加速功效,并得到此时系统哈密顿量满足新条件。接着,对可将全局以及局部绝热算法看成部分搜索算法特例的这一结论进行明确化,提出具体的实现方法,并给出相应做法的依据。同时,这里引入了一种部分绝热算法的变体—基于部分演化的局部绝热演化算法,但发现该算法并不能较局部或者部分绝热算法再次提供加速,相反,它们恰具有相同的时间复杂度,从而亦间接表明此算法性能的最优。同时,文中给出对这一算法的两种等价观点。针对有关文献给出部分绝热搜索算法时间复杂度的一个错误,文中进行了修正,即研究发现:当无序数据库中的元素数日M大于1时,部分绝热搜索量子算法并不能相对局部绝热演化提供D((?))加速功能,并且文中证明了部分绝热搜索算法在M≥1时算法性能的最优性。再次,文中详细讨论如何将绝热算法转化为线路模型下对应的量子算法,这里研究了常见的绝热搜索算法在量子线路下的实现—全局绝热、局部绝热、部分绝热以及由此衍生的基于部分绝热的局部演化算法。研究表明,所有这些算法的时间复杂度与线路模型下所得到的时间分片数是一致的。最后,文中给出了绝热计算的若干应用,包括预知元素先验概率分布的绝热量子搜索、将绝热计算用于制备简易量子纠缠态以及在绝热计算框架下实现量子线路模型下的常用量子门。
其他文献
政治因素增加了中国企业海外并购跨国并购的风险。论文从三个方面分析了中国企业海外并购所面临的政治因素的干扰,并提出了化解的建议。
自21世纪以来,我国社会的生产力水平不断提升,其大大促进了经济的发展,是我国迅速成为世界经济大国,与此同时,人们对企业竞争的核心——人力资源的重视程度不断加深。人力资源是企
随着信息技术的不断发展,企业改革也不断深入,企业档案管理作为企业基础管理的重要内容,正面临着巨大的挑战。如何在新形势下进行科学合理的企业档案管理,使企业档案管理能够更为
文章先对无线传感器网络定位技术当前的概况进行介绍,又重点介绍了国内外对该技术的应用现状,从而在各个领域全方位的对无线传感器网络定位技术的应用进行研究。
本设备主要于油压机配合使用,用于从油压机内部取出加工完成的工件。为与油压机的动作配合,建立了与油压机的信号通讯,本设备主要由横行运动单元、上下行运动单元、吸盘组件
一概述: 本設計系××工程中对給水所供电的专用变电所。由电厂以35kv单回路榆电线向各变电所供电,輸电綫全长38km,沿綫共有七个变电所。各变电所采用了越級降压,直接由35kv
回 回 产卜爹仇贱回——回 日E回。”。回祖 一回“。回干 肉果幻中 N_。NH lP7-ewwe--一”$ MN。W;- __._——————》 砧叫]们羽 制作:陈恬’#陈川个美食 Back to yield
期刊
根据复合材料与工程专业发展要求,从《高分子物理》课程自身特点出发,对教学内容、教学方法和考核方式进行了探索和改革。结果表明,改革和创新对提高学生的积极性、参与度和
冬季,在寒冷的北方,老人都得在浴室内洗澡,但有的老人在浴室内洗澡时,往往会感到头晕、气急、胸闷、心跳加快,甚至有的老人为此而晕倒。这是什么原因呢?人的血液循环系统,有
【正】 “史学归约”是现代历史哲学的一个术语,特指从历史研究中得出的一般知识(知识性史学归约)和提出的具有普遍性或声称具有普遍性的概念、观点、原理(理论性史学归约)。