Efficient decoding of random errors for quantum expander codes
arXiv:1711.08351 · doi:10.1145/3188745.3188886
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 -percolation: for a random subset of vertices of a given graph, we consider the size of the largest connected -subset of , where is an -subset of if .
arXiv comment26 pages
References in corpus (13)
- Fault-tolerant quantum computation by anyons
- Good Quantum Error-Correcting Codes Exist
- Topological quantum memory
- Quantum LDPC codes with positive rate and minimum distance proportional to n^{1/2}
- 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
- Quantum Expander Codes
- Quantum error-correcting codes and 4-dimensional arithmetic hyperbolic manifolds
- Fault-Tolerant Quantum Computation with Constant Overhead
- Threshold error rates for the toric and surface codes
- Decoding in Hyperbolic Spaces: LDPC Codes With Linear Rate and Efficient Error Correction
- Golden codes: quantum LDPC codes built from regular tessellations of hyperbolic 4-manifolds