Efficient decoding of random errors for quantum expander codes

We show that quantum expander codes, a constant-rate family of quantum low-density parity check (LDPC) codes, with the quasi-linear time decoding algorithm of Leverrier, Tillich and Zémor 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 α-percolation: for a random subset E of vertices of a given graph, we consider the size of the largest connected α-subset of E , where X is an α-subset of E if | X ∩ E | ≥ α | X |.

Authors

• Omar Fawzi
• Antoine Grospellier
• Anthony Leverrier

Keywords

• Decoding algorithm
• expander codes
• percolation
• quantum error correction