A snapshot of quantum algorithms for optimization

Event Sponsor: 
Mathmatics and Computer Science Division Seminar
Start Date: 
Jul 29 2019 - 3:00pm
Building 240/Room 1404-1405
Argonne National Laboratory
Giacomo Nannicini
Speaker(s) Title: 

There is much hype surrounding quantum computing and its potential applications for optimization. However, the technical details are often lost in translation. In this (mostly) survey talk I will give an overview of quantum algorithms that could potentially be useful for continuous and discrete optimization. I will discuss benefits and limitations of algorithms for SDP and LP (via faster solution of the Newton linear system, or via the multiplicative weights update method), the quantum approximate optimization algorithm, and hybrid quantum/classical variational methods for combinatorial problems. I will also discuss some fundamental open questions, highlighting what algorithmic limitations need to be overcome for quantum computing to have an impact on the practice of optimization.