Published in

American Physical Society, Physical Review Letters, 20(104)

DOI: 10.1103/physrevlett.104.207206

Links

Tools

Export citation

Search in Google Scholar

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

Journal article published in 2010 by Thomas Jörg, Florent Krzakala ORCID, Guilhem Semerjian, Francesco Zamponi ORCID
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Green circle
Postprint: archiving allowed
Upload
Green circle
Published version: archiving allowed
Upload
Policy details
Data provided by SHERPA/RoMEO

Abstract

We present a study of the phase diagram of a random optimization problem in 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. ; Comment: 4 pages, 4 figures; final version accepted on Phys.Rev.Lett