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

Codes correcteurs quantiques pouvant se décoder itérativement

Denise Maurice

Published Jun 26, 2014• 2 citations
Publisher

Abstract

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.

DOI
10.70675/9ee0b573z0814z4aa8z85adz400199df03cd

Related papers

Etudes de codes correcteurs quantiques LDPC

Vivien Londe

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.

•Dec 6, 2019•0 citations

Study of Quantum LDPC Codes and their Decoding

Wouter Rozendaal

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

•Dec 2, 2025•0 citations

Turbo-codes quantiques

Mamdouh Abbara

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.

•Apr 9, 2013•0 citations

Contribution au décodage à décision douce des codes correcteurs en bloc

Senad Mohamed Mahmoud

Pour des trames de longueurs n supérieures ou égales à quelques milliers de bits (n > 1000), les turbocodes et les codes LDPC (Low-Density Parity Check) ou leurs variantes donnent d'excellentes performances avec une complexité raisonnable pour des implémentations "temps réel" même pour des débits très élevés (GigaBit/s). Par contre pour les petites longueurs (n < 1000) de trames, les turbocodes et codes LDPC courts sont moins performants. En effet, pour avoir de grandes distances minimales dmin avec des codes de petites longueurs n et de grandes capacités de correction, il faut des codes dont les matrices de contrôle de parité soient de densité élevée et non creuse, c'est à dire avec beaucoup de 1 et très peu de 0, comme celles des codes LDPC ou des turbocodes. La densité élevée de la matrice de contrôle du code conduit à des cycles courts dans le graphe de Tanner correspondant et donc rend les algorithmes type BP (Belief Propagation) inefficaces. L'objectif principal de cette thèse est donc de contribuer à améliorer le décodage à décision douce des codes en bloc linéaires courts. Nos travaux se sont orientés, dans un premier temps, vers l'étude d'une classe particulière de codes en bloc appelés codes Cortex. La construction Cortex repose sur l'utilisation de codes de base de petites longueurs assemblés en étages reliés par des permutations. Nous proposons une nouvelle méthode pour estimer les variables cachées dans la structure afin de pouvoir effectuer un décodage itératif entre les codes de base. Nous proposons une deuxième méthode de décodage qui ne nécessite pas d'estimation des variables cachées en les dissimulant dans des équations booléennes. Dans un second temps nous avons élargi nos recherches à des algorithmes de décodage très généraux valables pour tout code en bloc. Nous proposons dans ce cadre trois méthodes de décodage basées sur des treillis-produits de complexité réduite construits à partir des lignes des matrices génératrice et de contrôle du code en bloc.

•Jan 13, 2016•0 citations

Traitement quantique de l’information pour les simulations quantiques

Camille Le Calonnec

La recherche en informatique quantique a pris de l’ampleur dans les deux dernières décennies, notamment grâce aux financements massifs des gouvernements et de l’industrie dans les technologies quantiques. L’ordinateur quantique promet de résoudre des problèmes qui jusqu’à présent restaient insurmontables à cause du temps déraisonnable qu’il faudrait pour les résoudre sur les ordinateurs classiques les plus puissants. L’idée de l’ordinateur quantique consiste à utiliser des propriétés quantiques de la matière, telles que l’intrication et la superposition quantique des états, pour effectuer des calculs d’une nouvelle manière. L’informatique quantique requiert un nouveau type d’ordinateur où les bits d’information classique, généralement représentés par la présence ou non de courant à l’entrée d’un transistor, sont remplacés par des bits quantiques aussi appelés qubits, et qui sont représentés par l’état d’un système quantique. De plus, il est nécessaire de développer de nouveaux algorithmes capables d’être implémentés sur un ordinateur quantique et capables de tirer parti de l’avantage quantique. Cette thèse porte sur ces deux composantes complémentaires : la construction de portes logiques, un bloc fondamental de tout ordinateur, et la création de meilleurs algorithmes pour résoudre des problèmes pertinents sur ces machines. Parmi les plateformes les plus avancées pour l’ordinateur quantique, on trouve les circuits supraconducteurs, qui sont la plateforme sur laquelle ont misé Google, IBM, Alice&Bob, Nord Quantique et bien d’autres compagnies. Malgré les avancées des dernières décennies, de nombreux défis restent à être relevés pour que les machines existantes soient en mesure de résoudre des problèmes pertinents et surpassent les ordinateurs classiques. L’un des défis auquel cette thèse s’attaque est la réalisation de portes logiques à deux qubits rapides et à haute fidélité. La rapidité est cruciale pour pouvoir réaliser le plus d’opérations possible avant que les qubits ne perdent leur cohérence quantique, et une haute fidélité est requise pour minimiser les erreurs de calcul et permettre d’implémenter de la correction d’erreurs quantiques. De plus, certains qubits supraconducteurs sont connus pour être affectés par une interaction indésirable, l’interaction ZZ qui, même si relativement faible, affecte la fidélité des portes logiques quantiques, empêchant d’atteindre des fidélités supérieures à 99.9% nécessaires à la correction d’erreurs. En parallèle avec l’amélioration des composantes de l’ordinateur quantique, il est important de développer des applications pour ce nouveau type de machine. Parmi les approches étudiées, les algorithmes quantiques variationnels (VQA) sont ceux qui sont les plus susceptibles d’être déployés sur les ordinateurs quantiques de petites tailles existants. Ce sont des algorithmes hybrides qui nécessitent à la fois de la puissance de calcul classique et quantique. Ces algorithmes semblent prometteurs pour résoudre de nombreux problèmes concrets d’intérêt industriel, comme obtenir les propriétés de molécules ou trouver les solutions de problèmes d’optimisation combinatoire. En effet, ces problèmes peuvent être formulés sous forme d’un Hamiltonien et résolus en déterminant son état fondamental. Dans ce but, les VQAs utilisent un circuit quantique paramétré appelé ansatz, dont les paramètres sont optimisés pour s’approcher de l’état fondamental. Un premier défi consiste à trouver un ansatz qui permette, pour un problème donné, de converger le plus efficacement possible vers la solution. Un deuxième défi est de trouver un circuit fait de portes logiques facilement implémentables sur les plateformes physiques actuelles. Les travaux effectués dans cette thèse apportent des contributions à ces deux défis. Dans la première partie de la thèse, nous introduisons le dispositif que nous avons conçu et qui permet de réaliser des portes d’intrication paramétrique entre deux qubits supraconducteurs. Cette approche a permis à nos collaborateurs du groupe d’Andrew Houck de l’Université de Princeton de réaliser expérimentalement une opération de type √iSWAP en 15 ns avec une fidélité de 98.8%, et ce dans un dispositif où l’interaction ZZ est supprimée. Dans la seconde partie de la thèse, nous avons développé un ansatz pour les VQAs permettant de résoudre le modèle de Fermi Hubbard. Ce nouvel ansatz utilise les avantages de deux ansätze préexistants, et permet d’obtenir l’énergie et l’état fondamental du FHM avec une précision de plusieurs ordres de grandeur supérieure aux ansätze standards, et ce en réduisant significativement le nombre de portes d’intrication CNOT qui sont généralement imparfaites et longues à implémenter.

•Jan 1, 2024•0 citations

Codes LDPC multi-binaires hybrides et méthodes de décodage itératif

Lucile Sassatelli

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.

•Oct 3, 2008•0 citations
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.
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.
É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.
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.
Pour des trames de longueurs n supérieures ou égales à quelques milliers de bits (n > 1000), les turbocodes et les codes LDPC (Low-Density Parity Check) ou leurs variantes donnent d'excellentes performances avec une complexité raisonnable pour des implémentations "temps réel" même pour des débits très élevés (GigaBit/s). Par contre pour les petites longueurs (n < 1000) de trames, les turbocodes et codes LDPC courts sont moins performants. En effet, pour avoir de grandes distances minimales dmin avec des codes de petites longueurs n et de grandes capacités de correction, il faut des codes dont les matrices de contrôle de parité soient de densité élevée et non creuse, c'est à dire avec beaucoup de 1 et très peu de 0, comme celles des codes LDPC ou des turbocodes. La densité élevée de la matrice de contrôle du code conduit à des cycles courts dans le graphe de Tanner correspondant et donc rend les algorithmes type BP (Belief Propagation) inefficaces. L'objectif principal de cette thèse est donc de contribuer à améliorer le décodage à décision douce des codes en bloc linéaires courts. Nos travaux se sont orientés, dans un premier temps, vers l'étude d'une classe particulière de codes en bloc appelés codes Cortex. La construction Cortex repose sur l'utilisation de codes de base de petites longueurs assemblés en étages reliés par des permutations. Nous proposons une nouvelle méthode pour estimer les variables cachées dans la structure afin de pouvoir effectuer un décodage itératif entre les codes de base. Nous proposons une deuxième méthode de décodage qui ne nécessite pas d'estimation des variables cachées en les dissimulant dans des équations booléennes. Dans un second temps nous avons élargi nos recherches à des algorithmes de décodage très généraux valables pour tout code en bloc. Nous proposons dans ce cadre trois méthodes de décodage basées sur des treillis-produits de complexité réduite construits à partir des lignes des matrices génératrice et de contrôle du code en bloc.
La recherche en informatique quantique a pris de l’ampleur dans les deux dernières décennies, notamment grâce aux financements massifs des gouvernements et de l’industrie dans les technologies quantiques. L’ordinateur quantique promet de résoudre des problèmes qui jusqu’à présent restaient insurmontables à cause du temps déraisonnable qu’il faudrait pour les résoudre sur les ordinateurs classiques les plus puissants. L’idée de l’ordinateur quantique consiste à utiliser des propriétés quantiques de la matière, telles que l’intrication et la superposition quantique des états, pour effectuer des calculs d’une nouvelle manière. L’informatique quantique requiert un nouveau type d’ordinateur où les bits d’information classique, généralement représentés par la présence ou non de courant à l’entrée d’un transistor, sont remplacés par des bits quantiques aussi appelés qubits, et qui sont représentés par l’état d’un système quantique. De plus, il est nécessaire de développer de nouveaux algorithmes capables d’être implémentés sur un ordinateur quantique et capables de tirer parti de l’avantage quantique. Cette thèse porte sur ces deux composantes complémentaires : la construction de portes logiques, un bloc fondamental de tout ordinateur, et la création de meilleurs algorithmes pour résoudre des problèmes pertinents sur ces machines. Parmi les plateformes les plus avancées pour l’ordinateur quantique, on trouve les circuits supraconducteurs, qui sont la plateforme sur laquelle ont misé Google, IBM, Alice&Bob, Nord Quantique et bien d’autres compagnies. Malgré les avancées des dernières décennies, de nombreux défis restent à être relevés pour que les machines existantes soient en mesure de résoudre des problèmes pertinents et surpassent les ordinateurs classiques. L’un des défis auquel cette thèse s’attaque est la réalisation de portes logiques à deux qubits rapides et à haute fidélité. La rapidité est cruciale pour pouvoir réaliser le plus d’opérations possible avant que les qubits ne perdent leur cohérence quantique, et une haute fidélité est requise pour minimiser les erreurs de calcul et permettre d’implémenter de la correction d’erreurs quantiques. De plus, certains qubits supraconducteurs sont connus pour être affectés par une interaction indésirable, l’interaction ZZ qui, même si relativement faible, affecte la fidélité des portes logiques quantiques, empêchant d’atteindre des fidélités supérieures à 99.9% nécessaires à la correction d’erreurs. En parallèle avec l’amélioration des composantes de l’ordinateur quantique, il est important de développer des applications pour ce nouveau type de machine. Parmi les approches étudiées, les algorithmes quantiques variationnels (VQA) sont ceux qui sont les plus susceptibles d’être déployés sur les ordinateurs quantiques de petites tailles existants. Ce sont des algorithmes hybrides qui nécessitent à la fois de la puissance de calcul classique et quantique. Ces algorithmes semblent prometteurs pour résoudre de nombreux problèmes concrets d’intérêt industriel, comme obtenir les propriétés de molécules ou trouver les solutions de problèmes d’optimisation combinatoire. En effet, ces problèmes peuvent être formulés sous forme d’un Hamiltonien et résolus en déterminant son état fondamental. Dans ce but, les VQAs utilisent un circuit quantique paramétré appelé ansatz, dont les paramètres sont optimisés pour s’approcher de l’état fondamental. Un premier défi consiste à trouver un ansatz qui permette, pour un problème donné, de converger le plus efficacement possible vers la solution. Un deuxième défi est de trouver un circuit fait de portes logiques facilement implémentables sur les plateformes physiques actuelles. Les travaux effectués dans cette thèse apportent des contributions à ces deux défis. Dans la première partie de la thèse, nous introduisons le dispositif que nous avons conçu et qui permet de réaliser des portes d’intrication paramétrique entre deux qubits supraconducteurs. Cette approche a permis à nos collaborateurs du groupe d’Andrew Houck de l’Université de Princeton de réaliser expérimentalement une opération de type √iSWAP en 15 ns avec une fidélité de 98.8%, et ce dans un dispositif où l’interaction ZZ est supprimée. Dans la seconde partie de la thèse, nous avons développé un ansatz pour les VQAs permettant de résoudre le modèle de Fermi Hubbard. Ce nouvel ansatz utilise les avantages de deux ansätze préexistants, et permet d’obtenir l’énergie et l’état fondamental du FHM avec une précision de plusieurs ordres de grandeur supérieure aux ansätze standards, et ce en réduisant significativement le nombre de portes d’intrication CNOT qui sont généralement imparfaites et longues à implémenter.
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.