CE47 - Technologies quantiques

Quantum algorithms for modern optimization and sampling – QUOPS

Submission summary

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.

Project coordination

Simon Apers (Institut de Recherche en Informatique Fondamentale)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.

Partner

IRIF Institut de Recherche en Informatique Fondamentale

Help of the ANR 201,062 euros
Beginning and duration of the scientific project: December 2022 - 48 Months

Useful links

Explorez notre base de projets financés

 

 

ANR makes available its datasets on funded projects, click here to find more.

Sign up for the latest news:
Subscribe to our newsletter