PIRSA:22110083 Conference Condensed Matter

DOI10.48660/22110083

Conference/School: New Frontiers in Machine Learning and Quantum

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

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"

Resources

Next talk

Related Talks