Algorithmes quantiques pour les problèmes d'optimisation du management de l'énergie Le domaine du management de l'énergie implique de nombreux problèmes d'optimisation combinatoire connus pour être difficiles. L'émergence des ordinateurs quantiques suggère de nouvelles approches pour ces problèmes. Pour les machines du futur proche, les heuristiques quantiques variationnelles telles que QAOA, qui peuvent tirer parti de la puissance de calcul des ordinateurs quantiques imparfaits, sont particulièrement prometteuses. Nous explorons le potentiel des algorithmes quantiques variationnels pour des problèmes d'optimisation issus du domaine de "smart charging" des véhicules électriques. Nous considérons deux problèmes inspirés de cas d'utilisation réels. Dans le premier problème, modélisé par Max-K-Cut, nous cherchons à planifier un ensemble de charges avec priorités sur plusieurs stations tout en minimisant le temps de completion pondéré. Dans le deuxième problème, modélisé par Maximum Independent Set, nous cherchons à maximiser le nombre de demandes de charge satisfaites sur une seule station tout en respectant les conflits entre les demandes. Pour les deux problèmes, nous développons un protocole expérimental spécifiant l'encodage et la routine d'optimisation des paramètres. Nos expériences numériques confirment l'intérêt des heuristiques quantiques pour ces problèmes ainsi que la qualité de notre protocole expérimental. Afin d'étendre l'applicabilité des heuristiques quantiques au-delà de QUBO, nous introduisons une nouvelle approche hybride qui intègre des routines quantiques dans l'algorithme classique de Branch & Price pour les programmes linéaires en nombres entiers. Nous testons cette approche sur un problème de smart charging qui se modélise comme problème de coloration de graphe. Nos résultats numériques affirment le potentiel de l'approche hybride tout en révélant la dépendance considérable du gain de performance sur l'instance particulière du problème. Les parties importants des algorithmes variationnels peuvent être représentés sous forme de diagrammes ZX. Nous démontrons comment les règles de réécriture du ZX-calculus peuvent être utilisées pour dériver la formule analytique de l'énergie moyenne d'un modèle d'Ising dans un état QAOA with depth 1. De plus, nous contribuons à l'exploration théorique des algorithmes variationnels en étendant le ZX-calcul avec addition et différenciation de ZX-diagrammes. Notre procédure inductive pour l'addition est entièrement graphique. Pour la différenciation, nous suggérons deux approches. La première approche est inductive, elle s'appuie sur notre procédure d'addition pour représenter explicitement les règles du produit. La deuxième approche est résumée dans deux formules qui sont dérivées de la forme factorisée des diagrammes paramétrés.
Algorithmes quantiques pour les problèmes d'optimisation du management de l'énergie Le domaine du management de l'énergie implique de nombreux problèmes d'optimisation combinatoire connus pour être difficiles. L'émergence des ordinateurs quantiques suggère de nouvelles approches pour ces problèmes. Pour les machines du futur proche, les heuristiques quantiques variationnelles telles que QAOA, qui peuvent tirer parti de la puissance de calcul des ordinateurs quantiques imparfaits, sont particulièrement prometteuses. Nous explorons le potentiel des algorithmes quantiques variationnels pour des problèmes d'optimisation issus du domaine de "smart charging" des véhicules électriques. Nous considérons deux problèmes inspirés de cas d'utilisation réels. Dans le premier problème, modélisé par Max-K-Cut, nous cherchons à planifier un ensemble de charges avec priorités sur plusieurs stations tout en minimisant le temps de completion pondéré. Dans le deuxième problème, modélisé par Maximum Independent Set, nous cherchons à maximiser le nombre de demandes de charge satisfaites sur une seule station tout en respectant les conflits entre les demandes. Pour les deux problèmes, nous développons un protocole expérimental spécifiant l'encodage et la routine d'optimisation des paramètres. Nos expériences numériques confirment l'intérêt des heuristiques quantiques pour ces problèmes ainsi que la qualité de notre protocole expérimental. Afin d'étendre l'applicabilité des heuristiques quantiques au-delà de QUBO, nous introduisons une nouvelle approche hybride qui intègre des routines quantiques dans l'algorithme classique de Branch & Price pour les programmes linéaires en nombres entiers. Nous testons cette approche sur un problème de smart charging qui se modélise comme problème de coloration de graphe. Nos résultats numériques affirment le potentiel de l'approche hybride tout en révélant la dépendance considérable du gain de performance sur l'instance particulière du problème. Les parties importants des algorithmes variationnels peuvent être représentés sous forme de diagrammes ZX. Nous démontrons comment les règles de réécriture du ZX-calculus peuvent être utilisées pour dériver la formule analytique de l'énergie moyenne d'un modèle d'Ising dans un état QAOA with depth 1. De plus, nous contribuons à l'exploration théorique des algorithmes variationnels en étendant le ZX-calcul avec addition et différenciation de ZX-diagrammes. Notre procédure inductive pour l'addition est entièrement graphique. Pour la différenciation, nous suggérons deux approches. La première approche est inductive, elle s'appuie sur notre procédure d'addition pour représenter explicitement les règles du produit. La deuxième approche est résumée dans deux formules qui sont dérivées de la forme factorisée des diagrammes paramétrés.
Le domaine du management de l'énergie implique de nombreux problèmes d'optimisation combinatoire connus pour être difficiles. L'émergence des ordinateurs quantiques suggère de nouvelles approches pour ces problèmes. Pour les machines du futur proche, les heuristiques quantiques variationnelles telles que QAOA, qui peuvent tirer parti de la puissance de calcul des ordinateurs quantiques imparfaits, sont particulièrement prometteuses. Nous explorons le potentiel des algorithmes quantiques variationnels pour des problèmes d'optimisation issus du domaine de "smart charging" des véhicules électriques. Nous considérons deux problèmes inspirés de cas d'utilisation réels. Dans le premier problème, modélisé par Max-K-Cut, nous cherchons à planifier un ensemble de charges avec priorités sur plusieurs stations tout en minimisant le temps de completion pondéré. Dans le deuxième problème, modélisé par Maximum Independent Set, nous cherchons à maximiser le nombre de demandes de charge satisfaites sur une seule station tout en respectant les conflits entre les demandes. Pour les deux problèmes, nous développons un protocole expérimental spécifiant l'encodage et la routine d'optimisation des paramètres. Nos expériences numériques confirment l'intérêt des heuristiques quantiques pour ces problèmes ainsi que la qualité de notre protocole expérimental. Afin d'étendre l'applicabilité des heuristiques quantiques au-delà de QUBO, nous introduisons une nouvelle approche hybride qui intègre des routines quantiques dans l'algorithme classique de Branch & Price pour les programmes linéaires en nombres entiers. Nous testons cette approche sur un problème de smart charging qui se modélise comme problème de coloration de graphe. Nos résultats numériques affirment le potentiel de l'approche hybride tout en révélant la dépendance considérable du gain de performance sur l'instance particulière du problème. Les parties importants des algorithmes variationnels peuvent être représentés sous forme de diagrammes ZX. Nous démontrons comment les règles de réécriture du ZX-calculus peuvent être utilisées pour dériver la formule analytique de l'énergie moyenne d'un modèle d'Ising dans un état QAOA with depth 1. De plus, nous contribuons à l'exploration théorique des algorithmes variationnels en étendant le ZX-calcul avec addition et différenciation de ZX-diagrammes. Notre procédure inductive pour l'addition est entièrement graphique. Pour la différenciation, nous suggérons deux approches. La première approche est inductive, elle s'appuie sur notre procédure d'addition pour représenter explicitement les règles du produit. La deuxième approche est résumée dans deux formules qui sont dérivées de la forme factorisée des diagrammes paramétrés.
Méthodes d'optimisation variationnelles quantiques et leurs applications 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.
Conception et application d’algorithmes quantiques pour la résolution de problèmes d’optimisation ferroviaire Cette thèse est dédiée à la conception et à l’application d’algorithmes quantiques pour la résolution de problèmes d’optimisation combinatoire ferroviaires. Aujourd’hui, les problèmes d’optimisation auxquels fait face la SNCF sont complexes, empêchant souvent une résolution à l’optimalité via des méthodes classiques en un temps raisonnable. L’informatique quantique est pressentie pour améliorer la qualité des solutions et diminuer le temps de calcul pour certains de ces problèmes. Actuellement, les algorithmes quantiques pour l’optimisation se divisent en deux classes : les algorithmes exacts et les heuristiques. Les premiers présentent un avantage théorique pour plusieurs problèmes, mais ne sont pas implémentables sur les machines actuelles car trop gourmands en ressources. Les seconds sont implémentables dès aujourd’hui, au moins sur de petites instances, ouvrant la porte aux premières applications, bien qu’ils ne présentent pas encore de garanties de performances ni d'avantage quantique. Dans cette thèse, nous analysons et proposons des algorithmes qui appartiennent à chacune de ces deux classes.D’une part, nous étudions une classe d’heuristiques appelée Algorithmes Variationnels Quantiques. Il s’agit d’algorithmes hybrides quantique-classique, qui alternent entre l’exécution d’un circuit quantique paramétré et l’optimisation classique des paramètres. Ils permettent de résoudre des problèmes non contraints à variables binaires, et nous proposons une méthode générale pour reformuler des problèmes contraints à variables entières sous cette forme. Nous présentons certaines propriétés des Algorithmes Variationnels Quantiques, nécessaires pour envisager des preuves théoriques de garanties de performances. En particulier, nous étudions QAOA (Quantum Approximate Optimization Algorithm) en l'analysant à la lumière des précédentes propriétés et en donnant une décomposition universelle de son circuit quantique pour des problèmes dont la fonction objectif est polynomiale. Avec cet algorithme, nous résolvons un problème de conception de plan de transport de la SNCF. Ce problème a pour but de trouver un plan de transport qui correspond au meilleur compromis économique entre les bénéfices générés par la vente de billets aux voyageurs et les coûts d'exploitation, tout en respectant la disponibilité du réseau ferroviaire. Pour résoudre ce problème avec QAOA, nous proposons deux simplifications correspondant à différentes adaptations du problème métier initial.D’autre part, nous élaborons des algorithmes quantiques-classiques exacts pour deux grandes familles de problèmes combinatoires. La première famille concerne les problèmes d’ordonnancement. L’algorithme proposé s’applique à une large classe de problèmes d’ordonnancement à une machine, NP-difficiles, qui satisfont une propriété de programmation dynamique particulière (Dynamic Programming Across the Subsets). L’algorithme, reprenant l’idée de Ambainis et al. (2019), allie la programmation dynamique classique et l’algorithme quantique de recherche du minimum dans une table (basé sur l’algorithme de Grover). Il permet de réduire la complexité en temps pire-cas, parfois au détriment de l’introduction d’un terme pseudo-polynomial. Nous étendons cet algorithme au problème du flowshop à trois machines, pour lequel une accélération est aussi obtenue. La deuxième famille relève des problèmes d’optimisation robuste où l’ensemble d’incertitude est un polytope. Nous proposons un algorithme qui, partant de l’algorithme classique traitant de ces problèmes, remplace certaines opérations par des routines quantiques afin d’obtenir une accélération. Précisément, nous étudions l'utilisation des deux routines quantiques suivantes : la recherche du minimum dans une table et la résolution d’un système linéaire.
Dynamique quantique à N-corps pour l'optimisation combinatoire et le machine learning L'objectif de cette thèse est d'explorer et de qualifier l'utilisation de la dynamique quantique à N-corps pour résoudre des problèmes industriels difficiles et des tâches d'apprentissage automatique. En tant que collaboration entre des partenaires industriels et universitaires, cette thèse explore les capacités d'un dispositif à atome neutre pour résoudre des problèmes réels. Tout d'abord, nous examinons les problèmes d'optimisation combinatoire et montrons comment les atomes neutres peuvent naturellement encoder un célèbre problème d'optimisation combinatoire appelé le "Maximum Independent Set on Unit-Disk graphs". Ces problèmes apparaissent dans les défis industriels tels que le chargement intelligent des véhicules électriques. L'objectif est de comprendre pourquoi et comment on peut s'attendre à ce qu'une approche quantique résolve ce problème plus efficacement qu'une méthode classique. Les algorithmes que nous proposons sont testés sur un véritable à l'aide d'un ensemble de données provenant d'EDF, la compagnie française d'électricité. Nous explorons en outre l'utilisation d'atomes neutres en 3D pour résoudre des problèmes qui sont hors de portée des méthodes d'approximation classiques. Enfin, nous essayons d'améliorer notre intuition sur les types d'instances pour lesquelles une approche quantique peut (ou ne peut pas) donner de meilleurs résultats que les méthodes classiques. Dans la deuxième partie de cette thèse, nous explorons l'utilisation de la dynamique quantique dans le domaine de l'apprentissage automatique. En plus d'être une grande chaîne de mots à la mode, l'apprentissage automatique quantique (QML) a été de plus en plus étudié ces dernières années. Dans cette partie, nous proposons et mettons en œuvre un protocole quantique pour l'apprentissage automatique sur des ensembles de données de graphes, et nous montrons des résultats prometteurs en ce qui concerne la complexité de l'espace de caractéristiques associé. Enfin, nous explorons l'expressivité des modèles d'apprentissage automatique quantique et présentons des exemples où les méthodes classiques peuvent approximer efficacement les modèles d'apprentissage automatique quantique.
L'objectif de cette thèse est d'explorer et de qualifier l'utilisation de la dynamique quantique à N-corps pour résoudre des problèmes industriels difficiles et des tâches d'apprentissage automatique. En tant que collaboration entre des partenaires industriels et universitaires, cette thèse explore les capacités d'un dispositif à atome neutre pour résoudre des problèmes réels. Tout d'abord, nous examinons les problèmes d'optimisation combinatoire et montrons comment les atomes neutres peuvent naturellement encoder un célèbre problème d'optimisation combinatoire appelé le "Maximum Independent Set on Unit-Disk graphs". Ces problèmes apparaissent dans les défis industriels tels que le chargement intelligent des véhicules électriques. L'objectif est de comprendre pourquoi et comment on peut s'attendre à ce qu'une approche quantique résolve ce problème plus efficacement qu'une méthode classique. Les algorithmes que nous proposons sont testés sur un véritable à l'aide d'un ensemble de données provenant d'EDF, la compagnie française d'électricité. Nous explorons en outre l'utilisation d'atomes neutres en 3D pour résoudre des problèmes qui sont hors de portée des méthodes d'approximation classiques. Enfin, nous essayons d'améliorer notre intuition sur les types d'instances pour lesquelles une approche quantique peut (ou ne peut pas) donner de meilleurs résultats que les méthodes classiques. Dans la deuxième partie de cette thèse, nous explorons l'utilisation de la dynamique quantique dans le domaine de l'apprentissage automatique. En plus d'être une grande chaîne de mots à la mode, l'apprentissage automatique quantique (QML) a été de plus en plus étudié ces dernières années. Dans cette partie, nous proposons et mettons en œuvre un protocole quantique pour l'apprentissage automatique sur des ensembles de données de graphes, et nous montrons des résultats prometteurs en ce qui concerne la complexité de l'espace de caractéristiques associé. Enfin, nous explorons l'expressivité des modèles d'apprentissage automatique quantique et présentons des exemples où les méthodes classiques peuvent approximer efficacement les modèles d'apprentissage automatique quantique.
Informatique quantique pour la recherche opérationnelle : une approche spéciale pour ordonnancement de projet Le calcul quantique, avec son potentiel profond, a suscité une attention significative ; cependant, son intégration dans la Recherche Opérationnelle (RO) reste naissante. Cette dissertation tente de combler cette lacune en introduisant des algorithmes innovants ancrés dans les principes du calcul quantique pour s'attaquer aux problèmes d'optimisation discrets. La première partie se concentre sur les fondamentaux du calcul quantique et analyse l'algorithme de Grover. Peut-être l'algorithme quantique le plus important, qui est renommé pour son accélération quadratique dans les recherches non structurées. En tirant parti de l'algorithme de Grover, l'étude présente une procédure qui résout efficacement le problème du sac à dos binaire, surmontant des défis souvent négligés dans la littérature sur le calcul quantique.Dans la seconde partie, la thèse affine la performance des algorithmes développés dans le premier chapitre, introduisant deux procédures novatrices : un algorithme hybride de branchement et de bornage et un algorithme d'ascension aléatoire. Ces procédures se révèlent capables d'égaler la performance des algorithmes classiques leaders sur 66000 instances du problème du sac à dos binaire. Notablement, elles étendent leur applicabilité aux problèmes d'optimisation discrets manquant de structures claires, démontrant le potentiel des approches inspirées par le quantique.Dans la troisième partie, l'exploration s'étend à l'examen des limites des algorithmes quantiques existants dans la résolution des problèmes d'optimisation discrets. L'étude évalue de manière critique les algorithmes de comptage quantique, ainsi que les variantes de l'algorithme de Grover telles que la recherche quantique imbriquée, les marches quantiques, et l'algorithme d'amplification d'amplitude, révélant des instances où les contreparties classiques peuvent dominer.Dans la quatrième partie de cette dissertation, nous explorons une avenue prometteuse du calcul quantique pour résoudre des problèmes complexes d'optimisation combinatoire, appelée recuit quantique, et nous l'utilisons spécifiquement pour résoudre le Problème d'Ordonnancement de Projets avec Contraintes de Ressources (RCPSP). Formulant le RCPSP à la fois comme un problème d'Optimisation Binaire Quadratique non contrainte (QUBO) et un modèle Hamiltonien d'Ising, l'étude emploie l'annealeur quantique D-Wave Advantage 6.3 disponible commercialement, appliqué aux instances RCPSP du générateur aléatoire RANGEN1. Les évaluations comparatives contre les solveurs classiques et les algorithmes métaheuristiques affirment le potentiel du recuit quantique, particulièrement pour les instances RCPSP de taille petite à moyenne. Le paysage diversifié de solutions qu'il offre fait du recuit quantique un candidat convaincant pour des algorithmes d'optimisation hybrides, promettant d'améliorer la qualité des solutions.Cette thèse exhaustive contribue à la compréhension théorique et aux applications pratiques du calcul quantique en Recherche Opérationnelle, démontrant son potentiel à révolutionner les méthodologies de résolution de problèmes.Le chapitre cinq de cette thèse explore une nouvelle bibliothèque open-source Python dédiée à l'ordonnancement de projets appelée cheche-pm, qui incorpore et rend disponibles des méthodes d'ordonnancement issues de la littérature pour résoudre le RCPSP et ses variantes. Cette bibliothèque se concentre sur l'apport d'une collection complète de méthodes d'ordonnancement à la fois aux praticiens et aux chercheurs. L'utilisation de cette bibliothèque a été cruciale pour le développement du quatrième chapitre de cette thèse.Enfin, le chapitre six explore l'utilisation d'une implémentation hybride quantique et classique du recuit quantique pour résoudre un cas spécial du problème semi-affectation quadratique QSAP, dans le contexte