Restart Belief: A General Quantum LDPC Decoder
Lorenzo Valentini, Diego Forlivesi, Andrea Talarico, and Marco Chiani · 2025
Read Restart Belief: A General Quantum LDPC Decoder by Lorenzo Valentini, Diego Forlivesi, Andrea Talarico, and Marco Chiani (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-13281.txt.
Introduction
Lorenzo Valentini and 3 co-authors propose Restart Belief, a decoder for quantum low-density parity-check codes. Decoders built on belief propagation are friendly to hardware, but quantum degeneracy often stops them from settling on an answer. The new decoder adds restarts guided by ideas from branch-and-bound search.
Each restart gives the message-passing process a fresh chance to escape a stalled state. From their analysis, the authors find Restart Belief to be the fastest and most accurate decoder yet for these codes. It was designed to push error correction close to the full distance that the code can in principle handle.
Catalog record
| CREATOR | Lorenzo Valentini, Diego Forlivesi, Andrea Talarico, and Marco Chiani |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-13281
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Restart Belief: A General Quantum LDPC Decoder Lorenzo Valentini, Diego Forlivesi, Andrea Talarico, and Marco Chiani Abstract Hardware-friendly quantum low-density parity-check (QLDPC) decoders are commonly built upon belief propagation (BP) processing. Yet, quantum degeneracy often prevents BP from achieving reliable convergence. To overcome this fundamental limitation, we propose the restart belief (RB) decoder, an iterative BP-based algorithm inspired by branch-and-bound optimization principles. From our analysis we find that the RB decoder represents both the fastest and most accurate decoding algorithm applicable to QLDPC codes to date, conceived with the explicit goal of approaching error correction up to the code distance. ASIC application-specific integrated circuit AWGN additive white Gaussian noise BB bivariate bicycle BC bubble clustering BCH Bose–Chaudhuri–Hocquenghem BD bounded distance BP belief propagation BPGD belief propagation based on guided decimation CDF cumulative distribution function CER codeword error rate CRC cyclic redundancy code CSS Calderbank, Shor, and Steane FPGA field-programmable gate array i.i.d. independent identically distributed LDPC low-density parity-check LEMON library for efficient modeling and optimization in networks LLR log-likelihood ratio LUT lookup table ML maximum likelihood MPS matrix product state MST minimum spanning tree MW minimum weight MWPM minimum weight perfect matching OSD ordered statistics decoding PDF probability density function PMF probability mass function PruST pruned spanning tree QEC quantum error correction QECC quantum error correcting code QLDPC quantum low-density parity-check RFire Rapid-Fire RelayBP relay belief propagation RB restart belief STM spanning tree matching UF union-find WE weight enumerator WEP weight enumerator polynomial I Introduction Preserving quantum information through QEC ( QEC ) is essential for scalable quantum computing and reliable quantum memories [ 18 ] . Because quantum states are extremely fragile, QEC encodes logical qubits redundantly into many physical qubits and continuously detects and corrects errors without collapsing the state. In a typical QEC cycle, the system periodically measures stabilizer generators, identifies potential errors through syndrome extraction, and applies corrective operations to restore the quantum information [ 9 ] . Therefore, achieving practical fault-tolerant operation requires decoders that are not only accurate, but also extremely fast and hardware-friendly, capable of running efficiently on specialized platforms such as FPGA or ASIC [ 13 ] . Among various QEC schemes, QLDPC ( QLDPC ) codes are particularly promising due to their low-weight stabilizer generators, which reduce circuit complexity and error propagation while maintaining good distance properties. In particular, the CSS ( CSS ) version of these codes is advantageous, as the separation between \bm{Z} -type and \bm{X} -type generators simplifies both the circuit design and the decoding process, while enabling many transversal encoded operations that are highly desirable for fault-tolerant quantum computation [ 3 , 19 ] . These features make them attractive for large-scale fault-tolerant architectures where both qubit efficiency and reliable error suppression are critical. In this context, surface codes [ 1 ] , structured instances of QLDPC codes, have received significant attention, with several specialized decoders such as MWPM ( MWPM ), UF ( UF ), and BC ( BC ) [ 11 , 5 , 7 , 8 ] . However, these decoders are highly specialized and tailored to the specific structure of surface codes. For this reason, researchers have actively explored BP ( BP )-based approaches for decoding general QLDPC codes. In this direction, [ 14 ] proposed enhancing the BP algorithm by incorporating a post-processing stage based on OSD ( OSD ), resulting in the combined decoding strategy known as BP + OSD . However, this approach has certain drawbacks: the OSD step requires matrix inversion, which can be computationally expensive, and it does not always preserve the code distance. Subsequently, [ 20 ] introduced the decoder BPGD ( BPGD ), in which multiple instances of BP are executed iteratively until convergence is achieved. In each iteration where the decoder becomes trapped, the most reliable LLR ( LLR ) is fixed to guide the decoding process toward convergence. This algorithm is computationally more efficient, however, it provides a limited performance advantage compared to conventional BP . Recently, [ 13 ] introduced a novel decoding scheme, termed RelayBP ( RelayBP ), which aims to simultaneously achieve high decoding performance and low latency. The core concept involves running the BP algorithm and, in cases where convergence is not reached, restarting the process while updating the input LLR using a damped version of the output LLR from the previous iteration. This decoder has been shown to obtain very good performance and decoding complexity for certain QLDPC codes such as the bivariate bicycle and the rotated surface ones. In this paper, we continue the search for a general QLDPC decoder that balances performance and complexity. Our proposed decoder, hereafter named RB ( RB ), executes a first BP and its output LLR are sorted. The minimum LLR is used to guide the decoder by applying an error to the corresponding qubit and updating the syndrome and the qubit LLR before the next BP . If the decoder still fails to converge, this process is repeated. Once convergence is achieved and a valid solution is obtained, the process is restarted using the second smallest LLR from the root BP , then the third, and so forth until a maximum is reached. In this way, the minimum LLR of the root generate each a solution exploring a branch of the decision tree. To enhance the speed of the decoder we also include code distance-specific and defect-specific early termination strategies. In addition, it is worth noting that all the branches BP , generating a solution, can be efficiently executed in parallel. To benchmark and validate our RB decoder we selected various QLDPC codes and compare the results with all the above mentioned QLDPC decoders based on BP . II Efficient Decoders for QLDPC Codes The Pauli operators are denoted by \bm{X} , \bm{Y} , and \bm{Z} . A quantum error correcting code encoding k logical qubits \ket{\varphi} into n physical qubits \ket{\psi} with minimum distance d is represented as [[n,k,d]] , and can correct any error affecting up to t=\lfloor(d-1)/2\rfloor qubits. In the stabilizer formalism, the code is defined by n-k independent, commuting generators \bm{G}_{i}\in\mathcal{G}_{n} , where \mathcal{G}_{n} denotes the n -qubit Pauli group [ 10 ] . The subgroup generated by all \bm{G}_{i} forms the stabilizer \mathcal{S} , and the code space \mathcal{C} consists of all states \ket{\psi} satisfying \bm{S}\ket{\psi}=\ket{\psi} for every \bm{S}\in\mathcal{S} . Stabilizer generators correspond to measurements that leave the encoded state unchanged and are implemented using ancillary qubits. When an error \bm{E}\in\mathcal{G}_{n} acts on a codeword, producing \bm{E}\ket{\psi} , the resulting binary syndrome vector \bm{s} encodes commutation information: s_{i}=0 if \bm{G}_{i} commutes with \bm{E} and s_{i}=1 otherwise. In this context, the structure of a code can be represented as a bipartite graph, where two types of nodes are distinguished: variable nodes and check nodes. Variable nodes correspond to the errors on data qubits, while check nodes represent the generator constraints. The goal of decoding is to determine the most likely configuration of errors on the variable nodes that is consistent with the observed syndrome. In the following, we consider CSS codes [ 3 , 19 ] , where the decoding of \bm{X} and \bm{Z} Pauli errors can be treated independently. Therefore, for the sake of presentation, we