完全图上结构异常的搜索算法——融入量子计算思维的经典算法探讨
发布时间：2018-11-13 13:17
【摘要】：采用量子计算思维探索新的图结构搜索方法,提出了一种基于散射量子行走的完全图上结构异常的搜索算法.在N个顶点的完全图上外接一个悬挂点,既破坏了完全图的对称性,也预示着图的拓扑结构将发生变化.首先给出完全图上散射量子行走酉算子U的解析刻画,将行走的Hilbert空间投影到低维不变子空间S,并给出酉算子U在空间S中的作用US的形式;然后将完全图中所有状态的均匀叠加态选择为行走的初态,借用微扰理论求出酉算子US的本征值和特征向量,通过数学解析计算出行走的终态(悬挂点);最后分析算法的时间复杂度和成功概率.算法分析及Matlab仿真结果表明,利用散射量子行走可以在O(N~(1/2))步内以接近于1的概率找到异常位置,而经典算法中使用邻接矩阵查找该异常点的时间复杂度为O(N),因此相对特定问题和特定的经典算法,使用散射量子行走搜索算法可以实现二次加速.
[Abstract]:In this paper, a new method of graph structure search is explored by quantum computing thinking, and an algorithm for searching structural anomalies on complete graph based on scattered quantum walk is proposed. A suspension point is attached to the complete graph of N vertices, which not only destroys the symmetry of the complete graph, but also indicates that the topological structure of the graph will change. Firstly, the analytic characterization of the scattered quantum walking unitary operator U on a complete graph is given. The traveling Hilbert space is projected to the low dimensional invariant subspace S, and the form of US of the unitary operator U acting in the space S is given. Then, the uniform superposition states of all states in the complete graph are selected as the initial states of the walk, the eigenvalues and eigenvectors of the unitary operator US are obtained by using perturbation theory, and the final states (suspending points) of the walk are calculated by mathematical analysis. Finally, the time complexity and success probability of the algorithm are analyzed. The algorithm analysis and Matlab simulation results show that the anomalous position can be found in O (N ~ (1 / 2) step with the probability of approaching 1 by using scattering quantum walk. The time complexity of using the adjacency matrix to find the outlier in the classical algorithm is O (N),. Therefore, compared with the specific problem and the specific classical algorithm, the scattering quantum walk search algorithm can be used to achieve secondary acceleration.
【作者单位】： 东南大学计算机科学与工程学院;东南大学计算机网络和信息集成教育部重点实验室;南京森林公安学院信息技术系;南京邮电大学通信与信息工程学院;
【分类号】：O157.5
[Abstract]:In this paper, a new method of graph structure search is explored by quantum computing thinking, and an algorithm for searching structural anomalies on complete graph based on scattered quantum walk is proposed. A suspension point is attached to the complete graph of N vertices, which not only destroys the symmetry of the complete graph, but also indicates that the topological structure of the graph will change. Firstly, the analytic characterization of the scattered quantum walking unitary operator U on a complete graph is given. The traveling Hilbert space is projected to the low dimensional invariant subspace S, and the form of US of the unitary operator U acting in the space S is given. Then, the uniform superposition states of all states in the complete graph are selected as the initial states of the walk, the eigenvalues and eigenvectors of the unitary operator US are obtained by using perturbation theory, and the final states (suspending points) of the walk are calculated by mathematical analysis. Finally, the time complexity and success probability of the algorithm are analyzed. The algorithm analysis and Matlab simulation results show that the anomalous position can be found in O (N ~ (1 / 2) step with the probability of approaching 1 by using scattering quantum walk. The time complexity of using the adjacency matrix to find the outlier in the classical algorithm is O (N),. Therefore, compared with the specific problem and the specific classical algorithm, the scattering quantum walk search algorithm can be used to achieve secondary acceleration.
【作者单位】： 东南大学计算机科学与工程学院;东南大学计算机网络和信息集成教育部重点实验室;南京森林公安学院信息技术系;南京邮电大学通信与信息工程学院;
【分类号】：O157.5
【相似文献】
相关期刊论文 前10条
1 王光辉;周珊;;完全图中的正常染色的路和圈(英文)[J];运筹学学报;2011年03期
2 王殿军;完全图圈分解的一种新方法[J];高校应用数学学报A辑(中文版);1993年04期
3 邓觐超,佟玉凤;有关完全图的算法及实现技术[J];烟台大学学报(自然科学与工程版);1997年03期
4 张文军;;完全图的最小6-圈覆盖和8-圈覆盖[J];山东理工大学学报(自然科学版);2008年04期
5 O赐蜢，
本文编号：2329223
本文链接：https://www.wllwen.com/kejilunwen/yysx/2329223.html
