 |
Center for Nonlinear Studies |
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.