Degeneracy Cutting: A Local and Efficient Post-Processing for Belief Propagation Decoding of Quantum Low-Density Parity-Check Codes

Basic Information

• Paper ID: 2510.08695
• Title: Degeneracy Cutting: A Local and Efficient Post-Processing for Belief Propagation Decoding of Quantum Low-Density Parity-Check Codes
• Authors: Kento Tsubouchi, Hayata Yamasaki, Shiro Tamiya
• Classification: quant-ph (Quantum Physics)
• Publication Date: October 9, 2024
• Paper Link: https://arxiv.org/abs/2510.08695

Abstract

Quantum low-density parity-check (qLDPC) codes show great promise for implementing scalable fault-tolerant quantum computation due to their potential for low-overhead protocols. A common approach for decoding qLDPC codes is to use belief propagation (BP) decoders followed by post-processing steps to improve decoding accuracy. For real-time decoding, post-processing algorithms must have low computational cost and rely only on local operations on the Tanner graph to facilitate parallel implementation. To meet these requirements, this paper proposes degeneracy cutting (DC), an efficient post-processing technique for BP decoders that operates only on the support set of each stabilizer generator. DC selectively removes variable nodes with the lowest error probability for each stabilizer generator, significantly improving decoding performance while maintaining the favorable computational scaling and parallelization structure inherent to BP.

Research Background and Motivation

Problem Definition

1. Core Problem: Belief propagation decoding of qLDPC codes suffers significantly degraded performance due to the degeneracy of quantum codes, necessitating efficient post-processing methods to improve decoding accuracy.
2. Practical Requirements: Fault-tolerant quantum computation requires real-time decoding capability, demanding decoding algorithms with low computational complexity and high parallelization potential.
3. Limitations of Existing Methods:
   • BP+OSD achieves high accuracy but has O(n³) computational complexity, unsuitable for real-time applications.
   • Other post-processing methods either have high computational complexity or rely on global information comparison, making them difficult to parallelize.

Research Motivation

Degeneracy in quantum codes refers to the phenomenon where different physical error patterns may produce identical symptoms, preventing BP decoders from distinguishing between these patterns. This degeneracy causes particularly severe decoding failures in qLDPC codes, as low-weight stabilizer generators produce numerous plausible degenerate error patterns.

Core Contributions

1. Proposes Degeneracy Cutting (DC) Algorithm: A linear-time post-processing technique based solely on local information.
2. Maintains Computational Efficiency: Reduces computational complexity from O(n³) to O(n) while maintaining performance close to BP+OSD.
3. Introduces Detector Degeneracy Matrix: Extends the method to realistic noise models (phenomenological and circuit-level noise models).
4. Achieves High Parallelizability: Algorithm decisions are based only on local comparisons within each stabilizer generator, facilitating parallel implementation.
5. Numerical Verification: Validates the method's effectiveness on surface codes and bivariate bicycle (BB) codes.

Methodology Details

Task Definition

Given:

• Input: Z-type parity-check matrix H_Z, observed syndrome s_Z, prior error probability p
• Output: Estimated X-type error ê_X, satisfying ê_X H_Z^T = s_Z with residual error being trivial

Core Algorithm: Degeneracy Cutting (DC)

Algorithm Flow

Algorithm 1: BP+DC decoder
Input: Parity-check matrices H_X, H_Z; observed syndrome s_Z; prior error probability p; 
        maximum BP iterations T_iter
Output: Estimated X-type error ê_X

1. (ê_X, p̂) ← BP_decode(H_Z, s_Z, p, T_iter)
2. if ê_X H_Z^T = s_Z then return ê_X
3. Cut_indexes ← {}
4. for each row vector h_X in H_X do
5.    i_min ← argmin_{i∈{i|(h_X)_i=1}} p̂_i
6.    Cut_indexes ← Cut_indexes ∪ {i_min}
7. Delete columns of H_Z indexed by Cut_indexes
8. (ê_X, p̂) ← BP_decode(H_Z, s_Z, p̂, T_iter)
9. return ê_X

Core Idea

1. Degeneracy Identification: For each X-type stabilizer generator h_X, identify the variable node with the lowest error probability within its support set.
2. Node Removal: Remove these nodes from the Tanner graph to break local degeneracy.
3. Re-decoding: Re-run BP decoding on the modified graph.

Technical Innovations

1. Locality Advantages

• Unlike global methods, DC performs comparisons only within each stabilizer generator.
• The number of compared nodes is bounded by a constant r (row weight).
• Naturally supports parallel implementation.

2. Degeneracy Handling Mechanism

For degenerate errors e_X and e'_X satisfying e_X + e'_X = h_X (stabilizer generator), DC eliminates degeneracy by removing variable nodes supporting one of the errors.

3. Computational Complexity Analysis

• Initial BP decoding: O(n)
• Node identification and removal: O(n) (bounded row weight)
• Second BP decoding: O(n)
• Total complexity: O(n)

Extension to Realistic Noise Models

Detector Degeneracy Matrix H_DDM

To handle additional degeneracies in phenomenological and circuit-level noise models, the paper introduces a detector degeneracy matrix:

1. Phenomenological Noise Model: Includes degeneracies caused by measurement errors.
2. Circuit-Level Noise Model: Includes weight-3 circuit-level degeneracies.

Construction Method

Each row of H_DDM represents a low-weight error satisfying:

• h_DDM H_DCM^T = 0 (undetected by detectors)
• h_DDM O^T = 0 (does not affect logical information)

Experimental Setup

Test Code Families

1. Surface Codes: Rotated surface codes with distance d ∈ {3,5,7}
2. Bivariate Bicycle Codes: [[72,12,6]], [[108,8,10]], [[144,12,12]]

Noise Models

1. Code Capacity Noise Model: Independent bit-flip errors on data qubits only
2. Phenomenological Noise Model: Errors on both data qubits and syndrome measurements
3. Circuit-Level Noise Model: Complete syndrome extraction circuit noise

Comparison Methods

• BP decoder
• BP+OSD decoder
• BP+DC decoder
• BP+DC+OSD decoder

Experimental Results

Main Results

Code Capacity Noise Model

• Surface Codes: BP+DC performance approaches BP+OSD with slight gap
• BB Codes: BP+DC outperforms BP+OSD

Phenomenological Noise Model

• BP+DC achieves logical error suppression comparable to BP+OSD on both surface codes and BB codes
• Computational complexity reduced from O(N³) to O(N)

Circuit-Level Noise Model

• BP+DC maintains performance within one order of magnitude of BP+OSD in more complex noise environments
• Performance gap increases for larger code distances

Key Findings

1. BB Code Advantage: For BB codes, using prior probability p rather than posterior probability p̂ as input to the second BP improves performance.
2. Validity Verification: BP+DC+OSD matches BP+OSD performance, confirming valid solutions exist in the modified Tanner graph.
3. Scalability: The method demonstrates good scalability across different code distances and noise models.

Related Work

Post-Processing Method Classification

1. Linear Equation Solving Based: OSD, local statistical decoding, fuzzy clustering
2. Sequential Decision Based: branch-and-bound decoding, decision tree decoding
3. Graph Modification Based: stabilizer deactivation, SymBreak, check node forgetting, guided extraction

Advantages of This Work

• Only method simultaneously achieving O(n) complexity, local decisions, and high performance
• Scalable stabilizer-based method for realistic noise models

Conclusions and Discussion

Main Conclusions

1. The DC algorithm effectively addresses degeneracy problems in BP decoding.
2. Achieves performance close to BP+OSD while maintaining linear computational complexity.
3. The detector degeneracy matrix successfully extends the method to realistic noise models.

Limitations

1. Under circuit-level noise, performance gap may increase with code distance.
2. Current detector degeneracy matrix construction may not capture all relevant degeneracies.
3. For certain code families (e.g., surface codes), using posterior probability for second BP is more effective, but the underlying reason remains unclear.

Future Directions

1. Improved Detector Degeneracy Matrix: Include higher-weight trivial errors.
2. Integration with Other BP Improvements: Such as code automorphisms, memory effects, etc.
3. Theoretical Analysis: Establish rigorous proofs for decoding thresholds.
4. Algorithm Optimization: Apply DC intermittently during BP iterations.

In-Depth Evaluation

Strengths

1. High Practical Value: Addresses critical bottleneck in real-time quantum error correction.
2. Theoretical Contribution: Detector degeneracy matrix concept has universal applicability.
3. Comprehensive Experiments: Covers multiple code families and noise models.
4. Engineering-Friendly: Highly parallelizable, suitable for hardware implementation.

Weaknesses

1. Insufficient Theoretical Analysis: Lacks theoretical guarantees for method validity.
2. Parameter Tuning: Different code families require different parameter selection strategies.
3. Performance Gap: Still shows notable gap with BP+OSD in certain settings.

Impact

1. Academic Contribution: Provides new practical method for qLDPC decoding.
2. Engineering Value: Offers viable path for fault-tolerant quantum computing hardware design.
3. Reproducibility: Clear algorithm description facilitates implementation.

Applicable Scenarios

1. Real-Time Quantum Error Correction: Particularly suitable for low-latency decoding scenarios.
2. Large-Scale Quantum Computing: Provides balanced performance in resource-constrained environments.
3. Parallel Processing Architectures: Fully leverages modern parallel computing capabilities.

References

The paper cites 63 relevant references covering key works in quantum error correction, LDPC codes, and belief propagation algorithms, providing solid theoretical foundation for the research.

Overall Assessment: This is a paper of significant practical value in quantum error correction. The degeneracy cutting algorithm cleverly balances decoding performance, computational efficiency, and implementation complexity, providing a valuable solution for practical fault-tolerant quantum computing systems. While improvements remain possible in certain aspects, its innovation and practicality make it an important contribution to the field.