This is a reminder about the talk today at 2pm. Yours truly, Man Hong ----------------------------------------------------------------------- Dr. Man-Hong Yung Postdoctoral Fellow Department of Chemistry and Chemical Biology Harvard University mhyung(a)chemistry.harvard.edu ----------------------------------------------------------------------- ---------- Forwarded message ---------- From: Man-Hong Yung <mhyung(a)chemistry.harvard.edu> Date: Fri, Jan 4, 2013 at 9:17 PM Subject: postdoc candidate talk next Monday 7 Jan To: A-G Group <aspuru-list(a)lists.fas.harvard.edu> Dear All, Speaker: Salvatore Mandrà Place: Division room Time: 2 pm, 7 Jan Salvatore Mandrà will give a talk in the division room, 2 pm, the coming Monday. His talk title and abstract are as follows: Title: Why does the QAA fail to solve NP-complete problems: an exhaustive analysis of the random graph coloring solution landscape Although many numerical and theoretical results have been found in recent years, the existence (or not) of an algorithm for solving NP complete problems in polynomial time still remains one of the hardest and fascinating question in computer science. In the wake of the success of Peter Shor who showed that the algorithm for finding prime factors has an exponential speed up on quantum computers, in 2002 Edward Farhi [1] proposed a new theoretical tool named the "Quantum Adiabatic Algorithm" (QAA) as general prescription for tackling NP-complete problems. Early results on the Exact Cover problem showed an exponential speed up using QAA for small instances. However, further studies, including many other NP complete problems, disproved this hypothesis by showing that the exponential speed up is lost for very large systems [2, 3]. In order to understand why QAA fails when solving NP-Complete problems, I will present some numerical results based on an exhaustive analysis of the classical solution space of random graph coloring, a well known problem belonging to the NP-Complete class. In particular, I will show how some structures present in the solution space might be the cause of the QAA failure. [1] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, Science 292, 5516 (2001) [2] A.P. Young, S. Knysh and V.N. Smelyanskiy, PRL 101, 17 (2010) [3] I. Hen, A.P. Young PRE 84, 6 (2011) Yours truly, Man Hong ----------------------------------------------------------------------- Dr. Man-Hong Yung Postdoctoral Fellow Department of Chemistry and Chemical Biology Harvard University mhyung(a)chemistry.harvard.edu -----------------------------------------------------------------------