Quantum LDPC Codes with Almost Linear Minimum Distance

Abstract

We give a construction of quantum LDPC codes of dimension $\Theta (\log N)$ and distance $\Theta (N/\log N)$ as the code length $N\to \infty$. Using a product of chain complexes this construction also provides a family of quantum LDPC codes of distance $\Omega (N^{1-\alpha /2}/\log N)$ and dimension $\Omega (N^{\alpha }\log N)$, where $0\le \alpha <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 $\Omega (N/\log N)$ as the code length $N\to \infty$.

17 pages, 2 figures. Accepted for publication in IEEE Transactions on Information Theory

References in corpus (3)

• Local stabilizer codes in three dimensions without string logical operators
• Efficient Algorithms for Maximum Likelihood Decoding in the Surface Code
• Fiber Bundle Codes: Breaking the $N^{1/2}\mathrm{polylog}(N)$ Barrier for Quantum LDPC Codes

Cited by in corpus (22)

• Quantum Low-Density Parity-Check Codes
• Low-overhead fault-tolerant quantum computing using long-range connectivity
• Fiber Bundle Codes: Breaking the $N^{1/2}\mathrm{polylog}(N)$ Barrier for Quantum LDPC Codes
• Trapping Sets of Quantum LDPC Codes
• Bias-tailored quantum LDPC codes
• Quantifying nonlocality: how outperforming local quantum codes is expensive
• Finite Rate QLDPC-GKP Coding Scheme that Surpasses the CSS Hamming Bound
• Tailored XZZX codes for biased noise
• Connectivity constrains quantum codes
• Fold-Transversal Clifford Gates for Quantum Codes
• Quantum LDPC Codes for Modular Architectures
• Error-correcting codes for fermionic quantum simulation
• Quantum XYZ Product Codes
• Entanglement Purification with Quantum LDPC Codes and Iterative Decoding
• CSS code surgery as a universal construction
• Quantum Routing with Teleportation
• Bounds on stabilizer measurement circuits and obstructions to local implementations of quantum LDPC codes
• Partially Concatenated Calderbank-Shor-Steane Codes Achieving the Quantum Gilbert-Varshamov Bound Asymptotically
• Circuit lower bounds for low-energy states of quantum code Hamiltonians
• A construction of Combinatorial NLTS
• Quantum Locally Testable Code with Constant Soundness
• Distilling GHZ States using Stabilizer Codes