Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Distributed randomized and quantum algorithms for cycle detection in networks

Maël Luce

Published Dec 17, 2024• 0 citations
Publisher

Abstract

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.

DOI
10.70675/1e5e2a18z592dz43eaz9c40zc7d470d88915

Related papers

Quantum algorithms for the Monte Carlo method

Yassine Hamoudi

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.

•Jul 7, 2021•0 citations

Quantum property testing and algebraic topology

Dániel Szabó

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é.

•Sep 9, 2025•0 citations

Quantum machine learning approaches for graphs and sequences : application to nuclear safety assessment

Ahmed Zaiou

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.

•Dec 9, 2022•1 citation

Classical and quantum cryptanalysis for Euclidean lattices and subset sums

Yixin Shen

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.

•May 11, 2021•0 citations

Apprentissage artificiel quantique

Kaoutar Benlamine

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é.

•Nov 3, 2020•2 citations

Towards efficient quantum algorithms for optimization and sampling

Dániel Szilágyi

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.

•Oct 20, 2022•0 citations
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é.
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.
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.
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é.
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.