Quantum LDPC Codes With Almost Linear Minimum Distance

We give a construction of quantum LDPC codes of dimension <tex-math notation="LaTeX">Θ (log N) </tex-math> and distance <tex-math notation="LaTeX">Θ (N/log N) </tex-math> as the code length <tex-math notation="LaTeX">N→ ∞ </tex-math> . Using a product of chain complexes this construction also provides a family of quantum LDPC codes of distance <tex-math notation="LaTeX">Ω (N1-α /2/log N) </tex-math> and dimension <tex-math notation="LaTeX">Ω (N^α log N) </tex-math> , where <tex-math notation="LaTeX">0 ≤ α < 1 </tex-math> . We also introduce and study a new operation called lifted product, which naturally generalizes the product operations for quantum codes and chain complexes. Moreover, as a simple byproduct of our results on quantum codes, we obtain a new result on classical codes. We show that for any fixed <tex-math notation="LaTeX">$R < 1$ </tex-math> there exists an asymptotically good family of classical quasi-cyclic LDPC codes of rate at least <tex-math notation="LaTeX">R </tex-math> with, in some sense, optimal circulant size <tex-math notation="LaTeX">Ω (N/log N) </tex-math> as the code length <tex-math notation="LaTeX">N→ ∞ </tex-math> .