Power and Limitations of Linear Programming Decoder for Quantum LDPC Codes

• URL: http://arxiv.org/abs/2508.04769v1
• Date: Wed, 06 Aug 2025 18:00:01 GMT
• Title: Power and Limitations of Linear Programming Decoder for Quantum LDPC Codes
• Authors: Shouzhen Gu, Mehdi Soleimanifar,
• Abstract summary: Decoding quantum error-correcting codes is a key challenge in enabling fault-tolerant quantum computation.<n>In this work, we uncover a key limitation of linear programming (LP) decoding for quantum low-density parity-check codes.<n>We incorporate a post-processing technique known as ordered statistics decoding (OSD) which significantly enhances LP decoding performance in practice.
• Score: 0.30912596009895504
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Decoding quantum error-correcting codes is a key challenge in enabling fault-tolerant quantum computation. In the classical setting, linear programming (LP) decoders offer provable performance guarantees and can leverage fast practical optimization algorithms. Although LP decoders have been proposed for quantum codes, their performance and limitations remain relatively underexplored. In this work, we uncover a key limitation of LP decoding for quantum low-density parity-check (LDPC) codes: certain constant-weight error patterns lead to ambiguous fractional solutions that cannot be resolved through independent rounding. To address this issue, we incorporate a post-processing technique known as ordered statistics decoding (OSD), which significantly enhances LP decoding performance in practice. Our results show that LP decoding, when augmented with OSD, can outperform belief propagation with the same post-processing for intermediate code sizes of up to hundreds of qubits. These findings suggest that LP-based decoders, equipped with effective post-processing, offer a promising approach for decoding near-term quantum LDPC codes.

Related papers

• On the Efficacy of the Peeling Decoder for the Quantum Expander Code [7.474073164750919]
  We show the use of quantum expander codes in conjunction with the peeling decoder that has linear complexity.<n>We also discuss additional techniques including small-set-flip decoding, that can be applied following the peeling operation.
  arXiv  Detail & Related papers  (2025-04-30T17:54:49Z)
• Decoding Quantum LDPC Codes using Collaborative Check Node Removal [0.0]
  We present a strategy to improve the performance of the iterative decoders based on a collaborative way.<n>We show that an integration of information measurements (IM) for qubits and it's adjacent stabilizer checks, can be exploited to extract far better performing results.
  arXiv  Detail & Related papers  (2025-01-14T11:41:45Z)
• Erasure Decoding for Quantum LDPC Codes via Belief Propagation with Guided Decimation [7.185960422285947]
  We show that guided decimation (BPGD) decoding of quantum LDPC codes offers competitive performance on quantum erasure channels. BPGD is an effective general-purpose solution for erasure decoding across the quantum LDPC landscape.
  arXiv  Detail & Related papers  (2024-11-12T20:45:43Z)
• Limitations of the decoding-to-LPN reduction via code smoothing [59.90381090395222]
  Researchers have attempted to demonstrate the algorithmic hardness of the Learning Parity with Noise problem.<n>We characterize the efficiency of the reduction in terms of the parameters of the decoding and primitive problems.
  arXiv  Detail & Related papers  (2024-08-07T12:54:43Z)
• Breadth-first graph traversal union-find decoder [0.0]
  We develop variants of the union-find decoder that simplify its implementation and provide potential decoding speed advantages. We show how these methods can be adapted to decode non-topological quantum low-density-parity-check codes.
  arXiv  Detail & Related papers  (2024-07-22T18:54:45Z)
• Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation [55.8930142490617]
  We propose a decoder for QLDPC codes based on BP guided decimation (BPGD) BPGD significantly reduces the BP failure rate due to non-convergence.
  arXiv  Detail & Related papers  (2023-12-18T05:58:07Z)
• Testing the Accuracy of Surface Code Decoders [55.616364225463066]
  Large-scale, fault-tolerant quantum computations will be enabled by quantum error-correcting codes (QECC) This work presents the first systematic technique to test the accuracy and effectiveness of different QECC decoding schemes.
  arXiv  Detail & Related papers  (2023-11-21T10:22:08Z)
• Single-shot decoding of good quantum LDPC codes [38.12919328528587]
  We prove that quantum Tanner codes facilitate single-shot quantum error correction (QEC) of adversarial noise. We show that in order to suppress errors over multiple repeated rounds of QEC, it suffices to run the parallel decoding algorithm for constant time in each round.
  arXiv  Detail & Related papers  (2023-06-21T18:00:01Z)
• Modular decoding: parallelizable real-time decoding for quantum computers [55.41644538483948]
  Real-time quantum computation will require decoding algorithms capable of extracting logical outcomes from a stream of data generated by noisy quantum hardware. We propose modular decoding, an approach capable of addressing this challenge with minimal additional communication and without sacrificing decoding accuracy. We introduce the edge-vertex decomposition, a concrete instance of modular decoding for lattice-surgery style fault-tolerant blocks.
  arXiv  Detail & Related papers  (2023-03-08T19:26:10Z)
• Deep Quantum Error Correction [73.54643419792453]
  Quantum error correction codes (QECC) are a key component for realizing the potential of quantum computing. In this work, we efficiently train novel emphend-to-end deep quantum error decoders. The proposed method demonstrates the power of neural decoders for QECC by achieving state-of-the-art accuracy.
  arXiv  Detail & Related papers  (2023-01-27T08:16:26Z)
• Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices [60.02503434201552]
  We propose to decode QLDPC codes based on a check matrix with redundant rows, generated from linear combinations of the rows in the original check matrix. This approach yields a significant improvement in decoding performance with the additional advantage of very low decoding latency.
  arXiv  Detail & Related papers  (2022-12-20T13:41:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.