Quantum adiabatic speedup on a class of combinatorial optimization problems

          @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}}
          }
          

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"