Thèse Vers des Algorithmes Variationnels Quantiques Plus Précis et Efficaces en Environnement Bruité et Distribué pour les Problèmes d'Optimisation Sous Contraintes Liés à l'Écoroutage H/F

Doctorat.Gouv.Fr

Établissement : Université Paris-Saclay GS Informatique et sciences du numérique
École doctorale : Sciences et Technologies de l'Information et de la Communication
Laboratoire de recherche : IFP Energies Nouvelles - Sciences et Technologies du Numérique
Direction de la thèse : Quang Huy TRAN ORCID 0000000177713154
Début de la thèse : 2026-11-02
Date limite de candidature : 2026-10-31T23:59:59

L'optimisation du trajet des véhicules électriques (VE) ainsi que du placement des stations de recharge [B] joue un rôle clé dans le contexte de la transition énergétique et de la mobilité durable [DH]. À cette fin, IFPEN développe des outils avancés, notamment un planificateur d'itinéraire intégrant les caractéristiques spécifiques des VE, telles que les capacités des batteries et les niveaux de charge, ainsi que l'emplacement des stations de recharge pour minimiser les coûts et les impacts environnementaux.

Ce problème est modélisé comme la recherche du meilleur chemin entre deux noeuds d'un graphe, les poids associés aux arêtes représentant la distance, le temps de parcours ou la consommation énergétique. Cependant, lorsqu'on y ajoute des contraintes supplémentaires comme des restrictions sur les ressources, des limitations de parcours ou des besoins énergétiques spécifiques, ce problème devient NP-difficile. Sa résolution par des méthodes classiques est alors prohibitivement chère.

Dans ces conditions, les algorithmes variationnels quantiques tels que VQE [PM] et QAOA [FG] offrent des perspectives prometteuses. Ces algorithmes hybrides, qui combinent un circuit quantique au sein d'une boucle classique destinée à trouver les meilleurs paramètres du circuit, ont démontré leur pertinence sur des problèmes assez simples comme le max-cut [Cr] ou des variantes du problème du plus court chemin [FX]. Cependant, ils présentent également des limites [TA] :

1) Convergence lente. Une mauvaise initialisation de la boucle classique externe ralentit voire détruit la convergence. L'effort déployé pour améliorer le point initial, e.g., par une heuristique de démarrages multiples [SS] ou à chaud [EM], engendre des calculs supplémentaires, alourdissant significativement le temps CPU sans toujours garantir la convergence. Un compromis équilibré est à ce jour difficile à atteindre. Un autre facteur contribuant à la lenteur de l'optimisation externe est qu'elle se fait souvent par des méthodes sans gradient [NM], les dérivées par rapport aux paramètres d'angles étant coûteuses.

2) Amplitudes faibles. Comme dans tout algorithme quantique, la solution obtenue provient d'une mesure qui réduit l'état superposé à un vecteur de base. À convergence de la boucle externe, il faut relancer plusieurs fois l'évaluation quantique interne pour effectuer des statistiques permettant d'attribuer une amplitude de probabilité à chaque solution potentielle. Or, à l'inverse des algorithmes quantiques célèbres sur des problèmes simples, ces amplitudes s'avèrent uniformément faibles, si bien qu'il n'est plus possible de dire quelle solution s'impose comme la plus probable.

Dans cette thèse, nous souhaitons explorer plusieurs pistes pour pallier ces défauts, d'abord sur un ordinateur idéal sans bruit, puis en environnement réaliste bruité et distribué. La première direction porte sur les techniques d'amplification généralisant l'algorithme de Grover avec un oracle convenablement modifié, proposées par [KC] sur les problèmes QUBO. Nous envisageons de les transposer aux algorithmes variationnels.

Une deuxième approche consiste à considérer une évolution quantique en temps imaginaire (QITE), susceptible de conduire plus rapidement à l'état fondamental qu'en temps réel comme dans QAOA. Dans cette technique [KS1, KS2], la mise à jour des paramètres se fait selon une direction privilégiée, qui joue un rôle analogue au gradient et permet d'accélérer exponentiellement la boucle externe.

Enfin, une question centrale concerne la qualité d'approximation de la variété des états possibles. En effet, le paramétrage des états s'effectue selon un certain ansatz. Pour avoir des probabilités élevées, l'ensemble généré doit contenir ou passer près des éléments susceptibles d'être la solution exacte. Aussi, une analyse fine de cette variété est indispensable.

Ces dernières années, les algorithmes variationnels quantiques [CA] se sont imposés comme la catégorie la plus performante de méthodes quantiques susceptibles d'offrir un avantage quantique dans plusieurs domaines scientifiques, du moins sur un ordinateur quantique NISQ (Noisy Intermediate-Scale Quantum) [Pr]. Aussi ont-ils été étudiés pour les problèmes d'optimisation sur graphes liés à l'écoroutage des véhicules électriques, avec un enjeu majeur pour la mobilité et la transition énergétique. De ces travaux [DH, TA], il est apparu que plusieurs défis scientifiques restent à relever avant que ces algorithmes atteignent un degré d'intérêt véritablement opérationnel. L'objectif de cette thèse est d'aborder deux d'entre eux, que nous appelons respectivement la précision (mieux concentrer les amplitudes de probabilité sur une solution quasi-optimale) et l'efficacité (accélérer la convergence tout en maintenant la robustesse).

- Accroître le contraste entre les amplitudes de probabilité obtenues par les approches variationnelles quantiques, afin de sélectionner plus précisément et sans ambigüité une solution quasi-optimale privilégiée.
- Améliorer l'efficacité, en termes de rapidité et de robustesse, de la procédure externe d'optimisation des paramètres d'angle du circuit quantique en conditions non idéales, notamment en environnement distribué avec bruit.