March 31: Prof. Aram Harrow (MIT) on “Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing”

Title: Prof. Aram Harrow on “Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing
Location: 26-214, Thursday March. 31, Noon-1pm. Pizza at 11:45!
(Feel free to bring your own cup and plate)

Abstract:

Simulated Quantum Annealing (SQA) is a Markov Chain Monte-Carlo algorithm that samples the equilibrium thermal state of a Quantum Annealing (QA) Hamiltonian. In addition to simulating quantum systems, SQA has also been proposed as another physics-inspired classical algorithm for combinatorial optimization, alongside classical simulated annealing. However, in many cases it remains an open challenge to determine the performance of both QA and SQA. In this work we apply a comparison method to rigorously show that the Markov chain underlying SQA efficiently samples the target distribution and finds the global minimum of the spike cost function in polynomial time.

“The IGERT program has been developed to meet the challenges of educating U.S. Ph.D. scientists, engineers, and educators with the interdisciplinary backgrounds, deep knowledge in chosen disciplines, and technical, professional, and personal skills to become in their own careers the leaders and creative agents for change.”

—The National Science Foundation