Quantum LDPC Codes With Almost Linear Minimum Distance

2021/10/11 by Pavel Panteleev, Gleb Kalachev · 44 citations
Computer Science · #Quantum Computing Algorithms and Architecture #Error Correcting Code Techniques #Advanced Data Storage Technologies

paper · doi:10.1109/tit.2021.3119384

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">Θ (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">Θ (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→ ∞ </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">Ω (N^{1-α /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">Ω (N^α 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 ≤ α &lt; 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 &lt; 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">Ω (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→ ∞ </tex-math></inline-formula> .

Citations

• Quantum LDPC Codes With Positive Rate and Minimum Distance Proportional to the Square Root of the Blocklength

Cited by

• Learning to Decode Quantum LDPC Codes via Cluster-Based Sequential Belief Propagation
• Design and Analysis of Quantum Dual-Containing CSS LDPC Codes based on Quasi-Dyadic Matrices
• LDGM-Based Quantum Codes for Fault-Tolerant Quantum Computation
• Quantum XYZ Stabilizer Codes
• Full Extractors for Logical Processing in Hypergraph Product Codes
• Engineering CSS surgery: compiling any CNOT in any code
• Distilling GHZ States using Stabilizer Codes
• Machine Learning Decoding of Circuit-Level Noise for Bivariate Bicycle Codes
• Scalable Neural Decoders for Practical Fault-Tolerant Quantum Computation
• Evolutionary BP+OSD Decoding for Low-Latency Quantum Error Correction
• SAQ: Stabilizer-Aware Quantum Error Correction Decoder
• Cycle Basis Algorithms for Reducing Maximum Edge Participation
• Addressable gate-based logical computation with quantum LDPC codes
• Good quantum codes with addressable and parallelizable non-Clifford gates
• Decoding Correlated Errors in Quantum LDPC Codes
• Degeneracy Cutting: A Local and Efficient Post-Processing for Belief Propagation Decoding of Quantum Low-Density Parity-Check Codes
• Noisy-Syndrome Decoding of Hypergraph Product Codes
• Transversal dimension jump for product qLDPC codes
• Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks
• Layer codes as partially self-correcting quantum memories
• Cored product codes for quantum self-correction in three dimensions
• Correcting quantum errors using a classical code and one additional qubit
• Bounds on stabilizer measurement circuits and obstructions to local implementations of quantum LDPC codes
• Decoding quantum low density parity check codes with diffusion
• Pair-Partition Constructions for CPM-Based Quantum LDPC Codes
• Rare Event Simulation of Quantum Error-Correcting Circuits
• Fermion-to-Fermion Low-Density Parity-Check Codes
• Tableau-Based Framework for Efficient Logical Quantum Compilation
• A simple universal routing strategy for reducing the connectivity requirements of quantum LDPC codes
• Magic tricycles: Efficient magic state generation with finite block-length quantum LDPC codes
• GPU-Accelerated Syndrome Decoding for Quantum LDPC Codes below the 63 μs Latency Threshold
• Growing Sparse Quantum Codes from a Seed
• Power and Limitations of Linear Programming Decoder for Quantum LDPC Codes
• No-go theorems for logical gates on product quantum codes
• Transversal non-Clifford gates on qLDPC codes breaking the √(N) distance barrier and quantum-inspired geometry with ℤ₂ systolic freedom
• Small Quantum Low Density Parity Check Codes for Near-Term Experiments
• Bias-tailored single-shot quantum LDPC codes
• Improved energy barrier in higher-dimensional hypergraph product codes
• Abelian multi-cycle codes for single-shot error correction
• Transversal Gates for Highly Asymmetric qLDPC Codes
• Constructing Grith Eight GC-LDPC Codes Based on the GCD FLRM Matrix with a New Lower Bound. [europepmc]
• Quantum Coding via Quasi-Cyclic Block Matrix. [europepmc]
• Quantum LDPC Codes Based on Cocyclic Block Matrices. [europepmc]
• High-threshold and low-overhead fault-tolerant quantum memory. [europepmc]
• Layer codes. [europepmc]
• Decoding correlated errors in quantum LDPC codes. [europepmc]

Related

• Quantum LDPC Codes of Almost Linear Distance via Homological Products
• Quantum LDPC Codes With Positive Rate and Minimum Distance Proportional to the Square Root of the Blocklength
• Decodable quantum LDPC codes beyond the √(n) distance barrier using high dimensional expanders
• Balanced Product Quantum Codes
• Numerical Techniques for Finding the Distances of Quantum Codes