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

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• 6 citations
Publisher

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

Exponential vanishing of the ground-state gap of the QREM via adiabatic quantum computing

Juan I. Adame, Simone Warzel

In this note we use ideas of Farhi, Goldstone, Gosset, Gutmann, Nagaj and Shor 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.

arXiv:1412.8342•Dec 29, 2014•2 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

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•Sep 30, 2010•0 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•0 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.

Quantum Information and Computation•Sep 1, 2011•15 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•100 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.
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.