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:1412.8342 · Journal of Mathematical Physics

Exponential vanishing of the ground-state gap of the quantum random energy model via adiabatic quantum computing

Juan I. Adame, Simone Warzel

Published Nov 1, 2015• 7 citations
arXivHTMLPDF

Abstract

In this note, we use ideas of Farhi et al. [Int. J. Quantum. Inf. 6, 503 (2008) and Quantum Inf. Comput. 11, 840 (2011)] who link a lower bound on the run time of their quantum adiabatic search algorithm to an upper bound on the energy gap above the ground-state of the generators of this algorithm. We apply these ideas to the quantum random energy model (QREM). Our main result is a simple proof of the conjectured exponential vanishing of the energy gap of the QREM.

DOI
10.1063/1.4934723

Related papers

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

•May 9, 2002•2 citations

Unstructured randomness, small gaps and localization

Edward Farhi, Jeffrey Goldstone, David Gosset +2 more

We study the Hamiltonian associated with the quantum adiabatic algorithm with a random cost function. Because the cost function lacks structure we can prove results about the ground state. We find the ground state energy as the number of bits goes to infinity, show that the minimum gap goes to zero exponentially quickly, and we see a localization transition. We prove that there are no levels approaching the ground state near the end of the evolution. We do not know which features of this model are shared by a quantum adiabatic algorithm applied to random instances of satisfiability since despite being random they do have bit structure.

arXiv:1010.0009•Quantum Information and Computation•Sep 1, 2011•18 citations

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•2 citations

First-Order Transitions and the Performance of Quantum Algorithms in Random Optimization Problems

Thomas Jörg, Florent Krząkała, Guilhem Semerjian +1 more

We present a study of the phase diagram of a random optimization problem in the presence of quantum fluctuations. Our main result is the characterization of the nature of the phase transition, which we find to be a first-order quantum phase transition. We provide evidence that the gap vanishes exponentially with the system size at the transition. This indicates that the quantum adiabatic algorithm requires a time growing exponentially with system size to find the ground state of this problem.

arXiv:0911.3438•Physical Review Letters•May 20, 2010•107 citations

Universal witnesses of vanishing energy gap

Konrad Szymański, Karol Życzkowski

Abstract Energy gap, the difference between the energy of the ground-state of a given Hamiltonian and the energy of its first excited state, is a parameter of a critical importance in analysis of phase transitions and adiabatic quantum computation. We present a concrete technique to determine an upper bound for the energy gap of a Hamiltonian H 0 based on properties of the set of expectation values of H 0 and an additional auxiliary Hamiltonian V . This formalism can be applied to obtain an effective criterion of gaplessness, which we illustrate with a concrete example of the XY model —a physical system with vanishing energy gap.

arXiv:2104.13884•Europhysics Letters (EPL)•Nov 1, 2021•4 citations

How the High-energy Part of the Spectrum Affects the Adiabatic Computation Gap

Yosi Atia, Dorit Aharonov

Towards better understanding of how to design efficient adiabatic quantum algorithms, we study how the adiabatic gap depends on the spectra of the initial and final Hamiltonians in a natural family of test-bed examples. We show that perhaps counter-intuitively, changing the energy in the initial and final Hamiltonians of only highly excited states (we do this by assigning all eigenstates above a certain cutoff the same value), can turn the adiabatic algorithm from being successful to failing. Interestingly, our system exhibits a phase transition; when the cutoff in the spectrum becomes smaller than roughly $n/2$, $n$ being the number of qubits, the behavior transitions from a successful adiabatic process to a failed one. To analyze this behavior, and provide an upper bound on both the minimal gap as well as the success of the adiabatic algorithm, we introduce the notion of "escape rate", which quantifies the rate by which the system escapes the initial ground state (a related notion was also used by Ilin and Lychkovskiy in arXiv:1805.04083). Our results indicate a phenomenon that is interesting on its own right: an adiabatic evolution may be robust to bounded-rank perturbations, even when the latter closes the gap or makes it exponentially small.

arXiv:1906.02581•Jun 6, 2019•2 citations
In this note, we use ideas of Farhi et al. [Int. J. Quantum. Inf. 6, 503 (2008) and Quantum Inf. Comput. 11, 840 (2011)] who link a lower bound on the run time of their quantum adiabatic search algorithm to an upper bound on the energy gap above the ground-state of the generators of this algorithm. We apply these ideas to the quantum random energy model (QREM). Our main result is a simple proof of the conjectured exponential vanishing of the energy gap of the QREM.
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
We study the Hamiltonian associated with the quantum adiabatic algorithm with a random cost function. Because the cost function lacks structure we can prove results about the ground state. We find the ground state energy as the number of bits goes to infinity, show that the minimum gap goes to zero exponentially quickly, and we see a localization transition. We prove that there are no levels approaching the ground state near the end of the evolution. We do not know which features of this model are shared by a quantum adiabatic algorithm applied to random instances of satisfiability since despite being random they do have bit structure.
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.
Abstract Energy gap, the difference between the energy of the ground-state of a given Hamiltonian and the energy of its first excited state, is a parameter of a critical importance in analysis of phase transitions and adiabatic quantum computation. We present a concrete technique to determine an upper bound for the energy gap of a Hamiltonian H 0 based on properties of the set of expectation values of H 0 and an additional auxiliary Hamiltonian V . This formalism can be applied to obtain an effective criterion of gaplessness, which we illustrate with a concrete example of the XY model —a physical system with vanishing energy gap.
Towards better understanding of how to design efficient adiabatic quantum algorithms, we study how the adiabatic gap depends on the spectra of the initial and final Hamiltonians in a natural family of test-bed examples. We show that perhaps counter-intuitively, changing the energy in the initial and final Hamiltonians of only highly excited states (we do this by assigning all eigenstates above a certain cutoff the same value), can turn the adiabatic algorithm from being successful to failing. Interestingly, our system exhibits a phase transition; when the cutoff in the spectrum becomes smaller than roughly n/2n/2n/2, nnn being the number of qubits, the behavior transitions from a successful adiabatic process to a failed one. To analyze this behavior, and provide an upper bound on both the minimal gap as well as the success of the adiabatic algorithm, we introduce the notion of "escape rate", which quantifies the rate by which the system escapes the initial ground state (a related notion was also used by Ilin and Lychkovskiy in arXiv:1805.04083). Our results indicate a phenomenon that is interesting on its own right: an adiabatic evolution may be robust to bounded-rank perturbations, even when the latter closes the gap or makes it exponentially small.