Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1410.3562 · Physical Review A

Theorem on the existence of a nonzero energy gap in adiabatic quantum computation

Da-Jian Zhang, Xiao‐Dong Yu, D. M. Tong

Published Oct 16, 2014• 15 citations
arXivHTMLPDF

Abstract

Adiabatic quantum computation, based on the adiabatic theorem, is a promising alternative to conventional quantum computation. The validity of an adiabatic algorithm depends on the existence of a nonzero energy gap between the ground and excited states. However, it is difficult to ascertain the exact value of the energy gap. In this paper, we put forward a theorem on the existence of nonzero energy gap for the Hamiltonians used in adiabatic quantum computation. It can help to effectively identify a large class of the Hamiltonians without energy-level crossing between the ground and excited states.

DOI
10.1103/physreva.90.042321

Related papers

Speedup in Quantum Adiabatic Evolution Algorithm

Joonwoo Bae, Younghun Kwon

The quantum adiabatic evolution algorithm suggested by Farhi et al. was effective in solving NPcomplete problems. The algorithm is governed by the adiabatic theorem. Therefore, in order to reduce the running time, it is essential to examine the minimum energy gap between the ground level and the next one in the evolution. In this paper we show a way of speedup in the quantum adiabatic evolution algorithm, using an extended Hamiltonian. We present the exact relation between the energy gap and the elements of the extended Hamiltonian, which provides a new point of view to reduce the running time.

arXiv:quant-ph/0205048•Zeitschrift für Naturforschung A•Apr 1, 2003•0 citations

Adiabatic quantum computation: Noise in the adiabatic theorem and using the Jordan -Wigner transform to find effective Hamiltonians

Michael J. O’Hara

This thesis explores two mathematical aspects of adiabatic quantum computation. Adiabatic quantum computation depends on the adiabatic theorem of quantum mechanics, and (a) we provide a rigorous formulation of the adiabatic theorem with explicit definitions of constants, and (b) we bound error in the adiabatic approximation under conditions of noise and experimental error. We apply the new results to a standard example of violation of the adiabatic approximation, and to a superconducting flux qubit. Further, adiabatic quantum computation requires large ground-state energy gaps throughout a Hamiltonian evolution if it is to solve problems in polynomial time. We identify a class of random Hamiltonians with non-nearest-neighbor interactions and a ground-state energy gap of $\mathcal{O}(1/\sqrt{n})$, where $n$ is the number of qubits. We also identify two classes of Hamiltonians with non-nearest-neighbor interactions whose ground state can be found in polynomial time with adiabatic quantum computing. We then use the Jordan-Wigner transformation to derive equivalent results for Hamiltonians defined using Pauli operators.

•Apr 22, 2008•0 citations

Speedup in Quantum Adiabatic Evolution Algorithm

Joonwoo Bae, Younghun Kwon

Quantum adiabatic evolution algorithm suggested by Farhi et al. was effective in solving instances of NP-complete problems. The algorithm is governed by the adiabatic theorem. Therefore, in order to reduce the running time, it is essential to examine the minimum energy gap between the ground level and the next one through the evolution. In this letter, we show a way of speedup in quantum adiabatic evolution algorithm,using the extended Hamiltonian. We present the exact relation between the energy gap and the elements of the extended Hamiltonian, which provides the new point of view to reduce the running time. It is generally expected that quantum computation may solve the problems which are hard in classical context. Shor’s quantum factorization algorithm[1] and Grover’s quantum search algorithm[2] are the preludes to such expectation. Factorization problem, which is to factorize a large number, needs exponential time resource when a known classical algorithm is applied. However, Shor’s algorithm solves the problem with exponential speedup. Grover algorithm finds a target with quadratic speedup, compared to any known classical search algorithms. Quantum adiabatic evolution algorithm was proposed by Farhi et al. and applied to solve instances of NPcomplete

•Jan 1, 2002•0 citations

Comments on Adiabatic Quantum Algorithms

Mary Beth Ruskai

Recently a method for adiabatic quantum computation has been proposed and there has been considerable speculation about its efficiency for NP-complete problems. Heuristic arguments in its favor are based on the unproven assumption of an eigenvalue gap. We show that, even without the assumption of an eigenvalue gap, other standard arguments can be used to show that a large class of Hamiltonians proposed for adiabatic quantum computation have unique ground states. We also discuss some of the issues which arise in trying to analyze the behavior of the eigenvalue gap. In particular, we propose several mechanisms for modifying to final Hamiltonian to perform an adiabatic search with efficiency comparable to that for 3-SAT. We also propose the use of randomly defined final Hamiltonians as a mechanism for analyzing the generic spectral behavior of the interpolating Hamiltonians associated with problems which lack sufficent structure to be amenable to efficient classical algorithms.

arXiv:quant-ph/0203127•Mar 26, 2002•0 citations

Adiabatic quantum computation with a one-dimensional projector Hamiltonian

Avatar Tulsi

Adiabatic quantum computation is based on the adiabatic evolution of quantum systems. We analyze a particular class of quantum adiabatic evolutions where either the initial or final Hamiltonian is a one-dimensional projector Hamiltonian on the corresponding ground state. The minimum-energy gap, which governs the time required for a successful evolution, is shown to be proportional to the overlap of the ground states of the initial and final Hamiltonians. We show that such evolutions exhibit a rapid crossover as the ground state changes abruptly near the transition point where the energy gap is minimum. Furthermore, a faster evolution can be obtained by performing a partial adiabatic evolution within a narrow interval around the transition point. These results generalize and quantify earlier works.

arXiv:0806.0385•Physical Review A•Nov 23, 2009•27 citations

Adiabatic preparation without quantum phase transitions

Gernot Schaller

Many physically interesting models show a quantum phase transition when a single parameter is varied through a critical point, where the ground state and the first excited state become degenerate. When this parameter appears as a coupling constant, these models can be understood as straight-line interpolations between different Hamiltonians ${H}_{\mathrm{I}}$ and ${H}_{\mathrm{F}}$. For finite-size realizations however, there will usually be a finite energy gap between ground and first excited state. By slowly changing the coupling constant through the point with the minimum energy gap one thereby has an adiabatic algorithm that prepares the ground state of ${H}_{\mathrm{F}}$ from the ground state of ${H}_{\mathrm{I}}$. The adiabatic theorem implies that in order to obtain a good preparation fidelity the runtime $\ensuremath{\tau}$ should scale with the inverse energy gap and thereby also with the system size. In addition, for open quantum systems not only nonadiabatic but also thermal excitations are likely to occur. It is shown that---using only local Hamiltonians---for the one-dimensional quantum Ising model and the cluster model in a transverse field the conventional straight-line path can be replaced by a series of straight-line interpolations, along which the fundamental energy gap is always greater than a constant independent on the system size. The results are of interest for adiabatic quantum computation since strong similarities between adiabatic quantum algorithms and quantum phase transitions exist.

arXiv:0807.2516•Physical Review A•Sep 23, 2008•28 citations
Adiabatic quantum computation, based on the adiabatic theorem, is a promising alternative to conventional quantum computation. The validity of an adiabatic algorithm depends on the existence of a nonzero energy gap between the ground and excited states. However, it is difficult to ascertain the exact value of the energy gap. In this paper, we put forward a theorem on the existence of nonzero energy gap for the Hamiltonians used in adiabatic quantum computation. It can help to effectively identify a large class of the Hamiltonians without energy-level crossing between the ground and excited states.
The quantum adiabatic evolution algorithm suggested by Farhi et al. was effective in solving NPcomplete problems. The algorithm is governed by the adiabatic theorem. Therefore, in order to reduce the running time, it is essential to examine the minimum energy gap between the ground level and the next one in the evolution. In this paper we show a way of speedup in the quantum adiabatic evolution algorithm, using an extended Hamiltonian. We present the exact relation between the energy gap and the elements of the extended Hamiltonian, which provides a new point of view to reduce the running time.
This thesis explores two mathematical aspects of adiabatic quantum computation. Adiabatic quantum computation depends on the adiabatic theorem of quantum mechanics, and (a) we provide a rigorous formulation of the adiabatic theorem with explicit definitions of constants, and (b) we bound error in the adiabatic approximation under conditions of noise and experimental error. We apply the new results to a standard example of violation of the adiabatic approximation, and to a superconducting flux qubit. Further, adiabatic quantum computation requires large ground-state energy gaps throughout a Hamiltonian evolution if it is to solve problems in polynomial time. We identify a class of random Hamiltonians with non-nearest-neighbor interactions and a ground-state energy gap of O(1/n)\mathcal{O}(1/\sqrt{n})O(1/n​), where nnn is the number of qubits. We also identify two classes of Hamiltonians with non-nearest-neighbor interactions whose ground state can be found in polynomial time with adiabatic quantum computing. We then use the Jordan-Wigner transformation to derive equivalent results for Hamiltonians defined using Pauli operators.
Quantum adiabatic evolution algorithm suggested by Farhi et al. was effective in solving instances of NP-complete problems. The algorithm is governed by the adiabatic theorem. Therefore, in order to reduce the running time, it is essential to examine the minimum energy gap between the ground level and the next one through the evolution. In this letter, we show a way of speedup in quantum adiabatic evolution algorithm,using the extended Hamiltonian. We present the exact relation between the energy gap and the elements of the extended Hamiltonian, which provides the new point of view to reduce the running time. It is generally expected that quantum computation may solve the problems which are hard in classical context. Shor’s quantum factorization algorithm[1] and Grover’s quantum search algorithm[2] are the preludes to such expectation. Factorization problem, which is to factorize a large number, needs exponential time resource when a known classical algorithm is applied. However, Shor’s algorithm solves the problem with exponential speedup. Grover algorithm finds a target with quadratic speedup, compared to any known classical search algorithms. Quantum adiabatic evolution algorithm was proposed by Farhi et al. and applied to solve instances of NPcomplete
Recently a method for adiabatic quantum computation has been proposed and there has been considerable speculation about its efficiency for NP-complete problems. Heuristic arguments in its favor are based on the unproven assumption of an eigenvalue gap. We show that, even without the assumption of an eigenvalue gap, other standard arguments can be used to show that a large class of Hamiltonians proposed for adiabatic quantum computation have unique ground states. We also discuss some of the issues which arise in trying to analyze the behavior of the eigenvalue gap. In particular, we propose several mechanisms for modifying to final Hamiltonian to perform an adiabatic search with efficiency comparable to that for 3-SAT. We also propose the use of randomly defined final Hamiltonians as a mechanism for analyzing the generic spectral behavior of the interpolating Hamiltonians associated with problems which lack sufficent structure to be amenable to efficient classical algorithms.
Adiabatic quantum computation is based on the adiabatic evolution of quantum systems. We analyze a particular class of quantum adiabatic evolutions where either the initial or final Hamiltonian is a one-dimensional projector Hamiltonian on the corresponding ground state. The minimum-energy gap, which governs the time required for a successful evolution, is shown to be proportional to the overlap of the ground states of the initial and final Hamiltonians. We show that such evolutions exhibit a rapid crossover as the ground state changes abruptly near the transition point where the energy gap is minimum. Furthermore, a faster evolution can be obtained by performing a partial adiabatic evolution within a narrow interval around the transition point. These results generalize and quantify earlier works.
Many physically interesting models show a quantum phase transition when a single parameter is varied through a critical point, where the ground state and the first excited state become degenerate. When this parameter appears as a coupling constant, these models can be understood as straight-line interpolations between different Hamiltonians HI{H}_{\mathrm{I}}HI​ and HF{H}_{\mathrm{F}}HF​. For finite-size realizations however, there will usually be a finite energy gap between ground and first excited state. By slowly changing the coupling constant through the point with the minimum energy gap one thereby has an adiabatic algorithm that prepares the ground state of HF{H}_{\mathrm{F}}HF​ from the ground state of HI{H}_{\mathrm{I}}HI​. The adiabatic theorem implies that in order to obtain a good preparation fidelity the runtime $\ensuremath{\tau}$ should scale with the inverse energy gap and thereby also with the system size. In addition, for open quantum systems not only nonadiabatic but also thermal excitations are likely to occur. It is shown that---using only local Hamiltonians---for the one-dimensional quantum Ising model and the cluster model in a transverse field the conventional straight-line path can be replaced by a series of straight-line interpolations, along which the fundamental energy gap is always greater than a constant independent on the system size. The results are of interest for adiabatic quantum computation since strong similarities between adiabatic quantum algorithms and quantum phase transitions exist.