摘要：完全图KN上某个顶点连接到图G将破坏其对称性.为加速定位这类结构异常,基于散射量子行走模型设计搜索算法,首先给出了算法酉算子的定义,在此基础上利用完全图的对称性,将算法的搜索空间限定为一个低维的坍缩图空间.以G为一个顶点的情况为例,利用硬币量子行走模型上的研究结论简化了坍缩图空间中酉算子的计算,并借助矩阵扰动理论分析算法演化过程.针对星图SN上结构异常的研究表明,以星图中心节点为界将整个图分为左右两个部分,当且仅当两部分在N→∞时具有相同的特征值,搜索算法可以获得量子加速.本文说明星图上的分析方法和结论可以推广至完全图的坍缩图上.基于此,本文证明无论完全图连接的图G结构如何,搜索算法均可在O（√N）时间内定位到目标顶点,成功概率为1-O（1/√N）,即量子行走搜索该类异常与经典搜索相比有二次加速.

关键词：散射量子行走 量子搜索 完全图 

单位：东南大学计算机科学与工程学院 南京210096