PIRSA:14120029

Video URL

https://pirsa.org/14120029

Different Strategies for Quantum Adiabatic Optimization, and the Computational Power of Simulated Quantum Annealing

(2014). Different Strategies for Quantum Adiabatic Optimization, and the Computational Power of Simulated Quantum Annealing. Perimeter Institute for Theoretical Physics. https://pirsa.org/14120029

Different Strategies for Quantum Adiabatic Optimization, and the Computational Power of Simulated Quantum Annealing. Perimeter Institute for Theoretical Physics, Dec. 03, 2014, https://pirsa.org/14120029 

          @misc{ scivideos_PIRSA:14120029,
            doi = {10.48660/14120029},
            url = {https://pirsa.org/14120029},
            author = {},
            keywords = {Quantum Information},
            language = {en},
            title = {Different Strategies for Quantum Adiabatic Optimization, and the Computational Power of Simulated Quantum Annealing},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2014},
            month = {dec},
            note = {PIRSA:14120029 see, \url{https://scivideos.org/pirsa/14120029}}
          }
Talk numberPIRSA:14120029
DOI10.48660/14120029
Source RepositoryPIRSA
Collection
Talk Type Scientific Series
Subject

Abstract

Quantum Adiabatic Optimization proposes to solve discrete optimization problems by mapping them onto quantum spin systems in such a way that the optimal solution corresponds to the ground state of the quantum system. The standard method of preparing these ground states is using the adiabatic theorem, which tells us that quantum systems tend to remain in the ground state of a time-dependent Hamiltonian which transforms sufficiently slowly. In this talk I'll show that alternative strategies using non-adiabatic effects can in some cases be dramatically faster for instances which are hard for the traditional adiabatic method.

I will also discuss Simulated Quantum Annealing (SQA), which is a classical simulation of adiabatic optimization at non-zero temperature based on Path-Integral Quantum Monte Carlo. SQA is widely used in practice to study adiabatic optimization, but relatively little is known about the rate of convergence of the markov chain that underlies the algorithm. By focusing on a family of instances which adiabatic optimization solves in polynomial time, but require exponential time to solve using classical (thermal) simulated annealing, I will present numerical evidence as well as a work-in-progress proof that SQA can be exponentially faster than classical simulated annealing.