Improved Belief Propagation Decoding Algorithms for Surface Codes

• URL: http://arxiv.org/abs/2407.11523v4
• Date: Tue, 31 Dec 2024 03:26:56 GMT
• Title: Improved Belief Propagation Decoding Algorithms for Surface Codes
• Authors: Jiahan Chen, Zhengzhong Yi, Zhipeng Liang, Xuan Wang,
• Abstract summary: Belief propagation (BP) is notable for its nearly linear time complexity and general applicability to stabilizer codes. This article focuses on improving the decoding accuracy of BP over GF(4) for surface codes. We propose EWAInit-BP, which adaptively updates initial probabilities and provides a 1 to 3 orders of magnitude improvement over traditional BP.
• Score: 5.916355710767515
• License:
• Abstract: Quantum error correction is crucial for universal fault-tolerant quantum computing. Highly accurate and low-time-complexity decoding algorithms play an indispensable role in ensuring quantum error correction works effectively. Among existing decoding algorithms, belief propagation (BP) is notable for its nearly linear time complexity and general applicability to stabilizer codes. However, BP's decoding accuracy without post-processing is unsatisfactory in most situations. This article focuses on improving the decoding accuracy of BP over GF(4) for surface codes. Inspired by machine learning optimization techniques, we first propose Momentum-BP and AdaGrad-BP to reduce oscillations in message updating, breaking the trapping sets of surface codes. We further propose EWAInit-BP, which adaptively updates initial probabilities and provides a 1 to 3 orders of magnitude improvement over traditional BP for planar surface code, toric code, and XZZX surface code without any post-processing method, showing high decoding accuracy even under parallel scheduling. The theoretical $O(1)$ time complexity under parallel implementation and high accuracy of EWAInit-BP make it a promising candidate for high-precision real-time decoders.

Related papers

• Efficient Approximate Degenerate Ordered Statistics Decoding for Quantum Codes via Reliable Subset Reduction [5.625796693054094]
  We introduce the concept of approximate degenerate decoding and integrate it with ordered statistics decoding (OSD) We present an ADOSD algorithm that significantly improves OSD efficiency in the code capacity noise model.
  arXiv  Detail & Related papers  (2024-12-30T17:45:08Z)
• Demonstrating dynamic surface codes [138.1740645504286]
  We experimentally demonstrate three time-dynamic implementations of the surface code. First, we embed the surface code on a hexagonal lattice, reducing the necessary couplings per qubit from four to three. Second, we walk a surface code, swapping the role of data and measure qubits each round, achieving error correction with built-in removal of accumulated non-computational errors. Third, we realize the surface code using iSWAP gates instead of the traditional CNOT, extending the set of viable gates for error correction without additional overhead.
  arXiv  Detail & Related papers  (2024-12-18T21:56:50Z)
• SymBreak: Mitigating Quantum Degeneracy Issues in QLDPC Code Decoders by Breaking Symmetry [13.97553415798807]
  Quantum low-density parity check (qLDPC) codes have emerged as a promising alternative, requiring fewer qubits. SymBreak is a novel decoder for qLDPC codes that adaptively modifies the decoding graph to improve the performance of state-of-the-art belief propagation decoders. Our results demonstrate that SymBreak outperforms BP and BP+OSD-a more complex variant of BP-with a $16.17times$ reduction in logical error rate compared to BP and $3.23times$ compared to BP+OSD across various qLDPC code families.
  arXiv  Detail & Related papers  (2024-12-03T22:45:43Z)
• A High-Performance List Decoding Algorithm for Surface Codes with Erroneous Syndrome [9.191400697168389]
  We propose a high-performance list decoding algorithm for surface codes with erroneous syndromes. We first use belief propagation (BP) decoding for pre-processing with syndrome soft information, followed by ordered statistics decoding (OSD) for post-processing to list and recover both qubits and syndromes.
  arXiv  Detail & Related papers  (2024-09-11T03:12:18Z)
• Let the Code LLM Edit Itself When You Edit the Code [50.46536185784169]
  underlinetextbfPositional textbfIntegrity textbfEncoding (PIE) PIE reduces computational overhead by over 85% compared to the standard full recomputation approach. Results demonstrate that PIE reduces computational overhead by over 85% compared to the standard full recomputation approach.
  arXiv  Detail & Related papers  (2024-07-03T14:34:03Z)
• 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)
• 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)
• 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)
• Refined Belief-Propagation Decoding of Quantum Codes with Scalar Messages [4.340338299803562]
  Codes based on sparse matrices have good performance and can be efficiently decoded by belief-propagation (BP) BP decoding of stabilizer codes suffers a performance loss from the short cycles in the underlying Tanner graph. We show that running BP with message normalization according to a serial schedule may significantly improve the decoding performance and error-floor in computer simulation.
  arXiv  Detail & Related papers  (2021-02-14T10:29:58Z)
• Refined Belief Propagation Decoding of Sparse-Graph Quantum Codes [4.340338299803562]
  We propose a refined BP decoding algorithm for quantum codes with complexity roughly the same as binary BP. For a given error syndrome, this algorithm decodes to the same output as the conventional quaternary BP, but the passed node-to-node messages are single-valued. Message strength normalization can naturally be applied to these single-valued messages to improve the performance.
  arXiv  Detail & Related papers  (2020-02-16T03:51:59Z)

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.