“Convex optimization algorithms on quantum computers”
Martedì 9 Lunedì 8 Aprile 2024, ore 9:30 - Aula 2BC30 - Giacomo Nannicini (University of Southern California)
Abstract
Optimization is often mentioned as one of the main application areas for quantum computers, but is this claim backed up by theoretical evidence? In this talk we provide a gentle overview of recent advances in quantum optimization, with an emphasis on algorithms and subroutines for convex optimization problems that lead to rigorous asymptotic speedups. The main results of this talk are a faster classical algorithm for the semidefinite relaxation of the MaxCut problem, an even faster quantum algorithm for the same problem, and a new idea for linear optimization on quantum computers.
