PIRSA:15120042

Video URL

https://pirsa.org/15120042

Spectral graph theory applied to simulating stoquastic adiabatic optimization

Jarret, M. (2015). Spectral graph theory applied to simulating stoquastic adiabatic optimization. Perimeter Institute for Theoretical Physics. https://pirsa.org/15120042

Jarret, Michael. Spectral graph theory applied to simulating stoquastic adiabatic optimization. Perimeter Institute for Theoretical Physics, Dec. 16, 2015, https://pirsa.org/15120042 

          @misc{ scivideos_PIRSA:15120042,
            doi = {10.48660/15120042},
            url = {https://pirsa.org/15120042},
            author = {Jarret, Michael},
            keywords = {Quantum Information},
            language = {en},
            title = {Spectral graph theory applied to simulating stoquastic adiabatic optimization},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2015},
            month = {dec},
            note = {PIRSA:15120042 see, \url{https://scivideos.org/pirsa/15120042}}
          }

Michael Jarret George Mason University

Talk numberPIRSA:15120042
DOI10.48660/15120042
Source RepositoryPIRSA
Collection
Talk Type Scientific Series
Subject

Abstract

Quantum adiabatic optimization (QAO) slowly varies an initial Hamiltonian with an easy-to-prepare ground-state to a final Hamiltonian whose ground-state encodes the solution to some optimization problem. Currently, little is known about the performance of QAO relative to classical optimization algorithms as we still lack strong analytic tools for analyzing its performance. In this talk, I will unify the problem of bounding the runtime of one such class of Hamiltonians -- so-called stoquastic Hamiltonians -- with questions about functions on graphs, heat diffusion, and classical sub-stochastic processes. I will introduce new tools for bounding the spectral gap of stoquastic Hamiltonians and, by exploiting heat diffusion, show that one of these techniques also provides an optimal and previously unknown gap bound for particular classes of graphs. Using this intuition and combining heat diffusion with classical sub-stochastic processes, I will offer a classical adiabatic algorithm that exhibits behavior typically considered "quantum", such as tunneling.