Calcul analogique quantique pour des problèmes combinatoires sur graphes NP-difficile L'objectif principal de cette thèse est de fournir un éclairage théorique de la complexité du calcul quantique en temps continu (QA et AQC), de la compréhension du phénomène physique (AC) qui conduit à l'échec de l'AQC jusqu'à des preuves de performance de QA en temps court et constant. Pour atteindre cet objectif, nous utilisons différents outils analytiques empruntés à la physique théorique, comme l'analyse perturbative des systèmes quantiques et la borne de Lieb-Robinson sur la vitesse de corrélation dans les systèmes quantiques. La manipulation des graphes et la théorie spectrale des graphes sont nécessaires pour obtenir des résultats sur des classes spécifiques de graphes. Nous avons également introduit une nouvelle version paramétrée du QA standard afin d'affiner l'analyse.Tout d'abord, nous souhaitons obtenir une définition mathématique d'un AC afin d'en faciliter la compréhension lors de l'étude d'une classe spécifique de graphes sur lesquels nous souhaitons résoudre le problème de Maximum Cut. En plus de l'appui analytique que nous développons, nous apportons une étude numérique pour justifier la nature plus générale de notre définition par rapport à la précédente. Grâce à une analyse perturbative, nous parvenons à montrer que sur les graphes bipartis, un gap de fermeture exponentielle peut apparaître si le graphe est suffisamment irrégulier. Notre nouvelle définition de l'AC nous permet de remettre en question l'efficacité de l'AQC pour le résoudre malgré le temps d'exécution exponentiellement long que le théorème adiabatique impose pour garantir la solution optimale. Le deuxième axe est consacré à la performance du QA en temps constant court. Bien que le QA soit intrinsèquement non-local, la borne de LR nous permet de l'approximer avec une évolution locale. Une première approche est utilisée pour développer la méthode et montrer la non trivialité du résultat, c'est-à-dire au-dessus du choix aléatoire. Ensuite, nous définissons une notion d'analyse locale en exprimant le ratio d'approximation avec la seule connaissance de la structure locale. Une borne LR fine et adaptative est développée, nous permettant de trouver une valeur numérique du ratio d'approximation surpassant les algorithmes quantiques et classiques (strictement) locaux. Tous ces travaux de recherche ont été poursuivis entre l'équipe QuantumLab d'Eviden et l'équipe Graphes, Algorithmes et Modèles de Calcul (GAMoC) du Laboratoire d'Informatique Fondamentale d'Orléans (LIFO). Le travail numérique a été implémenté en utilisant le langage de programmation Julia ainsi que Python avec le logiciel QAPTIVA d'Eviden pour simuler efficacement l'équation de Schrödinger.
Calcul analogique quantique pour des problèmes combinatoires sur graphes NP-difficile L'objectif principal de cette thèse est de fournir un éclairage théorique de la complexité du calcul quantique en temps continu (QA et AQC), de la compréhension du phénomène physique (AC) qui conduit à l'échec de l'AQC jusqu'à des preuves de performance de QA en temps court et constant. Pour atteindre cet objectif, nous utilisons différents outils analytiques empruntés à la physique théorique, comme l'analyse perturbative des systèmes quantiques et la borne de Lieb-Robinson sur la vitesse de corrélation dans les systèmes quantiques. La manipulation des graphes et la théorie spectrale des graphes sont nécessaires pour obtenir des résultats sur des classes spécifiques de graphes. Nous avons également introduit une nouvelle version paramétrée du QA standard afin d'affiner l'analyse.Tout d'abord, nous souhaitons obtenir une définition mathématique d'un AC afin d'en faciliter la compréhension lors de l'étude d'une classe spécifique de graphes sur lesquels nous souhaitons résoudre le problème de Maximum Cut. En plus de l'appui analytique que nous développons, nous apportons une étude numérique pour justifier la nature plus générale de notre définition par rapport à la précédente. Grâce à une analyse perturbative, nous parvenons à montrer que sur les graphes bipartis, un gap de fermeture exponentielle peut apparaître si le graphe est suffisamment irrégulier. Notre nouvelle définition de l'AC nous permet de remettre en question l'efficacité de l'AQC pour le résoudre malgré le temps d'exécution exponentiellement long que le théorème adiabatique impose pour garantir la solution optimale. Le deuxième axe est consacré à la performance du QA en temps constant court. Bien que le QA soit intrinsèquement non-local, la borne de LR nous permet de l'approximer avec une évolution locale. Une première approche est utilisée pour développer la méthode et montrer la non trivialité du résultat, c'est-à-dire au-dessus du choix aléatoire. Ensuite, nous définissons une notion d'analyse locale en exprimant le ratio d'approximation avec la seule connaissance de la structure locale. Une borne LR fine et adaptative est développée, nous permettant de trouver une valeur numérique du ratio d'approximation surpassant les algorithmes quantiques et classiques (strictement) locaux. Tous ces travaux de recherche ont été poursuivis entre l'équipe QuantumLab d'Eviden et l'équipe Graphes, Algorithmes et Modèles de Calcul (GAMoC) du Laboratoire d'Informatique Fondamentale d'Orléans (LIFO). Le travail numérique a été implémenté en utilisant le langage de programmation Julia ainsi que Python avec le logiciel QAPTIVA d'Eviden pour simuler efficacement l'équation de Schrödinger.
L'objectif principal de cette thèse est de fournir un éclairage théorique de la complexité du calcul quantique en temps continu (QA et AQC), de la compréhension du phénomène physique (AC) qui conduit à l'échec de l'AQC jusqu'à des preuves de performance de QA en temps court et constant. Pour atteindre cet objectif, nous utilisons différents outils analytiques empruntés à la physique théorique, comme l'analyse perturbative des systèmes quantiques et la borne de Lieb-Robinson sur la vitesse de corrélation dans les systèmes quantiques. La manipulation des graphes et la théorie spectrale des graphes sont nécessaires pour obtenir des résultats sur des classes spécifiques de graphes. Nous avons également introduit une nouvelle version paramétrée du QA standard afin d'affiner l'analyse.Tout d'abord, nous souhaitons obtenir une définition mathématique d'un AC afin d'en faciliter la compréhension lors de l'étude d'une classe spécifique de graphes sur lesquels nous souhaitons résoudre le problème de Maximum Cut. En plus de l'appui analytique que nous développons, nous apportons une étude numérique pour justifier la nature plus générale de notre définition par rapport à la précédente. Grâce à une analyse perturbative, nous parvenons à montrer que sur les graphes bipartis, un gap de fermeture exponentielle peut apparaître si le graphe est suffisamment irrégulier. Notre nouvelle définition de l'AC nous permet de remettre en question l'efficacité de l'AQC pour le résoudre malgré le temps d'exécution exponentiellement long que le théorème adiabatique impose pour garantir la solution optimale. Le deuxième axe est consacré à la performance du QA en temps constant court. Bien que le QA soit intrinsèquement non-local, la borne de LR nous permet de l'approximer avec une évolution locale. Une première approche est utilisée pour développer la méthode et montrer la non trivialité du résultat, c'est-à-dire au-dessus du choix aléatoire. Ensuite, nous définissons une notion d'analyse locale en exprimant le ratio d'approximation avec la seule connaissance de la structure locale. Une borne LR fine et adaptative est développée, nous permettant de trouver une valeur numérique du ratio d'approximation surpassant les algorithmes quantiques et classiques (strictement) locaux. Tous ces travaux de recherche ont été poursuivis entre l'équipe QuantumLab d'Eviden et l'équipe Graphes, Algorithmes et Modèles de Calcul (GAMoC) du Laboratoire d'Informatique Fondamentale d'Orléans (LIFO). Le travail numérique a été implémenté en utilisant le langage de programmation Julia ainsi que Python avec le logiciel QAPTIVA d'Eviden pour simuler efficacement l'équation de Schrödinger.
Apprentissage automatique quantique pour les graphes et les séquences : application à la sûreté nucléaire Dans cette thèse, notre objectif est de fournir des solutions moins complexes en utilisant des algorithmes purement quantiques ainsi que des algorithmes d'apprentissage automatique quantique pour traiter des problèmes dans le domaine des études probabilistes de sécurité (EPS) avec un temps raisonnable. Nous abordons les deux aspects du problème des EPS, statique et dynamique. Pour le problème statique, où nous sommes intéressés à trouver toutes les combinaisons d'événements de base du système qui peuvent générer des accidents graves, nous proposons d'obtenir ces combinaisons d'événements de base par un algorithme quantique, en utilisant des graphes orientés au lieu de chercher toutes les solutions d'un problème SAT. Notre contribution est un algorithme quantique qui utilise un nombre linéaire de qubits et grâce à un filtre classique, nous pouvons trouver toutes les combinaisons d'événements de base qui peuvent générer ces accidents. Dans le cas dynamique, où nous sommes intéressés à trouver toutes les séquences accidentelles d'un système, notre principal intérêt est le traitement de ces séquences. Dans le cas classique, afin de trouver toutes ces séquences, nous utilisons le graphe d'état du système et nous cherchons tous les chemins entre l'état courant et tous les états critiques. Comme ce problème est NP-complet, nous proposons une solution quantique pour trouver tous ces chemins. Nous proposons deux algorithmes quantiques, tous les deux basés sur la philosophie des marches quantiques. Le premier algorithme permet de trouver tous les chemins entre un sommet source et plusieurs sommets destination dans un graphe orienté a-cyclique. Cet algorithme utilise N qubits et M portes afin de trouver tous les chemins. Le second est une version hybride du premier, il est capable de traiter de grands graphes même avec un nombre réduit de qubits. Une autre contribution consiste une approche quantique de l'algorithme Dynamic Time Warping (DTW) afin de calculer la similarité entre ces séquences, ainsi qu'une version capable de trouver la meilleure correspondance entre les séquences en utilisant des sous-séquences dont la longueur varie dynamiquement. Nous proposons également une stratégie d'apprentissage pour les modèles de Markov cachés quantiques (QHMM) afin de générer des scénarios accidentels à partir de n'importe quel état initial du système et également pour gérer le système en temps réel. Nous proposons enfin une version améliorée de k-means quantique. La complexité de chaque itération de la version classique de k-means est de O(K × M × N). Dans notre cas, le calcul de toutes les distances entre les observations et les centres des clusters avec un seul circuit quantique, et l'utilisation de l'algorithme de recherche quantique de Grover, nous permet de réduire la complexité à O(log(K × M × N)). Une autre version de l'algorithme des k-means équilibrés quantiques est aussi proposé en utilisant le quantique adiabatique. Enfin, nous proposons une version quantique de l'algorithme Convex-NMF qui est plus rapide que la version classique. Nous concluons cette thèse par une application de nos approches proposées sur un système réel dans le domaine des EPS.
Algorithmes quantiques pour les équations aux dérivées partielles : circuits quantiques et applications physiques Les simulations classiques actuelles des phénomènes physiques présentent de nombreuses limitations, en particulier lorsqu'il s'agit de systèmes complexes tels que les fluides turbulents, les plasmas ou les matériaux quantiques fortement corrélés. Ces simulations rencontrent souvent des difficultés liées à des coûts de calculs élevés, une mise à l'échelle limitée à travers plusieurs dimensions ou échelles temporelles, ainsi qu'à la complexité de capturer des dynamiques intrinsèquement non-linéaires ou chaotiques. Même avec l'accès à des ressources de calcul haute performance (HPC), la résolution précise des dynamiques à fine échelle ou des évolutions sur de longues périodes reste un défi majeur. Le développement de nouvelles méthodes numériques est donc essentiel, tant pour la recherche académique que pour les applications industrielles. Les ordinateurs quantiques émergent comme de nouveaux outils numériques pour l'étude de tels systèmes et la résolution des équations aux dérivées partielles qui les modélisent. Grâce aux propriétés de superposition et d'intrication des qubits, les calculs numériques peuvent être réalisés de manière inédite, offrant des avantages théoriques prometteurs pour certains problèmes. Dans ce contexte, cette thèse contribue au développement et à la compréhension des algorithmes quantiques, allant de la conception de circuits quantiques à la résolution numérique d'équations différentielles partielles et ordinaires. Dans une première partie, des circuits quantiques efficaces sont présentés pour l'implémentation de routines couramment utilisées dans les algorithmes quantiques (opérations multi-contrôlées, préparation d'états quantiques, opérations diagonales), ainsi que pour une nouvelle routine : la transformée de Laplace quantique. Ces routines limitaient l'efficacité des algorithmes quantiques en raison d'implémentations génériques dont la complexité croissait de manière exponentielle avec le nombre de qubits. Désormais, ces tâches peuvent être réalisées à l'aide de circuits quantiques adaptés qui exploitent la structure des problèmes physiques. Dans une seconde partie, des schémas numériques quantiques sont introduits pour résoudre des équations de transport anisotropes et des équations différentielles ordinaires hamiltoniennes non linéaires. Ces schémas se composent de trois étapes (initialisation, évolution et mesure) et reposent sur des approximations en différences finies d'ordre élevé et des formules de Trotterisation. Des protocoles efficaces pour mesurer des grandeurs d'intérêt sont présentés, et une nouvelle analyse numérique, basée sur la norme vectorielle plutôt que sur la norme d'opérateur générique, est introduite. Cette approche permet d'atteindre une précision donnée tout en réduisant le nombre de pas de temps par un facteur qui croît de manière exponentielle avec le nombre de qubits. De plus, une étude de différentes transformations de Madelung non linéaires est présentée afin de résoudre certaines équations fluides sur ordinateur quantique. Les différents résultats de cette thèse sont illustrés par des simulations classiques des algorithmes quantiques ainsi que par des simulations sur des processeurs quantiques actuels. Ce travail pose les bases de la simulation pratique de systèmes physiques classiques, aussi bien sur les dispositifs quantiques actuels de type NISQ (noisy intermediate-scale quantum) que sur les futurs ordinateurs quantiques tolérants aux erreurs.
Algorithmes quantiques pour la méthode de Monte Carlo La méthode de Monte Carlo est un paradigme central de l'algorithmique basée sur l'analyse statistique et sur les techniques d'échantillonnage aléatoire appliquées aux problèmes ayant une interprétation probabiliste. Cette thèse explore les avantages qu'offrirait un ordinateur quantique pour augmenter l'efficacité de cette méthode. Nous étudions dans un premier temps le problème d'estimation de valeurs moyennes par des techniques à temps de calcul minimal. Nous développons de nouveaux algorithmes quantiques pour estimer l'espérance d'une variable aléatoire réelle produite en sortie d'un processus quantique. Les estimateurs que nous construisons procurent une accélération quadratique par rapport au nombre d'échantillons classiques nécessaires pour obtenir une borne d'erreur sous-gaussienne ou une (epsilon,delta)-approximation. Nous décrivons également un cadre théorique fournissant une notion de «temps d'arrêt» pour un processus quantique générant une variable aléatoire. Nous démontrons que le problème d'estimation de la moyenne peut être résolu plus efficacement lorsque le temps d'arrêt moyen du processus sous-jacent est court. Ces résultats sont appliqués au développement d'un algorithme de requête quantique quasi-optimal pour approximer le nombre de triangles dans un graphe. Dans un second temps, nous étudions le problème d'échantillonnage préférentiel et ses applications en optimisation stochastique. Nous construisons un algorithme quantique pour échantillonner plusieurs éléments d'une distribution finie spécifiée par un vecteur de probabilité. Notre approche résout le problème plus général consistant à préparer plusieurs copies d'un état quantique dont les amplitudes sont accessibles via un oracle. L'utilité de ce résultat est illustrée à travers le développement de deux algorithmes hybrides quantiques-classiques basés sur la méthode des poids multiplicatifs et sur l'algorithme du gradient stochastique. Ces deux applications concernent la prédiction en ligne avec conseil d'experts, et la minimisation des fonctions sous-modulaires. La dernière partie de cette thèse est consacrée à l'étude des algorithmes quantiques à mémoire limitée. Nous étudions tout d'abord le problème d'approximation des moments de fréquence dans le modèle de flots de données à passes multiples. Nous construisons un algorithme quantique qui nécessite une quantité de mémoire moindre que les meilleurs algorithmes de streaming classiques possible. Notre méthode repose sur les estimateurs quantiques de moyenne susmentionnés et sur des techniques de simulation de calcul reversible. Nous explorons ensuite certaines limites des algorithmes à mémoire restreinte dans le modèle de requête quantique. Nous développons une nouvelle approche pour obtenir des bornes inférieures temps-mémoire, basée sur une technique récente d'enregistrement des requêtes quantiques. Ce résultat est appliqué au problème de la recherche de paires de collisions dans une fonction aléatoire. Nous démontrons que la complexité en requête quantique de cette tâche augmente lorsque la quantité de mémoire disponible diminue.
Dans cette thèse, notre objectif est de fournir des solutions moins complexes en utilisant des algorithmes purement quantiques ainsi que des algorithmes d'apprentissage automatique quantique pour traiter des problèmes dans le domaine des études probabilistes de sécurité (EPS) avec un temps raisonnable. Nous abordons les deux aspects du problème des EPS, statique et dynamique. Pour le problème statique, où nous sommes intéressés à trouver toutes les combinaisons d'événements de base du système qui peuvent générer des accidents graves, nous proposons d'obtenir ces combinaisons d'événements de base par un algorithme quantique, en utilisant des graphes orientés au lieu de chercher toutes les solutions d'un problème SAT. Notre contribution est un algorithme quantique qui utilise un nombre linéaire de qubits et grâce à un filtre classique, nous pouvons trouver toutes les combinaisons d'événements de base qui peuvent générer ces accidents. Dans le cas dynamique, où nous sommes intéressés à trouver toutes les séquences accidentelles d'un système, notre principal intérêt est le traitement de ces séquences. Dans le cas classique, afin de trouver toutes ces séquences, nous utilisons le graphe d'état du système et nous cherchons tous les chemins entre l'état courant et tous les états critiques. Comme ce problème est NP-complet, nous proposons une solution quantique pour trouver tous ces chemins. Nous proposons deux algorithmes quantiques, tous les deux basés sur la philosophie des marches quantiques. Le premier algorithme permet de trouver tous les chemins entre un sommet source et plusieurs sommets destination dans un graphe orienté a-cyclique. Cet algorithme utilise N qubits et M portes afin de trouver tous les chemins. Le second est une version hybride du premier, il est capable de traiter de grands graphes même avec un nombre réduit de qubits. Une autre contribution consiste une approche quantique de l'algorithme Dynamic Time Warping (DTW) afin de calculer la similarité entre ces séquences, ainsi qu'une version capable de trouver la meilleure correspondance entre les séquences en utilisant des sous-séquences dont la longueur varie dynamiquement. Nous proposons également une stratégie d'apprentissage pour les modèles de Markov cachés quantiques (QHMM) afin de générer des scénarios accidentels à partir de n'importe quel état initial du système et également pour gérer le système en temps réel. Nous proposons enfin une version améliorée de k-means quantique. La complexité de chaque itération de la version classique de k-means est de O(K × M × N). Dans notre cas, le calcul de toutes les distances entre les observations et les centres des clusters avec un seul circuit quantique, et l'utilisation de l'algorithme de recherche quantique de Grover, nous permet de réduire la complexité à O(log(K × M × N)). Une autre version de l'algorithme des k-means équilibrés quantiques est aussi proposé en utilisant le quantique adiabatique. Enfin, nous proposons une version quantique de l'algorithme Convex-NMF qui est plus rapide que la version classique. Nous concluons cette thèse par une application de nos approches proposées sur un système réel dans le domaine des EPS.
Vers des algorithmes quantiques efficaces pour l'optimisation et l'échantillonnage Récemment, avec l'avènement du big data et de l'apprentissage machine à grande échelle, il y a eu une demande croissante pour des algorithmes quantiques qui seraient plus directement applicables à des problèmes pertinents en pratique. Dans cette thèse, nous présentons trois algorithmes qui visent à nous rapprocher de cet objectif. Premièrement, nous développons un algorithme quantique pour l'optimisation cornettique, une classe de problèmes d'optimisation qui se situe entre les programmes linéaires et semi-définis en termes d'expressivité et de facilité de résolution. Ces problèmes sont le plus souvent résolus avec l'aide d'une méthode de point intérieur, dont la complexité est principalement imposée par le coût de la résolution d'une série de systèmes linéaires. Dans notre algorithme, nous résolvons ces systèmes linéaires de manière approximative à l'aide d'un algorithme quantique, et nous prouvons que la méthode des points intérieurs qui en résulte converge vers la solution correcte en un même nombre d'itérations. Nous donnons des preuves numériques que l'algorithme fournit des accélérations de bout en bout dans certaines applications de faible précision telles que les machines à vecteurs de support et l'optimisation de portefeuille financier. L'algorithme des systèmes linéaires quantiques que nous utilisons est le résultat d'une longue ligne de recherche engendrée par l'algorithme de système linéaire quantique de Harrow, Hassidim et Lloyd. Bien qu'il ait été prouvé qu'il est asymptotiquement optimal, le circuit correspondant compliqué et nécessite un prétraitement classique. La deuxième contribution de cette thèse est un algorithme quantique amélioré pour les systèmes linéaires, basé sur la méthode classique optimale de l'itération de Chebyshev. Enfin, nous observons que les algorithmes susmentionnés ont la propriété commune d'approximer l'unique vraie solution du problème donné. En général, la conception de tels algorithmes quantiques est difficile, car souvent la seule façon de récupérer (une approximation de) la vraie solution est d'exécuter l'algorithme plusieurs fois (soit naïvement, soit par amplification d'amplitude) et de calculer certaines statistiques (par exemple la moyenne) des sorties mesurées. Si les ordinateurs quantiques donnent intrinsèquement accès à l'échantillonnage de leurs sorties, pourrions-nous les exploiter pour accélérer les problèmes d'échantillonnage classiques? De manière surprenante, il s'avère que l'échantillonnage gaussien n'est pas un problème complètement résolu, même sur les ordinateurs classiques. Notre troisième contribution est un algorithme de Monte Carlo Hamiltonien classique pour l'échantillonnage gaussien dans le modèle d'interrogation du premier ordre. Nous surmontons et contournons plusieurs limites inférieures en prenant des étapes longues et aléatoires pour intégrer le hamiltonien au cœur de l'algorithme.