PIRSA:22110083

Quantum adiabatic speedup on a class of combinatorial optimization problems

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

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

          @misc{ pirsa_PIRSA:22110083,
            doi = {10.48660/22110083},
            url = {https://pirsa.org/22110083},
            author = {Cain, Madelyn},
            keywords = {Condensed Matter},
            language = {en},
            title = {Quantum adiabatic speedup on a class of combinatorial optimization problems},
            publisher = {Perimeter Institute},
            year = {2022},
            month = {nov},
            note = {PIRSA:22110083 see, \url{https://pirsa.org}}
          }
Talk number
PIRSA:22110083
Collection
Talk Type
Subject
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"