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.
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.
La recherche en informatique quantique a pris de l’ampleur dans les deux dernières décennies, notamment grâce aux financements massifs des gouvernements et de l’industrie dans les technologies quantiques. L’ordinateur quantique promet de résoudre des problèmes qui jusqu’à présent restaient insurmontables à cause du temps déraisonnable qu’il faudrait pour les résoudre sur les ordinateurs classiques les plus puissants. L’idée de l’ordinateur quantique consiste à utiliser des propriétés quantiques de la matière, telles que l’intrication et la superposition quantique des états, pour effectuer des calculs d’une nouvelle manière. L’informatique quantique requiert un nouveau type d’ordinateur où les bits d’information classique, généralement représentés par la présence ou non de courant à l’entrée d’un transistor, sont remplacés par des bits quantiques aussi appelés qubits, et qui sont représentés par l’état d’un système quantique. De plus, il est nécessaire de développer de nouveaux algorithmes capables d’être implémentés sur un ordinateur quantique et capables de tirer parti de l’avantage quantique. Cette thèse porte sur ces deux composantes complémentaires : la construction de portes logiques, un bloc fondamental de tout ordinateur, et la création de meilleurs algorithmes pour résoudre des problèmes pertinents sur ces machines. Parmi les plateformes les plus avancées pour l’ordinateur quantique, on trouve les circuits supraconducteurs, qui sont la plateforme sur laquelle ont misé Google, IBM, Alice&Bob, Nord Quantique et bien d’autres compagnies. Malgré les avancées des dernières décennies, de nombreux défis restent à être relevés pour que les machines existantes soient en mesure de résoudre des problèmes pertinents et surpassent les ordinateurs classiques. L’un des défis auquel cette thèse s’attaque est la réalisation de portes logiques à deux qubits rapides et à haute fidélité. La rapidité est cruciale pour pouvoir réaliser le plus d’opérations possible avant que les qubits ne perdent leur cohérence quantique, et une haute fidélité est requise pour minimiser les erreurs de calcul et permettre d’implémenter de la correction d’erreurs quantiques. De plus, certains qubits supraconducteurs sont connus pour être affectés par une interaction indésirable, l’interaction ZZ qui, même si relativement faible, affecte la fidélité des portes logiques quantiques, empêchant d’atteindre des fidélités supérieures à 99.9% nécessaires à la correction d’erreurs. En parallèle avec l’amélioration des composantes de l’ordinateur quantique, il est important de développer des applications pour ce nouveau type de machine. Parmi les approches étudiées, les algorithmes quantiques variationnels (VQA) sont ceux qui sont les plus susceptibles d’être déployés sur les ordinateurs quantiques de petites tailles existants. Ce sont des algorithmes hybrides qui nécessitent à la fois de la puissance de calcul classique et quantique. Ces algorithmes semblent prometteurs pour résoudre de nombreux problèmes concrets d’intérêt industriel, comme obtenir les propriétés de molécules ou trouver les solutions de problèmes d’optimisation combinatoire. En effet, ces problèmes peuvent être formulés sous forme d’un Hamiltonien et résolus en déterminant son état fondamental. Dans ce but, les VQAs utilisent un circuit quantique paramétré appelé ansatz, dont les paramètres sont optimisés pour s’approcher de l’état fondamental. Un premier défi consiste à trouver un ansatz qui permette, pour un problème donné, de converger le plus efficacement possible vers la solution. Un deuxième défi est de trouver un circuit fait de portes logiques facilement implémentables sur les plateformes physiques actuelles. Les travaux effectués dans cette thèse apportent des contributions à ces deux défis. Dans la première partie de la thèse, nous introduisons le dispositif que nous avons conçu et qui permet de réaliser des portes d’intrication paramétrique entre deux qubits supraconducteurs. Cette approche a permis à nos collaborateurs du groupe d’Andrew Houck de l’Université de Princeton de réaliser expérimentalement une opération de type √iSWAP en 15 ns avec une fidélité de 98.8%, et ce dans un dispositif où l’interaction ZZ est supprimée. Dans la seconde partie de la thèse, nous avons développé un ansatz pour les VQAs permettant de résoudre le modèle de Fermi Hubbard. Ce nouvel ansatz utilise les avantages de deux ansätze préexistants, et permet d’obtenir l’énergie et l’état fondamental du FHM avec une précision de plusieurs ordres de grandeur supérieure aux ansätze standards, et ce en réduisant significativement le nombre de portes d’intrication CNOT qui sont généralement imparfaites et longues à implémenter.
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
En exploitant à la fois les ressources classiques et quantiques, les algorithmes variationnels quantiques peuvent exécuter des tâches computationnelles complexes sur des ordinateurs quantiques bruités, sans nécessiter de correction d'erreurs. Ces algorithmes visent notamment à résoudre des problèmes d'optimisation combinatoire, se plaçant ainsi en concurrence avec des algorithmes classiques perfectionnés au fil des décennies. Une approche complémentaire consiste à se tourner vers des problèmes intrinsèquement plus complexes: les problèmes de dénombrement. Ces derniers, qui consistent à compter le nombre de solutions aux problèmes de décision, pourraient se révéler plus accessibles aux algorithmes variationnels quantiques qu'aux algorithmes classiques. Dans le cadre de ce mémoire, un algorithme surnommé VQCount est introduit pour la résolution de problèmes de dénombrement. VQCount s'appuie sur l'équivalence entre l'échantillonnage aléatoire et le comptage approximatif pour estimer le nombre de solutions à un facteur multiplicatif près, en exploitant l'ansatz quantique à opérateurs alternants comme générateur de solutions. Cette approche nécessite l'échantillonnage d'un nombre polynomial de solutions selon la taille du problème, même lorsque ce dernier possède un nombre exponentiel de solutions, ce qui constitue une amélioration exponentielle par rapport à des travaux précédents. À l'aide de simulations de réseaux de tenseurs, la performance de VQCount avec des circuits de faible profondeur est étudiée sur des instances synthétiques de deux problèmes #P-difficile, positif #1-in-3SAT et positif #NAE3SAT, en employant comme générateurs de solutions l'algorithme quantique d'optimisation approximative ainsi que l'ansatz quantique à opérateurs alternants avec forçage de Grover. Un compromis entre la probabilité de succès et l'uniformité de l'échantillonnage du générateur est observé et exploité pour atteindre un gain en efficacité exponentiel par rapport à l'échantillonnage par rejet naïf. Ces résultats soulignent le potentiel et les limites des algorithmes variationnels quantiques pour le comptage approximatif.
Bruit et capacité d'apprentissage en apprentissage automatique quantique Cette thèse est consacrée à l'exploration de l'interface entre l'informatique quantique et l'apprentissage automatique, en mettant l'accent sur les effets du bruit et de la décohérence. Dans la première partie, nous étudions l'utilisation de systèmes quantiques ouverts pour la réalisation de tâches classiques de reconnaissance des formes. En particulier, nous nous intéressons à l'impact du bruit sur les machines à noyau quantique dans une configuration de calcul à réservoir. Les modèles que nous considérons sont basés sur l'utilisation d'un système quantique de grande taille et non contrôlé, un réservoir, qui est excité par un signal d'entrée à traiter. Des mesures sont ensuite effectuées sur le système et une combinaison linéaire des résultats est optimisée afin de réaliser la tâche souhaitée. Dans le cadre théorique associé aux méthodes à noyau, nous analysons l'effet de la dissipation sur l'expressivité de ces modèles. Nous montrons que le bruit affectant le réservoir peut agir comme une régularisation implicite qui aide à prévenir l'ajustement excessif. Ces résultats sont accompagnés d'une étude numérique d'un ensemble de machines à noyaux bruitées basées sur des chaînes de spins quantiques sujets à de la décohérence, et dont l'évolution markovienne est décrite par une équation maîtresse de type Lindblad. Dans la deuxième partie de la thèse, nous nous concentrons sur les algorithmes quantiques variationnels. Nous y présentons un schéma de simulation classique efficace pour estimer des quantités moyennées à la sortie d'un circuit quantique paramétré dont les paramètres de rotation sont choisis aléatoirement. Nous étudions d'abord les canaux quantiques associés aux moyennes de rotations aléatoires d'un et de deux qubits autour d'un axe Z. Sous certaines hypothèses, nous montrons que ces canaux peuvent être décomposés en sommes convexes de canaux associés à des transformations unitaires de Clifford. Ce résultat peut être interprété comme un effet de décohérence artificiel induit par le choix aléatoire des angles de rotation. Il nous permet construire un schéma de simulation efficace basé sur le célèbre théorème de Gottesman-Knill. Cette méthode permet notamment d'estimer efficacement l'amplitude moyenne du gradient de la fonction de coût par des simulations classiques avec une complexité polynomiale en le nombre de qubits. Elle peut donc être utilisée pour explorer des stratégies de conception de circuits variationnels quantiques permettant d'éviter les difficultés d'entrainement due à une disparition du gradient.