Efficient decoding of random errors for quantum expander codes

Abstract : We show that quantum expander codes, a constant-rate family of quantum LDPC codes, with the quasi-linear time decoding algorithm of Leverrier, Tillich and Z\'emor can correct a constant fraction of random errors with very high probability. This is the first construction of a constant-rate quantum LDPC code with an efficient decoding algorithm that can correct a linear number of random errors with a negligible failure probability. Finding codes with these properties is also motivated by Gottesman's construction of fault tolerant schemes with constant space overhead. In order to obtain this result, we study a notion of $\alpha$-percolation: for a random subset $W$ of vertices of a given graph, we consider the size of the largest connected $\alpha$-subset of $W$, where $X$ is an $\alpha$-subset of $W$ if $|X \cap W| \geq \alpha |X|$.
Type de document :
Pré-publication, Document de travail
2017
Liste complète des métadonnées

https://hal.inria.fr/hal-01671348
Contributeur : Anthony Leverrier <>
Soumis le : vendredi 22 décembre 2017 - 10:52:24
Dernière modification le : lundi 15 octobre 2018 - 10:58:01

Lien texte intégral

Identifiants

  • HAL Id : hal-01671348, version 1
  • ARXIV : 1711.08351

Collections

Citation

Omar Fawzi, Antoine Grospellier, Anthony Leverrier. Efficient decoding of random errors for quantum expander codes. 2017. 〈hal-01671348〉

Partager

Métriques

Consultations de la notice

93