Research On Appiications Of The Adiabatic Approximation In Quantum Computation

Adiabatic quantum computation offers a promising alternative to the conven-tional quantum computation. It is polynomially equivalent to the circuit model in computational power,and may be more physically realistic and implementable than the circuit model due to its inherent robustness against some types of errors. Adiabatic quantum algorithm is based on the adiabatic evolution, i.e.,if the time-dependent Hamiltonian interpolating smoothly from the initial Hamiltonian to the final Hamiltonian varies sufficiently slowly, the final state of the quantum system, starting from the ground state of the initial Hamiltonian, is close to the ground state of the final Hamiltonian,which encodes the solution to a problem. The "slowness" required by the adiabatic theorem is usually encoded in the adiabatic condition, which is directly related to the energy gap between the ground state and excited states of the time-dependent Hamiltonian. It shows that the energy gap plays an important role in adiabatic quantum computation. The validity of an adiabatic algorithm, i.e.,the existence of a finite runtime, completely depends on the exis-tence of a nonzero gap,while the efficiency of the algorithm, i.e.,the scaling of the runtime,depends on the value of the nonzero gap.However, it is quite difficult to ascertain the exact value of the energy gap for the Hamiltonians used in adiabatic quantum computation. Due to the difficulty, researchers have to resort to numerical simulations to evaluate the runtime of the adiabatic algorithm. Yet, the approach to illustrate the validity and efficiency of an adiabatic algorithm by numerical simulation is restricted by the numbers of instances as well as by the size of the problem under consideration. So far, neither validity issue nor efficiency one has been effectively resolved.In this thesis, we investigate the existence as well as computability of the energy gap in adiabatic quantum computation, from which one can deduce the validity and efficiency of an adiabatic algorithm. The main results are as follows: 1)We investigate the validity issue and present a theorem on the existence of a nonzero energy gap in adiabatic quantum computation. The theorem indi-cates that a nonzero energy gap between the ground and excited states of the time-dependent Hamiltonian is guaranteed if the initial Hamiltonian is properly chosen such that the conditions of our theorem are fulfilled. Despite the fact that these conditions restrict the choice of Hamiltonians, the theorem can ac-tually identify a large class of the Hamiltonians with a nonzero energy gap. To illustrate the usefulness of the theorem, we apply it to the models considered in the previous papers. Without the need for complicated calculations, we can immediately confirm that all the Hamiltonians used in these papers belong to this class, i.e., they are with a nonzero energy gap. Since there has not been an effective approach to examine the existence of a non-zero gap, the theorem may be helpful in choosing alternative Hamiltonians for an adiabatic algorithm.2) We investigate the computability of the energy gap in adiabatic quantum com-putation. Specifically, we investigate the role of symmetries of Hamiltonians in ascertaining the exact value of the energy gap. We first classify the symme-tries of the time-dependent Hamiltonians into three types, i.e., local symmetries, global symmetries, and continuous symmetries. Then we show that the presence of local symmetries may cause energy-level crossing, which makes an adiabatic algorithm invalid, while the presence of global as well as continuous symmetries usually results in the evolution of a system being constrained in a certain sub-space, which reduces the difficulty of ascertaining the value of the energy gap. With the aid of global symmetries, we find a way to determine the runtime of an adiabatic algorithm in the case of multiple solutions to the problem under consideration, which is an open problem in adiabatic quantum computation. In this case, the ground state becomes degenerate at the end of the evolution, and hence the energy gap becomes zero. By choosing the initial Hamiltonian prop-erly, we obtain a time-dependent Hamiltonian with global symmetries, implying that the evolution of a system is constrained in a subspace. Inside this subspace, the ground state is nondegenerate, and hence the runtime is available.3) We put forward an alternative quantum algorithm for finding Hamiltonian cycles in any N-vertex graph based on adiabatic quantum computation. The Hamil-tonian cycle problem is an NP-complete problem, one of the well-known Karp’s 21 NP-complete problems, which is believed to be an intractable problem with a classical computer. By aid of the proposed algorithm, one can determine whether there is a Hamiltonian cycle in the graph and pick out a cycle if there is any. We show that our algorithm provides a quadratic speedup, and hence has the same complexity as the Grover’s algorithm which is a circuit-based algo-rithm. Although the speedup achieved here is the same as the previous works, possessing an alternative algorithm based on the adiabatic model is instructive because of its inherent robustness. Together with other related works, this result supports the conjecture that the power of adiabatic quantum computation is e-quivalent, not merely polynomial-equivalent, to the circuit model. It is worthy noting that the proposed algorithm can be regarded as an example of the appli-cations of the results we present in 1) and 2), i.e., the initial Hamiltonian of our algorithm is chosen properly such that it fulfills the conditions of our theorem, which guarantee the validity of our algorithm, and results in a time-dependent Hamiltonian with global symmetries, which makes us get access to the efficiency of our algorithm.