完全图上结构异常的搜索算法——融入量子计算思维的经典算法探讨  

Search algorithm of abnormal structure on complete graph:Discussion of classical algorithm merged into the quantum computing thinking

作　　者：陈汉武[1,2] 李文骞[1,3] 刘志昊 赵生妹[4] 

机构地区：[1]东南大学计算机科学与工程学院,南京211189 [2]东南大学计算机网络和信息集成教育部重点实验室,南京211189 [3]南京森林公安学院信息技术系,南京210023 [4]南京邮电大学通信与信息工程学院,南京210003

出　　处：《东南大学学报（自然科学版）》2017年第5期866-872,共7页Journal of Southeast University：Natural Science Edition

摘　　要：采用量子计算思维探索新的图结构搜索方法,提出了一种基于散射量子行走的完全图上结构异常的搜索算法.在N个顶点的完全图上外接一个悬挂点,既破坏了完全图的对称性,也预示着图的拓扑结构将发生变化.首先给出完全图上散射量子行走酉算子U的解析刻画,将行走的Hilbert空间投影到低维不变子空间S,并给出酉算子U在空间S中的作用US的形式;然后将完全图中所有状态的均匀叠加态选择为行走的初态,借用微扰理论求出酉算子US的本征值和特征向量,通过数学解析计算出行走的终态(悬挂点);最后分析算法的时间复杂度和成功概率.算法分析及Matlab仿真结果表明,利用散射量子行走可以在O(N^(1/2))步内以接近于1的概率找到异常位置,而经典算法中使用邻接矩阵查找该异常点的时间复杂度为O(N),因此相对特定问题和特定的经典算法,使用散射量子行走搜索算法可以实现二次加速.Quantum computing thinking is used to explore newsearch methods for graph structures.A search algorithm for structural anomalies on complete graphs based on scattering quantum walk is proposed. Adding a pendant vertex to a complete graph,in which the number of vertices is N,breaks the symmetry of the complete graph and indicates the change of the topology of the complete graph. First,the precise definition of the evolutionary unitary operator U of scattering quantum walk in the complete graph is presented. The Hilbert space in which the walk occurs is projected to a low-er-dimensional invariant subspace S,and the action of the evolutionary operator in the subspace USis given. Then,the equal superposition of all the basis states in the complete graph is chosen as the initial state. The eigenvalues and the eigenstates of USis calculated by using the perturbation theory,and the final state（ pendants） of the algorithm is solved. Finally,the time complexity and the success probability of the algorithm are analyzed. The algorithm analysis and the Matlab simulation results showthat the quantum search algorithm using scattering quantum walk can find the anomaly in O（√N） steps with the probability near to 1. However,the time complexity of the classical algorithm for searching the anomaly by the adjacency list is O（ N）. Therefore,the search algorithm based on scattering quantum walk can provide a quadric speed up over the classical algorithm for this specific problem.

关 键 词：散射量子行走 完全图 结构异常 不变子空间 微扰理论 

分 类 号：TP387[自动化与计算机技术—计算机系统结构]