Search algorithm of abnormal structure on complete graph: Discussion of classical algorithm merged into the quantum computing thinking
- Publication Type:
- Journal Article
- Citation:
- Dongnan Daxue Xuebao (Ziran Kexue Ban)/Journal of Southeast University (Natural Science Edition), 2017, 47 (5), pp. 866 - 872
- Issue Date:
- 2017-09-20
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| 完全图上结构异常的搜索算法——融入量子计算思维的经典算法探讨.pdf | Published Version | 616.91 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
© 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 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(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: