Résumé
L'informatique quantique est un domaine en plein essor qui a suscité un intérêt considérable au cours des deux dernières décennies en raison de sa promesse de révolutionner plusieurs domaines des affaires et de la science. Il s'agit d'une nouvelle façon d'effectuer des calculs en utilisant les propriétés fondamentales de la mécanique quantique telles que la superposition et l'intrication. L'optimisation, quant à elle, est un domaine omniprésent dans l'industrie et où de petites améliorations peuvent avoir un impact significatif. Cette thèse vise à résoudre des problèmes d'optimisation à l'aide d'algorithmes quantiques.Les problèmes d'optimisation NP-difficiles ne sont pas considérés comme pouvant être résolus exactement par des algorithmes généraux en temps polynomial. Les algorithmes quantiques variationnels (VQA en anglais) destinés à résoudre ces problèmes combinatoires ont récemment fait l'objet d'un grand intérêt. Ces algorithmes sont heuristiques et visent à obtenir une solution approximative. Cependant, le matériel en est encore à ses débuts et les ordinateurs quantiques bruyants à échelle intermédiaire (NISQ en anglais) actuels ne sont pas en mesure d'optimiser les problèmes d'intérêt industriel. De plus, le stockage des qubits et l'introduction de l'intrication nécessitent des conditions physiques extrêmes. Les algorithmes d'optimisation quantique contemporains, tels que le algorithme d'optimisation approximative quantique, Quantum Approximate Optimization Algorithm (QAOA) en anglais, posent un problème : leur échelle est linéaire en fonction de la taille du problème. Pour résoudre ce problème, nous présentons l'encodage LogQ, qui permet de concevoir des algorithmes variationnels quantiques dont l'échelle est logarithmique avec la taille du problème, ce qui ouvre la voie au traitement de problèmes d'optimisation d'une ampleur sans précédent sur des ordinateurs quantiques basés sur des portes. Nous montrons comment cet algorithme peut être appliqué à plusieurs problèmes d'optimisation combinatoire tels que Maximum Cut, Minimum Partition, Maximum Clique and Maximum Weighted Independent Set (MWIS). Ensuite, ces algorithmes sont testés sur un simulateur quantique avec des graphes de plus d'une centaine de nœuds et sur un véritable ordinateur quantique jusqu'à des graphes de taille 256. À notre connaissance, il s'agit des plus grands problèmes réalistes d'optimisation combinatoire jamais exécutés sur une machine NISQ, dépassant de près de dix fois la taille des problèmes résolus précédemment.Ensuite, nous appliquons le codage LogQ à deux cas d'utilisation pour de grandes entreprises telles que TotalEnergies. La conversion de la flotte est le processus de transition d'une flotte de véhicules vers des alternatives plus durables et plus respectueuses de l'environnement. Il est modélisé comme un schéma de génération de colonnes avec le problème MWIS comme sous-problème ou problème de travailleur. Nous utilisons la méthode LogQ pour résoudre le problème de travailleur MWIS et démontrons comment les solveurs quantiques et classiques peuvent être utilisés ensemble pour aborder un cas d'utilisation de taille industrielle. La segmentation de maillage fait référence au processus de division d'un maillage complexe (composé de sommets, d'arêtes et de faces) en parties ou régions significatives et sémantiquement cohérentes. La segmentation du maillage joue un rôle important dans la modélisation informatique, qui est largement utilisée dans les domaines clés des activités de TotalEnergies, tels que l'imagerie terrestre, la modélisation physique des réservoirs, etc. Nous définissons le problème comme un problème d'optimisation de graphe et utilisons l'encodage LogQ pour le résoudre.