Quantum LDPC Codes With Almost Linear Minimum Distance
Pavel Panteleev, Gleb Kalachev
Abstract
We give a construction of quantum LDPC codes of dimension <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Theta (\log N)$ </tex-math></inline-formula> and distance <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Theta (N/\log N)$ </tex-math></inline-formula> as the code length <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$N\to \infty $ </tex-math></inline-formula> . Using a product of chain complexes this construction also provides a family of quantum LDPC codes of distance <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Omega (N^{1-\alpha /2}/\log N)$ </tex-math></inline-formula> and dimension <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Omega (N^\alpha \log N)$ </tex-math></inline-formula> , where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$0 \le \alpha < 1$ </tex-math></inline-formula> . 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$R < 1$ </tex-math></inline-formula> there exists an asymptotically good family of classical quasi-cyclic LDPC codes of rate at least <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$R$ </tex-math></inline-formula> with, in some sense, optimal circulant size <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Omega (N/\log N)$ </tex-math></inline-formula> as the code length <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$N\to \infty $ </tex-math></inline-formula> .