Abstract: Recent developments in quantum computation, especially in the emerging topic of âquantum machine learningâ, suggest that quantum algorithms might offer significant speed-ups for optimization and machine learning problems. In this talk, I will describe three recent developments on provable quantum advantages for optimization and machine learning from our group.
(1) The first one optimizes a general (dimension n) convex function over a convex body using O(n) quantum queries to oracles that evaluate the objective function and determine membership in the convex body; this gives a quadratic improvement over the best-known classical algorithm.
(2) The second one solves a special class of convex optimization problems, semidefinite programs (SDPs), where we design a quantum algorithm that solves n-dimensional SDPs with m constraints in O(\sqrt{n} +\sqrt{m}), whereas the state-of-the-art classical algorithms run in time at least linear in n and m.
(3) The third one is a sublinear quantum algorithm for training linear and kernel-based classifiers that runs in O(\sqrt{n}+\sqrt{d}) given n data points in R^d, whereas the state-of-the-art (and optimal) classical algorithm runs in O(n +d).
Based on results in arXiv:1809.01731v1 (QIP 2019), arXiv:1710.02581v2 (QIP 2019), and arXiv: 1904.02276 (ICML 2019).