Physics (Internal)

The efficiency of the quantum adiabatic algorithm

This event is part of the Biophysics/Condensed Matter Seminar Series.

Abstract:
I will describe results of quantum Monte Carlo simulations for quite large problem sizes which aim to determine how efficiently the quantum adiabatic algorithm (QAA) could solve hard optimization problems on a quantum computer. Results will be presented for a particular “constraint satisfaction problem”. Next, results from a classical, heuristic, algorithm will be presented for several problems, and, in the rest of the talk, I will discuss the application of the QAA to the hardest of these. Curiously, although this problem is very hard for standard algorithms, including the QAA, it can solved in polynomial time using a special approach.