Algorithmes quantiques pour l'optimisation et l'échantillonnage moderne – QUOPS

Avec la construction en cours d'ordinateurs quantiques de taille intermédiaire, le développement de nouveaux algorithmes quantiques n'a jamais été aussi pertinent. Le but de ce projet est de repousser la frontière des algorithmes quantiques et des techniques algorithmiques quantiques pour résoudre des problèmes clés en optimisation et en échantillonnage. À cette fin, nous combinerons et exploiterons des progrès récents, mais pour la plupart disjoints, réalisés dans le domaine des algorithmes quantiques dans des contextes discrets et continus. Des exemples récents de telles avancées sont les algorithmes quantiques dûs au coordinateur scientifique pour les problèmes de graphes tels que la sparsification et la résolution du laplacien, ainsi qu'une ligne indépendante de travaux sur les algorithmes quantiques pour les techniques d'optimisation convexe telles que la descente de gradient et la programmation semi-définie. Le projet s'inspire du paradigme moderne de l'optimisation et de l'échantillonnage à haute dimension qui combine de manière critique des techniques issues dans des contextes discrets et continus. En effet, les meilleurs algorithmes actuels pour des problèmes tels que la programmation linéaire et l'échantillonnage de polytopes combinent des techniques de sparsification avec des algorithmes de marche aléatoire et des méthodes de points intérieurs issues de l'optimisation convexe. En s'appuyant sur ces nouvelles connaissances, le projet QUOPS vise à mieux comprendre les accélérations quantiques pour ces problèmes. Les objectifs concrets sont les algorithmes quantiques qui accélèrent les problèmes d'optimisation canonique tels que le flux maximum et la régression lp, et les tâches clés en statistique et en apprentissage automatique telles que l'échantillonnage logconcave et l'échantillonnage polytope. En nous appuyant sur l'expertise combinée du consortium en matière d'algorithmes quantiques et d'optimisation moderne, nous serons en mesure de combler le fossé actuel entre les algorithmes quantiques et les paradigmes modernes du calcul classique.