title: Solvable model of quantum random optimization problems.
abstract: We study the quantum version of a simplified model of optimization problems, where quantum fluctuations are introduced by a transverse field acting on the qubits. We find a complex low-energy spectrum of the quantum Hamiltonian, characterized by an abrupt condensation transition and a continuum of level crossings as a function of the transverse field. We expect this complex structure to have deep consequences on the behavior of quantum algorithms attempting to find solutions to these problems.
authors.affiliation: LPTENS, CNRS UMR 8549, associée à l'UPMC Paris 06, 24 Rue Lhomond, 75005 Paris, France.
authors.forename: Laura
authors.initials: L
authors.lastname: Foini
authors.forename: Guilhem
authors.initials: G
authors.lastname: Semerjian
authors.forename: Francesco
authors.initials: F
authors.lastname: Zamponi