Adiabatic Quantum Search Algorithm

Shor's algorithm for factoring and Grover's search algorithm have proved that quantum computation is more powerful than classical computation. However, it is difficult to design a quantum algorithm, which is faster than any classical algorithm, for a given problem. There are two main reasons. On the one hand, designers'intuition is rooted in the classical world. In order to design a faster quantum algorithm, one has to turn off one's classical intuition. On the other hand, a quantum algorithm designed for a given problem has to perform better than all known classical algorithms for the problem, otherwise it will not excite enough interest. Adiabatic quantum computation is one of the main research fields in quantum computation, along with the quantum fourier transformation and Grover's search algorithm. It is based on quantum adiabatic theorem, which is essentially one kind of continuous time quantum computation, and is robust to certain quantum noises, as opposed to the quantum circuit model. The unordered database search problem which is solved by Grover's algorithm, is one of the hot spot issues in quantum computation. To investigate the problem based on quantum adiabatic evolution may help us to understand the essence of adiabatic quantum computation and then the quantum computation, and hence is significant.Apparently, the system Hamiltonian of global adiabatic quantum computation model is obtained by linear interpolation, and the run time of its corresponding algorithm can be calculated by applying the adiabatic condition to the whole time. The evolution path of local adiabatic quantum computation model and its time complexity is determined by applying the adiabatic condition to infinitesimal time interval. Whereas, partial adiabatic quantum computation model evolves only within a small interval around the minimum energy gap. But our research reveals that the difference among the three adiabatic quantum computation is their evolution path.The system Hamiltonian lies at the heart of quantum adiabatic evolution, which directly determines the whole process of the quantum system. In adiabatic quantum computation, the system Hamiltonian is composed of initial Hamiltonian, final Hamiltonian and evolution path. How to calculate the minimum energy gap between the ground state and the first ex-cited state is the main problem in adiabatic quantum computation. Generally, the spectrum of a system Hamiltonian is difficult to analyze, and so the minimum energy gap. But in spe-cial case, we can reduce the Hilbert space, in which the system works, to a lower dimension making the analysis more easy to do. For instance, Grover problem can be considered as a special case of 3SAT. On studying this problem, one can reduce the N dimensional Hilbert space to n+1 dimension, and then investigate the minimum energy gap using approximate or analytical method.Grover's algorithm has been proven to be optimal based on Oracle call, whose time complexity is O((?)). Is has been shown that global adiabatic quantum search algorithm performs as fast as the classical brute search, while local adiabatic search algorithm has the same time complexity as that of Grover's algorithm. Our research shows that partial adiabatic quantum search algorithm performs better than Grover's algorithm in the case that M>1. It provides a speed up of O((?)) over Grover's algorithm, and in the case of M=1, provides the same time complexity as that of Grover's algorithm.Adiabatic quantum computation is essentially one kind of continuous time quantum computation. To convert it into its corresponding quantum circuit based algorithm in general includes two steps. The first step is to cut the run time into R time intervals, and approximate the quantum continuous time transformation within each interval using a unitary transformation. The second step is to analyze the error introduced by the approximation, and determine the number of the intervals.