2020/12/31 by Pavel Panteleev, Gleb Kalachev · 54 citations
Computer Science · Mathematics · Physics and Astronomy · #Advanced Data Storage Technologies #Algorithm #Chain (unit) #Code (set theory) #Combinatorics #Computer science #Decoding methods #Dimension (graph theory) #Discrete mathematics #Error Correcting Code Techniques #Geometry #Low-density parity-check code #Mathematics #Minimum distance #Omega #Physics #Product (mathematics) #Quantum #Quantum Computing Algorithms and Architecture #Quantum mechanics #Set (abstract data type) #cs.IT #math.IT #msc:81P73 #msc:94Bxx #quant-ph
paper · pdf · doi:10.1109/tit.2021.3119384
published in IEEE Transactions on Information Theory 68(1), 213-229 (Institute of Electrical and Electronics Engineers) · 17 pages, 2 figures. Accepted for publication in IEEE Transactions on Information Theory
arxiv created 2021/10/03 · openalex publication_date 2021/10/11 · arxiv updated 2022/01/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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→∞.