Lab Home | Phone | Search
Center for Nonlinear Studies  Center for Nonlinear Studies
 Colloquia Archive 
 Postdoc Seminars Archive 
 Quantum Lunch 
 Quantum Lunch Archive 
 CMS Colloquia 
 Q-Mat Seminars 
 Q-Mat Seminars Archive 
 Kac Lectures 
 Dist. Quant. Lecture 
 Ulam Scholar 
 CNLS Fellowship Application 
 Summer Research 
 Past Visitors 
 History of CNLS 
 Maps, Directions 
 CNLS Office 
Thursday, April 08, 2010
12:30 PM - 2:00 PM
T-DO Conference Room (TA-3, Bldg 123, Room 121)

Quantum Lunch

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

Florent Krzakala
ESPCI, Paris

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.