论文部分内容阅读
作为设计随机算法的一个有力的数学工具,经典随机行走为因式分解、k-SAT、图同构等问题提供了一系列最广为人知的算法。量子行走提供了加速经典随机行走的可能性,近年来设计基于量子行走的搜索算法成为量子计算领域的研究热点。研究的核心问题之一是搜索算法在何种图结构上的行走能实现量子加速。算法的分析是其中的难点,量子迭代算法分析的关键是求得演化算子的特征谱,从而确定算法的演化过程。早期成功的搜索算法普遍采用Grover算子作为算法的演化算子,当图满足某种性质时,如正则性、对称性,将算法的演化空间限定在坍缩图对应的子空间中加以分析。抽象搜索算法和算子扰动理论是基于离散时间量子行走搜索算法的两种主要分析手段。本文在以下方面做出了探索:(1)搜索算法在商图上的演化算子的计算是搜索算法分析的一个重要步骤。演化算子包含移位算子和硬币算子。以超立方体为例,构造出Grover硬币算子在商图上对应的矩阵形式,并给出了其正确性证明。由于商图上的移位算子可由原图上的移位算子直接导出,从而确定了使用Grover算子作为硬币的量子行走在商图上的演化算子。超立方体商图上的硬币算子形式可以推广至其他图上,如完全图、强正则图等。(2)图上结构发生改变称之为结构异常。完全图有外接图称之为外部结构异常;内部结构发生改变成为内部结构异常。基于散射量子行走设计搜索算法定位完全图上的结构异常。利用完全图的对称性,将算法的搜索空间限定在一个低维的坍缩图空间。利用算子扰动理论证明只要完全图和外接图的连接度足够小,则完全图外接任意图均可以在O((?))时间步内解决。用类似的方法证明完全图缺失边和有多余自环边时搜索算法也有二次加速。(3)基于散射量子行走设计强正则图上的搜索算法研究图的对称性对搜索算法性能的影响。对于较大的N强正则图不具有全局对称性,但可以利用局部对称性将搜索空间限制在对应坍缩图的低维子空间中。当k与N同阶时,利用Cottrell提出的基本配对定理量化算法的性能;当k与(?)同阶时不满足该定理,使用算子扰动理论分析。结果表明,在两类强正则图上的搜索算法均可在O((?))时间步内以接近1的概率定位到目标顶点。(4)完全图上结构异常搜索和强正则图上搜索的成功说明图的正则性和全局对称性不是最优搜索的必要条件。二者的分析过程表明星图上的基本配对定理可以推广至完全图及部分强正则图的坍缩图上。