Research On Discrete Quantum Random Walk Search Algorithm

Quantum random walk is put forward by Aharonov in 1993. Compared with the classical random walk, quantum random walk has a faster diffusion velocity. In 2003, the first quantum random walk search algorithm, namely the SKW algorithm, theoretically proved the superiority of quantum random walk compared with the classic algorithms, and explored the new application fields of quantum random walk algorithm. In recent years, some researchers have devoted to the research of walking structure and algorithm of random walk.Finding structural anomalies in complete graph using scattering quantum walk is proposed in this paper. Adding a pendant vertex to the complete graph, in which the number of vertices is N, will broke the symmetry of the complete graph. The definition of the evolutionary operator is presented. Based on the symmetry of the complete graph, the walking space is collapsed to a lower-dimensional invariant subspace, and the action of evolutionary operator in the subspace is given. In order to analyze the evolutionary process of the search algorithm, we find the eigenvalues and eigenstates of operator using perturbation theory, and represent the initial state of the algorithm with these eigenvectors. We solve the final state of the algorithm to analyze the time complexity and success probability. Algorithm analysis and Matlab simulation results show that quantum algorithm using scattering quantum walk will succeed in 0((?)) with the probability near to 1 to find the anomaly, while the time complexity of finding the anomaly is O(N) by using an adjacency matrix in the classical algorithm. So scattering quantum walk search algorithm can provide a quadric speed up over classical algorithm.