Algorithme de recherche par marche quantique sur hypercube : analyse propre et calcul de la probabilité de succès en temps polynomial Les algorithmes de marche quantique à temps discret sont les analogues directs des algorithmes de marche aléatoire classiques, une famille importante en informatique. Ils peuvent résoudre une variété de problèmes, dont le problème NP-complet SAT, en un temps relativement court. Ainsi, l'étude des marches quantiques pourrait amener à la conception de nouveaux algorithmes quantiques. Parmi les algorithmes quantiques, l'un des plus étudiés est l'algorithme de recherche de Grover, un processus itératif qui peut trouver un élément parmi N qui répond à un certain critère, avec un gain de temps quadratique par rapport à n'importe quel algorithme classique. Dans cette thèse, on étudie la variante de l'algorithme de recherche de Grover proposée par Shenvi, Kempe et Whaley, basée sur les marches sur les graphes hypercubes. Comme les algorithmes de recherche sont des processus itératifs, il faut calculer le nombre correct d'étapes R avant de lancer la recherche, car la probabilité de succès diminue au-delà d'un certain point. La valeur de R dépend du nombre d'éléments N, mais aussi du nombre de solutions M. Pour l'algorithme de Grover, le nombre optimal d'itérations est bien connu, mais ce n'est pas le cas pour la recherche sur l'hypercube dès qu'il y a plusieurs solutions. Dans cette thèse, on propose une analyse propre exhaustive de l'algorithme de recherche sur l'hypercube, qui conduit à une procédure permettant de calculer la probabilité de succès de l'algorithme de recherche sur l'hypercube sans l'exécuter, en temps polynomial.
Algorithme de recherche par marche quantique sur hypercube : analyse propre et calcul de la probabilité de succès en temps polynomial Les algorithmes de marche quantique à temps discret sont les analogues directs des algorithmes de marche aléatoire classiques, une famille importante en informatique. Ils peuvent résoudre une variété de problèmes, dont le problème NP-complet SAT, en un temps relativement court. Ainsi, l'étude des marches quantiques pourrait amener à la conception de nouveaux algorithmes quantiques. Parmi les algorithmes quantiques, l'un des plus étudiés est l'algorithme de recherche de Grover, un processus itératif qui peut trouver un élément parmi N qui répond à un certain critère, avec un gain de temps quadratique par rapport à n'importe quel algorithme classique. Dans cette thèse, on étudie la variante de l'algorithme de recherche de Grover proposée par Shenvi, Kempe et Whaley, basée sur les marches sur les graphes hypercubes. Comme les algorithmes de recherche sont des processus itératifs, il faut calculer le nombre correct d'étapes R avant de lancer la recherche, car la probabilité de succès diminue au-delà d'un certain point. La valeur de R dépend du nombre d'éléments N, mais aussi du nombre de solutions M. Pour l'algorithme de Grover, le nombre optimal d'itérations est bien connu, mais ce n'est pas le cas pour la recherche sur l'hypercube dès qu'il y a plusieurs solutions. Dans cette thèse, on propose une analyse propre exhaustive de l'algorithme de recherche sur l'hypercube, qui conduit à une procédure permettant de calculer la probabilité de succès de l'algorithme de recherche sur l'hypercube sans l'exécuter, en temps polynomial.
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.
Le développement de la Théorie du Calcul Quantique provient de l'idée qu'un ordinateur est avant tout un système physique, de sorte que ce sont les lois de la Nature elles-mêmes qui constituent une limite ultime sur ce qui peut être calculé ou non. L'intérêt pour cette discipline fut stimulé par la découverte par Peter Shor d'un algorithme quantique rapide pour factoriser un nombre, alors qu'actuellement un tel algorithme n'est pas connu en Théorie du Calcul Classique. Un autre résultat important fut la construction par Lov Grover d'un algorithme capable de retrouver un élément dans une base de donnée non-structurée avec un gain de complexité quadratique par rapport à tout algorithme classique. Alors que ces algorithmes quantiques sont exprimés dans le modèle ``standard' du Calcul Quantique, où le registre évolue de manière discrète dans le temps sous l'application successive de portes quantiques, un nouveau type d'algorithme a été récemment introduit, où le registre évolue continûment dans le temps sous l'action d'un Hamiltonien. Ainsi, l'idée à la base du Calcul Quantique Adiabatique, proposée par Edward Farhi et ses collaborateurs, est d'utiliser un outil traditionnel de la Mécanique Quantique, à savoir le Théorème Adiabatique, pour concevoir des algorithmes quantiques où le registre évolue sous l'influence d'un Hamiltonien variant très lentement, assurant une évolution adiabatique du système. Dans cette thèse, nous montrons tout d'abord comment reproduire le gain quadratique de l'algorithme de Grover au moyen d'un algorithme quantique adiabatique. Ensuite, nous montrons qu'il est possible de traduire ce nouvel algorithme adiabatique, ainsi qu'un autre algorithme de recherche à évolution Hamiltonienne, dans le formalisme des circuits quantiques, de sorte que l'on obtient ainsi trois algorithmes quantiques de recherche très proches dans leur principe. Par la suite, nous utilisons ces résultats pour construire un algorithme adiabatique pour résoudre des problèmes avec structure, utilisant une technique, dite de ``nesting', développée auparavant dans le cadre d'algorithmes quantiques de type circuit. Enfin, nous analysons la résistance au bruit de ces algorithmes adiabatiques, en introduisant un modèle de bruit utilisant la théorie des matrices aléatoires et en étudiant son effet par la théorie des perturbations.
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.
Discrete time quantum walk algorithms are the direct analogs of classical random walk algorithms, an important family in theoretical informatics. They can solve a variety of problems, in particular the NPcomplete SAT problem, in a relatively short time. Thus, the study of quantum walks could lead to the conception of new quantum algorithms. Among the quantum algorithms, one of the most extensively studied is Grover’s searchalgorithm, an iterative process that can find one element among N that meet a certain criterion, with a quadratic time gain over any classical algorithm. In this thesis, we study the variant of Grover’s search algorithm proposed by Shenvi, Kempe and Whaley, based on walks on hypercube graphs.As search algorithms are iterative processes, one has to compute the correct number of steps R before running the search, as the probability of success decreases past a certain point. The value of R depends on the number of elements N, but also the number of solutions M. For Grover's algorithm, the optimal number of iterations is well known, but this is not the case for the search on the hypercube as soon as there are multiple solutions. In this thesis, we propose an extensive eigenanalysis of the hypercube search algorithm, which leads to a procedure that allows us to compute the probability of success of the search algorithm on the hypercube without running it, in polynomial time.
On sait depuis vingt ans maintenant qu'un ordinateur quantique permettrait de résoudre en temps polynomial plusieurs problèmes considérés comme difficiles dans le modèle classique de calcul, comme la factorisation ou le logarithme discret. Entre autres, un tel ordinateur mettrait à mal tous les systèmes de chiffrement à clé publique actuellement utilisés en pratique, mais sa réalisation se heurte, entre autres, aux phénomènes de décohérence qui viennent entacher l'état des qubits qui le constituent. Pour protéger ces qubits, on utilise des codes correcteurs quantiques, qui doivent non seulement être performants mais aussi munis d'un décodage très rapide, sous peine de voir s'accumuler les erreurs plus vite qu'on ne peut les corriger. Une solution très prometteuse est fournie par des équivalents quantiques des codes LDPC (Low Density Parity Check, à matrice de parité creuse). Ces codes classiques offrent beaucoup d'avantages : ils sont faciles à générer, rapides à décoder (grâce à un algorithme de décodage itératif) et performants. Mais leur version quantique se heurte (entre autres) à deux problèmes. On peut voir un code quantique comme une paire de codes classiques, dont les matrices de parité sont orthogonales entre elles. Le premier problème consiste alors à construire deux « bons » codes qui vérifient cette propriété. L'autre vient du décodage : chaque ligne de la matrice de parité d'un des codes fournit un mot de code de poids faible pour le second code. En réalité, dans un code quantique, les erreurs correspondantes sont bénignes et n'affectent pas le système, mais il est difficile d'en tenir compte avec l'algorithme de décodage itératif usuel. On étudie dans un premier temps une construction existante, basée sur un produit de deux codes classiques. Cette construction, qui possède de bonnes propriétés théoriques (dimension et distance minimale), s'est avérée décevante dans les performances pratiques, qui s'expliquent par la structure particulière du code produit. Nous proposons ensuite plusieurs variantes de cette construction, possédant potentiellement de bonnes propriétés de correction. Ensuite, on étudie des codes dits q-Aires~: ce type de construction, inspiré des codes classiques, consiste à agrandir un code LDPC existant en augmentant la taille de son alphabet. Cette construction, qui s'applique à n'importe quel code quantique 2-Régulier (c'est-À-Dire dont les matrices de parité possèdent exactement deux 1 par colonne), a donné de très bonnes performances dans le cas particulier du code torique. Ce code bien connu se décode usuellement très bien avec un algorithme spécifique, mais mal avec l'algorithme usuel de propagation de croyances. Enfin, un équivalent quantique des codes spatialement couplés est proposé. Cette idée vient également du monde classique, où elle améliore de façon spectaculaire les performances des codes LDPC : le décodage s'effectue en temps quasi-Linéaire et atteint, de manière prouvée, la capacité des canaux symétriques à entrées binaires. Si dans le cas quantique, la preuve éventuelle reste encore à faire, certaines constructions spatialement couplées ont abouti à d'excellentes performances, bien au-Delà de toutes les autres constructions de codes LDPC quantiques proposées jusqu'à présent.
Depuis une dizaine d'annees, le calcul quantique est un domaine de recherche tres actif. Surtout depuis le fameux algorithme de factorisation de nombres en temps polynomial par un ordinateur quantique (shor 95) la recherche dans cette discipline a declenche. Mon travail porte sur deux aspects du calcul quantique lies a l'algorithmique et a la cryptographie quantiques. Algorithmique : nous initions l'etude de la generalisation des marches aleatoires sur les graphes finis au monde quantique. La methode des chaines de markov, basee sur l'echantillonnage rapide d'une distribution probabilistique a permis de resoudre efficacement une grande classe de problemes en informatique classique. En quantique, de telles marches aleatoires ne convergent pas a priori vers une distribution stationnaire. Neanmoins en relaxant les definitions de facon appropriee, nous obtenons des mesures de vitesse pour lesquelles la marche quantique se disperse. Nous etablissons des definitions (comme temps de melange) donnant un sens theorique aux chaines de markov quantiques. Nous demontrons que sur le modele du cercle, les mesures de vitesse de convergence sont quadratiquement plus rapides que dans le cas classique. Nous etablissons des bornes inferieures de l'acceleration quantique sur les graphes generaux. Cryptographie : nous etudions l'enchevetrement quantique sous trois aspects : - nous analysons la possibilite de convertir des etats quantiques enchevetres par des moyens locaux ou encore par l'utilisation d'information stockee cachee : nous montrons que des etats localement iso spectraux ne peuvent pas etre convertis entre eux localement. Ceci donne lieu a un nouveau protocole du secret-sharing. - nous etablissons un nouveau critere pour determiner si un etat quantique donne est enchevetre (base sur la theorie de majoration probabiliste). - nous etudions le comportement d'un modele physique pour le clonage quantique et demontrons son optimalite.