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 students in MIT’s new NSF training program will be encouraged to cross disciplines, and develop a common fellowship with their peers. We will also address training for post-academic jobs directly by connecting students to government and industrial members of the iQuISE Consortium.”

—Seth Lloyd, Co-Director, iQuISE, and Professor of Mechanical Engineering and Professor of Engineering Systems