Research On Search Algorithms Based On Discrete-time Quantum Walk Model

Classical random walk is a powerful mathematical tool to design random algorithms,and provides the best-known algorithms for factorization,k-SAT and graph automorphism problems.Search algorithms based on quantum walk have recently become an active and interesting research area of quantum computation because some properties of quantum walk outperform their classical counterparts.One of the core problems is to determine the type of graph on which the search algorithms can acquire quantum speedup.The characteristic spectrum of the evolutionary operator must be obtained to determine the evolution process of the algorithm and to analyze the performance of quantum iterative search algorithms.The Grover diffusion operation is adopted among the early fast quantum search algorithms.If the graph on which the walk takes place satisfies certain properties,such as symmetry and regularity,then the search space can be constrained within a small subspace that corresponds to the quotient graph.The two main analysis tools for search algorithms based on discrete-time quantum walk are the search algorithm and operator perturbation theory.This thesis explored the following aspects:(1)The calculation of the quantum walk evolution operator on quotient graphs,which consists of shift operator and coin operator,is an important step in analyzing search algorithms.A method is presented to construct the matrix of the Grover coin operator on the quotient graph of hypercube and provides a proof of its correctness.The unitary evolution operator of quantum walks with the Grover coin operator can be determined because the shift operator on quotient graph can be derived in a straightforward manner from the shift operator on the original graph.The form of the coin operator on the quotient graph of a hypercube can be generalized to other graphs,such as complete grahs,strongly regular graphs,etc.(2)A complete graph with a second graph attached to one of its vertices is referred to as external structural anomaly.The structural change within a complete graph is called internal structural anomaly.Search of structural anomalies in complete graph KN is investigated using scattering quantum walks.Taking advantage of the obvious symmetries in complete graphs,the search space is confined to a low dimensional collapsed space.Using matrix perturbation theory,a general proof is given to show the vertex that G is attached to can be found in O((?))time steps,as long as the connectivity between G and KN is far less than N.Two kinds of internal structural anomalies,complete graph with a missing edge or an extra loop,can be solved in a similar way as external anomalies,and again,in O((?))time steps.(3)Search algorithms based on scattering quantum walks are designed to investigate the influence of the symmetry of graphs to the performance of the algorithms.Although strongly regular graphs are proved to be asymmetric for large N,local symmetry allows us to constrain the search algorithms in a small subspace corresponding to the collapse graph.Search on known families of strongly regular graphs(SRGs)with parameters(N,k,?,?)is considered in the language of scattering quantum walk.The search space is confined to a low-dimensional subspace that corresponds to the collapsed SRGs.The fundamental pairing theorem is used to quantify the search algorithm on the SRGs with k scales as N.However,the search on the SRGs with k scales as(?)cannot be quantified.Thus,and matrix perturbation theory is used to provide an analysis.Both cases can be solved in O((?))time steps with success probability close to 1.(4)The success of search on a structurally changed complete graph and a strongly regular graph demonstrate that the regularity and global symmetry are not necessary conditions for fast quantum search.These examples in turn show that the formalism on star graphs can be applied generally.