Accelerating A*-Based Algorithms for Decoding Quantum Low-Density Parity-Check Codes

• URL: http://arxiv.org/abs/2609.10056v1
• Date: Wed, 09 Sep 2026 11:30:45 GMT
• Title: Accelerating A*-Based Algorithms for Decoding Quantum Low-Density Parity-Check Codes
• Abstract summary: Quantum low-density parity-check (QLDPC) codes represent a promising approach for error correction in quantum computing.<n>The recently proposed Tesseract decoder uses the A* search algorithm that guarantees finding the most likely error pattern.<n>We propose a two-stage decoding framework to improve decoding efficiency.
• Score: 9.231222321291964
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum low-density parity-check (QLDPC) codes represent a promising approach for error correction in quantum computing. The recently proposed Tesseract decoder uses the A* search algorithm that guarantees finding the most likely error pattern. However, practical implementations of Tesseract often involve an extremely large graph, and the inherently sequential nature of the search results in high computational overhead and long runtime. To improve decoding efficiency, we propose a two-stage decoding framework. First, a belief propagation (BP) decoder efficiently processes the syndrome. This step generates hard decisions (a binary error vector) and soft information (per-qubit confidence levels). In non-convergent BP cases, a gating mechanism examines the BP decoder's output to identify and filter out qubits with oscillating confidence values. In these cases, the refined output serves as input to Tesseract, which then attempts to identify and correct any residual errors. This hybrid approach leverages the high speed of BP decoding and delegates the more challenging decoding instances to Tesseract. Numerical results demonstrate a substantial reduction in overall decoding complexity while maintaining the logical error rate (LER) of the stand-alone Tesseract. Across all tested physical error rates, the proposed method achieves at least 5x reduction in the number of expanded nodes in the Tesseract, with a peak reduction of nearly 15x at a physical error rate of p = 0.05 for the [[126, 12, d < 11]] T1 code, and approximately 8.8x at p = 0.05 for the [[72, 12, 6]] bicycle bivariate (BB) code.

Related papers

• Certified decoding of quantum LDPC codes [31.93810256110857]
  Quantum low-density parity-check (qLDPC) codes reduce the qubit overhead of fault-tolerant quantum computation by an order of magnitude.<n>Because many physical errors are equivalent up to stabilizers, the degenerate maximum-likelihood (ML) decoder must compare the probabilities of entire equivalence classes of errors, that is, partition functions, rather than single errors.<n>We treat degenerate decoding as probabilistic inference in an undirected graphical model.
  arXiv  Detail & Related papers  (2026-08-26T08:57:01Z)
• Optimal Decoding of Small Codes by Density Matrix Propagation [0.0]
  We study the accuracy of practical decoding algorithms under circuit-level noise.<n>We apply this framework to small instances of the repetition code and a cellular automaton code.<n>We find significant deviations for the cellular code, with BP+OSD deteriorating already in experimentally relevant noise regimes.
  arXiv  Detail & Related papers  (2026-06-12T13:43:44Z)
• Accelerating BP-OSD Decoder for QLDPC Codes with Local Syndrome-Based Preprocessing [4.392193109807139]
  Low-density parity-check (QLDPC) codes are one of the most promising quantum error correction methods.<n>BP-OSD is the state-of-the-art decoder for QLDPC codes, but it suffers from high decoding latency.<n>We propose a lightweight preprocessing step that utilizes local syndrome patterns to detect likely trivial error events.
  arXiv  Detail & Related papers  (2025-09-02T02:30:02Z)
• Reducing Storage of Pretrained Neural Networks by Rate-Constrained Quantization and Entropy Coding [56.066799081747845]
  The ever-growing size of neural networks poses serious challenges on resource-constrained devices.<n>We propose a novel post-training compression framework that combines rate-aware quantization with entropy coding.<n>Our method allows for very fast decoding and is compatible with arbitrary quantization grids.
  arXiv  Detail & Related papers  (2025-05-24T15:52:49Z)
• Fast correlated decoding of transversal logical algorithms [67.01652927671279]
  Quantum error correction (QEC) is required for large-scale computation, but incurs a significant resource overhead.<n>Recent advances have shown that by jointly decoding logical qubits in algorithms composed of logical gates, the number of syndrome extraction rounds can be reduced.<n>Here, we reform the problem of decoding circuits by directly decoding relevant logical operator products as they propagate through the circuit.
  arXiv  Detail & Related papers  (2025-05-19T18:00:00Z)
• Tesseract: A Search-Based Decoder for Quantum Error Correction [0.029541734875307393]
  Tesseract is a Most-Likely Error decoder for low-density-parity-check quantum error-correcting codes.<n>We show that Tesseract is significantly faster than integer programming while retaining moderate physical error rates.<n>We also find that Tesseract can decode protocols for surface codes on neutral atom quantum computers.
  arXiv  Detail & Related papers  (2025-03-14T01:23:53Z)
• An almost-linear time decoding algorithm for quantum LDPC codes under circuit-level noise [0.562479170374811]
  Fault-tolerant quantum computers must be designed in conjunction with classical co-processors.<n>We introduce the belief propagation plus ordered Tanner forest (BP+OTF) algorithm as an almost-linear time decoder for quantum low-density parity-check codes.
  arXiv  Detail & Related papers  (2024-09-02T19:50:57Z)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
  We propose a new technique to provide accurate estimates of the DFR of a two-iterations (parallel) bit flipping decoder.<n>We validate our results, providing comparisons of the modeled and simulated weight of the syndrome, incorrectly-guessed error bit distribution at the end of the first iteration, and two-itcrypteration Decoding Failure Rates (DFR)
  arXiv  Detail & Related papers  (2024-01-30T11:40:24Z)
• 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)
• Improved decoding of circuit noise and fragile boundaries of tailored surface codes [61.411482146110984]
  We introduce decoders that are both fast and accurate, and can be used with a wide class of quantum error correction codes. Our decoders, named belief-matching and belief-find, exploit all noise information and thereby unlock higher accuracy demonstrations of QEC. We find that the decoders led to a much higher threshold and lower qubit overhead in the tailored surface code with respect to the standard, square surface code.
  arXiv  Detail & Related papers  (2022-03-09T18:48:54Z)
• Pruning Neural Belief Propagation Decoders [77.237958592189]
  We introduce a method to tailor an overcomplete parity-check matrix to (neural) BP decoding using machine learning. We achieve performance within 0.27 dB and 1.5 dB of the ML performance while reducing the complexity of the decoder.
  arXiv  Detail & Related papers  (2020-01-21T12:05:46Z)

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.