The Research On Controlling Probability Amplitudes Of Quantum Walk-Model,Applications And Implementations

Quantum computing is a new technology which makes use of quantum mechanical phenomena to perform the computing,and it can obtain much higher computing power than classical computing.Quantum walk is an important aspect of the research of quantum computing.Because the classical counterpart of quantum walk,i.e.classical random walk,is the foundation of many classical algorithms,quantum walk is considered as an important tool to develop quantum algorithms.There are already some quantum walk based algorithms which realise significant speedup than classical algorithms.However,how to develop or optimize the quantum walk based algorithm is still a big challenge.We believe that the challenge in this field mainly causes by the lack of researches on the general and basic method to develop algorithms based on quantum walk.And we believe that finding the relation between the evolution of quantum walk and the design of quantum algorithms is an important way to solve this challenge.In our research,we found that controlling the probability amplitudes of quantum walker plays a key role in the design of quantum walk based algorithm.In this thesis,we firstly introduce a model of probability amplitudes controlling,and then classify the probability amplitudes controlling methods.Secondly,we optimize the algorithms in two applications of quantum walk which have been studied widely,and then we develop two new quantum walk based algorithms to expand the application field of the quantum walk.Finally,we research the physical implementation of the proposed method.In the final part,we proposed the scheme how to realise the probability amplitudes controlling methods,and perform the physical experiment.The main contributions of this thesis are as follows.1,We summarize the general rules in developing quantum algorithms based on quantum walk,and found that controlling the probability amplitudes of walker plays a key role in the development of quantum algorithm.Based on the finding above,we proposed the general and basic method to develop quantum walk based algorithm——probability amplitudes controlling.Through analysis,we find that the quantum walk based algorithm always encode the information from problems need to be solved into some key elements of quantum walk model which will affect the evolution of quantum walk greatly.Through this process,the quantum walk will evolve along a certain trajectory according to the condition of the problem.Then we can change the quantum walk from a physical process into a computing process.From the mathematical model of quantum walk and its physical meaning,key elements affecting the quantum walk can be summarized as the evolution operator,the initial state of quantum walk and the topology of the graph.Then we call the method which controls the probability amplitudes of walkers by these three elements as the operator controlling,initial state controlling and the topology controlling respectively.Finally,we proposed a general and basic method to develop quantum walk based algorithm based on these three probability amplitudes controlling methods.2,Based on the proposed method,we optimized the algorithms in two main application field of quantum walk.By these works,we verified that the proposed is practical and effective in optimizing quantum algorithm.In this thesis,we optimize the quantum walk based algorithm in the applications of the quantum search and the graph isomorphism,which are the most widely searched area in the quantum walk based computing.In the optimization of quantum walk search,we firstly analyze the current algorithm through the idea of probability amplitudes controlling,and based on this analysis we proposed a new topology controlling method by which we can adjust the power of self-loops on the graph.And then,by the proposed topology controlling method,we optimize the quantum walk search algorithm significantly.In the optimization of graph isomorphism algorithms,we first optimize a graph isomorphism algorithm based on continuous-time quantum walk,and then propose a new graph isomorphism algorithm base on discrete-time quantum walk.The proposed algorithm outperforms the previous algorithms both on the power to distinguish similar graphs and the computational complexity.3,Based on the proposed method,we develop two new algorithms to extend the application fields of the quantum walk.By these works,we verified that the proposed method is practical and effective in developing new quantum algorithm.In this thesis,we firstly proposed a new quantum algorithm which integrates the quantum walk search and the quantum PageRank into a single process,and we name it the SearchRank algorithm.This new algorithm has the ability to search targets from directed network and rank them at the same time,which is the first algorithm has this ability as far as we know.Secondly,we proposed a method to generate Bell state through two-particle quantum walk by operator controlling method for the first time.4,We study the physical implementation of proposed the methods,to verify the proposed method is feasible in physical implementation.In this thesis,we proposed physical implementation schemes of the topology controlling methods which have been used in the optimization of the quantum walk search and the graph isomorphism algorithm,and realise the schemes on the real physical real physical platforms.More specifically,we realise the adjustable self-loop on one-dimensional discrete-time quantum walk on the bulk platforms,and realise the self-loop on one-dimensional continuous-time quantum walk on a waveguide chip.Through the works in this thesis,we develop a general and basic method to design and optimize the quantum walk based algorithm,which will make contributions to the research on quantum computing based on quantum walk.