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 $({\mathbb{F}}_2^{m\times m}{)}^V\stackrel{{\delta }^0}{\to }({\mathbb{F}}_2^m{)}^E\stackrel{{\delta }^1}{\to }{\mathbb{F}}_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:{\mathbb{F}}_2^m\to {\mathbb{F}}_2^{\mathrm{\Delta }}$ where $\mathrm{\Delta }$ 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.