Research On Adiabatic Evolution Based Quantum Search Algorithms

The traditional quantum circuit based Shor’s algorithm for factoring integers, Grover’s quantum search algorithm and the quantum algorithm for solving linear systems of equations demonstrate big computational power of quantum computers. But the designing of quantum algorithms is a challenging task. Around the year of2000, a new quantum computational model, called adiabatic quantum computing was proposed. It is based on the adiabatic theorem in quantum mechanics, belonging to the category of continuous time evolution quantum computational model. The main idea behind adiabatic quantum computing can be summarized as:initialize the ground sate of the beginning Hamiltonian of the quantum system, which is easy to be prepared physically. Let the solution of the problem of interest be encoded as the ground state of a final Hamiltonian, then construct the instantaneous system Hamiltonian by choosing an evolution path which connects the former two. Let the whole quantum system evolve according to the Schrodinger equation, and the solution of the problem can be extracted with a high probability by measurement after long enough time. The whole evolution time can be estimated by the adiabatic theorem in quantum mechanics.When Grover’s algorithm was recast in the initial adiabatic computing model, it was found that the global adiabatic quantum search had no advantage over the classical algo-rithms. To deal with this problem, a local adiabatic evolution quantum algorithm was pro-posed, and it just demonstrates the same performance as the original Grover’s algorithm. A new adiabatic quantum search algorithm named partial adiabatic evolution was initialized by Tulsi in2009, which can be considered as a paradigm between the former two adiabatic evo-lution. On one side, it inherits the intrinsic robustness against quantum noise of the global adiabatic computing, and it also has the advantage of a quadratic speedup over the classical algorithms provided by the local adiabatic evolution on the other side. Recently, a quan-tum search algorithm by partial adiabatic evolution has been studied in the corresponding literatures.Due to the fact that the evolution path is one of the main ingredients of an adiabatic algorithm, in chapter2, we firstly study a specific problem defined in the context in the framework of global adiabatic evolution, with two different kinds of nonlinear evolution paths. It is found that one of the nonlinear adiabatic evolution path could lead to an infinite time complexity for the adiabatic evolution when the initial state has a zero overlap with the final state. This is quite unlike the conclusion that has been shown in related literature, which states that the time complexity of the adiabatic search could be improved to the constant while increasing the energy of the quantum system temporarily. Nearly at the same time, the conclusion above remains unchanged when applying a variation of this model to the same problem—running time of infinity for the adiabatic evolution. This later model which can be considered as another form of the second nonlinear path is originated from the idea of keeping the system ground state energy being zero during the whole adiabatic evolution procedure. But the situation is very different when we turn to the second nonlinear evolution path in the global adiabatic algorithm. At this time, the algorithm could always provide a constant time complexity for the problem. The phenomena above imply the advantages and disadvantages of nonlinear evolution paths in adiabatic quantum algorithms.Next, the quantum search problem has been abstracted here. A new form for the global adiabatic evolution which can also provide a quadratic speedup over the classical algorithms is shown here. Even more, by selecting appropriate factor, the global adiabatic evolution could accomplish the evolution in arbitrarily fast running time. The way of the energy change in this new model of global adiabatic is analyzed, and also it is compared with one kind of the nonlinear evolution path in global adiabatic discussed in chapter2and local adiabatic evolution. The mechanism behind the speedup has been shown in the meanwhile. Obviously, when a local adiabatic algorithm is applied to the problem, the quadratic speedup can be easily obtained. For this abstracted problem, it is found that the conditions for the original partial adiabatic cannot be satisfied fully. But it is also found that a partial adiabatic algorithm could still applied to the problem for speedup of the search. And it is derived that the new conditions that should be satisfied in current different situation in order to guarantee a valid partial adiabatic evolution.In chapter4, the evidence that global and local adiabatic algorithm can be considered as two special cases of the partial adiabatic is shown in detail, although this has been implied in related literatures. At the same time, an adiabatic algorithm which is based on a local and partial adiabatic evolution is introduced, and it just has the same algorithmic performance as the two, which implies the optimality of the algorithm. Two alternate viewpoints have also been given for this new adiabatic algorithm.Partial adiabatic evolution based quantum search first has been studied in related literatures. But it is found here the conclusion when there exist multiple solutions, the search can provide better time complexity may be in error. In fact, whether the number of the solution is bigger than one or not, the optimality of the partial adiabatic quantum search can always be proven. It is no surprise that partial and local adiabatic have the same performance.The problem how to implement adiabatic algorithms on quantum circuit model is dis-cussed in chapter5. In this chapter, four kinds of adiabatic quantum search algorithms have been discussed here—global adiabatic evolution, local adiabatic evolution, partial adiabatic evolution and these two latter based adiabatic evolution. The conclusion derived here shows that, the resultant time slices for the circuit model implementation of all the adiabatic algo-rithms should be of the same order as the time complexities of these quantum algorithms.Finally, applications of adiabatic computing for some related problems are shown in chapter6, this includes:adiabatic search under a priori probability, applying adiabatic search to prepare some simple quantum entangled states, and implementing the usual quantum gates in the circuit model by adiabatic evolution method.