First-order transitions and the performance of quantum algorithms in random optimization problems

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 expon...

Full description

Saved in:
Bibliographic Details
Published in:Physical review letters 2010-05, Vol.104 (20), p.207206-207206, Article 207206
Main Authors: Jörg, Thomas, Krzakala, Florent, Semerjian, Guilhem, Zamponi, Francesco
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0031-9007
1079-7114
DOI:10.1103/physrevlett.104.207206