东南大学学报（自然科学版）2017，Vol.47Issue(5)：866-872,7.DOI:10.3969/j.issn.1001-0505.2017.05.005
完全图上结构异常的搜索算法——融入量子计算思维的经典算法探讨
Search algorithm of abnormal structure on complete graph: Discussion of classical algorithm merged into the quantum computing thinking
陈汉武 1李文骞 2刘志昊 1赵生妹3
作者信息
- 1. 东南大学计算机科学与工程学院,南京211189
- 2. 东南大学计算机网络和信息集成教育部重点实验室,南京211189
- 3. 南京森林公安学院信息技术系,南京210023
- 折叠
摘要
Abstract
Quantum computing thinking is used to explore new search 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 Us is 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 Us is 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 show that 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.关键词
散射量子行走/完全图/结构异常/不变子空间/微扰理论Key words
scattering quantum walk/complete graph/structural anomalies/invariant subspace/perturbation theory分类
信息技术与安全科学引用本文复制引用
陈汉武,李文骞,刘志昊,赵生妹..完全图上结构异常的搜索算法——融入量子计算思维的经典算法探讨[J].东南大学学报（自然科学版）,2017,47(5):866-872,7.
