Good Quantum LDPC Codes with Linear Time Decoders

2022/06/15 by Irit Dinur, Min-Hsiu Hsieh, Dinur, Irit +5 · 42 citations
Computer Science · Physics and Astronomy · #Error Correcting Code Techniques #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.2206.07750

arxiv created 2022/06/15 · openalex publication_date 2022/06/15 · arxiv updated 2022/06/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We construct a new explicit family of good quantum low-density parity-check codes which additionally have linear time decoders. Our codes are based on a three-term chain (\mathbbF₂^{m× m})^V \xrightarrowδ⁰ (\mathbbF₂^m)^E \xrightarrowδ¹ \mathbbF₂^F where V (X-checks) are the vertices, E (qubits) are the edges, and F (Z-checks) are the squares of a left-right Cayley complex, and where the maps are defined based on a pair of constant-size random codes C_A,C_B:\mathbbF₂^m→\mathbbF₂^Δ where Δ is the regularity of the underlying Cayley graphs. One of the main ingredients in the analysis is a proof of an essentially-optimal robustness property for the tensor product of two random codes.

Cited by

• Quantum Weight Reduction with Layer Codes
• Small quantum Tanner codes from left--right Cayley complexes
• Optimized Many-Hypercube Codes toward Lower Logical Error Rates and Earlier Realization
• Sequences of Bivariate Bicycle Codes from Covering Graphs
• The Fast for the Curious: How to accelerate fault-tolerant quantum applications
• Good quantum codes with addressable and parallelizable transversal non-Clifford gates
• Universal energy-space localization and stable quantum phases against time-dependent perturbations
• Decoding Correlated Errors in Quantum LDPC Codes
• Quantum Low-Density Parity-Check Codes
• Simplified Quantum Weight Reduction with Optimal Bounds
• Partial Self-Correction in Layer 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
• Diffusion Codes: Self-Correction from Small(er)-Set Expansion with Tunable Non-locality
• 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
• Nonlocal Magic Generation and Information Scrambling in Noisy Clifford Circuits
• CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version)
• State complexity and phase identification in adaptive quantum circuits
• Rare Event Simulation of Quantum Error-Correcting Circuits
• Efficient Entanglement Purification Circuit Design for Dual-Species Atom Arrays
• Tableau-Based Framework for Efficient Logical Quantum Compilation
• A simple universal routing strategy for reducing the connectivity requirements of quantum LDPC codes
• Generalized Bicycle Codes with Low Connectivity: Minimum Distance Bounds and Hook Errors
• GPU-Accelerated Syndrome Decoding for Quantum LDPC Codes below the 63 μs Latency Threshold
• Growing Sparse Quantum Codes from a Seed
• ConiQ: Enabling Concatenated Quantum Error Correction on Neutral Atom Arrays
• Explicit Instances of Quantum Tanner Codes
• Power and Limitations of Linear Programming Decoder for Quantum LDPC Codes
• No-go theorems for logical gates on product quantum codes
• Towards self-correcting quantum codes for neutral atom arrays
• Small Quantum Low Density Parity Check Codes for Near-Term Experiments
• Unified Framework for Quantum Code Embedding
• Improved energy barrier in higher-dimensional hypergraph product codes
• Planar fault-tolerant logical measurements with low qubit overhead
• Transversal Gates for Highly Asymmetric qLDPC Codes
• Algebraic Topology Principles behind Topological Quantum Error Correction
• On the Efficacy of the Peeling Decoder for the Quantum Expander Code
• List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
• Planar quantum low-density parity-check codes with open boundaries

Related

• Good quantum LDPC codes with linear time decoder from lossless expanders
• List Decodable Quantum LDPC Codes
• An efficient decoder for a linear distance quantum LDPC code
• Decoding Quasi-Cyclic Quantum LDPC Codes
• Quantum Expander Codes