Le concept d’informatique quantique existe depuis plus de 30 ans, avec les travaux fondateurs de Shor(1944) ou Grover (1996) sur les premiers algorithmes. Ces dix dernières années ont vu l’émergence de véritables machines quantiques (allant de 5 à 5000 qubits), sur lesquelles il est désormais possible d’exécuter ces algorithmes, soit directement sur un QPU (Quantum Processing Unit), soit par émulation sur GPU.
L’équipe s’est naturellement orientée vers la Recherche Opérationnelle Quantique, qui vise à résoudre des problèmes d’optimisation à l’aide de ce nouveau paradigme de calcul. Eric Bourreau a d’ailleurs présenté une plénière sur ce sujet lors de la conférence ROADEF 2021. En effet, l’approche quantique repose sur une philosophie totalement différente, où les variables de décision sont en superposition, et où les mesures, par écroulement, introduisent une dimension stochastique dans la lecture des résultats.
Ces optimisations peuvent être menées :
— de manière globale, en recherchant un optimum,
— ou via des algorithmes d’approximation par recherche locale dits variationnels
Plusieurs thèses ont ainsi été lancées au sein de l’équipe, avec une double ambition :
— Obtenir des résultats théoriques sur les bornes de complexité des problèmes d’ordonnancement
— Explorer des cas d’usage industriels, notamment :
o SNCF (thèse Camille Grange soutenue) : planification des transports ferroviaires
o TotalEnergies (thèse Yagnik Chatterjee soutenue) : optimisation d’une flotte de véhicules
o La Poste (thèse Imran Meghazi en cours) : impact des machines quantiques sur les futurs défis postaux.
Enfin, le boom des architectures quantiques (basées sur des photons, ions piégés, atomes froids ou supraconducteurs) induit diverses modélisations des mêmes problèmes combinatoires. Ces différentes approches nous forcent à évaluer leurs performances actuelles ainsi que leur scalabilité future.