Skip to main content
Seminar | Mathematics and Computer Science

A Snapshot of Quantum Algorithms for Optimization

LANS Informal Seminar

Abstract: 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.