Quantum algorithms for modern optimization and sampling – QUOPS

With intermediate-size quantum computers currently being built, the development of new quantum algorithms has never been more relevant. The aim of this project is to push forward the frontier of quantum algorithms and quantum algorithmic techniques for solving key problems in optimization and sampling. To this end, we will combine and build on recent but mostly disjoint progress in quantum algorithms in discrete and continuous settings. Examples are the recent quantum algorithms by the scientific coordinator for graph problems such as sparsification and Laplacian solving, and an independent line of works on quantum algorithms for convex optimization techniques such as gradient descent and semi-definite programming. The project takes inspiration from the modern paradigm in optimization and high-dimensional sampling that critically combines techniques from both discrete and continuous settings. Indeed, the current best algorithms for problems such as linear programming and sampling from polytopes combine sparsification techniques with random walk algorithms and interior point methods from convex optimization. Building on these new insights, the QUOPS project is bound to obtain a better understanding of quantum speedups for these problems. Concrete objectives are quantum algorithms that speed up canonical optimization tasks such as maximum flow and lp-regression, and key tasks in statistics and machine learning such as logconcave sampling and polytope sampling. By building on the consortium expertise both in quantum algorithms and in modern optimization, we will be able to bridge the current gap between quantum algorithms and modern paradigms in classical computing.