New Directions in Quantum Algorithms

With Fernando Brandao, Caltech

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

Add to your calendar or Include in your list