22110083

Quantum adiabatic speedup on a class of combinatorial optimization problems

APA

Cain, M. (2022). Quantum adiabatic speedup on a class of combinatorial optimization problems. Perimeter Institute for Theoretical Physics. http://pirsa.org/22110083

MLA

Cain, Madelyn. Quantum adiabatic speedup on a class of combinatorial optimization problems. Perimeter Institute for Theoretical Physics, Nov. 22, 2022, http://pirsa.org/22110083

BibTex

          @misc{ scitalks_22110083,
            doi = {},
            url = {http://pirsa.org/22110083},
            author = {Cain, Madelyn},
            keywords = {Quantum Matter},
            language = {en},
            title = {Quantum adiabatic speedup on a class of combinatorial optimization problems},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2022},
            month = {nov},
            note = {Talk #22110083 see, \url{https://scitalks.ca}}
          }
          
Source Repository PIRSA
Talk Type Conference

Abstract

"One of the central challenges in quantum information science is to design quantum algorithms that outperform their classical counterparts in combinatorial optimization. In this talk, I will describe a modification of the quantum adiabatic algorithm (QAA) [1] that achieves a Grover-type speedup in solving a wide class of combinatorial optimization problem instances. The speedup is obtained over classical Markov chain algorithms including simulated annealing, parallel tempering, and quantum Monte Carlo. I will then introduce a framework to predict the relative performance of the standard QAA and classical Markov chain algorithms, and show problem instances with quantum speedup and slowdown. Finally, I will apply this framework to interpret results from a recent Rydberg atom array experiment [2], which suggest a superlinear speedup in solving the Maximum Independent Set problem on unit-disk graphs. [1] Farhi et al. (2001) Science 292, 5516 [2] Ebadi et al. (2022) Science 376, 6598"