Research On Quantum Search Algorithm

In the 90s of the last century, bringing in some properties of the quantum mechanics, some new quantum algorithms that have powerful computing capabilities have been proposed, Grover algorithm and Shor algorithm are most famous of them. The two algorithms fully demonstrate that quantum computers overstep classical computers on the computing capabilities, therefore people begin to pay attention to the quantum algorithms. Among them quantum search algorithms have a broad application prospect, Grover algorithm is one of them.This paper firstly introduces the basics of quantum computation, and then discusses the research contents related to quantum search algorithms. Among them describes Grover algorithm and makes analysis of it, pointing out the main problems of it. Then the introduction of the quantum random walks and quantum walk search algorithm and SKW algorithm is discussed in detail.Then based on the phase matching condition of the Grover algorithm, the paper proposes a new quantum walk search algorithm. Firstly gives the graph to the quantum walk, and then describes the algorithm. Algorithm uses different coin operators and shift operators for two different cases, and draws the corresponding iteration operators. Then proves iteration operators used in the algorithm are unitary operators. Then makes analysis of time complexity and probability of success of the algorithm. Analysis indicates that the time complexity of the algorithm is the same as Grover algorithm, however when the targets to be searched are more than total’s 1/3,the algorithm’s probability of success is greater than Grover algorithm. At last gives the circuit implementation of the algorithm.