Research On Quantum Walking Search Algorithm Based On Graph Theory

The emergence of quantum computing and quantum algorithms has injected new impetus into social progress and technological development.As one of the important research contents of quantum algorithms,quantum walk algorithm is widely used in different fields because of its unique properties,especially in solving problems related to lattice and graph theory,such as optimization,search,classification,etc.It plays an important role.In addition,the quantum walk algorithm also plays a key role in the construction of the quantum search algorithm.Therefore,more and more scientific researchers are devoted to the related research of the quantum walk algorithm to solve the problem of low search rate,low accuracy and poor controllability in the quantum search algorithm.Therefore,this paper uses the basic theory in group theory and quantum walk algorithm to improve the existing quantum search algorithm,in order to reduce the number of iterations,improve the search rate,and enhance the controllability and search accuracy of the algorithm.The main content of the paper includes the following two parts:introducing a permutation group based on the quantum walk search algorithm,and constructing a quantum walk feedback search algorithm based on the permutation group on multi-particle rings;in SKW(Neil Shenvi,Julia Kempe and K.Birgitta Whaley)search algorithm based on the subgroup theory of group theory,established a quantum walk search algorithm with optimized multi-objective states on the hypercube.For the first part,a feedback search algorithm for quantum walks on rings based on multi-particles on permutation groups is proposed.Compared with the Grover search algorithm,the algorithm can significantly improve the search speed and enhance the maneuverability of the search algorithm.First,according to the uniqueness of the quantum walk algorithm "superposition state" that enables walkers to be at multiple nodes at the same time with a certain probability,the design introduces the quantum walk algorithm into the search algorithm,in order to reduce the number of iterations of the algorithm.Secondly,based on the quantum walking algorithm on The Cayley graph,using the unique permutation relationship between elements in the permutation group to form a closed loop,the design of the quantum search algorithm on the permutation group,and then extended to the multi-particle walking algorithm on the permutation subgroup,its purpose is to increase the search rate of the search algorithm.Thirdly,the quantum state is used to store the function values of all nodes to form a search feedback algorithm.The purpose is to make the algorithm stop automatically during the search process,reduce the unnecessary number of iterations in the search process,and increase the controllability of the algorithm.Finally,by analyzing the time complexity(the number of iterations)of the quantum walk feedback search algorithm in the form of multiple particles,it is found that the number of particles and the time complexity are nonlinearly negatively correlated;the constructed algorithm still satisfies the zero-point condition and the infimum condition,and is not affected by the quantity parameter j.In order to visualize the advantages of the algorithm,we carried out a numerical analysis of the algorithm,and the numerical results show that the time complexity(the number of iterations)of the new algorithm is equivalent to o((?)).Compared with Grover’s quantum search algorithm,the newly established search algorithm has an absolute advantage in search speed.For the second part,it mainly uses the subgroup theory of group theory to improve the SKW search algorithm,and proposes a multi-objective quantum walk search algorithm with optimized iteration times on the hypercube.The purpose is to reduce the search process.number of iterations(time-consuming)and increase the accuracy of the search for the target state.Due to the limitation that the SKW search algorithm needs to use a specific vector as the target state in the algorithm construction,the algorithm can only search for one target node in the search space.Although some scholars later proposed the multi-objective state form of the SKW search algorithm,when the number of target nodes is greater than 2,the multi-objective form of the SKW search algorithm still cannot search for more than 2 target states.In addition,the optimal number of iterations of the search algorithm also depends on the number m of target states.In previous studies,some scholars applied quantum computation and quantum algorithm to solve these problems,but these solutions needed to run more Oracle operators,which would make the operation of the algorithm complicated and tedious,and could not measure the target state with a higher probability.Therefore,in order to solve the problem of cumbersome operation and low accuracy of the algorithm,we improved the quantum walk search algorithm in the form of multi-objective state,and established a quantum walk search algorithm with the optimal number of iterations.Firstly,the Hilbert space where the search space is located is divided into multiple search subspaces to increase the component value of the projection space so as to increase the accuracy of the search algorithm.After analysis,the accuracy of the algorithm to search the target state is improved from pc=1/2-O(1/n)to pc=1-O(1/n).Secondly,we introduce the multi-particle form of the quantum walk algorithm,and use the quantum walk algorithm to search the target state in each search subspace,which reduces the running times of Oracle operator in the algorithm.Thirdly,the phase detection gate(Phase operator)is embedded in the original algorithm to make the algorithm stop iterating when the amplitude value of the target state reaches the maximum value for the first time,so as to obtain the optimal number of iterations.Finally,through time complexity analysis of the search algorithm,it is found that the number of iterations of the algorithm is tf=(π/2)(?).Compared with SKW quantum walk search algorithm,the new search algorithm has faster search speed and higher accuracy.