绝热量子搜索算法分析与优化研究

发布时间：2020-04-22 01:27

【摘要】：绝热量子计算是一种基于绝热定理的全新量子计算模型,与量子线路模型相比,具有操控相对比较简单、天然抗噪声的优点,并且已被证明与线路模型等价,是未来通用量子计算的备选方案之一。而密钥搜索则是密码学最基本的攻击手段之一,因此,利用绝热计算模型的优点开展绝热量子搜索算法的研究,意义重大。本文针对绝热量子搜索算法,从算法分析、算法加速、量子资源三个方面进行了系统的研究,主要研究成果如下:一、在算法分析方面,研究了局域绝热量子搜索算法中成功率与演化时间的定量关系,为绝热量子搜索算法实现时演化时间的选择提供指导。局域绝热量子搜索算法中成功率与演化时间的定量关系研究。在实际演化过程中,绝热算法必须在有限时间内运行完毕,从而可能发生能级跃迁,如何求局域绝热量子搜索算法的成功率?目前没有解析的解,而成功率与演化时间的定量关系可以为算法实现时最优演化时间的选择提供指导。我们在等价的二能级系统中分析绝热量子搜索算法的量子动力学,通过简化含时薛定谔方程,得出了求解成功率的微分方程组;利用这个微分方程组,数值地给出了局域绝热量子搜索算法中成功率与演化时间的解析表达式,该表达式给出了成功率增速变缓的临界时间点并间接验证了局域绝热搜索算法最优的时间复杂度为O(N~（1/2）)。在密钥搜索问题中,当给定成功率时,可以依据我们给出的表达式精确的控制最优演化时间。二、在算法加速方面,分别从绝热捷径技术和绝热量子搜索算法一般化两个方向,克服绝热量子搜索算法要求系统缓慢演化的的弱点,并从能量的角度定量分析了算法取得加速的代价。1、局域绝热量子搜索算法中的无跃迁量子驱动研究。局域绝热量子搜索算法的时间复杂度已经为O(N~（1/2）),而无跃迁量子驱动可以通过抑制原系统的能级跃迁来加速演化过程,两者相结合会不会得到更优量级的时间复杂度?我们将无跃迁量子驱动方法应用于局域绝热量子搜索算法,给出了局域绝热量子搜索算法中应添加的驱动哈密顿量,理论上证明了在系统能量可以任意大的前提下,当添加无跃迁量子驱动时,对于任意长的演化时间,算法成功率都可以为1;我们对加速原因和实现难度进行了分析,指出算法获得加速的原因是添加驱动项后算法基态与第一激发态之间的瞬时能隙在演化过程中增大到了O(N~（1/2）)的规模,在实际中,系统能量不可能任意大,所以算法的演化时间不能任意小,但是无跃迁量子驱动仍然对算法有很好的加速作用并在离子阱系统上得到了演示验证。2、绝热量子搜索算法一般化及其加速研究。一般化绝热量子搜索算法的演化可以是非绝热的并且可以选择任意的插值函数,判断算法是否有效的依据是末了时刻算法的成功率是否符合要求,但是在一般化的绝热搜索算法中,成功率难以解析给出。我们利用无跃迁量子驱动来构造具有解析成功率的一般化绝热量子搜索算法,给出了更一般的驱动哈密顿量形式;求出成功率的解析表达式并给出了一个确保成功率为1的充分条件,在能量可以任意大的前提下,当插值函数满足这个条件时,算法可以在任意演化时间下成功率为1,对于不满足条件的插值函数,也可以根据成功率公式选择更优的参数。该工作将无跃迁驱动的应用拓展到了一般化的绝热搜索算法,事实上,对于现有基于哈密顿量演化的量子搜索算法,都可以用给出的方法进行加速。3、绝热量子搜索算法中时间与能量的定量关系研究。目前,绝热量子搜索算法的复杂度一般是指算法的演化时间,而Das算法和绝热捷径都能以常数的演化时间完成搜索,其代价是要在演化过程中增加能量,因此,在绝热量子搜索算法中,衡量算法的复杂度必须综合考虑时间和能量。我们提出了绝热量子搜索算法中定量刻画能量复杂度的方法;在给出的方法下,计算出了不同绝热量子搜索算法的能量复杂度并证明综合考虑时间复杂度和能量复杂度时,绝热量子搜索算法的复杂度至少为O(N~（1/2）)量级;此外,定量分析了Das算法中时间和能量的关系,在实验允许的前提下,可以根据时间和能量的定量关系选择参数使得演化时间最短。值得一提的是,本文提出的能量复杂度刻画方法也适用于其它的绝热算法。三、在量子资源方面,研究了相干在绝热量子搜索算法中的作用,定量分析了相干对算法成功率和算法效率的影响。绝热量子搜索算法中相干的作用研究。研究相干在量子算法中的作用对分析量子加速的原理具有重要意义,我们利用相干的联合熵量化方法系统地分析了相干在绝热量子搜索算法中的作用。在理想和非理想情况下,定量的分析了相干随着时间的变化并给出了相干与成功率的解析关系式;对比研究了全局绝热量子搜索算法、局域绝热量子搜索算法、Das算法中相干的变化,指出要想实现常数演化时间的搜索,系统的相干必须指数的减少;更重要的是,以绝热捷径为例说明了可以通过合适的方法加快系统相干的消耗来提高绝热量子搜索算法的效率,这一思想可以推广到其它的绝热算法,为提升绝热算法的效率找到了一个新的方向。
【图文】：

摩尔定律,量子效应,计算方式,量子计算

第 1 页图 1.1 单个芯片中晶体管数目增长趋势遵循摩尔定律子计算是一种基于量子效应的新型计算方式[1]，其基本原理是：以量子比特和存储的基本单元，通过大量量子比特的受控演化来完成计算任务。相比经子计算机在信息编码载体、逻辑运算基础和运行方式上都发生了颠覆性的改变曼首次提出了量子计算机的概念[2]，1985 年，Deutsch 基于经典图灵机模型灵机模型[3]。1992 年，Deutsch 和 Josza 一起提出了 Deutsch-Josza 算法[4]，在

动力学演化,演化路径,路径,局域

1arctan 1 2 1 arctan 12 1Nt N s NN arctan 为反正切函数。令 s 1，，得到1arctan 11NT NN arctan 11NN ，演化就是绝热的并且成功率大于等于21- 。演化时间T 的关系，包括1arctan 11NT NN ，所以我们 tan 2 / 1 arctan 1 12 1t T N Ns tN 后我们称之为局域演化路径。显然，它满足边界条件：当 t 当 t T时， s 1且 pH s H。局域演化路径与全局演化路径
【学位授予单位】：战略支援部队信息工程大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：O413;TP301.6

【相似文献】