Quantum computers hold the promise of solving certain problems much faster than classical devices. An important challenge in quantum computing is to come up with more quantum algorithms offering speed-ups. I will discuss recent results on quantum algorithms for semidefinite programming, an important class of convex optimization problems with widespread applications (from resource allocation to approximating hard combinatorial problems). I will show how solving semidefinite programs (SDPs) is connected to the task of quantum Gibbs sampling (which consists of computing properties of thermal states at finite temperature on a quantum computer). I will then discuss results on the time of thermalization of many-body quantum systems and show that they directly give quantum speed-ups for SDPs. I will also argue that the quantum algorithm for SDPs can be seen as a generalization of quantum annealing and is a good candidate for realisation on small quantum computers.
Part of the Mathematics of Quantum Information workshop