Description
Date depot: 1 janvier 1900
Titre: Codes LDPC quantiques : constructions et décodage
Directeur de thèse:
Jean-Pierre TILLICH (Inria-Paris (ED-130))
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Le thème central de la thèse est la théorie quantique de la correction d’erreurs dont le but est de protéger l’information quantique encodée sur des systèmes physiques. Etant donnée la fragilité des qubits face à la décohérence, l’utilisation de bons codes correcteurs quantiques semble être un préalable incontournable afin de développer à terme un ordinateur quantique. En particulier, on souhaite développer des codes qui soient pratiques (raisonnablement faciles à implémenter), avec une bonne capacité de correction (protégeant l’information contre les erreurs les plus usuelles) et disposant d’algorithmes de décodage efficaces.
Une approche particulièrement prometteuse consiste à développer l’analogue quantique des codes Low-Density Parity-Check (LDPC) qui sont particulièrement versatiles dans le cadre classique et dont la matrice de parité creuse semble être nécessaire pour obtenir des codes possibles à implémenter.
Une construction récente [TZ14] permet d’obtenir un code LDPC quantique à partir de 2 codes LDPC classiques. L’application de cette construction à des codes expanseurs [LTZ15] a permis d’exhiber la première famille de codes quantiques à rendement non nul disposant d’un algorithme de correction efficace corrigeant un nombre d’erreurs proportionnel à la racine carrée de la longueur du code.
Plusieurs questions ouvertes se situent de manière naturelle dans le prolongement de ces travaux et trouveraient d’importantes applications dans le domaine du calcul quantique.
1) Les meilleures constructions actuelles de codes LDPC quantiques peuvent corriger un motif d’erreur arbitraire de poids sous-linéaire avec une complexité polynomiale (linéaire). Quelle est la performance de ces codes pour des erreurs aléatoires ? Si de tels codes pouvaient corriger une fraction constante d’erreurs, alors ils pourraient être utilisés pour rendre des circuits quantiques tolérants aux fautes avec un coût constant en terme de taille de circuit (plutôt que polylogarithmique comme dans les meilleures constructions connues). La première partie de la thèse sera donc consacrée à l’étude d’algorithme de décodage pour les codes LDPC quantiques.
2) Pour de nombreuses applications des codes correcteurs en informatique, la notion de robustesse est pertinente : un code est robuste ou localement testable si le nombre de contraintes de parité violées par un mot est proportionnel à la distance du mot au code. En particulier, une erreur peut-être détectée en vérifiant un petit nombre de contraintes. La même notion peut être définie pour un code quantique. Alors qu’on connaît plusieurs familles de localement testables classiques, l’existence de codes localement testables quantiques reste une question ouverte aujourd’hui qui trouverait des applications en complexité hamiltonienne. Une approche naturelle pour obtenir de tels codes serait d’appliquer la construction [TZ14] à des codes classiques localement testables. La deuxième partie de la thèse pourra être dédiée à cette question.
3) Enfin, la dernière partie de la thèse pourra éventuellement porter sur la question de la faisabilité des mémoires quantiques auto-correctrices. L’une des raisons fondamentales qui a permis le développement de l’informatique est le fait qu’il est possible de stocker très facilement de grandes quantités d’information sur des supports physiques comme des disques durs, qui ne nécessitent pas de dispositifs de correction d’erreur active. La situation est malheureusement plus compliquée dans le cas de l’information quantique : toutes les mémoires quantiques connues requièrent de corriger les erreurs en temps réel afin de protéger l’information. Une solution beaucoup plus avantageuse serait de stocker l’information dans l’état fondamental d’un Hamiltonien dégénéré et qui protégerait contre les erreurs grâce à des barrières d’énergie. S’il est bien connu que la version à 4 dimensions du code torique constitue une telle mémoire quantique auto-correctrice, on souhaiterait développer une version à 3 dimensions (ou moins) afin de pouvoir espérer l’implémenter. Là encore, le produit de codes LDPC semble fournir une piste d’investigation prometteuse.
Mots-clés
Codes correcteurs, Codes quantiques, Théorie quantique de l’information, Complexité hamiltonienne
[TZ14] J.P. Tillich, G. Zémor, Quantum LDPC Codes With Positive Rate and Minimum Distance Proportional to the Square Root of the Blocklength. IEEE Trans. Information Theory 60(2): 1193-1202 (2014)$
[LTZ15] A. Leverrier, J.P. Tillich, G. Zémor:
Quantum Expander Codes. FOCS 2015: 810-824
Doctorant.e: Grospellier Antoine