Quantum Colloquium – Quantum Algorithms For Optimization

Tuesday, May 11th, 2021, 11:00 am12:00 pm

Add to Calendar

Parent Program: 

Ronald de Wolf (QuSoft, CWI and University of Amsterdam)


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.