11:45 am, November 21, 2019
Invited Speaker: Michael Jarret, Booz Allen Hamilton
Location: Johnson Center 337 (Meeting Room G)
- Snack and Chat (15 minutes)
- Focus Presentation (60 minutes)
- Q & A (15 minutes)
Dr. Michael Jarret is a Lead Scientist of Booz Allen Hamilton. Before joining BAH, Michael received his PhD in Physics from the University of Maryland’s Joint Center for Quantum Information and Computer Science (QuICS) and was a postdoctoral fellow at the Perimeter Institute. Michael studies quantum and classical algorithms as well as spectral graph theory.
Backtracking algorithms, such as the famous Davis-Putnam-Logemann-Loveland (DPLL) algorithm, explore a data structure constructed on-the-fly which encodes features of a problem to be solved. These structures are used in many applications, most notably boolean satisfiability (SAT). In this talk, I will review DPLL and SAT, introduce quantum subroutines for accelerating backtracking, and describe recent advances on quantum backtracking algorithms. I will also discuss open problems and current progress towards an optimal quantum backtracking algorithm, as well as applications and extensions of these backtracking methods that are of current interest to the quantum algorithms community. All of these techniques use a “local query” quantum walk and rely heavily on the quantum phase estimation algorithm. This talk is based in part on work done in collaboration with Kianna Wan (arXiv:1711.05295).