title: First-order transitions and the performance of quantum algorithms in random optimization problems.
abstract: 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.
authors.affiliation: LPTENS, CNRS UMR 8549, associée à l'UPMC Paris 06, 24 Rue Lhomond, 75005 Paris, France.
authors.forename: Thomas
authors.initials: T
authors.lastname: Jörg
authors.forename: Florent
authors.initials: F
authors.lastname: Krzakala
authors.forename: Guilhem
authors.initials: G
authors.lastname: Semerjian
authors.forename: Francesco
authors.initials: F
authors.lastname: Zamponi