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.