Le contenu de cette page n’est pas disponible en français. Veuillez nous en excuser.
 

Faster quantum and classical SDP approximations for quadratic binary optimization



Playing this video requires the latest flash player from Adobe.

Download link (right click and 'save-as') for playing in VLC or other compatible player.


Recording Details

Speaker(s): 
PIRSA Number: 
19100088

Abstract

We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. The class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms.
This is joint work with Fernando Brandao (Caltech) and Daniel Stilck Franca (QMATH, Copenhagen).