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é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 $\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|\ge \alpha |X|$.

26 pages

References in corpus (4)

• A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes
• Almost-linear time decoding algorithm for topological codes
• Fault-Tolerance of "Bad" Quantum Low-Density Parity Check Codes
• Golden codes: quantum LDPC codes built from regular tessellations of hyperbolic 4-manifolds

Cited by in corpus (1)

• Connectivity constrains quantum codes