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

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 nœuds 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. École doctorale : Sciences et Technologies de l'Information et de la Communication Direction : Quang Huy TRAN Financement : Programme doctoral 'Quantique'