Physics (Internal)

Out-of-equilibrium states and quantum annealing speed up in non-convex optimization and learning problems

This event is part of the Condensed Matter Theory Seminar Series.

Quantum annealers aim at solving non-convex optimization problems by exploiting cooperative tunneling effects to escape local minima. A key challenge is to identify classes of non-convex optimization problems for which this scheme can induce an exponential speed up compared to thermal annealing. We show that this happens for a wide class of optimization problems which are also central to machine learning. Their energy landscape is exponentially dominated by local minima that trap classical thermal annealers, while quantum annealing converges efficiently to rare dense regions of optimal solutions. For non convex problems, these will not in general correspond to configuration dominating the Gibbs measure.