Efficient Approximate Degenerate Ordered Statistics Decoding for Quantum Codes via Reliable Subset Reduction

Ching-Feng Kung, Kao-Yueh Kuo, and Ching-Yi Lai · 2024

Read Efficient Approximate Degenerate Ordered Statistics Decoding for Quantum Codes via Reliable Subset Reduction by Ching-Feng Kung, Kao-Yueh Kuo, and Ching-Yi Lai (2024) 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-2412-21118.txt.

Description

Abstract Efficient and scalable decoding of quantum codes is essential for high-performance quantum error correction. In this work, we introduce Reliable Subset Reduction (RSR), a reliability-driven preprocessing framework that leverages belief propagation (BP) statistics to identify and remove highly reliable qubits, substantially reducing the effective problem size.

Catalog record

CREATORChing-Feng Kung, Kao-Yueh Kuo, and Ching-Yi Lai
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE73 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-21118

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficient Approximate Degenerate Ordered Statistics Decoding for Quantum Codes via Reliable Subset Reduction Ching-Feng Kung, Kao-Yueh Kuo, and Ching-Yi Lai Abstract Efficient and scalable decoding of quantum codes is essential for high-performance quantum error correction. In this work, we introduce Reliable Subset Reduction (RSR), a reliability-driven preprocessing framework that leverages belief propagation (BP) statistics to identify and remove highly reliable qubits, substantially reducing the effective problem size. Additionally, we identify a degeneracy condition that allows high-order OSD to be simplified to order-0 OSD. By integrating these techniques, we present an ADOSD algorithm that significantly improves OSD efficiency. Our BP+RSR+ADOSD framework extends naturally to circuit-level noise and can handle large-scale codes with more than 10 4 10^{4} error variables. Through extensive simulations, we demonstrate improved performance over MWPM and Localized Statistics Decoding for a variety of CSS and non-CSS codes under the code-capacity noise model, and for rotated surface codes under realistic circuit-level noise. At low physical error rates, RSR reduces the effective problem size to as little as 1% (e.g., for ϵ = 0.001 \epsilon=0.001 in surface-code DEM), enabling higher-order OSD with drastically reduced computational complexity. These results highlight the practical efficiency and broad applicability of the BP+ADOSD framework for both theoretical and realistic quantum error correction scenarios. I Introduction Reliable quantum communication is a critical area of research, essential for scaling quantum systems, enabling the exchange of quantum information across distances, and facilitating multiparty protocols. Quantum states are inherently fragile, requiring the implementation of quantum error correction to mitigate the effects of noise and decoherence [ 2 , 3 , 4 ] . Quantum stabilizer codes, analogous to classical linear block codes, allow efficient encoding and binary syndrome decoding [ 5 , 6 , 7 ] . A notable class of stabilizer codes is quantum low-density parity-check (LDPC) codes, which are preferred for their high code rates and feasible syndrome measurements from low-weight stabilizers. These codes can be decoded using belief propagation (BP), similar to classical LDPC codes [ 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 ] . A quantum LDPC code of the Calderbank–Shor–Steane (CSS) type [ 21 , 22 ] can be decoded by the BP algorithm for binary codes (BP 2 ) by treating X and Z errors separately. When X and Z errors exhibit correlations, such as in depolarizing channels, a quaternary BP algorithm (BP 4 ) could be more effective, as it better exploits the error correlations during decoding. An important feature of quantum codes is their binary error syndromes, unlike classical nonbinary codes. Consequently, the complexity of BP 4 can be reduced by restricting message passing in the Tanner graph [ 13 ] to scalar messages, which encode the likelihood ratios associated with Pauli commutation relations. The decoding problem for highly degenerate quantum codes, such as topological codes [ 23 , 24 , 25 , 26 , 27 , 28 , 29 ] , remains particularly challenging for belief propagation (BP). A variety of remedies have been proposed to improve BP convergence and accuracy, including random perturbation [ 9 ] , enhanced feedback [ 10 , 11 ] , check-matrix augmentation [ 12 ] , message normalization and offsets [ 13 , 14 ] , and trapping-set analysis [ 30 , 31 ] . A notable advance is MBP 4 [ 32 ] , which introduces memory effects and enables BP to decode many topological codes. When BP alone is insufficient, postprocessing decoders such as ordered statistic decoding (OSD) are commonly employed. OSD was originally developed in classical coding theory as a controllable-complexity approximation to maximum-likelihood decoding [ 33 , 34 , 35 , 36 , 37 , 38 , 39 , 40 , 41 , 42 ] , and later adapted to syndrome-based and quantum decoding [ 43 , 44 ] . Its core operation is Gaussian elimination on an m\times n parity-check matrix, followed by flipping unreliable bits, but high-order OSD incurs significant computational cost [ 45 , 46 , 47 , 48 , 49 , 50 ] . In the quantum regime, several BP–OSD hybrids and variants have been proposed [ 51 , 52 , 53 ] , along with divide-and-conquer approaches such as ambiguity clustering (AC) [ 54 ] and localized statistics decoding (LSD) [ 55 ] . These methods attempt to reduce the Gaussian elimination burden by partitioning the problem. Despite these developments, most existing postprocessing schemes under the code-capacity noise model rely on binary BP applied to quaternary quantum errors, thereby discarding X/Z correlations and leading to intrinsic suboptimality. In contrast, the quaternary AMBP 4 decoder [ 32 ] directly exploits these correlations and has been shown to outperform all of the above decoders on a wide range of quantum codes, including topological codes [ 25 ] , BB codes [ 56 ] , and generalized hypergraph-product codes [ 44 , 51 ] . However, AMBP 4 still fails on certain important code families, such as lift-connected surface (LCS) codes [ 57 ] , motivating the need for a more powerful postprocessing framework. In this paper, we investigate postprocessing techniques for enhancing the performance of BP. When BP fails to converge to a valid global solution, it still provides rich statistical information about the error configuration. In particular, observing the convergence behavior of belief propagation on sparse graphs, most error variables are typically resolved with high confidence, except for a small number of unsettled variables associated with trapping sets [ 30 ] . Consequently, a large fraction of variables can be regarded as already determined and effectively part of the solution. Based on this observation, we propose reliable subset reduction (RSR). In the code-capacity decoding problem of an [[n,k]] quantum code, decoding amounts to solving a linear system with 2n binary variables subject to n-k independent constraints. The central idea of RSR is that if a subset of variables can be identified as highly reliable, the linear system can be reduced by fixing those variables, thereby substantially lowering the computational burden of subsequent postprocessing steps, such as Gaussian elimination. To identify such a reliable subset, we exploit both the hard-decision history and the final soft information produced by BP 4 [ 1 ] . Variables whose hard decisions remain nearly constant across BP iterations and whose final beliefs have high confidence are classified as reliable. At low physical error rates, a large fraction of variables satisfy these criteria, so eliminating them dramatically reduces the effective problem size and accelerates downstream postprocessing decoders. We apply OSD after RSR, using the reliabilities produced by RSR to order the remaining unreliable variables. The resulting OSD variant, which is driven by BP 4 statistics, is denoted as OSD 4 . We next consider approximate degenerate OSD for quantum codes. In typical OSD, a list of error candidates consistent with a given syndrome is generated and the minimum-weight candidate is selected. For quantum codes, however, the optimal criterion is to choose the most probable error coset, which is generally intractable. To address this, we adopt an approximate degenerate decoding strategy in which only low-weight representatives within each coset are considered. When RSR is applied,

Read the complete text