Description
Date depot: 8 avril 2021
Titre: Etude de codes LDPC quantiques avec distance quasi-linéaire
Directeur de thèse:
Anthony LEVERRIER (Inria-Paris (ED-130))
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé: Les codes correcteurs quantiques forment un prérequis incontournable si l’on veut un jour exploiter les propriétés quantiques pour transmettre et traiter l’information, en particulier si l’on veut développer l’ordinateur quantique. Leur objectif est le même que celui des codes correcteurs classiques, à savoir utiliser de la redondance afin de protéger de l’information contre diverses formes de bruit (par exemple, la décohérence dans le cas quantique). On souhaite notamment obtenir des familles de codes avec de bonnes capacités de correction, et des algorithmes de décodage efficaces.
Classiquement, les codes LDPC, qui correspondent au noyau d’une matrice de parité creuse, sont intéressants car ils peuvent être décodés de manière efficace grâce à des algorithmes de propagation de croyance. Par ailleurs, il est relativement simple d’obtenir de bons codes LDPC classiques, avec un rendement constant et une distance minimale linéaire. Dans le cas quantique, le caractère LDPC d’un code est d’autant plus important qu’il signifie que les contraintes (correspondant aux équations de parité) n’affectent qu’un petit nombre de qubits à la fois : cette propriété est essentielle en vue de la réalisation expérimentale de tels codes.
Jusqu’à très récemment, les meilleurs codes LDPC quantiques avaient une distance bornée essentiellement par la racine carrée de leur longueur. En particulier, les produits d’hypergraphes [1] sont une famille de codes quantiques LDPC particulièrement intéressante pour le calcul quantique tolérant aux fautes [2,3]. En effet, on a établi que ces codes permettent d’obtenir des schémas de tolérance aux fautes avec un ratio constant entre nombre de qubits physiques nécessaire à l’implémentation du circuit tolérant aux fautes et le nombre de qubits logiques du circuit que l’on veut simuler.
Très récemment, plusieurs généralisations des produits d’hypergraphes viennent d’être proposées [4,5] et permettent de briser la barrière de la racine carrée. Ces généralisations correspondent toujours à un produit de 2 codes classiques, avec de nouvelles notions de produit correspondant à un espace fibré pour [4], ou à un produit dans une algèbre commutative pour [5]. Ces différentes notions peuvent également être interprétées comme un « balanced product » [6]. L’objectif de cette thèse est d’explorer les voies proposées par ces nouvelles constructions, et en particulier de comprendre dans quelle mesure les nouvelles bornes sur les performances des codes LDPC : distance minimale d=O(n/log n), et compromis kd^2 = O(n^2) avec k la dimension du code, sont fondamentales, ou bien s’il est possible de construire de bons codes LDPC avec une distance et une dimension (quasi)-linéaire.
[1] Tillich, J. P., & Zémor, G. (2013). Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength. IEEE Transactions on Information Theory, 60(2), 1193-1202.
[2] Leverrier, A., Tillich, J. P., & Zémor, G. (2015, October). Quantum Expander Codes. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on (pp. 810-824). IEEE.
[3] Fawzi, O., Grospellier, A., & Leverrier, A. (2018, October). Constant overhead quantum fault-tolerance with quantum expander codes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) (pp. 743-754). IEEE.
[4] Hastings, M. B., Haah, J., & O’Donnell, R. (2020). Fiber Bundle Codes: Breaking the N^1/2 polylog (N) Barrier for Quantum LDPC Codes. arXiv preprint arXiv:2009.03921.
[5] Panteleev, P., & Kalachev, G. (2020). Quantum LDPC Codes with Almost Linear Minimum Distance. arXiv preprint arXiv:2012.04068.
[6] Breuckmann, N. P., & Eberhardt, J. N. (2020). Balanced Product Quantum Codes. arXiv preprint arXiv:2012.09271.