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

Publication Type:
Journal Article
Dongnan Daxue Xuebao (Ziran Kexue Ban)/Journal of Southeast University (Natural Science Edition), 2017, 47 (5), pp. 866 - 872
Issue Date:
Full metadata record
Files in This Item:
© 2017, Editorial Department of Journal of Southeast University. All right reserved. 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 lower-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 show that the quantum search algorithm using scattering quantum walk can find the anomaly in O(N1/2) 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.
Please use this identifier to cite or link to this item: