[QIP-Sem] QIP seminar, Mon 3/8, 4:30, 36-462, Krovi,Hari

[Peter Shor]

MIT Quantum Information Processing seminar
Monday 3/8 at 4:30 in 36-462
-------------------------------------------------

 Krovi,Hari (University of Connecticut)

Adiabatic quantum optimization fails for random instances of NP-complete problems

Abstract:

 Adiabatic quantum optimization has attracted a lot of attention because small scale simulations gave hope that it could solve NP-complete problems efficiently. Later, negative results proved the existence of specifically designed hard instances where adiabatic optimization requires exponential time. These hard instances usually lie far from the satisfiability threshold of random instances of NP-complete problems and this is regime where classical solvers are inefficient. Thus, it is important to understand whether adiabatic quantum optimization is efficient in this regime. Here, we will show that because of a phenomenon similar to Anderson localization, an exponentially small eigenvalue gap appears in the spectrum of the adiabatic Hamiltonian for large random instances, very close to the end of the algorithm. This implies, unfortunately, that adiabatic quantum optimization fails for these instances by getting stuck in a local minimum, unless the computation is exponentially 
 long. (Joint work with Boris Altshuler and Jérémie Roland)

-------------------------------------------------
http://qis.mit.edu
http://mailman.mit.edu/mailman/listinfo/qip-sem