Quantum Colloquium — Quantum Algorithms For Optimization

Faster algorithms for optimization problems are among the main potential applications for future quantum computers. There has been interesting progress in this area in the last few years, for instance improved quantum algorithms for gradient descent and for solving linear and semidefinite programs. In this talk I will survey what we know about quantum speed-ups both for discrete and for continuous optimization. I'll also discuss some issues with these algorithms, in particular that quadratic quantum speedups will only kick in for very large instance sizes and that many of these algorithms require some kind of QRAM.

Panel discussion: Andrew Childs (UMD), Eddie Farhi (MIT/Google), Ashley Montanaro (U. Bristol), Umesh Vazirani (UC Berkeley; moderator)