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 iQuISE program represents a bold step forward to coalesce and cohere the education and research training that will produce a new generation of quantum information researchers for our nation.”

—Claude R. Canizares, Bruno Rossi Professor of Physics, Vice President for Research, and Associate Provost