Discrete Quantum Random Walking Research

Quantum computing is a new computing mode.It shows that the calculation abil-ity is more efficient than the calssical calculation when solving the computing problems such as quality factor decomposition.Therefore,it attracts a wide attention.With the further study of quantum computing in recent years,researchers have made many im-portant advances in quantum random walk,solutions of linear equations and so on.Quantum random walk,as a natural extension of random walk in quantum field,pro-vides a new research idea for people to discover more and better quantum algorithms.This article will introduce the content of quantum random walk.In this paper,firstly,some basic concepts of quantum mechanics and Grover algo-rithm are introduced,and an application example of Grover algorithm is given.Then we will introduce the two models of quantum random walk,namely,coin quantum random walk and scattering quantum random walk.By comparing the quantum random walk of the H coin on the line and the classical one-dimensional random walk,which can show that the quantum random walk has the potential of accelerating the algorithm.In addition,the first quantum random walk algorithm named skw algorithm is introduced.Although the time complexity of this algorithm is the same as the Grover algorithm,but it can easy to realize for its low function space dimension.Finally,we will introduce important application of the quantum random walk,which is one of the best algorithm on finding trangle questions.This algorithm combines the ideas of quantum random walk on the Johnson graph and combination to reduce the algorithm complexity.What is more,we will present a new proof of an important lemma.