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.
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.
La correction d'erreur est l'ensemble des techniques utilisees pour stocker, processer et transmettre de l'information de facon fiable dans un environnement bruite. La theorie de la correction d'erreur classique est fondee sur l'encodage redondant de l'information. L'un des buts principaux de cette theorie est de trouver des compromis optimaux entre la redondance, qu'on essaie de minimiser, et la tolerance au bruit, qu'on essaie de maximiser.
La theorie quantique de la correction d'erreur ne peut pas directement imiter les schemas redondants de la theorie classique parce qu'elle doit faire avec le theoreme de non-clonage: l'information quantique ne peut pas etre copiee. La correction d'erreur quantique est neanmoins possible en repartissant l'information sur un plus grand nombre d'elements de memoire quantique que necessaire. Dans la theorie de l'information quantique, la dilution de l'information remplace la redondance parce que la copie est interdite par les lois de la mecanique quantique.
Au dela de cette difference conceptuelle, la correction d'erreur quantique a beaucoup herite de son equivalent classique. Dans cette these nous nous interessons a une classe de codes correcteurs quantiques dont l'equivalent classique a ete definie en 1961 par Gallager. A cette epoque l'information quantique n'etait meme pas encore un domaine de recherche. Cette classe est la famille des codes LDPC (low density parity check). De facon informelle un code est dit LDPC si les contraintes imposees pour assurer la redondance dans le cas classique ou la dilution dans le cas quantique sont locales.
Plus precisement cette these se concentre sur un sous-ensemble des codes correcteurs quantiques LDPC: les codes correcteurs quantiques homologiques. Ces codes tiennent leur nom du domaine mathematique de l'homologie, dont les objets d'etude sont des suites d'applications lineaires telles que le noyau d'une application contienne l'image de son voisin de gauche. Initialement introduite pour etudier la topologie de formes geometriques, la theorie de l'homologie comprend maintenant egalement des branches plus algebriques, dont le centre d'interet est plus abstrait et combinatoire. Les codes homologiques ont suivi la meme trajectoire: ils ont ete introduits en 1996 par Kitaev avec un code quantique qui a la forme d'un tore. Ils forment maintenant une vaste famille de codes quantiques LDPC, certains plus inspires de formes geometriques que d'autres. Des codes quantiques homologiques ont ete construits a partir de geometries spheriques, euclidiennes et hyperboliques, a partir d'objets de dimension 2 et de dimension 4, a partir d'objets de dimension croissante et non bornee et a partir de produits d'hypergraphes et homologiques.
Apres avoir introduit des concepts generaux de l'information quantique dans le premier chapitre de cette these, nous nous concentrons dans les deux chapitres suivants sur des familles de code quantique fondee sur des objets hyperboliques de dimension 4. Nous insistons sur l'interconnexion entre leur cote geometrique, donne par des varietes, et leur cote cote combinatoire, donne par des polytopes abstraits. Nous utilisons ces deux aspects pour analyser les codes quantiques correspondants. Dans le quatrieme et dernier chapitre nous analysons une famille de codes quantiques fondee sur des objets spheriques de dimension quelconque. Pour avoir plus de flexibilite dans la construction de codes quantiques, nous utilisons des objets combinatoires qui realisent cette geometrie spherique: des hypercubes. Ce contexte nous permet d'introduire un nouveau lien entre corrections d'erreur classique et quantique ou des codes classiques sont utilises pour introduire de l'homologie dans les hypercubes.
Dans ce travail nous nous intéressons aux problèmes liés à l'amélioration des performances d'erreur des codes LDPC. Cette amélioration peut être faite pendant la construction des codes LDPC ou pendant leur processus de décodage. Nous concentrons notre attention vers l'amélioration du décodage. Nous proposons un algorithme de décodage itératif log-SPA modifié, qui minimise l'erreur du décodage pour les mots-codes qui ne peuvent pas être décodés par l'algorithme SPA connu. L'algorithme proposé est basé sur une dépendance entre le poids d'un syndrome et le poids de la séquence d'erreurs généré au cours des itérations du décodage. Nous analysons plus en détail cette dépendance et l'effet du décodage log-SPA moyenne sur les poids des vecteurs d'erreur et les poids du syndrome, et ce, sur les ensembles de piégeage. Concernant la construction des codes LDPC, on s'intéresse aux différents paramètres qui posent des problèmes dans la performance d'erreur : au plancher d'erreur, au périmètre du graphe de Tanner, à la distance minimale du code, aux ensembles de piégeage et aux ensembles d'arrêt. On présente différentes méthodes appliquées dans la construction des différents types de codes, pour éviter l'apparition des structures non-souhaitables dans le code. Nous faisons une comparaison entre la performance des codes pseudo-aléatoires et les codes structurés, basés sur les geometries finies euclidienne et géométrique. On présente aussi différentes méthodes de construction des codes LDPC quasi-cycliques, qui peuvent éviter la formation de certains types d'ensembles de piégeage. d'ensembles d'arrêt ainsi que les cycles courts dans le graphe de Tanner. Les méthodes proposées donnent de très bas planchers d'erreur et une faible complexité du codage.
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.
Étude de codes LDPC quantiques et de leur décodage Les codes quantiques de type LDPC (Low-Density Parity-Check, à matrice de parité creuse) offrent une solution prometteuse pour protéger l’information quantique contre les erreurs et sont donc considérés comme une étape importante dans la réalisation à grande échelle d’un ordinateur quantique tolérant aux fautes. Dans cette thèse, nous étudions les codes LDPC quantiques selon trois approches différentes, en analysant le décodage par renormalisation du code torique de Kitaev, en établissant des limites sur la distance minimale des codes géométriquement locaux et en construisant de petits exemples de codes de Tanner quantiques. Le code torique de Kitaev est un code LDPC quantique remarquable et est actuellement le plus largement considéré pour une mise en œuvre expérimentale. Nous examinons les décodeurs par renormalisation probabiliste introduits par Duclos-Cianci et Poulin, une famille de décodeurs qui offrent l’un des meilleurs compromis entre précision et rapidité. Nous étudions la manière dont ils gèrent les erreurs adverses en introduisant un décodeur par renormalisation déterministe, n’utilisant pas les probabilités a priori du modèle d’erreur. Nous constatons que ce décodeur par renormalisation admet des motifs d’erreurs incorrigibles de type fractal et nous obtenons une borne inférieure sur le poids de ces erreurs. En raison de contraintes physiques, une grande attention a été accordée aux codes LDPC quantiques dont les stabilisateurs n’agissent que sur un nombre limité de qubits voisins. Nous étendons la fameuse borne de Bravyi-Terhal aux codes quantiques définis par des contraintes locales sur un quotient de réseau, fournissant ainsi un aperçu essentiel des limites des codes stabilisateurs géométriquement locaux. En guise d’application, nous fournissons des bornes supérieures sur la distance minimale de codes à deux blocs construits à l’aide d’une algèbre d’un groupe abélien, une famille de codes LDPC quantiques pour laquelle la distance minimale est actuellement inconnue. Ces dernières années, des codes LDPC quantiques asymptotiquement bons ont été construits, mais les résultats démontrables concernant leurs distances minimales ne s’appliquent qu’à des codes trop longs pour être utilisables. Dans le cadre des efforts visant à concevoir des codes pouvant être mis en œuvre à court terme, nous construisons des instances courtes de codes quantiques de Tanner à l’aide de complexes carrés obtenus à partir de produits liftés de graphes réguliers. Plusieurs instances explicites de ces codes présentent des distances minimales dépassant la racine carrée de la longueur du code.
Cette thèse porte sur l'analyse et le design de codes de canal définis par des graphes creux. Le but est de construire des codes ayant de très bonnes performances sur de larges plages de rapports signal à bruit lorsqu'ils sont décodés itérativement. Dans la première partie est introduite une nouvelle classe de codes LDPC, nommés code LDPC hybrides. L'analyse de cette classe pour des canaux symétriques sans mé- moire est réalisée, conduisant à l'optimisation des paramètres, pour le canal gaussien à entrée binaire. Les codes LDPC hybrides résultants ont non seulement de bonnes proprié- tés de convergence, mais également un plancher d'erreur très bas pour des longueurs de mot de code inférieures à trois mille bits, concurrençant ainsi les codes LDPC multi-edge. Les codes LDPC hybrides permettent donc de réaliser un compromis intéressant entre ré- gion de convergence et plancher d'erreur avec des techniques de codage non-binaires. La seconde partie de la thèse a été consacrée à étudier quel pourrait être l'apport de méthodes d'apprentissage artificiel pour le design de bons codes et de bons décodeurs itératifs, pour des petites tailles de mot de code. Nous avons d'abord cherché comment construire un code en enlevant des branches du graphe de Tanner d'un code mère, selon un algorithme d'apprentissage, dans le but d'optimiser la distance minimale. Nous nous sommes ensuite penchés sur le design d'un décodeur itératif par apprentissage artificiel, dans l'optique d'avoir de meilleurs résultats qu'avec le décodeur BP, qui devient sous- optimal dès qu'il y a des cycles dans le graphe du code. Dans la troisième partie de la thèse, nous nous sommes intéressés au décodage quan- tifié dans le même but que précédemment : trouver des règles de décodage capables de décoder des configurations d'erreur difficiles. Nous avons proposé une classe de déco- deurs utilisant deux bits de quantification pour les messages du décodeur. Nous avons prouvé des conditions suffisantes pour qu'un code LDPC, avec un poids de colonnes égal à quatre, et dont le plus petit cycle du graphe est de taille au moins six, corrige n'importe quel triplet d'erreurs. Ces conditions montrent que décoder avec cette règle à deux bits permet d'assurer une capacité de correction de trois erreurs pour des codes de rendements plus élevés qu'avec une règle de décodage à un bit.
Cette thèse se consacre à l'étude de décodeurs itératifs, pour des codes correcteurd'erreurs binaires et non-binaires à faible densité (LDPC). Notre objectif est de modéliserdes décodeurs de complexité faibles et de faible latence tout en garantissantde bonne performances dans la région des très faibles taux d'erreur (error floor).Dans la première partie de cette thèse, nous étudions des décodeurs itératifssur des alphabets finis (Finite Alphabet iterative decoders, FAIDs) qui ont étérécemment proposés dans la littérature. En utilisant un grand nombre de décodeursFAIDs, nous proposons un nouvel algorithme de décodage qui améliore la capacité decorrections d'erreur des codes LDPC de degré dv = 3 sur canal binaire symétrique.La diversité des décodeurs permet de garantir une correction d'erreur minimale sousdécodage itératif, au-delà de la pseudo-distance des codes LDPC. Nous donnonsdans cette thèse un exemple detailé d'un ensemble de décodeur FAIDs, qui corrigetous les évènements d'erreur de poids inférieur ou égal à 7 avec un LDPC de petitetaille (N=155,K=64,Dmin=20). Cette approche permet de corriger des évènementsd'erreur que les décodeurs traditionnels (BP, min-sum) ne parviennent pas à corriger.Enfin, nous interprétons les décodeurs FAIDs comme des systèmes dynamiques etnous analysons les comportements de ces décodeurs sur des évènements d'erreur lesplus problématiques. En nous basant sur l'observation des trajectoires périodiquespour ces cas d'étude, nous proposons un algorithme qui combine la diversité dudécodage avec des sauts aléatoires dans l'espace d'état du décodeur itératif. Nousmontrons par simulations que cette technique permet de s'approcher des performancesd'un décodage optimal au sens du maximum de vraisemblance, et ce pourplusieurs codes.Dans la deuxième partie de cette thèse, nous proposons un nouvel algorithmede décodage à complexité réduite pour les codes LDPC non-binaires. Nous avonsappellé cet algorithme Trellis-Extended Min-Sum (T-EMS). En transformant le domainede message en un domaine appelée domaine delta, nous sommes capable dechoisir les déviations ligne par ligne par rapport à la configuration la plus fiable,tandis que les décodeurs habituels comme le décodeur EMS choisissent les déviationscolonne par colonne. Cette technique de sélection des déviations ligne parligne nous permet de réduire la complexité du décodage sans perte de performancepar rapport aux approches du type EMS. Nous proposons également d'ajouter une colonne supplémentaire à la représentation en treillis des messages, ce qui résoudle problème de latence des décodeurs existants. La colonne supplémentaire permetde calculer tous les messages extrinséque en parallèle, avec une implémentationmatérielle dédiée. Nous présentons dans ce manuscrit, aussi bien les architecturesmatérielles parallèle que les architectures matérielles série pour l'exécution de notrealgorithme T-EMS. L'analyse de la complexité montre que l'approche T-EMS estparticulièrement adapté pour les codes LDPC non-binaires sur des corps finis deGalois de petite et moyenne dimensions.