Dans le cadre de la mission menée pour la Banque de France, Ekaterina ALEKSEEVA, consultante senior en optimisation chez EURODECISION, a exposé une expérimentation de calculs quantiques à la conférence en recherche opérationnelle « EURO 2024 » qui se tenait à l’université de Copenhague du 30 juin au 3 juillet et rassemblait environ 3 000 participants pour 2 520 présentations.

Ce fut une bonne occasion d’approfondir en trois jours les connaissances sur les sujets innovants tels que l’Informatique Quantique (IQ) et l’Intelligence Artificielle Générative (IAG) et suivre le rythme de leurs applications aux problématiques de la recherche opérationnelle.

 

Informatique Quantique

L’Informatique Quantique (IQ) est une des nouvelles technologies activement explorées par les spécialistes en recherche opérationnelle grâce à ses nombreuses applications en optimisation et sa promesse alléchante concernant une vitesse de calcul accrue par rapport aux ordinateurs conventionnels. Ainsi, cette année un groupe de travail dirigé par Philipe LACOMME à ISIMA LIMOS a organisé une session dédiée à l’IQ appliquée aux problèmes d’optimisation qui comprenait 18 présentations faites par la Banque de France, PASQAL, EdF, MBDA, La Poste, et des chercheurs d’universités en France, Slovénie, Luxembourg et Allemagne.

Wesley COELHO (Quantum Graph Optimization Lead chez PASQAL, une start-up française qui fabrique des ordinateurs quantiques à base d’atomes neutres) a fait les trois présentations suivantes.

  • La 1ère était une implémentation d’une approche de génération de colonnes où un Quantum Processor Unit (QPU) permet de définir certains paramètres à chaque itération qui sont utilisés par la suite dans les calculs faits par un ordinateur conventionnel. Cette approche a été testée sur un problème de coloration de sommets ayant jusqu’aux 140 nœuds. Elle nécessite moins d’itérations que son implémentation classique, néanmoins elle prend deux heures (pour 140 nœuds) de calculs.
  • La 2ème présentation abordait la résolution d’un Quadratic Unconstrained Binary Optimization (QUBO) problème par un algorithme de variation quantique adapté à une technologie physique utilisée par PASQAL qui est basée sur des atomes neutres et nécessite l’intégration de la matrice QUBO dans le registre atomique, et l’ajustement des impulsions laser afin de manipuler les états des qubits.
Pour en savoir plus, contactez-nous
Nom
Prénom
Société
E-mail *
Téléphone
Votre message *

* Champs obligatoires

  • La 3ème présentation expliquait principalement les aspects physiques quantiques de la manière dont PASQAL crée des qubits. Il s’agit de piéger les atomes avec des lasers. Leurs ordinateurs quantiques n’ont pas besoin que la température soit proche du zéro absolu. La localisation des atomes correspond aux contraintes (liens) entre variables dans un modèle mathématique : plus les atomes sont proches, plus les variables sont liées. PASQAL applique le recuit quantique (quantum annealing) ou informatique analogique. Grâce à ça, il est possible de faire la préparation quantique, c’est-à-dire de créer une première solution à un problème d’optimisation qui sera améliorée par la suite par un algorithme.

La Poste en collaboration avec l’Université de Montpellier a présenté : « Efficient encoding for the traveling salesman problem using quantum variational algorithm » basée sur le code de Lehmer connu depuis 1888. L’idée est d’énumérer efficacement toutes les solutions du problème, par exemple, problème du voyageur du commerce, et les intégrer dans un algorithme d’optimisation quantique approximative (QAOA) afin de réduire le nombre de portes nécessaires à un ordinateur quantique pour résoudre ce problème. Une présentation faite par Phlippe LACOMME du Laboratoire d’Informatique à Clermont-Ferrand explore la même idée mais appliquée à un autre problème d’optimisation.

Edouard DEBRY a présenté la résolution d’un cas d’usage de MBDA d’optimisation combinatoire, rendu NP dur par certaines contraintes métiers, avec l’algorithme quantique d’optimisation approximative (Farhi, 2014). Deux façons différentes de traiter les contraintes dures ont été présentées et comparées sur de petites instances, du fait des limitations actuels des accès aux QPU. Le traitement des contraintes métiers par l’algorithmie quantique est un enjeu majeur pour les cas d’usage de MBDA, afin que les algorithmes développés puissent passer à l’échelle de grandes instances.

Ekaterina ALEKSEEVA d’EURODECISION a présenté une expérimentation de résolution quantique d’un problème de coupe minimum adapté au processus de règlement des transactions par la Banque de France. Ce travail conjoint avec Pierrick VALLAT d’EURODECISION et Nicolas WOLTERS a pour objectif d’évaluer la maturité et les limites des ordinateurs quantiques existants et disponibles. Lire le résumé

En conclusion, ces présentations montrent le grand intérêt que la communauté de la recherche opérationnelle porte à l’informatique quantique et les efforts des scientifiques et des praticiens pour se préparer à lancer leurs algorithmes quantiques et applications sur des ordinateurs quantiques puissants dans un avenir proche. Une actualité publiée le 25 juin 2024 par PASQAL rapporte le franchissement d’une étape technologique significative : une capacité de piéger et de manipuler plus de 1000 atomes. Néanmoins, en marge de la conférence, on comprend que cette avancée ne signifie pas qu’on dispose d’un ordinateur quantique qui possède 1000 qubits disponibles pour l’exécution d’un algorithme.

 

Intelligence Artificielle Générative

Un autre sujet de l’innovation abordé dans plusieurs présentations était l’IAG, en mettant l’accent sur la manière dont elle peut contribuer à la recherche opérationnelle.

De plus en plus d’entreprises, notamment les éditeurs des solveurs d’optimisation (Gurobi, FICO, Amazon), les expérimentent, espérant améliorer et rendre leur service plus simple et efficace.

Oliver BASTERT, de l’entreprise américaine FICO (éditeur du logiciel d’optimisation), a présenté leur produit FICO Xpress optimizer, notamment un cas d’usage d’IAG afin d’interagir avec les utilisateurs du système FICO via un chatbot. Selon lui, l’IAG pourrait être utilisée pour la génération et la navigation dans les documents, ainsi que pour la génération de scénarios ou de tests d’un problème d’optimisation. Il a fait une démonstration du fonctionnement du chatbot basé sur Claude AI et intégré dans le système FICO. Les questions posées étaient autour d’une solution obtenue par Xpress au problème d’optimisation de portefeuille. Pour les commandes et les questions simples comme, par exemple :

  • « Optimise the portfolio » ; « Copy the scenario » ;
  • « What is Return on Investment for X ? » ; « What is my investment in Y ? » où X et Y sont des noms d’actifs financiers,

Les réponses obtenues sont fiables et basées sur une solution optimale. FICO souhaite aller plus loin et intégrer dans cet assistant virtuel une capacité de répondre à des questions plus sophistiquées qui nécessitent l’analyse du modèle mathématique. Par exemple, répondre à la question « When the model is infeasible ? ».

Plusieurs sociétés (Gurobi, FICO, Qampo, Amazon) sont en train d’expérimenter l’idée d’intégration des systèmes d’IAG dans leurs produits afin de vulgariser et expliquer des modèles mathématiques ; générer du code et des données de tests ou bien préparer des réunions. Néanmoins, elles sont conscientes des risques liés à l’application de l’IAG tels que la sécurité, l’exactitude, le manque de traçabilité et l’éthique. «Comment pouvons-nous faire confiance à un outil qui suggère d’utiliser de la colle pour maintenir le fromage à une pizza ?» (réponse ridicule générée par Google AI).

Michael LINDAHL de Qampo (le laboratoire de science de la décision à Copenhague) a comparé un modèle d’optimisation mathématique vs un LLM (Large Language Model). Il s’agit de profiter des points forts des LLMs et d’aider au traitement des données d’entrée pour les modèles mathématiques.

Par exemple, dans le cas où la description d’un problème se présente dans plusieurs documents et formats, l’IAG pourrait aider à :

  • récupérer les informations distribuées dans les documents et à les unifier dans un format approprié ;
  • traduire une phrase simple en une formule mathématique qui constitue une contrainte d’un modèle d’optimisation mathématique ;
  • traduire les formules mathématiques en texte.

Cette technologie n’est pas fiable pour choisir un algorithme de résolution du problème. De toute façon, même si l’IAG est appliquée, ses réponses doivent être vérifiées et validées par un expert.

Pendant le temps libre, une balade sur les fronts de mer, notamment dans le port de Nyhavn favorise les réflexions sur toutes les présentations suivies et permet d’observer non seulement La Petite Sirène, une statue en bronze qui représente le personnage du conte éponyme de Hans Christian Andersen, mais aussi le siège social de la plus grande entreprise danoise, le transporteur maritime Maersk. L’occasion d’apprendre que Maersk applique la recherche opérationnelle pour optimiser un réseau mondial de transport maritime desservant plus de 100 000 clients dans 130 pays, et pilote l’orchestration complexe des horaires de plus de 700 navires.