Academic literature on the topic 'Code quantique'

L'objet de cette thèse est l'étude des codes LDPC quantiques. Dans un premier temps, nous travaillons sur des constructions topologiques de codes LDPC quantiques. Nous proposons de construire une famille de codes couleur basée sur des pavages hyperboliques. Nous étudions ensuite les paramètres d'une famille de codes basée sur des graphes de Cayley.Dans une seconde partie, nous examinons les performances de ces codes. Nous obtenons une borne supérieure sur les performances des codes LDPC quantiques réguliers sur le canal à effacement quantique. Ceci prouve que ces codes n'atteignent pas la capacité du canal à effacement quantique. Dans le cas du canal de dépolarisation, nous proposons un nouvel algorithme de décodage des codes couleur basé sur trois décodages de codes de surface. Nos simulations numériques montrent de bonnes performances dans le cas des codes couleur toriques.Pour finir, nous nous intéressons au phénomène de percolation. La question centrale de la théorie de la percolation est la détermination du seuil critique. Le calcul exacte de ce seuil est généralement difficile. Nous relions la probabilité de percolation dans certains pavages réguliers du plan hyperbolique à la probabilité d'erreur de décodage pour une famille de codes hyperboliques. Nous en déduisons une borne sur le seuil critique de ces pavages hyperboliques basée sur des résultats de théorie de l'information quantique. Il s'agit d'une application de la théorie de l'information quantique à un problème purement combinatoire<br>This thesis is devoted to the study of quantum LDPC codes. The first part presents some topological constructions of quantum LDPC codes. We introduce a family of color codes based on tilings of the hyperbolic plane. We study the parameters of a family of codes based on Cayley graphs.In a second part, we analyze the performance of these codes. We obtain an upper bound on the performance of regular quantum LDPC codes over the quantum erasure channel. This implies that these codes don't achieve the capacity of the quantum erasure channel. In the case of the depolarizing channel, we propose a new decoding algorithm of color codes based on three surface codes decoding. Our numerical results show good performance for toric color codes.Finally, we focus on percolation theory. The central question in percolation theory is the determination of the critical probability. Computing the critical probability exactly is usually quite difficult. We relate the probability of percolation in some regular tilings of the hyperbolic plane to the probability of a decoding error for hyperbolic codes on the quantum erasure channel. This leads to an upper bound on the critical probability of these hyperbolic tilings based on quantum information. It is an application of quantum information to a purely combinatorial problem

L'idée des turbo-codes, construction très performante permettant l'encodage de l'information classique, ne pouvait jusqu'à présent pas être transposé au problème de l'encodage de l'information quantique. En effet, il subsistait des obstacles tout aussi théoriques que relevant de leur implémentation. A la version quantique connue de ces codes, on ne connaissait ni de résultat établissant une distance minimale infinie, propriété qui autorise de corriger un nombre arbitraire d'erreurs, ni de décodage itératif efficace, car les turbo-encodages quantiques, dits catastrophiques, propagent certaines erreurs lors d'un tel décodage et empêchent son bon fonctionnement. Cette thèse a permis de relever ces deux défis, en établissant des conditions théoriques pour qu'un turbo-code quantique ait une distance minimale infinie, et d'autre part, en exhibant une construction permettant au décodage itératif de bien fonctionner. Les simulations montrent alors que la classe de turbo-codes quantiques conçue est efficace pour transmettre de l'information quantique via un canal dépolarisant dont l'intensité de dépolarisation peut aller jusqu'à p = 0,145. Ces codes quantiques, de rendement constant, peuvent aussi bien être utilisés directement pour encoder de l'information quantique binaire, qu'être intégrés comme modules afin d'améliorer le fonctionnement d'autres codes tels que les LDPC quantiques.

Cette thèse porte sur la distribution quantique de clés, qui est une primitive cryptographique permettant à deux correspondants éloignés, Alice et Bob, d'établir une clé secrète commune malgré la présence potentielle d'un espion. On s'intéresse notamment aux protocoles " à variables continues " où Alice et Bob encodent l'information dans l'espace des phases. L'intérêt majeur de ces protocoles est qu'ils sont faciles à mettre en œuvre car ils ne requièrent que des composants télécom standards. La sécurité de ces protocoles repose sur les lois de la physique quantique : acquérir de l'information sur les données échangées par Alice et Bob induit nécessairement un bruit qui révèle la présence de l'espion. Une étape particulièrement délicate pour les protocoles à variables continues est la " réconciliation " durant laquelle Alice et Bob utilisent leurs résultats de mesure classiques pour se mettre d'accord sur une chaîne de bits identiques. Nous proposons d'abord un algorithme de réconciliation optimal pour le protocole initial, puis introduisons un nouveau protocole qui résout automatiquement le problème de la réconciliation grâce à l'emploi d'une modulation discrète. Parce que les protocoles à variables continues sont formellement décrits dans un espace de Hilbert de dimension infinie, prouver leur sécurité pose des problèmes mathématiques originaux. Nous nous intéressons d'abord à des symétries spécifiques de ces protocoles dans l'espace des phases. Ces symétries permettent de simplifier considérablement l'analyse de sécurité. Enfin, nous étudions l'influence des effets de tailles finies, tels que l'estimation du canal quantique, sur les performances des protocoles.

Cette thèse porte sur la distribution quantique de clés, qui est une primitive cryptographique qui permet à deux correspondants éloignés, Alice et Bob, d'établir une clé secrète commune malgré la présence potentielle d'un espion. On s'intéresse notamment aux protocoles « à variables continues »' où Alice et Bob encodent l'information dans l'espace des phases. L'intérêt majeur de ces protocoles est qu'ils sont faciles à mettre en œuvre car ils ne requièrent que des composants télécom standards. La sécurité de ces protocoles repose sur les lois de la physique quantique : acquérir de l'information sur les données échangées par Alice et Bob induit nécessairement un bruit qui révèle la présence de l'espion. Une étape particulièrement délicate pour les protocoles à variables continues est la « réconciliation » durant laquelle Alice et Bob utilisent leurs résultats de mesure classiques pour se mettre d'accord sur une chaîne de bits identiques. Nous proposons d'abord un algorithme de réconciliation optimal pour le protocole initial, puis introduisons un nouveau protocole qui résout automatiquement le problème de la réconciliation grâce à l'emploi d'une modulation discrète. Parce que les protocoles à variables continues sont formellement décrits dans un espace de Hilbert de dimension infinie, prouver leur sécurité pose des problèmes mathématiques originaux. Nous nous intéressons d'abord à des symétries spécifiques de ces protocoles dans l'espace des phases. Ces symétries permettent de simplifier considérablement l'analyse de sécurité. Enfin, nous étudions l'influence des effets de tailles finies, tels que l'estimation du canal quantique, sur les performances des protocoles<br>This thesis is concerned with quantum key distribution (QKD), a cryptographic primitive allowing two distant parties, Alice and Bob, to establish a secret key, in spite of the presence of a potential eavesdropper, Eve. Here, we focus on continuous-variable protocols, for which the information is coded in phase-space. The main advantage of these protocols is that their implementation only requires standard telecom components. The security of QKD lies on the laws of quantum physics: an eavesdropper will necessary induce some noise on the communication, therefore revealing her presence. A particularly difficult step of continuous-variable QKD protocols is the ``reconciliation'' where Alice and Bob use their classical measurement results to agree on a common bit string. We first develop an optimal reconciliation algorithm for the initial protocol, then introduce a new protocol for which the reconciliation problem is automatically taken care of thanks to a discrete modulation. Proving the security of continuous-variable QKD protocols is a challenging problem because these protocols are formally described in an infinite dimensional Hilbert space. A solution is to use all available symmetries of the protocols. In particular, we introduce and study a class of symmetries in phase space, which is particularly relevant for continuous-variable QKD. Finally, we consider finite size effects for these protocols. We especially analyse the influence of parameter estimation on the performance of continuous-variable QDK protocols

L’utilisation des codes MDPC (Moderate Density Parity Check) quasi-cycliques dans le cryptosystème de McEliece offre un schéma de chiffrement post-quantique dont les clés ont une taille raisonnable et dont le chiffrement et le déchiffrement n’utilisent que des opérations binaires. C’est donc un bon candidat pour l’implémentation embarquée ou à bas coût.Dans ce contexte, certaines informations peuvent être exploitées pour construire des attaques par canaux cachés.Ici, le déchiffrement consiste principalement à décoder un mot de code bruité. Le décodeur utilisé est itératif et probabiliste : le nombre d’itérations de l'algorithme varie en fonction des instances et certains décodages peuvent échouer. Ces comportements ne sont pas souhaitables car ils peuvent permettre d’extraire des informations sur le secret.Une contremesure possible est de limiter le nombre d’instances de chiffrement avec les mêmes clés. Une autre façon serait de recourir à un décodage à temps constant dont la probabilité d’échec au décodage est négligeable. L’enjeu principal de cette thèse est de fournir de nouveaux outils pour analyser du comportement du décodeur pour la cryptographie.Dans un second temps, nous expliquons pourquoi l'utilisation des codes polaires n'est pas sûre pour le cryptosystème de McEliece. Pour ce faire, nous utilisons de nouvelles techniques afin de résoudre une équivalence de codes. Nous exhibons de nombreux liens entre les codes polaires et les codes de Reed-Muller et ainsi d'introduire une nouvelle famille de codes : les codes monomiaux décroissants. Ces résultats sont donc aussi d'un intérêt indépendant pour la théorie des codes<br>Considering the McEliece cryptosystem using quasi-cylcic MDPC (Moderate Density Parity Check matrix) codes allows us to build a post-quantum encryption scheme with nice features. Namely, it has reasonable key sizes and both encryption and decryption are performed using binary operations. Thus, this scheme seems to be a good candidate for embedded and lightweight implementations. In this case, any information obtained through side channels can lead to an attack. In the McEliece cryptosystem, the decryption process essentially consists in decoding. As we consider the use of an iterative and probabilistic algorithm, the number of iterations needed to decode depends on the instance considered and some of it may fail to be decoded. These behaviors are not suitable because they may be used to extract information about the secrets. One countermeasure could be to bound the number of encryptions using the same key. Another solution could be to employ a constant time decoder with a negligible decoding failure probability, that is to say which is about the expected security level of the cryptosystem. The main goal of this thesis is to present new methods to analyse decoder behavior in a cryptographic context.Second, we explain why a McEliece encryption scheme based on polar code does not ensure the expected level of security. To do so, we apply new techniques to resolve the code equivalence problem. This allows us to highlight several common properties shared by Reed-Muller codes and polar codes. We introduce a new family of codes, named decreasing monomial codes, containing both Reed-Muller and polar codes. These results are also of independent interest for coding theory

Depuis 20 ans, l'information quantique a profondément changé notre façon d'appréhender la physique atomique, ainsi que la nature des ressources utiles au calcul. Cette thèse aborde trois aspects relatifs à l'information quantique: - Le phénomène de décohérence -- responsable de la transition quantique-classique -- est décrit quantitativement grâce à l'analyse de l'information mutuelle entre deux systèmes quantiques ; - Une nouvelle classe de codes correcteurs d'erreurs quantiques -- les codes convolutifs -- est introduite en detail et il est montré qu'elle partage les propriétés des codes convolutifs classiques (codage et décodage en ligne, algorithme efficace d'estimation d'erreurs au maximum de vraisemblance, existence de condition nécessaire et suffisante pour l'absence d'erreur catastrophique, etc.) ; - Quelques propositions expérimentales de manipulation d'information quantique sont décrites (porte de Toffoli et clonage universel pour l'électrodynamique quantique en cavité).

Le fameux Théorème d’Extension de MacWilliams affirme que, pour les codes classiques, toute isométrie deHamming linéaire d'un code linéaire se prolonge en une application monomiale. Cependant, pour les codeslinéaires sur les alphabets de module, l'existence d'un analogue du théorème d'extension n'est pas garantie.Autrement dit, il existe des codes linéaires sur certains alphabets de module dont les isométries de Hammingne sont pas toujours extensibles. Il en est de même pour un contexte plus général d'un alphabet de module munid'une fonction de poids arbitraire. Dans la présente thèse, nous prouvons des analogues du théorèmed'extension pour des codes construits sur des alphabets et fonctions de poids arbitraires. La propriétéd'extension est analysée notamment pour les codes de petite longueur sur un alphabet de module de matrices,les codes MDS généraux, ou encore les codes sur un alphabet de module muni de la composition de poidssymétrisée. Indépendamment de ce sujet, une classification des deux groupes des isométries des codescombinatoires est donnée. Les techniques développées dans la thèse sont prolongées aux cas des codesstabilisateurs quantiques et aux codes de Gabidulin dans le cadre de la métrique rang<br>The famous MacWilliams Extension Theorem states that for classical codes each linear Hamming isometry ofa linear code extends to a monomial map. However, for linear codes over module alphabets an analogue of theextension theorem does not always exist. That is, there may exists a linear code over a module alphabet with anunextendable Hamming isometry. The same holds in a more general context of a module alphabet equippedwith a general weight function. Analogues of the extension theorem for different classes of codes, alphabetsand weights are proven in the present thesis. For instance, extension properties of the following codes arestudied: short codes over a matrix module alphabet, maximum distance separable codes, codes over a modulealphabet equipped with the symmetrized weight composition. As a separate result, a classification of twoisometry groups of combinatorial codes is given. The thesis also contains applications of the developedtechniques to quantum stabilizer codes and Gabidulin codes

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<br>Fault tolerant quantum computation is a technique to perform reliable quantum computation using noisy components. In this context, quantum error correcting codes are used to keep the amount of errors under a sustainable threshold. One of the main problems of this field is to determine the minimum cost, in terms of memory and time, which is needed in order to transform an ideal quantum computation into a fault-tolerant one. In this PhD thesis, we show that the family of quantum expander codes and the small-set-flip decoder can be used in the construction of ref. [arXiv:1310.2984] to produce a fault-tolerant quantum circuit with constant space overhead. The error correcting code family and the decoder that we study has been introduced in ref. [arXiv:1504.00822] where an adversarial error model was examined. Based on the results of this article, we analyze quantum expander codes subjected to a stochastic error model which is relevant for fault-tolerant quantum computation [arXiv:1711.08351], [arXiv:1808.03821]. In addition, we show that the decoding algorithm can be parallelized to run in constant time. This is very relevant to prevent errors from accumulating while the decoding algorithm is running. Beyond the theoretical results described above, we perform a numerical analysis of quantum expander codes to measure their performance in practice [arXiv:1810.03681]. The error model used during these simulations generates X and Z type errors on the qubits with an independent and identically distributed probability distribution. Our results are promising because they reveal that these constant rate codes have a decent threshold and good finite length performance

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<br>Quantum information is a developping field of study with various applications (in cryptography, fast computing, ...). Its basic element, the qubit, is volatile : any measurement changes its value. This also applies to unvolontary measurements due to an imperfect insulation (as seen in any practical setting). Unless we can detect and correct these modifications, any quantum computation is bound to fail. These unwanted modifications remind us of errors that can happen in the transmission of a (classical) message. These errors can be accounted for with an error-Correcting code. For quantum errors, we need to set quantum error-Correcting codes. In order to prevent the clotting of errors that cannot be compensated, these quantum error-Correcting codes need to be both efficient and fast. Among classical error-Correcting codes, Low Density Parity Check (LDPC) codes provide many perks: They are easy to create, fast to decode (with an iterative decoding algorithme, known as belief propagation) and close to optimal. Their quantum equivalents should then be good candidates, even if they present two major drawbacks (among other less important ones). A quantum error correction code can be seen as a combination of two classical codes, with orthogonal parity-Check matrices. The first issue is the building of two efficient codes with this property. The other is in the decoding: each row of the parity-Check matrix from one code gives a low-Weight codeword of the other code. In fact, with quantum codes, corresponding errors do no affect the system, but are difficult to account for with the usual iterative decoding algorithm. In the first place, this thesis studies an existing construction, based on the product of two classical codes. This construction has good theoritical properties (dimension and minimal distance), but has shown disappointing practical results, which are explained by the resulting code's structure. Several variations, which could have good theoritical properties are also analyzed but produce no usable results at this time. We then move to the study of q-Ary codes. This construction, derived from classical codes, is the enlargement of an existing LDPC code through the augmentation of its alphabet. It applies to any 2-Regular quantum code (meaning with parity-Check matrices that have exactly two ones per column) and gives good performance with the well-Known toric code, which can be easily decoded with its own specific algorithm (but not that easily with the usual belief-Propagation algorithm). Finally this thesis explores a quantum equivalent of spatially coupled codes, an idea also derived from the classical field, where it greatly enhances the performance of LDPC codes. A result which has been proven. If, in its quantum form, a proof is still not derived, some spatially-Coupled constructions have lead to excellent performance, well beyond other recent constuctions

La cryptographie basée sur les codes n'est pas largement déployée dans la pratique. Principalement à cause de son inconvénient majeur: des tailles de clés énormes. Dans cette thèse, nous proposons deux approches différentes pour résoudre ce problème. Le premier utilise des codes algébriques, présentant un moyen de construire des codes de Goppa qui admettent une représentation compacte. Ce sont les Codes de Goppa p-adiques. Nous montrons comment construire ces codes pour instancier des systèmes de chiffrement à clé publique, comment étendre cette approche pour instancier un schéma de signature et, enfin, comment généraliser cet approche pour définir des codes de caractéristique plus grande au égale à deux. En résumé, nous avons réussi à produire des clés très compact basé sur la renommée famille de codes de Goppa. Bien qu'efficace, codes de Goppa p-adiques ont une propriété non souhaitable: une forte structure algébrique. Cela nous amène à notre deuxième approche, en utilisant des codes LDPC avec densité augmentée, ou tout simplement des codes MDPC. Ce sont des codes basés sur des graphes, qui sont libres de structure algébrique. Il est très raisonnable de supposer que les codes MDPC sont distinguable seulement en trouvant des mots de code de poids faible dans son dual. Ceci constitue un avantage important non seulement par rapport à tous les autres variantes du système de McEliece à clés compactes, mais aussi en ce qui concerne la version classique basée sur les codes de Goppa binaires. Ici, les clés compactes sont obtenus en utilisant une structure quasi-cyclique.