Séminaire

Date : 5 novembre 2026 13:30 - Salle :salle A002 Accélérations quantiques pour les problèmes combinatoires : du plus court chemin à l’ordonnancement en atelier Eric Bourreau - LIRMM

Depuis l’apparition de l’algorithme de Shor, il y a plus de trente ans, l’informatique quantique porte la promesse d’accélérations algorithmiques majeures. Depuis une dizaine d’années, les machines quantiques sont devenues une réalité, mais leur bruit et leur taille limitée ont jusqu’ici fortement restreint la portée des calculs réalisables. L’émergence prochaine de machines intégrant la correction quantique d’erreurs pourrait cependant ouvrir une nouvelle étape, dans laquelle de véritables algorithmes quantiques pourront être exécutés à une échelle pertinente. Dans cette présentation, je me concentrerai sur les apports théoriques de l’algorithmique quantique à des problèmes classiques d’optimisation combinatoire. Nous parcourrons plusieurs accélérations en complexité, depuis des problèmes polynomiaux — plus court chemin, arbre couvrant, couplage — jusqu’à des problèmes NP-difficiles tels que le voyageur de commerce et certains problèmes d’ordonnancement.

https://www.lirmm.fr/eric-bourreau/