Le problème de décodage quantique : bornes d'atteignabilité et applications à la recherche de mots de code courts Cette thèse repose sur le concept de cryptographie post-quantique, qui a pour objectif de concevoir des cryptosystèmes résistants aux attaques classiques et quantiques. Nous nous concentrons ici sur le problème de décodage (DP) et le problème du court mot de code (SCP) en cryptographie à base de codes. Nous allons étudier comment des algorithmes quantiques peuvent exploiter la structure de ces problèmes. Dans une première partie, nous avons généralisé la borne informationnelle d'atteignabilité du problème de décodage quantique à toutes les distributions de bruit sans mémoire. En combinant ce résultat avec la réduction quantique de Regev, on obtient un algorithme quantique qui échantillonne des mots du code dual dont le poids approche le minimum à la limite d'atteignabilité. Dans un second temps, nous formulons un cadre général pour adapter à la théorie des codes la réduction du problème Learning With Errors (LWE) au problème Extrapolated Dihedral Coset Problem (EDCP). Nous étudions ce cadre dans le cas de la métrique de Hamming binaire et montrons que le régime de paramètres obtenu peut déjà être décodé classiquement en temps polynomial.
Le problème de décodage quantique : bornes d'atteignabilité et applications à la recherche de mots de code courts Cette thèse repose sur le concept de cryptographie post-quantique, qui a pour objectif de concevoir des cryptosystèmes résistants aux attaques classiques et quantiques. Nous nous concentrons ici sur le problème de décodage (DP) et le problème du court mot de code (SCP) en cryptographie à base de codes. Nous allons étudier comment des algorithmes quantiques peuvent exploiter la structure de ces problèmes. Dans une première partie, nous avons généralisé la borne informationnelle d'atteignabilité du problème de décodage quantique à toutes les distributions de bruit sans mémoire. En combinant ce résultat avec la réduction quantique de Regev, on obtient un algorithme quantique qui échantillonne des mots du code dual dont le poids approche le minimum à la limite d'atteignabilité. Dans un second temps, nous formulons un cadre général pour adapter à la théorie des codes la réduction du problème Learning With Errors (LWE) au problème Extrapolated Dihedral Coset Problem (EDCP). Nous étudions ce cadre dans le cas de la métrique de Hamming binaire et montrons que le régime de paramètres obtenu peut déjà être décodé classiquement en temps polynomial.
Structures cachées et cryptanalyse quantique Nous étudions la sécurité de systèmes cryptographiques face à un adversaire muni d'un ordinateur quantique. En algorithmique quantique, nous avons étudié les problèmes de période et de décalage cachés, qui sont les seuls connus à ce jour ayant des applications en cryptographie et pour lesquels le meilleur algorithme quantique connu est plus que polynomialement plus rapide que le meilleur algorithme classique. Nous avons proposé des améliorations, de nouveaux compromis entre temps et mémoire classiques et quantiques, et étendu leur champ d'applications à des cas où seul un oracle classique est accessible. En cryptanalyse, en cryptographie symétrique, nous avons proposé des attaques de constructions symétriques utilisant des décalages cachés, et généralisé moult attaques exploitant des périodes cachées aux cas où l'accès à la construction est classique. Nous avons proposé une cryptanalyse quantique des différentes versions du chiffrement authentifié AEZ ainsi que des versions quantiques de multiples slide attacks, qui sont une famille classique d'attaques. Cette reformulation d'attaques dans le formalisme des périodes cachées nous ont permis de proposer de nouvelles attaques classiques sur différentes variantes du chiffrement MiMC. En cryptographie asymétrique, nous avons proposé une étude concrète et asymptotique de la sécurité quantique de schémas d'échange de clé à base d'isogénies. Enfin, nous avons étudié la sécurité dans des cadres où ces problèmes de structures cachées ne s'appliquent pas, avec la première analyse de sécurité quantique d'AES, le chiffrement symétrique le plus utilisé à l'heure actuelle.
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.
Bruit et capacité d'apprentissage en apprentissage automatique quantique Cette thèse est consacrée à l'exploration de l'interface entre l'informatique quantique et l'apprentissage automatique, en mettant l'accent sur les effets du bruit et de la décohérence. Dans la première partie, nous étudions l'utilisation de systèmes quantiques ouverts pour la réalisation de tâches classiques de reconnaissance des formes. En particulier, nous nous intéressons à l'impact du bruit sur les machines à noyau quantique dans une configuration de calcul à réservoir. Les modèles que nous considérons sont basés sur l'utilisation d'un système quantique de grande taille et non contrôlé, un réservoir, qui est excité par un signal d'entrée à traiter. Des mesures sont ensuite effectuées sur le système et une combinaison linéaire des résultats est optimisée afin de réaliser la tâche souhaitée. Dans le cadre théorique associé aux méthodes à noyau, nous analysons l'effet de la dissipation sur l'expressivité de ces modèles. Nous montrons que le bruit affectant le réservoir peut agir comme une régularisation implicite qui aide à prévenir l'ajustement excessif. Ces résultats sont accompagnés d'une étude numérique d'un ensemble de machines à noyaux bruitées basées sur des chaînes de spins quantiques sujets à de la décohérence, et dont l'évolution markovienne est décrite par une équation maîtresse de type Lindblad. Dans la deuxième partie de la thèse, nous nous concentrons sur les algorithmes quantiques variationnels. Nous y présentons un schéma de simulation classique efficace pour estimer des quantités moyennées à la sortie d'un circuit quantique paramétré dont les paramètres de rotation sont choisis aléatoirement. Nous étudions d'abord les canaux quantiques associés aux moyennes de rotations aléatoires d'un et de deux qubits autour d'un axe Z. Sous certaines hypothèses, nous montrons que ces canaux peuvent être décomposés en sommes convexes de canaux associés à des transformations unitaires de Clifford. Ce résultat peut être interprété comme un effet de décohérence artificiel induit par le choix aléatoire des angles de rotation. Il nous permet construire un schéma de simulation efficace basé sur le célèbre théorème de Gottesman-Knill. Cette méthode permet notamment d'estimer efficacement l'amplitude moyenne du gradient de la fonction de coût par des simulations classiques avec une complexité polynomiale en le nombre de qubits. Elle peut donc être utilisée pour explorer des stratégies de conception de circuits variationnels quantiques permettant d'éviter les difficultés d'entrainement due à une disparition du gradient.
Contextualité quantique, géométries finies & informatique quantique Le développement de machines quantiques de tailles modestes accessibles en ligne permet aujourd'hui de réaliser des expériences sur des calculateurs à distance. L'avantage de l'informatique quantique repose sur des phénomènes strictement non classiques, tels que la superposition et l'intrication, qui sont des ressources maintenant bien connues. Le phénomène non-classique de la contextualité est peut-être moins bien établi bien qu'il ouvre aussi des perspectives très intéressntes à travers de nombreuses applications telles que la cryptographie quantique, les codes d'accès aléatoires, les codes correcteurs d'erreurs et l'avantage du coût de la mémoire pour la simulation des mesures quantiques. L'objectif de cette thèse est triple : développer de nouveaux tests résistants au bruit pour démontrer la contextualité avec des ordinateurs quantiques bruités d'échelle intermédiaire ; concevoir des algorithmes quantiques pour calculer les limites classiques de ces tests, avec une meilleure complexité par rapport aux algorithmes existants ; interpreter les invariants algébriques, utilisés pour distinguer les classes d'intrication, en termes d'observables à base d'opérateurs de Pauli. À ces fins, l'utilisation de configurations géométriques telles que les espaces polaires symplectiques et leurs sous-géométries est largement exploitée, permettant d'établir un lien solide entre le domaine, relativement ancien des géométries finies, et les concepts plus récents de la théorie de l'information quantique. Pour le premier objectif, nous utilisons l'apport de la géométrie pour fournir des tests de contextualité qui violent largement les limites classiques sur tous les ordinateurs quantiques IBM. Ces tests démontrent empiriquement l'absence de modèles à variables cachées non contextuelles décrivant le système sous-jacent. C'est un résultat d'intérêt ontologique. Plus précisément, il s'agit de la première violation connue du jeu de pseudotélépathie de Mermin sur de telles machines, et des plus grandes violations du test de Rio Negro. Concernant le deuxième objectif, nous nous appuyons sur les symétries de nos géométries pour construire un algorithme quantique basé sur l'algorithme de recherche de Grover. Cet algorithme identifie une affectation optimale de variables cachées classiques avec une complexité comparable à l'algorithme de Grover. Un tel avantage algorithmique est intéressant dans une grande famille de problèmes, connus sous le nom de Max Lin 2, où plusieurs contraintes sur un ensemble de données ne peuvent pas être satisfaites simultanément. Ainsi, l'étude de la contextualité - qui peut être vue comme une limitation de la satisfaction logique pour décrire les systèmes physiques - peut apporter de nouvelles perspectives à des problèmes où la satisfaction d'instruction logique simultanée n'est pas viable. Enfin, pour le troisième objectif, nous proposons de nombreuses connexions entre les géométries finies et les invariants algébriques, en commençant par des liens entre les quadrangles généralisés et les invariants cubiques de Cartan, puis en montrant comment les géométries maximalement mixtes permettent de reconstruire les polynômes de Mermin, et finalement en décrivant les sous-ensembles minimaux d'opérateurs de Pauli qui permettent de calculer les hyperdéterminants. On peut ainsi, grâce à ces invariants, identifier la classe d'intrication de systèmes de qubits N=2,3,4 par des mesures sans avoir besoin d'une tomographie complète du système. En résumé dans cette thèse, nous abordons une grande variété de questions à l'intersection de la géométrie finie et de l'informatique quantique - de la conception de tests de contextualité à l'étude de la non-localité à travers des invariants algébriques en passant par le calcul quantique de bornes classiques. Les idées proposées dans ce travail pourront être utiles à la fois pour l'étude des fondements de la mécanique quantique et pour son application à l'informatique quantique.
Décodage des codes expanseurs quantiques et application au calcul quantique tolérant aux fautes Le calcul quantique tolérant aux fautes est un ensemble de techniques dont le but est d'effectuer des calculs quantiques de manière fiable en utilisant des composants bruités. Dans ce contexte, l'utilisation de codes correcteurs quantiques maintient le nombre d'erreurs présentes dans le système en dessous d'un seuil tolérable. L'un des principaux problèmes de ce domaine est d'évaluer le coût minimum (en mémoire et en temps) nécessaire pour transformer un calcul quantique idéal en un calcul tolérant aux fautes. Dans cette thèse, nous montrons que la famille des codes expanseurs quantiques associée à l'algorithme de décodage small-set-flip peut être utilisée dans la construction de ref. [arXiv:1310.2984] pour réaliser du calcul quantique tolérant aux fautes avec coût constant en mémoire. La famille de codes correcteurs ainsi que le décodeur que nous étudions ont été introduits dans ref. [arXiv:1504.00822] où un modèle de bruit adverse est considéré. En nous appuyant sur les résultats de cet article, nous analysons le comportement des codes expanseurs quantiques face à un modèle de bruit stochastique qui est pertinent dans le cadre du calcul tolérant aux fautes [arXiv:1711.08351], [arXiv:1808.03821]. De plus, nous montrons que l'algorithme de décodage peut être parallélisé pour fonctionner en temps constant. Cette propriété est essentielle pour éviter que les erreurs ne s'accumulent pendant que l'algorithme est exécuté. Au-delà des résultats théoriques décrits ci-dessus, nous avons effectué une analyse numérique des codes expanseurs quantiques dans le but d'évaluer leurs performances en pratique [arXiv:1810.03681]. Le modèle de bruit choisi pour ces simulations consiste à générer des erreurs de types X et Z de manière indépendante et identiquement distribuée sur les qubits. Les résultats obtenus pour ces codes de rendement constant sont prometteurs puisque nos simulations montrent que leur seuil est décent et que leurs performances à taille finie sont bonnes.
Décodage efficace de codes quantiques LDPC par passage de messages Pour construire un ordinateur quantique, il est nécessaire de corriger au fur et a mesure les erreurs qui se produisent au cours du calcul, qui, si elles s’accumulent, risquent de biaiser le résultat. Ces erreurs s’accumulent pour deux raisons, premièrement car les technologies utilisées aujourd’hui et dans un futur proche sont encore immatures, et deuxièmement, a cause d’un principe fondamental de la physique quantique, le principe d’incertitude de Hilbert. A cause des contraintes liées aux lois de la physique quantique, les méthodes utilisées pour protéger l’information quantique du bruit sont différentes en quantique comparé au classique. Par exemple, il n’est pas possible de faire des “sauvegardes” régulières sur un ordinateur quantique, a cause du Théorème de non-clonage qui stipule qu’il est impossible de copier parfaitement un état quantique.Par chance, il s’avère que la théorie de la correction d’erreur, utilisée de manière classique surtout dans les communications et le stockage d’information, trouve ici une application pour le calcul tolérant aux fautes.Parmi les nombreux problèmes liés a l’utilisation de cette belle et riche théorie pour le calcul tolérant aux fautes en quantique, dans la suite, nous nous intéresserons seulement à la question du décodage par passage de messages des codes LDPC. Dans la suite, je discuterai d’abord les limitations théoriques et pratique d’un certain type de décodeur par passage de message, le Min-Sum appliqué au code torique, un code pressenti pour être utilisé dans la première génération d’ordinateurs quantiques. Ensuite, je montrerai comment les performances pratiques des décodeurs par passage de message peuvent être grandement améliorées en utilisant des post-processings spécifiques aux codes quantiques.