New Directions in Quantum Algorithms: Thermalization meets Convex Optimization

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

• Speaker: Fernando Brandao, Caltech
• Friday 04 May 2018, 11:00–12:00
• Venue: MR2 Centre for Mathematical Sciences.
• Series: CCIMI Seminars; organiser: Rachel Furner.