Continuous Time Quantum Walk And It’s Applications

Quantum algorithms provides a new approach for solving classical difficult problems,and show the superiority in time complexity in many practical problems.At present,quantum al-gorithms can achieve exponential acceleration for a NP-hard problems(Shor’s algorithm),and can achieve quadratic acceleration for most problems.For example,the largest clique algo-rithm and graph isomorphism algorithm based on adiabatic evolution have achieved quadratic acceleration.How to innovatively launch more efficient quantum algorithms,as well as effi-cient classical algorithms inspired by the principle of quantum mechanics,are the basic issues of academic concern and research.Quantum algorithms based on quantum walks are currently widely used in the design of new algorithms.Quantum walks is the extension of classical ran-dom walks in quantum systems.Since quantum walks are universal quantum algorithm models,other new quantum algorithms can be constructed through quantum walking.The research in this article mainly involves quantum walks and its applications.Since the transfer characteris-tics of quantum walk are naturally related to the algebraic structure of the graphs or networks it walks on,quantum walks on graphs with specific algebraic structures can help solve different problems.For instance,quantum walks on strong regular graphs can be applied to spatial search algorithms,and quantum walks on cycle graphs can achieve perfect state transfer.However,the complexity of the graph also leads to the complex nature of the quantum walk on the graph,which makes it extremely difficult to obtain the probability of the evolution.In response to these problems,the thesis mainly focusses on the following research work:(1)On the Method of Obtaining Probability.The Hamiltonian for driving continuous time quantum walk(CTQW)is the Laplacian ma-trix or adjacency matrix of the graph,so the traditional method of obtaining the walking prob-ability is based on the eigendecomposition of matrix.Generally,the eigendecomposition of a matrix cannot be analytically solved,so for general graphs,CTQW can be obtained only by numerical calculation.Although the eigendecomposition is not suitable for most graphs,for some special types of graphs,the transmission probability of CTQW can be obtained analyti-cally,such as complete graphs,hypercube,etc.For some types of graphs,the adjacency matrix and Laplacian matrix cannot be obtained,so the eigendecomposition method cannot be used.Such graphs include strongly regular graphs,homogeneous trees,and so on.In this thesis,we adopted a method of determining the number of walks,and successfully obtained the probabil-ities of CTQW on these graphs.(2)On Perfect State Transfer of Cycle Graph.Bose proposed quantum transmission on the chain to realize quantum computing and short-distance quantum communication.Christandl further studied the XY chain(Chain or Path)to realize the perfect state transfer between the two ends of the chain.Perfect state transfer on distance regular graphs and circular graphs has also been studied by G.Coutinho,Milan and others.Perfect state transfer on the chain can be obtained by studying Jacobian matrices and orthogonal polynomials,and the perfect state transfer on distance regular graphs and circular graphs can be obtained by the approach of spectral decomposition.Cycle graph is a simple extension of the chain,but the perfect state transfer on cycle corresponds to the inverse problem of a periodic Jacobian matrix.There is no effective method for this problem as far as knowing.We found that cycle graph can be decomposed into two chains with loops at the two ends,and the study of chains can be reduced to the inverse problem of the Jacobi matrix,then give the spectral conditions of Jacobi matrix for implementing the perfect state transfer on cycle graph.(3)Multi-target spatial search based on CTQW.Grover search can provide quadratic acceleration to classic search algorithms.In Grover search,there is a transition rate between any two ground states.However,in many actual phys-ical networks,access or transmission can only take place in a physically adjacent state.This search in which only adjacent vertices have a transition rate is called a spatial search.Like Grover search,the quadratic acceleration of classic search can be achieved on many networks.These networks include strongly regular graphs,hypercube,complete graphs,etc.The spatial search on the complete graph is equal to Grover search.For many networks,the acceleration of multi-target search can even be achieved.We studied the double-target spatial search on the strongly regular graph,and gave the parameter setting for the optimal search.(4)The Algorithm for Maximum Clique Algorithm Based on CTQWThe Maximum Clique Problem is a classic NP-Complete problem(Non-deterministic Poly-nomial Complete Problem).At present,the complexity of the exact algorithm for the Maximum Clique Problem is 2~N4,where N is the problem size.Quantum algorithms for NP-complete prob-lems mainly include nested search algorithms based on Grover search and algorithms based on quantum adiabatic evolution.For CTQWs on graphs,different vertices have different trans-fer probabilities and probability amplitudes,and the intensity of the frequency components of the probability amplitude reflects to a certain extent whether the vertex belongs to the maxi-mum clique.This paper designs a maximum clique search algorithm based on CTQW.In a large number of numerical experiments,no counterexamples have been found.However,as the graph increases,the time complexity of the polynomial still requires a lot of time.(5)Research on graph isomorphism algorithm based on quantum circuitExisting studies have shown that the graph isomorphism algorithm based on CTQW cannot distinguish non-isomorphic strongly regular graphs with the same parameters.That is,CTQWs on strong regular graphs with same parameters exhibit the same transmission probability.How to use quantum algorithms to distinguish strongly regular graphs is still an open question.In the last part of the thesis,we propose a quantum algorithm which is based on quantum circuits and graph reconstruction conjecture.We first proposed the concept of statistical feature vector of the graph and the statistical feature vector of the deck of graph;then calculated the statistical feature vector of the graph or the statistical feature vector of the deck of graph through quantum circuits;finally,judged whether the given graphs are isomorphic according to whether the sta-tistical feature vectors are equal.Numerical experiments on strongly regular graphs below 64vertices have shown the reliability of the method,and numerical experiments demonstrate that the algorithm complexity of strongly regular graphs below 64 vertices is polynomial.