Grover's algorithm and its implications in dynamic programming

Grover's algorithm was a major theoretical advance in quantum computing because it allows a quadratic reduction in the complexity of finding a marked element in an arbitrary list. This algorithm was later extended to optimization problems as well as to dynamic programming algorithms. In this talk, I will first explain the fundamental ideas needed to understand this algorithm. I will then illustrate how it has been used effectively to improve the theoretical complexity of some dynamic programming algorithms. Note that these considerations are purely theoretical because today's quantum machines are very far from being able to perform the above mentioned algorithms.