Algorithmes randomisés et quantiques pour la détection de cycle dans les réseaux distribués Détecter la présence de sous-structures spécifiques (e.g. de cycles de longueur donnée) est un problème standard dans les réseaux d'algorithmique distribuée. Cette thèse se concentre sur la détection distribuée de cycles de longueur paire, c'est-à-dire décider si le réseau contient un cycle de longueur 2k comme sous-graphe, pour tout k\geq 2. Cette collection de problèmes (un pour chaque k) est étudiée à la fois en algorithmique distribuée randomisée et quantique, dans les variants correspondant du modèle \CONGEST. Dans le modèle randomisé, la meilleure borne inférieure connue pour décider C_{2k}-freeness dans le modèle \CONGEST est \tilde Omega(\sqrt n) rondes, et, avant notre travail, la meilleure borne supérieure générale pour le problème s'appliquant à tout k\geq 2 était \tilde O(n^{1-\nicefrac{1}{\theta(k^2)}}) rondes [Eden et al., 2022]. Un algorithme plus rapide existait cependant, mais seulement pour les petites valeurs de k, à savoir pour 2\leq k\leq 5, avec une complexité en rondes de O(n^{1-\nicefrac{1}{k}}) [Censor-Hillel et al., 2020]. Ce dernier algorithme se base sur une technique originale que nous appelons la technique \emph{Local Threshold}. Nous démontrons que la technique Local Threshold ne peut être étendue pour détecter efficacement les 2k-cycles pour k\geq 6 dans le modèle \CONGEST randomisé. Néanmoins, nous démontrons qu'elle peut tout de même être utilisée pour décider l'absence de certaines \emph{familles} de cycles de longueur paire. Par exemple, en utilisant cette technique, nous démontrons que \{C_{12},C_{14}\}-freeness peut être décidé en O(n^{1-\nicefrac{1}{7}) rondes. D'une façon similaire, la technique Local Threshold peut aussi décider \{C_{4\ell}\mid 1\leq \ell \leq k\}-freeness (resp. \{C_{4\ell+2} \mid 1\leq \ell \leq k\}-freeness) en O(n^{1-\nicefrac{1}{2k}}) (resp. O(n^{1-\nicefrac{1}{(2k+1)}})) rondes. Une des deux principales contributions de cette thèse est l'élaboration de la technique \emph{Global Threshold}, pour détecter les 2k-cycles en O(n^{1-\nicefrac{1}{k}}) rondes pour tout k\geq 2. Cette technique consiste grossièrement à fusionner toutes les sous-routines de recherche utilisée dans la technique Local Threshold en une seule recherche, pour laquelle un seuil peut être fixé pour chaque valeur de k\geq 2. La seconde contribution technique de cette thèse est la quantization de notre algorithme randomisé pour décider C_{2k}-freeness. Nous démontrons, grâce à une nouvelle technique distribuée d'amplification quantique Monte-Carlo, que pour tout k\geq 2, C_{2k}-freeness peut être décidé en \tilde O(n^{\nicefrac{1}{2}-\nicefrac{1}{2k}}) rondes. Similairement, pour tout k\geq 1, C_{2k+1}-freeness peut être décidé par un algorithme quantique s'exécutant en \tilde O(\sqrt n) rondes dans le modèle \CONGEST, améliorant ainsi quadratiquement la complexité de la détection de cycles de longueur impaire plus strictement plus grande que 3, comparé au cadre randomisé. Nous établissons également des bornes inférieures, à savoir \tilde\Omega(\sqrt{n}) pour détecter les cycles de longueur paire strictement plus grande que 3, s'alignant sur notre borne supérieure, et \tilde\Omega(n^{\nicefrac{1}{4}}) pour la détection de cycle de longueur paire.
Algorithmes randomisés et quantiques pour la détection de cycle dans les réseaux distribués Détecter la présence de sous-structures spécifiques (e.g. de cycles de longueur donnée) est un problème standard dans les réseaux d'algorithmique distribuée. Cette thèse se concentre sur la détection distribuée de cycles de longueur paire, c'est-à-dire décider si le réseau contient un cycle de longueur 2k comme sous-graphe, pour tout k\geq 2. Cette collection de problèmes (un pour chaque k) est étudiée à la fois en algorithmique distribuée randomisée et quantique, dans les variants correspondant du modèle \CONGEST. Dans le modèle randomisé, la meilleure borne inférieure connue pour décider C_{2k}-freeness dans le modèle \CONGEST est \tilde Omega(\sqrt n) rondes, et, avant notre travail, la meilleure borne supérieure générale pour le problème s'appliquant à tout k\geq 2 était \tilde O(n^{1-\nicefrac{1}{\theta(k^2)}}) rondes [Eden et al., 2022]. Un algorithme plus rapide existait cependant, mais seulement pour les petites valeurs de k, à savoir pour 2\leq k\leq 5, avec une complexité en rondes de O(n^{1-\nicefrac{1}{k}}) [Censor-Hillel et al., 2020]. Ce dernier algorithme se base sur une technique originale que nous appelons la technique \emph{Local Threshold}. Nous démontrons que la technique Local Threshold ne peut être étendue pour détecter efficacement les 2k-cycles pour k\geq 6 dans le modèle \CONGEST randomisé. Néanmoins, nous démontrons qu'elle peut tout de même être utilisée pour décider l'absence de certaines \emph{familles} de cycles de longueur paire. Par exemple, en utilisant cette technique, nous démontrons que {C_{12},C_{14}}-freeness peut être décidé en O(n^{1-\nicefrac{1}{7}) rondes. D'une façon similaire, la technique Local Threshold peut aussi décider {C_{4\ell}\mid 1\leq \ell \leq k}-freeness (resp. {C_{4\ell+2} \mid 1\leq \ell \leq k}-freeness) en O(n^{1-\nicefrac{1}{2k}}) (resp. O(n^{1-\nicefrac{1}{(2k+1)}})) rondes. Une des deux principales contributions de cette thèse est l'élaboration de la technique \emph{Global Threshold}, pour détecter les 2k-cycles en O(n^{1-\nicefrac{1}{k}}) rondes pour tout k\geq 2. Cette technique consiste grossièrement à fusionner toutes les sous-routines de recherche utilisée dans la technique Local Threshold en une seule recherche, pour laquelle un seuil peut être fixé pour chaque valeur de k\geq 2. La seconde contribution technique de cette thèse est la quantization de notre algorithme randomisé pour décider C_{2k}-freeness. Nous démontrons, grâce à une nouvelle technique distribuée d'amplification quantique Monte-Carlo, que pour tout k\geq 2, C_{2k}-freeness peut être décidé en \tilde O(n^{\nicefrac{1}{2}-\nicefrac{1}{2k}}) rondes. Similairement, pour tout k\geq 1, C_{2k+1}-freeness peut être décidé par un algorithme quantique s'exécutant en \tilde O(\sqrt n) rondes dans le modèle \CONGEST, améliorant ainsi quadratiquement la complexité de la détection de cycles de longueur impaire plus strictement plus grande que 3, comparé au cadre randomisé. Nous établissons également des bornes inférieures, à savoir \tilde\Omega(\sqrt{n}) pour détecter les cycles de longueur paire strictement plus grande que 3, s'alignant sur notre borne supérieure, et \tilde\Omega(n^{\nicefrac{1}{4}}) pour la détection de cycle de longueur paire.
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.
Test de propriétés quantique et topologie algébrique Cette thèse explore la puissance et les limitations du calcul quantique en développant de nouveaux algorithmes classiques et quantiques, ainsi qu'en établissant des bornes inférieures. Au passage, nous revisitons des résultats existants et les étendons à de nouveaux contextes. Nous utilisons deux types de modèles algorithmiques : les algorithmes d'approximation et les tests de propriété. Les problèmes étudiés se répartissent en deux catégories principales. La première est motivée par l'analyse topologique des données que nous abordons sous l'angle de la topologie algébrique. Ici, l'entrée est un complexe simplicial, qui modélise des relations de haute dimension dans les données. L'objectif est d'estimer le nombre de « trous » de haute dimension - formellement, les nombres de Betti, ou les rangs des groupes d'homologie du complexe. Un algorithme quantique efficace était déjà connu pour estimer de manière additive les nombres de Betti normalisés en haute dimension. Nous complétons ce résultat en fournissant une solution classique : un algorithme probabiliste de Monte Carlo à intégrale de chemin. Alors que l'algorithme quantique est efficace lorsque la précision souhaitée et l'écart spectral du laplacien combinatoire sont inversement polynomiaux, notre algorithme probabiliste est efficace dans un régime de paramètres plus restreint - en particulier, lorsque la précision et l'écart spectral sont constants. Pour le cas particulier des complexes de cliques, nous proposons une extension de ce régime. Dans les tests (probabilistes) de propriétés, il suffit que l'algorithme distingue avec une forte probabilité les entrées qui satisfont une certaine propriété de celles qui sont « éloignées » (selon une certaine distance et un paramètre) de toute entrée qui la satisfait. Nous étudions également un problème de test de propriété en analyse topologique de données : déterminer si un complexe de cliques a un nombre de Betti élevé (sur le corps fini à deux éléments), ou s'il est éloigné de tout tel complexe. Nous montrons qu'un nombre constant de requêtes suffit à résoudre ce problème pour les complexes de cliques si la dimension et le paramètre de proximité sont constants. La seconde classe de problèmes est liée au problème des k-collisions, où le but est de détecter si une chaîne de caractères contient k-uplets de caractères identiques. Nous formalisons cela comme un problème de test de propriété : distinguer les entrées sans k-collisions de celles qui en sont éloignées. Alors que la complexité classique de ce problème est établie, le cas quantique restait ouvert, avec seulement des bornes inférieures et supérieures partielles connues dans ce cadre. Nous généralisons un algorithme quantique connu pour le problème des k-collisions à un problème de test de la propriété de non-présence de sous-graphes dans le modèle orienté à degré borné. Nous prouvons ensuite une borne inférieure en utilisant la méthode polynomiale duale, étendant des résultats antérieurs à un cadre plus général. Enfin, nous présentons quelques problèmes de test de propriétés de graphes, parmi lesquels la version test de la 3-colorabilité, et montrons qu'ils ont une complexité de requête quantique asymptotiquement maximale dans le modèle à degré borné.
Cryptanalyse classique et quantique pour les réseaux euclidiens et le problème de la somme de sous-ensembles La cryptographie post-quantique est une branche de la cryptographie qui vise à concevoir des systèmes cryptographiques non quantiques (c'est-à-dire classiques), qui sont protégés contre un adversaire possédant un ordinateur quantique. Dans cette thèse, nous nous concentrons sur l'étude de deux problèmes fondamentaux pour la cryptographie post-quantique : le problème du plus court vecteur (SVP) et le problème de la somme de sous-ensembles aléatoires. Le SVP demande de trouver le plus court vecteur non nul d'un réseaux euclidien donné. Il sert de jauge pour quantifier la sécurité de la cryptographie reposant sur les réseaux euclidiens, qui est considérée comme prometteuse pour l'ère post-quantique. Les principales approches pour résoudre le SVP sont les algorithmes de tamisage, qui utilisent un temps et un espace exponentiels, et les algorithmes d'énumération, qui utilisent un temps superexponentiel et un espace polynomial. Dans cette thèse, nous donnons tout d'abord un compromis temps-mémoire prouvable qui interpole approximativement entre les garanties de ressources des algorithmes de tamisage et celles des algorithmes d'énumération. Nous montrons ensuite l'algorithme quantique prouvable le plus rapide connu qui résout le SVP en temps 2^(0.9535n) et en mémoire classique 2^(0.5n+o(n)) avec seulement un nombre poly(n) de qubits. Nous montrons également le meilleur algorithme prouvable classique connu dont la complexité en mémoire est de 2^(0.5n+o(n)). Quant aux algorithmes d'énumération, on pensait auparavant qu'ils pouvaient bénéficier d'une accélération quadratique quantique grâce à l'algorithme de Grover. Nous montrons que cette accélération quadratique peut effectivement être obtenue pour l'algorithme d'énumération de base et ses variantes d'élagage cylindrique et discret, mais avec des algorithmes quantiques plus sophistiqués tels que la marche quantique sur les arbres. Notre accélération quantique s'applique également à l'élagage extrême où l'on répète le processus d'énumération sur plusieurs bases réduites. Le problème de la somme de sous-ensembles aléatoires sous-tend également certains schémas cryptographiques visant à la sécurité post-quantique, bien qu'il soit principalement de nature académique. Dans un contexte de cryptanalyse, il sert souvent d'outil car de nombreux problèmes sur lesquels se fonde la cryptographie moderne peuvent être exprimés comme des variantes (vectorielles) du problème de la somme de sous-ensembles. Plus récemment, il a également été démontré qu'il peut être utilisé comme élément de base dans certains algorithmes de décalage caché quantique, qui ont des applications dans la cryptanalyse quantique de schémas symétriques et de schémas reposant sur les isogénies. Dans cette thèse, nous présentons de nouveaux algorithmes classiques et quantiques pour la résolution du problème de la somme de sous-ensembles aléatoires. Nous obtenons d'abord l'algorithme classique le plus rapide connu en temps Õ(2^0.283n)). Ensuite, nous améliorons l'état de l'art des algorithmes quantiques pour ce problème dans plusieurs directions. Nous concevons un algorithme avec un temps asymptotique Õ(2^0.236n), avec l'avantage d'utiliser une mémoire classique avec accès aléatoire quantique. Les algorithmes connus précédemment utilisaient des marches quantique, et nécessitaient une mémoire quantique avec accès aléatoire quantique.Nous proposons également des marches quantiques plus rapides pour ce problème en temps Õ(2^0.216n). Ce temps dépend d'une heuristique concernant le temps de mise à jour dans les marches quantiques. Les algorithmes précédents pour ce problème dépendaient eux aussi de cette heuristique. Nous montrons comment surmonter partiellement cette heuristique, et nous obtenons un algorithme quantique de temps Õ(2^0.218n) ne nécessitant que les heuristiques standard du problème de la somme de sous-ensembles aléatoires.
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.
Cette thèse se situe à la frontière entre l’informatique quantique et l’apprentissage artificiel et a pour objectif le traitement des données dans de très grandes dimensions. L’apprentissage artificiel quantique est un nouveau domaine d’étude avec de récents travaux sur les versions quantiques d’algorithmes supervisés et non supervisés. Ces dernières années, de nombreux algorithmes d’apprentissage artificiel quantique ont été proposés afin d’améliorer le temps de traitement des algorithmes classiques. La première contribution de cette thèse est de donner un aperçu sur le domaine quantique dans l’apprentissage artificiel. Ensuite, la quantification des algorithmes classiques. Nous avons proposé une analyse et une comparaison des différentes distances pour les algorithmes de clustering basés sur des prototypes. Pour un ordinateur conventionnel, calculer les distances euclidiennes est facile, mais le faire de la même manière sur un ordinateur quantique serait beaucoup plus compliqué et exigerait plus de qubits que ce que nous pouvons nous permettre. Pour définir une distance quantique, nous utiliserons la nature probabiliste des qubits pour mesurer les amplitudes probabiliste. Pour les algorithmes de clustering quantique, les distances sont nécessaires mais ne doivent pas nécessairement être proportionnelles à la distance réelle, elles doivent avoir qu’une corrélation positive avec elle. Tous les algorithmes de clustering basés sur des prototypes pourraient être résolus en utilisant ces distances. En tant qu’application de cette tâche, nous avons présenté une version quantique de K-means qui est un algorithme de clustering basé sur un prototype. Cet algorithme quantique K-means donne une bonne classification tout comme sa version classique, la seule différence réside dans la complexité: alors que la version classique de K-means prend du temps polynomial, la version quantique ne prend que du temps logarithmique surtout en grand ensembles de données. Nous avons également proposé la version quantique de la factorisation matricielle seminon négative ainsi que la version collaborative de ces algorithmes à savoir: K-means quantique collaboratif et la factorisation matricielle semi-non négative quantique collaborative qui se basent sur la combinaison de plusieurs solutions de clustering pour obtenir une meilleure solution en termes de clustering et de complexité.
La physique classique, par son caractère fondamentalement déterministe, ne permet pas la production d’aléa vrai. La physique quantique, quant à elle, fait des prévisions probabilistes, sur des processus qui paraissent fondamentalement aléatoires. De plus, les réponses apportées aux paradoxes de types EPR, comme la réponse formulée par les inégalités de Bell [16] et leurs expérimentations par Alain Aspect, montrent que la physique quantique ne peut être complétée en une théorie entièrement prédictive. Une question émane alors: Quelles sont les expériences quantiques fondamentalement aléatoires ? Cristian S.Calude et Al [4] montrent que presque toutes les mesures quantiques produisent de l’aléa (Théorème Strong Kochen Specker). Dans le cadre de cette thèse, notre but est ainsi de proposer de nouveaux schémas de génération quantique d’aléa (voir [10,13]) basés sur ce caractère aléatoire intrinsèque aux expériences quantiques. Ces protocoles explorent l’utilisation de produits d’observables incompatibles implémentées l’une à la suite de l’autre comme le font les auteurs de [36]. Pour un apport en sécurité à ces protocoles, nous dérivons, à partir d’inégalités de Bell déjà existantes notamment CHSH [28] et CHSH-3 (initialement CGLMP pour qutrits [29]), de nouvelles inégalités. Cette fois-ci, l’on considère des configurations constituées d’un unique Qutrit où la contrainte de commutativité des observables n’est pas imposée. La borne classique est cette fois-ci obtenue sous l’hypothèse du Réalisme macroscopique [51], comme celles des inégalités temporelles [36]. Ces bornes classiques sont égales à celles obtenues dans le cadre du réalisme locale. Cependant, les bornes quantiques, obtenues par SDP, peuvent être plus grandes que celles des expressions originelles permettant ainsi une meilleure résistance au bruit et donc à de potentielles attaques. Ces violations par rapport au cadre classique ne sont plus dues à la non localité mais plutôt au caractère indéfini des résultats de presque toutes les mesures quantiques. Avec les observables et états optimum de ces inégalités, nous donnons des arguments d'auto-test pour nos protocoles. Cette thèse a aussi été l’occasion de revisiter certains aspects de la cryptographie quantique comme la distribution quantique de clé.