Research On Analysis And Optimization Of Adiabatic Quantum Search Algorithm

The adiabatic quantum computing is a new quantum computing model based on the adiabatic theorem.Compared with the quantum circuit model,it has the advantages of relatively simple control and natural anti-noise.Moreover,it has been proved to be equivalent to the quantum circuit model and been regard as one of the options for the future general quantum computing.The quantum search algorithm has a square acceleration on the key search problem.Therefore,it is of great significance to carry out the research on the adiabatic version of the quantum search algorithm.This paper systematically studies the adiabatic quantum search algorithm from three aspects: algorithm design and analysis,algorithm optimization and acceleration,and quantum resources.The main research results are as follows:?1?Firstly,in the aspect of algorithm design and analysis,the relationship between the success rate and the arbitrary evolution time in the local adiabatic quantum search algorithm is studied,which provides guidance for the selection of the evolution time of the adiabatic quantum search algorithm.1.Research on the relationship between success rate and evolution time in local adiabatic quantum search algorithm.When the evolution time satisfies the adiabatic condition,the success rate of the adiabatic algorithm can be guaranteed by the adiabatic theorem.When the evolution time does not satisfy the adiabatic condition,how to find the success rate of the algorithm has no analytical solution.We make full use of the structural characteristics of the adiabatic quantum search algorithm to analyze the quantum dynamics of the adiabatic quantum search algorithm in an equivalent two-level system.By greatly simplifying the time-dependent Schr?dinger equation,we obtain the differential equations for solving the success rate.Utilizineg the differential equations,we numerically gives an analytical expression of the success rate and arbitrary evolution time in the local adiabatic subsearch algorithm.In the key search problem,one can select the optimal evolution time when a success rate is given?such as 0.5?according to the expression.?2?Secondly,in terms of algorithm optimization and acceleration.Remove the limit of slowly evolution which required in adiabatic quantum search algorithm from the two directions of adiabatic shortcut technology and non-adiabatic quantum search algorithm.And the acceleration ability to the adiabatic quantum search algorithm is analyzed.1.Research on transitionless quantum driving in local adiabatic quantum search algorithm.The time complexity of the local adiabatic quantum algorithm is O(N^1/2)already,and the adiabatic shortcut can accelerate the adiabatic evolution.Will the combination of the two get better time complexity? We apply the transitionless quantum driving to the local adiabatic quantum search algorithm.The driving terms in the local adiabatic quantum search algorithm are given.The time-dependent Schr?dinger equation is solved under the eigen-picture.Theoretically,the time complexity of the adiabatic quantum search algorithm can be reduced to O?7?1?8?when adding the transitionless quantum driving terms.The numerical simulation results are consistent with the theoretical proof and the reason for accelerattion is that the ground state of the algorithm increased after adding the driver.The energy gap between the excited states is temporarily increased to the scale of O(N^1/2)during the evolution process.2.Research on non-adiabatic quantum search algorithm and its shortcut.The Hamiltonian of the non-adiabatic quantum search algorithm is similar to the adiabatic search algorithm,but its evolution may not be adiabatic and does not require the system to remain in the ground state.It only requires the algorithm success rate does not increase with the data size.That's enough for the key search problem.However,in the case of non-adiabatic evolution,it is difficult to get the success rate.We use the transition quantumless driving to construct a non-adiabatic search algorithm which has analytic success rate.Unlike the adiabatic search algorithm,even if the transitionless quantum drive is applied,the success rate of the algorithm is not always 1.We obtain an analytical expression of success rate and give a sufficient condition to ensure a success rate of 1.When the interpolation function satisfies this condition,the algorithm can have a success rate of 1 at any evolution time.In addition,for interpolation function which do not satisfy the condition,we can also select better parameters according to the success rate formula.3.Research on trade-off relationship between time and energy in adiabatic search algorithm.At present,the complexity of the adiabatic search algorithm generally refers to the evolution time of the algorithm,and both the Das algorithm and the adiabatic shortcut can complete the search with the evolution time.This is incredible for the key search problem,therefore,in the,it is unreasonable to only use the evolution time as the complexity of adiabatic search algorithm.We propose the concept of energy complexity in adiabatic algorithm and give a method to quantitatively describe the difficulty of Hamiltonian evolution based on norm,and use it as the energy complexity in the adiabatic search algorithm.We calculate the energy complexity of different adiabatic search algorithms,the results indicate that the complexity of the adiabatic search algorithm is at least be O(N^1/2)when considering both the time complexity and energy complexity.In addition,the trade-off relationship between time and energy in the Das algorithm is analyzed.It can provide guidance on how to choose parameters to optimize the evolution time when the experimental conditions are given.It is worth mentioning that the energy complexity characterization method proposed in this paper is also applicable to other adiabatic algorithms.?3?Thirdly,in the aspect of quantum resources,the role of coherence in the adiabatic quantum search algorithm is studied,and the influence of quantum resources on algorithm success rate and algorithm efficiency is analyzed.1.The role of coherence in adiabatic search algorithms.Quantum coherence,as the underlying principle of quantum interference and multi-body entanglement,plays a central role in quantum information science.Studying the role of coherence in quantum algorithms is of great significance for analyzing the principle of quantum acceleration.We use the coherent joint entropy quantization method to systematically analyze the role of coherence in adiabatic search algorithms.In the ideal and non-ideal cases,the coherence versus time is analyzed quantitatively and the analytical relationship between coherence and success rate is given.The global adiabatic search algorithm,local adiabatic search algorithm and Das algorithm are compared.In order to achieve a constant evolution time search,the coherence of the system must be reduced by the exponent.More importantly,the adiabatic shortcut is used as an example to illustrate that the adiabatic search algorithm can be improved by accelerating the system coherent consumption by appropriate methods.This idea finding a new direction for improving the efficiency of adiabatic algorithms and can be extended to other adiabatic algorithms.