Quantum LDPC Codes with Almost Linear Minimum Distance

We give a construction of quantum LDPC codes of dimension Θ(log N) and distance Θ(N/log N) as the code length N → ∞. Using a product of chain complexes this construction also provides a family of quantum LDPC codes of distance Ω(N1-α/2/log N) and dimension Ω(Nα log N), where 0 ≤ α < 1. 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 R < 1 there exists an asymptotically good family of classical quasi-cyclic LDPC codes of rate at least R with, in some sense, optimal circulant size Ω(N/log N) as the code length N → ∞.