Quantum Institute: Visitor Schedule

The Quantum Lunch is regularly held on Thursdays in the Theoretical Division Conference Room, TA-3, Building 123, Room 121.
For more information, contact Diego Dalvit.
To add your name to the Quantum Lunch email list, contact Charlotte Lehman

Thursday, April 8, 2010
12:30 PM - 2:00 PM

Speaker: Florent Krzakala (ESPCI, Paris)

Technical Host: Lenka Zdeborova

TOPIC: Energy gaps in quantum first-order transitions: The problems that quantum annealing cannot solve

Abstract
Many important practical problems involve the minimization of a function of discrete variables. Solving such combinatorial problems by temperature annealing is a classical strategy : the idea is to use thermal fluctuations to avoid trapping the system in local minima, and thereby efficiently visit the whole configuration space. Quantum annealing is an extension of this approach to quantum fluctuations, where one try to solve the problem by tuning down the amplitude of a quantum mechanical kinetic operator such as a transverse magnetic field. But can this outperform the classical approach? And in particular, can problems that normally take exponential time be solved in only polynomial time?

In this talk, I will show how statistical physics tools can be used to study this problem, using exact analytical methods (replica, cavity, instanton...) and powerful numerical simulations (continuous time Monte-Carlo, diagonalization...). What we find is that for the really hard problems such as random satisfiability, or random vertex cover, the answer to this question is no: Quantum annealing does not help to solve the problem in polynomial time. In fact, it seems for such hard problems the algorithm always meet a first-order transition when the transverse field is cooled down and at this point adiabatically is hopelessly lost: this puts a strict limit to the performance of annealings with quantum computers.