Good Quantum LDPC Codes with Linear Time Decoders

We construct a new explicit family of good quantum low-density parity-check codes which additionally have linear time decoders. Our codes are based on a three-term chain (2 m × m ) V → δ 0 (2 m ) E → δ 1 2 F where V ( X -checks) are the vertices, E (qubits) are the edges, and F ( Z -checks) are the squares of a left-right Cayley complex, and where the maps are defined based on a pair of constant-size random codes C A , C B :2 m →2 Δ where Δ is the regularity of the underlying Cayley graphs. One of the main ingredients in the analysis is a proof of an essentially-optimal robustness property for the tensor product of two random codes.

Authors

• Irit Dinur
• Min-Hsiu Hsieh
• Ting-Chun Lin
• Thomas Vidick

Keywords

• error-correcting codes
• locally testable codes
• quantum low-density parity-check codes