 


Thursday, April 08, 201012:30 PM  2:00 PMTDO Conference Room (TA3, Bldg 123, Room 121) Quantum Lunch Energy gaps in quantum firstorder transitions: The problems that quantum annealing cannot solve Florent KrzakalaESPCI, 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 MonteCarlo, 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 firstorder 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.
