Speaker
Description
"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"
External references
- 22110083
- ab3e4ed4-4dd1-45ce-afe3-c59138d2e817
- a49e75db-c5af-46af-9b8e-e77203ee2dd9
