Quantum Algorithms for Optimization | Quantum Colloquium

Ronald de Wolf (QuSoft, CWI and University of Amsterdam)
Quantum Colloquium, May. 11th, 2021

Faster algorithms for optimization problems are among the main potential applications for future quantum computers. There has been interesting progress in this area in the last few years, for instance improved quantum algorithms for gradient descent and for solving linear and semidefinite programs. In this talk I will survey what we know about quantum speed-ups both for discrete and for continuous optimization. I'll also discuss some issues with these algorithms, in particular that quadratic quantum speedups will only kick in for very large instance sizes and that many of these algorithms require some kind of QRAM.

[joexu]

20:00 quantum speedup for discrete optimization: find minimum n^{1/2}; shortest path n^{1.5}; typicalled based on Grover's search

[joexu]

39:00 polynomial speedup for NP-hard optimization, don't expect exponential quantum speedup

[maxwellsdaemon]

At 24:00 he didn't define what e_i and e_j are. (Edit) but I figured what they must be - unit basis vectors, such that x^T L x gives the sum of squared differences of adjacent values x defined on the nodes of the graph.

[عليمحمودعلي-لص]

Quantum Cat Swarm Optimization Algorithm in python?

[joexu]

48:40 linear and semidefinite programming

[maxwellsdaemon]

I think he could have explained what a QRAM is in a better way, with a bit more detail.

[joexu]

4:25 discrete and continuous setting and the mix

[joexu]

11:10 caveat: most optimization speedups less than quadratic

[assahrasoumasahboou]

fathi medos fez aziza 1 said than you so much