Description
Date depot: 10 avril 2019
Titre: Décodage de codes quantiques LDPC
Directeur de thèse:
Anthony LEVERRIER (Inria-Paris (ED-130))
Directeur de thèse:
Omar FAWZI (Inria-Lyon)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Le principal obstacle technique à la construction d'un ordinateur quantique est la décohérence, c'est-à-dire le bruit induit par l'inévitable interaction entre l'information quantique stockée dans les bits quantiques (qubits) et l'environnement.
Pour résoudre ce problème, on a développé des techniques de calcul quantique tolérant aux fautes, qui reposent sur l'existence de bons codes correcteurs quantiques qui protègent l'information quantique de manière redondante.
En particulier, la famille des codes quantiques expanseurs [1,2] permet d'obtenir des schémas tolérants aux fautes tels que le ratio du nombre de qubits physiques (bruités) au nombre de qubits logiques (idéaux, sur lesquels on effectue le calcul) est asymptotiquement constant quand la taille du circuit augmente [3].
L'objectif de cette thèse est d'étudier les performances de ce schéma dans un cadre non asymptotique. Cette question porte donc sur les capacités de décodage des codes expanseurs quantiques. En particulier, les résultats asymptotiques de [3] sont obtenus en analysant la performance d'un algorithme de décodage inspiré du bit-flip et qui prend des décisions dures : à chaque étape de l'algorithme, on choisit de 'flipper' ou non un certain ensemble de qubits. Cette approche est clairement sous-optimale et l'on s'attend à ce que des algorithmes de décodage à décision souple améliorent les performances de manière significative. On est ainsi dans une situation analogue aux codes classiques où l'on sait que les algorithmes de type 'propagation de croyance' atteignent d'excellent résultats pour le décodage de codes LDPC (qui ont une matrice de parité creuse), et se comportent bien mieux que des algorithmes à décisions dures comme le bit-flip.
[1]A. Leverrier, J.P. Tillich, G. Zémor, Quantum expander codes, FOCS (2015)
[2] J.P. Tillich, G. Zémor, Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength, Transactions on Information Theory (2014)
[3] O. Fawzi, A. Grospellier, A. Leverrier, Constant overhead quantum fault-tolerance with quantum expander codes, FOCS (2018)
Doctorant.e: Groues Lucien