Quantum Expander Codes

We present an efficient decoding algorithm for constant rate quantum hyper graph-product LDPC codes which provably corrects adversarial errors of weight proportional to the code minimum distance, or equivalently to the square-root of the block length. The algorithm runs in time linear in the number of qubits, which makes its performance the strongest to date for linear-time decoding of quantum codes. The algorithm relies on expanding properties, not of the quantum code's factor graph directly, but of the factor graph of the original classical code it is constructed from.

Authors

• Anthony Leverrier
• Jean-Pierre Tillich
• Gilles Zémor

Keywords

• Decoding
• Graph theory
• Quantum computing
• Iterative decoding
• Robustness
• Generators
• Expander Codes
• Minimum Distance
• Linear Time
• Low-density Parity-check Codes
• Factor Graph
• Quantum Error Correction
• Decoding Algorithm
• Decoding Process
• Error Patterns
• Random Choice
• Linear Code
• Greek Letters
• Weight Error
• Neighboring Vertices
• Code Construction
• Decoding Scheme
• Subset Of Vertices
• Hamming Weight
• Parity-check Matrix
• Fractional Distance
• LDPC codes
• quantum codes
• CSS codes