Guided Decimation for Belief-Propagation Decoding of Quantum Low-Density Parity-Check Codes Master’s thesis in Communication Engineering WALEED ABU LABAN DEPARTMENT OF ELECTRICAL ENGINEERING CHALMERS UNIVERSITY OF TECHNOLOGY Gothenburg, Sweden 2023 www.chalmers.se www.chalmers.se MASTER’S THESIS 2023 Guided Decimation for Belief-Propagation Decoding of Quantum Low-Density Parity-Check Codes WALEED ABU LABAN Department of Electrical Engineering Communication Engineering CHALMERS UNIVERSITY OF TECHNOLOGY Gothenburg, Sweden 2023 Guided Decimation for Belief-Propagation Decoding of Quantum Low-Density Parity-Check Codes © WALEED ABU LABAN, 2023. Examiner: Alexandre Graell I Amat, Full Professor at Communication Systems Supervisor: Henry Pfister, Professor in the Department of Electrical and Computer Engineering Supervisor: Christian Häger, Assistant Professor at Communication Systems Master’s Thesis 2023 Department of Electrical Engineering Communication Engineering Chalmers University of Technology SE-412 96 Gothenburg Typeset in LATEX, template by Kyriaki Antoniadou-Plytaria Gothenburg, Sweden 2023 iii Guided Decimation for Belief-Propagation Decoding of Quantum Low-Density Parity-Check Codes WALEED ABU LABAN Department of Electrical Engineering Chalmers University of Technology Abstract Quantum low-density parity-check (qLDPC) codes have emerged as a promising solution for fault-tolerant quantum computing systems. However, the conventional belief propagation (BP) decoder applied to qLDPC codes suffers from the degeneracy problem and short cycles that lead to symmetric stabilizer trapping sets. To address these challenges, we propose a novel BP-based iterative algorithm referred to as BP guided decimation (BPGD). Decimation is assigning high belief to a variable node, and freezing that belief. After the first BP run, two new BP runs are initiated by decimating the variable node with the lowest absolute belief i.e., freezing its value to 0 and 1, respectively. This iterative process continues until convergence is attained or a fixed decimation count is reached. The complexity of BPGD is reduced by significantly reducing the count of the active nodes that participate in the BP operations. Pruning the BP runs is also done to reduce the complexity, by discarding the branch with the lowest total absolute beliefs. As a result, BPGD offers a controllable trade-off between complexity and performance, enabling the reduction of complexity at the expense of a potential decrease in performance. Notably, when compared against BP-ordered statistics decoding (order 0), BPGD demonstrates superior performance. iv Acknowledgements For the necessary being, that initiated the Big Bang. The one, the creator, that gave me everything precious to me. He is definitely the most precious! Waleed Abu Laban, Gothenburg, 06 2023 v List of Acronyms Below is the list of acronyms that have been used throughout this thesis: LDPC Low-Density Parity-Check qLDPC quantum Low-Density Parity-Check qBit quantum Bit BP Belief Propagation BPGD Belief Propagation Guided Decimation OSD Ordered Statistics Decoding OSD0 Ordered Statistics Decoding (Order 0) CSS Calderbank-Shor-Steane APP A Posteriori Probability LLR Log-Likelihood Ratio BSC Binary Symmetric Channel REP Repetition code SPC Single Parity Check code GF Galois Field vi Nomenclature Below is the nomenclature of parameters, and variables that have been used throughout this thesis: Variables H Parity Check Matrix x tranmitted codeword y recieved codeword ϵ error probablity |ψ⟩ general qbit |0⟩ zero qbit represented as [1, 0]T |1⟩ one qbit represented as [0, 1]T α |0⟩ factor β |1⟩ factor I Identity Pauli operator as [1, 0; 0, 1] X Bit flip Pauli operator as [0, 1; 1, 0] Z Phase flip Pauli operator as [1, 0; 0,−1] Y iXZ Pauli operator as [0,−i; i, 0] E general error as Pauli operator S stabilizer generator s syndrome e error as bits n physical code length Nj average column weight Tmax maximum number of BP iterations vii Parameters λmax Count of max decimation bits λmin Count of min decimation bits p Prune level viii Contents List of Acronyms vi Nomenclature vii List of Figures ix List of Tables x 1 Introduction 1 2 Background 3 2.1 Classical setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1.1 Classical LDPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1.2 Classical BP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Quantum setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2.1 Quantum Digitization . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2.2 No cloning for quantum states . . . . . . . . . . . . . . . . . . . . . . 5 2.2.3 Wave-function collapse . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.4 Stabilizer codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 Classical codes vs Quantum codes . . . . . . . . . . . . . . . . . . . . . . . . 7 3 Methods 8 3.1 Minimum decimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Maximum decimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.3 Pruned decimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4 Results 11 4.1 Minimum decimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 Maximum decimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.3 Pruned decimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.4 Complexity and performance . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5 Conclusion 18 Bibliography 18 ix List of Figures 2.1 Bipartite graph of the (7, 4) Hamming code given by the parity-check matrix in 2.1. Variable nodes, are represented by circles, and Check nodes, are repre- sented by squares. The bold edges show a cycle of length 4. . . . . . . . . . . . 3 3.1 BP guided decimation tree, starting with BP 0 that represents the initial BP run. 9 3.2 Pruned BP guided decimation tree at level 1, showing running operations in black. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.1 Decoding Hypergraph-product [[400,16,6]] using BPGD with 2 and 4 deci- mated bits, compared with BP and OSD0 performance. . . . . . . . . . . . . . 11 4.2 Decoding Hypergraph-product [[625,25,8]] using BPGD with 2 and 4 deci- mated bits, compared with BP and OSD0 performance. . . . . . . . . . . . . . 12 4.3 Decoding Hypergraph-product [[400,16,6]] using BPGD with 2 decimated bits but with different modes, compared with BP and OSD0 performance. . . . . . 12 4.4 BPGD(2) with different modes, BPGD(2): 1-1 represents decimating one node per BP run, while BPGD(2): 2-0 represents the decimation of two nodes per BP run. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.5 Decoding Hypergraph-product [[400,16,6]] using BPGD with 350 and 388 maximally decimated bits and 4 minimally decimated bits, compared with BP and OSD0 performance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.6 Decoding Hypergraph-product [[625,25,8]] using BPGD with 500 and 613 maximally decimated bits and 4 minimally decimated bits, compared with BP and OSD0 performance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.7 Decoding Hypergraph-product [[400,16,6]] using pruned BPGD with 4 deci- mated bits, compared with the non-pruned version, BP and OSD0 performance. 15 4.8 Decoding Hypergraph-product [[625,25,8]] using pruned BPGD with 4 deci- mated bits, compared with the non-pruned version, BP and OSD0 performance. 15 4.9 Decoding Hypergraph-product [[400,16,6]] using BPGD once with low com- plexity parameter setup and once with high performance setup, compared with BP and OSD0 performance. . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.10 Decoding Hypergraph-product [[625,25,8]] using BPGD once with low com- plexity parameter setup and once with high performance setup, compared with BP and OSD0 performance. . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 x List of Tables 2.1 Products of Pauli operators starting from operators in the row. . . . . . . . . . 5 2.2 Syndrome table for single error Shor code. . . . . . . . . . . . . . . . . . . . . 6 2.3 Classical codes vs Quantum codes. . . . . . . . . . . . . . . . . . . . . . . . . 7 3.1 Simulation parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 xi 1 Introduction Quantum Error Correction and fault-tolerant quantum computing play a crucial role in over- coming the inherent fragility of quantum systems, enabling reliable and accurate quantum in- formation processing. Error correcting codes specifically designed for quantum systems are utilized, to ensure the stability and integrity of quantum computations [25]. QLDPC codes offer a range of advantageous properties, including a linear relationship between minimum dis- tance and code length, a constant rate, and the ability to yield asymptotic codes [28], [27]. Moreover, qLDPC codes can be easily constructed using two classical LDPC codes, if these two parity check matrices were orthogonal they become classified as CSS codes [1]. QLDPC codes achieve fault tolerance [26], so multiple non-destructive stabilizer extraction operations are applied on the qbits, thereby obtaining the error syndrome without worrying about errors occurring in that process. Hence, qLDPC codes are also categorized as stabilizer codes. The needed Pauli operation to recover the codeword is calculated by utilizing the extracted syn- drome as input to the decoder [25]. All of these features make qLDPC codes highly desirable to be implemented in error correction for quantum systems. In contrast to classical LDPC codes, quantum LDPC codes face challenges due to the pres- ence of inevitable short cycles in their Tanner graphs. These unavoidable short cycles can impede the performance of BP decoders, which are conventionally employed with classical and quantum LDPC codes [1], [4]. However, classical LDPC codes do not suffer from the same issue due to the fact that high girth can be easily achieved. Although BP is an optimal algorithm for cycle-free graphs, it performs well when utilized with a girth of at least 6 [12]. However, due to the unavoidable 4 cycles in qLDPC code graphs, the ideal conditions for BP decoding are not met, which poses challenges and lead to more decoding failures in qLDPC codes [1]. Furthermore, the BP decoder encounters challenges in converging in the context of quantum error correction, primarily due to the degenerate nature of errors. Degeneracy implies the existence of multiple valid error patterns that yield the same syndrome. While degeneracy may initially appear advantageous, it leads to the formation of symmetric stabilizer trapping sets, as demonstrated in [19]. These trapping sets arise from the symmetric properties of the code, causing degenerate error candidates to exert equal influences on the flow of BP, but in opposite directions. As a result, the final error deviates from any individual error pattern. The issue of degeneracy is effectively addressed in [4], which provides a comprehensive example illustrating this challenge. Additionally, the concept of split belief highlighted in [20] relates to a similar issue, demonstrating how the presence of short cycles in the code structure exacerbates the problem. 1 In this study, we address the challenge of symmetry in the BP decoder, as suggested in [19] and [4], to ensure convergence to one of the degenerate error candidates. This is achieved by decimating the least reliable variable node and subsequently restarting BP with this modifica- tion. Other approaches have also been explored to tackle the issue of symmetry. For instance, the Stabilizer Inactivation algorithm [5] resolves the problem by inactivating and excluding the least reliable check node from the calculation process, instead of decimation in subsequent BP runs, then solves a linear system of equations based on the outcome. Conversely, OSD post-processing [11] does not attempt to break symmetry but rather considers a portion of the resulting error bits from the initial BP run that belong to the most reliable information set, which is determined using a greedy algorithm. These aforementioned algorithms are cate- gorized as post-processing techniques. Similarly, Enhanced Feedback [21] and Freezing and Random Perturbation [4] also fall under this category as they operate after a single BP run. In contrast to post-processing algorithms, some approaches aim to modify the BP decoder it- self. For instance, Neural Belief-Propagation Decoders [9] incorporate deep neural network layers into the BP layers [24], utilizing a loss function that accounts for degeneracy. Another example is matrix augmentation [22], which proposes a classical augmented decoder [23] with enhancements to fit the quantum setup. In addition to breaking symmetry, the proposed algorithm employs a brute force approach over the decimated nodes to address the challenge of short cycles, by exhaustively exploring their values in a guided manner. Furthermore, the algorithm achieves a flexible setup that accomplishes a balance between complexity and logical error rate, making it well-suited for delay-sensitive applications. Remarkably, our proposed method achieves comparable perfor- mance to OSD0 [11], one of the leading post-processing decoding methods in literature, while offering lower complexity. The remaining sections of this work are structured as follows: Chapter 2 provides a brief background, offering the necessary context for the study. Chapter 3 details the methods em- ployed and outlines the construction of the algorithm. Subsequently, Chapter 4 presents and comprehensively discusses the results obtained by running the algorithm over Hypergraph- product codes [28] of different sizes, which are part of the qLDPC codes family. Finally, Chapter 5 serves as the conclusion, encapsulating the findings and concluding the work. 2 2 Background 2.1 Classical setup 2.1.1 Classical LDPC Low-density parity-check (LDPC) codes are remarkable class of linear block codes with sparse parity-check matrices that can approach the Shannon limit of channel capacity. LDPC codes can be represented in two ways: matrix representation as in 2.1 matrix and graphical representation as in Figure 2.1. The matrix representation describes LDPC codewords as the null space of the parity-check matrix, also known as the H matrix, which has a size of (m x n) where m and n are the number of columns and rows, respectively. Notably, the H matrix does not need to be full rank. H = 1 1 1 0 1 0 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1  (2.1) On the other hand, the LDPC graphical representation involves a Tanner graph, which is a bipartite graph that separates the graph into two types of nodes: variable (or code-bit) and check (or constraint) nodes. Edges connect only nodes of different types, and this graph is useful in describing the decoding algorithms that propagate information between nodes to correct errors. Figure 2.1: Bipartite graph of the (7, 4) Hamming code given by the parity-check matrix in 2.1. Variable nodes, are represented by circles, and Check nodes, are represented by squares. The bold edges show a cycle of length 4. 3 Short cycles in LDPC codes can degrade the performance of iterative decoding algorithms. Therefore, having low density is necessary to avoid many short cycles. The graph’s girth rep- resents the minimum cycle length in a bipartite graph, which is an important metric used to evaluate the quality of the code. 2.1.2 Classical BP Belief propagation (BP), also known as message passing, is a decoding technique that in- volves cooperative distributed low-complexity decoders exchanging extrinsic information. The main objective of BP is to calculate the posterior probability of each bit, given the received codeword. The primary objective of BP is to maximize the a posteriori probability (APP) Pr(xj = 1|y), where x represents the transmitted codeword and y represents the received codeword. To simplify calculations in the binary decoding setup, the log-likelihood ratio (LLR) is employed, which is defined as: LLR(xj|y) ≜ log Pr(xj = 0|y) Pr(xj = 1|y) Distinct channels give rise to different LLR forms. In the case of binary symmetric channels (BSC), the received codeword y can only be 0 or 1, and the channel is characterized by the error probability ϵ. So, the LLR is calculated as follows: LLR(xj|yj) = (−1)yj log 1− ϵ ϵ . As mentioned earlier, BP decomposes the decoding process into low-complexity decoders, specifically repetition (REP) decoders for the variable nodes and single parity check (SPC) decoders for the check nodes. The extrinsic information calculation for the variable nodes and check nodes is represented by the following equations, respectively: LLRj→i = LLRj + ∑ i′∈N(j)−{i} LLRi′→j (2.2) LLRi→j = 2tanh−1( ∏ j′∈N(i)−{j} tanh(1 2LLRj′→i)) (2.3) Where N(.) represents the neighbors of this node. The final marginal belief for the single bit is calculated as: LLRtotal j→i = LLRj + ∑ i∈N(j) LLRi→j (2.4) 2.2 Quantum setup 2.2.1 Quantum Digitization In quantum computations, qbits serve as the fundamental units of quantum information, and they are represented by the |ψ⟩ = α |0⟩+β |1⟩, where α and β are complex numbers satisfying 4 the condition |α|2 + |β|2 = 1. Unlike classical information, qbits can take on continuous values due to their superposition property. However, when applying error correction codes to quantum information, it becomes necessary to discretize errors into specific basis. The Pauli basis is a well-suited choice for expanding quantum errors, as it comprises a closed group consisting of four key matrix elements {I,X,Z,Y}, which enable the decomposition of any coherent error. Table 2.1: Products of Pauli operators starting from operators in the row. I X Z Y I I X Z Y X X I -iY iZ Z Z iY I -iX Y Y -iZ iX I A key property of Pauli operators is their commutativity under multiplication. Table 2.1 demonstrates that the operators commute when multiplied by themselves or by the identity, while they anti-commute otherwise. Additionally, an interesting observation from the table is that if the phase i is disregarded, the Y operator simplifies to Y = ZX . By neglecting the phase, the Pauli operators can be reduced to {I,X,Z,ZX} for simplification purposes. Any error can be represented as: E |ψ⟩ = αII |ψ⟩+ αXX |ψ⟩+ αZZ |ψ⟩+ αZXZX |ψ⟩ As a result, quantum digitization has transformed the representation of quantum errors from analog to discrete forms, specifically the bit flip (X) and/or the phase flip (Z), which have the following effect on the qbit: X |ψ⟩ = αX |0⟩+ βX |1⟩ = α |1⟩+ β |0⟩ Z |ψ⟩ = αZ |0⟩+ βZ |1⟩ = α |0⟩ − β |1⟩ 2.2.2 No cloning for quantum states In error correction, redundancy of information plays a crucial role in achieving its objective. However, in quantum systems, a physical constraint prohibits the direct duplication of qbits. Consequently, there is no operator capable of cloning qbits at the encoder side. To address this challenge, redundancy is introduced by expanding the Hilbert space in which the qbits are encoded. The following example illustrates the idea: |ψ⟩ ∈ H2 = span{|0⟩ , |1⟩} → |ψ⟩ ∈ H4 = span{|00⟩ , |01⟩ , |10⟩ , |11⟩} In the new Hilbert space, the qbit can be encoded as follows: |ψ⟩L ∈ C = span{|00⟩ , |11⟩} ⊂ H4 Here, |ψ⟩L represents a single logical qbit that corresponds to two physical qbits. 5 2.2.3 Wave-function collapse The act of measuring a qubit leads to the destruction of the information it carries. Con- sequently, error correction techniques are designed to operate without directly measuring the encoded physical qbits. To achieve this, ancilla qbits are introduced into the system. These ancilla qbits undergo operations known as stabilizers, which do not disturb the encoded code- words they are applied to. The collective measurements of the ancilla qbits are then referred to as syndrome extraction. This methodology allows for error correction to be performed without directly measuring the encoded qbits, thereby preserving the integrity of the information. 2.2.4 Stabilizer codes The stabilizers mentioned earlier are Pauli operators that exploit the commutation property of quantum errors. Each stabilizer corresponds to a specific condition for a portion of the codeword. In the event of a failed condition, the stabilizer anti-commutes with the error, causing the corresponding ancilla qbit to measure as -1 (indicating an error in the syndrome as 1). Consequently, the combination of multiple stabilizers forms a stabilizer code. These stabilizers check both bit flip errors (X) and phase flip errors (Z) for each qbit. Hence, they must satisfy the following properties: 1) They exclusively consist of Pauli operators. 2) They do not affect the qbit itself, Sj |ψ⟩ = (+1) |ψ⟩. 3) All stabilizers must commute with one another. The first error correction code introduced was the Shor code [[9,1,3]], which employs 9 physical qubits to encode 1 logical qubit, with a minimum distance of 3. The stabilizers asso- ciated with this code are as follows: {Z1Z2, Z2Z3, Z4Z5, Z5Z6, Z7Z8, Z8Z9, X1X2X3X4X5X6, X4X5X6X7X8X9} Table 2.2: Syndrome table for single error Shor code. Error Syndrome Error Syndrome X1 10000000 Z1 00000010 X2 11000000 Z2 00000010 X3 01000000 Z3 00000010 X4 00100000 Z4 00000011 X5 00110000 Z5 00000011 X6 00010000 Z6 00000011 X7 00001000 Z7 00000001 X8 00001100 Z8 00000001 X9 00000100 Z9 00000001 Table 2.2 provides an overview of how these stabilizers interact with individual errors. It is worth noting that certain errors share the same syndrome. For instance, {Z1, Z2, Z3} share the syndrome 00000010. When the decoded operator for this syndrome is Z1, the Z1 error is resolved as Z1Z1 |ψ⟩ = (+1) |ψ⟩, as illustrated in Table 2.1. Conversely, the Z2 error is sub- jected to the Z1 operator, resulting in Z1Z2 |ψ⟩. However, since Z1Z2 belongs to the stabilizer 6 group of this code, stabilizers do not affect the qubit, leading to the resolution (+1) |ψ⟩. This phenomenon is known as the degeneracy property of the quantum code, which refers to the existence of multiple valid recovery operators for the same syndrome. 2.3 Classical codes vs Quantum codes Based on the information presented, the key distinctions between classical codes and quan- tum codes are summarized in Table 2.3. In the quantum case, the error vector signifies the occurrence of bit flip (X) and phase flip (Z) errors. Additionally, the syndrome is determined by calculating a special inner product between the error vector and the stabilizer matrix. It is important to note that the stabilizer matrix consists of Z stabilizers for X errors and vice versa. Consequently, the error vector must correspond to the opposite Pauli operator in the stabilizer matrix. The [.,.] operator represents the required symplectic inner product to facilitate this flipped relationship. Table 2.3: Classical codes vs Quantum codes. Classical codes Quantum codes Error e = {e1, e2, e3} e = {Xe1 , Xe2 , Xe3 , Ze4 , Ze5 , Ze6} Check H1 = [1, 1, 0], H2 = [0, 1, 1] S1 = [Z,Z, I], S2 = [I, Z, Z] Syndrome si = Hi.e si = [Si, e] Successful decoding edecoded = e [S⊥, e+ edecoded] = 0 and [S, e] = [S, edecoded] The final row in Table 2.3 highlights an important distinction between classical and quantum decoding. In classical coding, successful decoding requires the decoded error to exactly match the actual error. Conversely, quantum codes exhibit degeneracy, allowing for multiple decoded errors to result in successful decoding. Errors in the quantum case can be classified as follows: 1) Detected error patterns: The syndrome of the decoded error does not align with the input syndrome. 2) Harmful undetected error patterns: The syndrome matches, but the total error transforms the codeword into another valid codeword within the code space. 3) Harmless undetected error patterns: The syndrome matches, and the total error belongs to the code’s stabilizers, thereby having no impact on the codeword. Consequently, there are two types of harmful errors: flagged errors, where the decoder fails to match the input syndrome, and unflagged errors, where the total error represents a logical operator that decodes to an incorrect codeword within the code space. Another notable distinction in quantum codes is the use of qLDPC codes, which employ LDPC matrices as the foundation for their construction. A specific type of qLDPC code is CSS code, which is constructed as shown in matrix (2.5): H = ( H ′ z 0 0 H ′ x ) (2.5) Here, H ′ z and H ′ x must satisfy the condition H ′ zH ′T x = 0. CSS codes are relatively straight- forward to construct; however, they inherently suffer from the presence of unavoidable 4-length cycles, which can degrade the performance of the BP decoder. 7 3 Methods 3.1 Minimum decimation The algorithm is built upon a Monte-Carlo simulator designed to emulate a binary symmetric channel. This simulator incorporates the execution of syndrome based BP with specific param- eters, as outlined in Table 3.1. For the sake of simplicity, the simulations exclusively consider X-errors, where the physical error rate corresponds only to the probability of X-errors, although the same principles can be applied to Z-errors as well. Table 3.1: Simulation parameters Error frames until stop 500 Max frame count 107 Max iterations per BP run n BP method Sum− Product LLR clipping value 10 As an iterative algorithm based on BP, the initial step involves running BP to obtain the LLR values of the decoded codeword if the BP fails to converge to the input syndrome. A binary tree structure of BP operations is constructed incrementally, and it is traversed in a breadth-first manner, as illustrated in Figure 3.1. The variable node with the lowest absolute LLR value corresponds to the most uncertain node. This node is decimated by assigning it the most probable value based on the sign of its LLR (zero or one). Decimation involves emitting the high belief value without further updates or recalculations. Following the decimation of the lowest belief node, all other nodes are reset, and a new instance of the BP algorithm, referred to as BP 1 in Figure 3.1, is executed. If the decimated value fails to converge, the other value is tested on the same variable node, indicated as BP 2 in the Figure. If both values fail to converge, the algorithm proceeds to dec- imate a new node along with the first decimated one. This process continues until a syndrome converges or the depth of the tree reaches the count of decimated nodes. It is important to note that the tree is traversed in breadth-first order, and the numbers assigned to the BP runs in Figure 3.1 represent their respective running order. 8 Figure 3.1: BP guided decimation tree, starting with BP 0 that represents the initial BP run. Algorithm 1: BP Guided Decimation decodedLLRs← BP (H, s); decodedError ← decodedLLRs < 0; if H.decodedError == s then return decodedError; root = Node(index = −1, value = 0, parent = NULL); queue← [root]; while queue do breadth = size(queue); if log2 breadth == Min decimation count then return decodedError; \\Failed for i← 0 to breadth do parentNode = queue.pop(); decimatedNode← argmin(abs(decodedLLRs)); for t← 0 to 2 do decimatedV alue← decodedLLRs[decimatedNode] ∗ −1t < 0; Decimate(decimatedNode, decimatedV alue, parentNode); decodedLLRs← BP (H, s); decodedError ← decodedLLRs < 0; if H.decodedError == s then return decodedError; queue.push(Node(decimatedNode, decimatedV alue, parentNode)); The pseudo code for the algorithm is presented in Algorithm 1. It should be emphasized that the Decimate function within the algorithm resets all previous decimations then decimates the decimatedNode by assigning it either 0 or 1, depending on the value of decimatedV alue. Furthermore, the function also decimates all the parent nodes in the chain according to their respective decimated values. 9 3.2 Maximum decimation To optimize the computational costs associated with running multiple BPs, it is crucial to reduce these expenses without significantly sacrificing performance. One observation that can guide this optimization is that certain nodes manage to maintain high belief values despite the presence of other low beliefs. This suggests that these nodes are minimally affected by the conflicting beliefs and are likely to be correct. Therefore, there is no need to subject them to further changes. To address this, a new layer of decimation is introduced after the initial BP run. This layer collectively decimates a group of nodes with high LLR values, effectively preventing their recalculation in subsequent BP runs. Instead, the values of these nodes are treated as inputs to the check nodes only once, reducing the computational process. 3.3 Pruned decimation Figure 3.2: Pruned BP guided decimation tree at level 1, showing running operations in black. Another effective approach to reduce complexity is by minimizing the number of BP runs. The count of BP runs grows exponentially with the number of min decimated nodes, making it necessary to prune the branches of the BP binary tree. By selecting a specific branch after a certain depth, based on the total absolute sum of the LLRs, the algorithm can prioritize branches with higher confidence in their output. When pruning is performed after each min decimation (prune level = 1), Figure 3.2 illustrates the actual BP tree operations that will be executed, highlighted in black. 10 4 Results 4.1 Minimum decimation By breaking the symmetry in the decoder, the problem of degeneracy in BP can be addressed effectively [4]. BPGD tackles this challenge by decimating the lowest LLR bit through exhaus- tive evaluation of its possible values to mitigate for the short cycles effect. Notably, Figures 4.1 and 4.2 demonstrate the performance improvement achieved when BPGD is applied in conjunc- tion with Hypergraph-product codes of various sizes, as compared to using BP alone. These plots also highlight the superior performance of BPGD with just 2 bits min decimation over OSD0 [11], and indicate further enhancements as the minimum decimated count is increased. 10-2 10-1 physical error rate 10-3 10-2 10-1 100 lo g ic a l e rr o r ra te Hypergraph product code [[400,16,6]] BP OSD0 BPGD(2) BPGD(4) Figure 4.1: Decoding Hypergraph-product [[400,16,6]] using BPGD with 2 and 4 decimated bits, compared with BP and OSD0 performance. It is important to note that the performance gap between BPGD(2) and BP is greater than the difference between BPGD(2) and BPGD(4). This observation highlights that increasing the number of decimated nodes does not result in a linear improvement in performance. This is attributed to the presence of harmful undetected errors, known as unflagged errors, which can impact the overall performance of the decoder. 11 10-2 10-1 physical error rate 10-4 10-3 10-2 10-1 100 lo g ic a l e rr o r ra te Hypergraph product code [[625,25,8]] BP OSD0 BPGD(2) BPGD(4) Figure 4.2: Decoding Hypergraph-product [[625,25,8]] using BPGD with 2 and 4 decimated bits, compared with BP and OSD0 performance. 10-2 10-1 physical error rate 10-3 10-2 10-1 100 lo g ic a l e rr o r ra te Hypergraph product code [[400,16,6]] BP OSD0 BPGD(2): 1-1 BPGD(2): 2-0 Figure 4.3: Decoding Hypergraph-product [[400,16,6]] using BPGD with 2 decimated bits but with different modes, compared with BP and OSD0 performance. Decimating multiple nodes simultaneously has a bad effect on performance, as demonstrated in Figure 4.3. The algorithm’s structure in this scenario is depicted in Figure 4.4, where the two lowest nodes are decimated together. In the case of BPGD(2), if there are multiple symmetric stabilizer trapping sets [19], two main possibilities arise for the BPGD(2): 2-0 scenario. Either the decimated nodes belong to two different symmetric stabilizer trapping sets, re- sulting in the resolution of two sets. This explains why BPGD(2): 2-0 exhibits superior per- formance compared to BP. Or both nodes belong to the same symmetric stabilizer trapping set, allowing for the potential resolution of only this particular set. Consequently, BPGD(2): 1-1 outperforms BPGD(2): 2-0 as it ensures the breakage of symmetry structures at each iteration (always resolves two different sets). Furthermore, this result provides further evidence that BPGD enhances performance by disrupting the symmetric stabilizer trapping sets. 12 Figure 4.4: BPGD(2) with different modes, BPGD(2): 1-1 represents decimating one node per BP run, while BPGD(2): 2-0 represents the decimation of two nodes per BP run. 13 4.2 Maximum decimation The introduction of decimating multiple nodes with maximum beliefs after the initial BP run significantly reduces the complexity of BPGD. This approach effectively decreases the number of operations and iterations per BP run. As depicted in Figure 4.5, increasing the number of maximally decimated nodes results in higher error rates. This outcome is expected since the number of free nodes decreases, reducing the probability of encountering a harmless degenerate candidate. Figure 4.6 presents the results for a larger code size. 10-2 10-1 physical error rate 10-3 10-2 10-1 100 lo g ic a l e rr o r ra te Hypergraph product code [[400,16,6]] BP OSD0 BPGD(4) BPGD(4,350) BPGD(4,388) Figure 4.5: Decoding Hypergraph-product [[400,16,6]] using BPGD with 350 and 388 max- imally decimated bits and 4 minimally decimated bits, compared with BP and OSD0 perfor- mance. 10-2 10-1 physical error rate 10-4 10-3 10-2 10-1 100 lo g ic a l e rr o r ra te Hypergraph product code [[625,25,8]] BP OSD0 BPGD(4) BPGD(4,500) BPGD(4,613) Figure 4.6: Decoding Hypergraph-product [[625,25,8]] using BPGD with 500 and 613 max- imally decimated bits and 4 minimally decimated bits, compared with BP and OSD0 perfor- mance. 14 4.3 Pruned decimation By reducing the number of BP runs, the complexity of BPGD can also be significantly re- duced. However, it is important to note that pruning the runs leads to higher error rates, as depicted in Figures 4.7 and 4.8. With fewer investigated options, the influence of deviations in beliefs caused by short cycles becomes more pronounced, thereby compromising the overall performance of the algorithm. 10-2 10-1 physical error rate 10-3 10-2 10-1 100 lo g ic a l e rr o r ra te Hypergraph product code [[400,16,6]] BP OSD0 BPGD(4) BPGD(4,Pruned) Figure 4.7: Decoding Hypergraph-product [[400,16,6]] using pruned BPGD with 4 decimated bits, compared with the non-pruned version, BP and OSD0 performance. 10-2 10-1 physical error rate 10-4 10-3 10-2 10-1 100 lo g ic a l e rr o r ra te Hypergraph product code [[625,25,8]] BP OSD0 BPGD(4) BPGD(4,Pruned) Figure 4.8: Decoding Hypergraph-product [[625,25,8]] using pruned BPGD with 4 decimated bits, compared with the non-pruned version, BP and OSD0 performance. 15 4.4 Complexity and performance The complexity of a single BP run can be expressed as O(NjTmax) [30] [31], where Nj rep- resents the average column weight of the parity check matrix, and Tmax denotes the maximum number of iterations performed. In our simulation, we set the number of iterations for a single BP run to n. Consequently, the complexity of the initial BP run becomes O(Njn). However, subsequent BP runs exhibit lower complexity due to the utilization of max deci- mation. This approach reduces the number of free nodes that need to be processed, resulting in a decreased number of iterations, so the iterations’ count becomes equal to n− λmax, where λmax represents the count of the max decimation nodes. Thus, the complexity of any BP run after the initial one is given by O(Nj[n− λmax]). The number of BP runs depends on the count of min decimation nodes and the pruning level applied. In general, the total number of BP runs, excluding the initial run, is given by∑λmin−1 i=0 2(i mod p)+1, where p denotes the pruning level, and λmin represents the count of the min decimation nodes. Accordingly, the final complexity of BPGD(λmin, λmax, p) is O(Njn+ λmin−1∑ i=0 2(i mod p)+1Nj[n− λmax]) , which simplifies for the pruning case (prune level = 1) to O(Njn+ 2λminNj[n− λmax]) , and for the non-pruning case (prune level = λmin) to O(Njn+ 2(2λmin − 1)Nj[n− λmax]) 10-2 10-1 physical error rate 10-3 10-2 10-1 100 lo g ic a l e rr o r ra te Hypergraph product code [[400,16,6]] BP OSD0 BPGD(4) BPGD(4,350,Pruned) Figure 4.9: Decoding Hypergraph-product [[400,16,6]] using BPGD once with low complexity parameter setup and once with high performance setup, compared with BP and OSD0 perfor- mance. 16 By carefully tuning the parameters to BPGD(4, 3n/4, 1), where there are 4 min decimated nodes, 3n/4 max decimated nodes, and pruning occurs after each min node decimation. Figure 4.9 demonstrates how these optimized parameters, with a complexity of O(3Njn), outperform OSD0, which has a complexity of O(n3) [11]. It is important to note that in this case, n is set to 200 as we solely focus on X-errors. These same parameters were also evaluated with different code size, as depicted in figure 4.10. 10-2 10-1 physical error rate 10-4 10-3 10-2 10-1 100 lo g ic a l e rr o r ra te Hypergraph product code [[625,25,8]] BP OSD0 BPGD(4) BPGD(4,546,Pruned) Figure 4.10: Decoding Hypergraph-product [[625,25,8]] using BPGD once with low com- plexity parameter setup and once with high performance setup, compared with BP and OSD0 performance. By pushing the parameters to their extreme values of no pruning and no max decimation, it is possible to further enhance the performance of the algorithm. However, this improvement comes at the cost of increased complexity, which becomes O(31Njn). Despite the higher complexity, it is worth noting that it remains linear with respect to n. 17 5 Conclusion Classical BP is not capable of effectively handling qLDPC codes due to challenges such as degeneracy and the presence of unavoidable short cycles in certain structures. To address these issues, BPGD and other algorithms like Stabilizer Inactivation [5] employ the use of anchor bits that guide other bits towards one of the degenerate candidate errors. This approach not only breaks the symmetric stabilizer trapping sets but also leverages degeneracy to improve per- formance. BPGD, in particular, has demonstrated superior results by considering short cycles through exploring different options for the least reliable bit during the iterative decimation. To create balance between performance and complexity, BPGD introduces three parameters. The first parameter determines the number of variable nodes to be iteratively decimated, while the second parameter governs the number of nodes to be eliminated after the initial BP run. The final parameter controls BP branch pruning by removing branches with lower beliefs, further optimizing the algorithm’s efficiency. In the current implementation of BPGD, the algorithm terminates as soon as it encounters a syndrome that satisfies the error condition. However, to further improve performance, it is ben- eficial to introduce additional criteria for determining the best-performing decoded error among multiple candidates that achieve the syndrome. Furthermore, the algorithm can be enhanced by leveraging deep neural networks, similar to the approach used in Neural BP [9], to automate the selection of decimation and pruning strategies. Moreover, by incorporating GF(4) decoding formalism, which considers the interdependence between X and Z errors, the performance of the algorithm can be further elevated [8]. 18 Bibliography [1] Z. Babar, P. Botsinis, D. Alanis, S. X. Ng and L. Hanzo, "Fifteen Years of Quantum LDPC Coding and Improved Decoding Strategies," in IEEE Access, vol. 3, pp. 2492-2519, 2015, doi: 10.1109/ACCESS.2015.2503267. [2] S. K. Planjery, B. Vasic and D. Declercq, "Decimation-enhanced finite alphabet it- erative decoders for LDPC codes on the BSC," 2011 IEEE International Symposium on Information Theory Proceedings, St. Petersburg, Russia, 2011, pp. 2383-2387, doi: 10.1109/ISIT.2011.6033990. [3] Roffe, J., White, D.R., Burton, S. and Campbell, E.T., Decoding across the quantum LDPC code landscape (2020). arXiv preprint arXiv:2005.07016. [4] Poulin, D. and Chung, Y., 2008. On the iterative decoding of sparse quantum codes. arXiv preprint arXiv:0801.1241. [5] Du Crest, J., Mhalla, M. and Savin, V., 2022, November. Stabilizer inactivation for message-passing decoding of quantum ldpc codes. In 2022 IEEE Information Theory Workshop (ITW) (pp. 488-493). IEEE. [6] Wiesmayr, R., Marti, G., Dick, C., Song, H. and Studer, C., 2022. Bit Error and Block Error Rate Training for ML-Assisted Communication. arXiv preprint arXiv:2210.14103. [7] Bravyi, S., Suchara, M. and Vargo, A., 2014. Efficient algorithms for maximum likelihood decoding in the surface code. Physical Review A, 90(3), p.032326. [8] Miao, S., Schnerring, A., Li, H. and Schmalen, L., 2022. Neural Belief Propagation De- coding of Quantum LDPC Codes Using Overcomplete Check Matrices. arXiv preprint arXiv:2212.10245. [9] Liu, Y.H. and Poulin, D., 2019. Neural belief-propagation decoders for quantum error- correcting codes. Physical review letters, 122(20), p.200501. [10] Devitt, S.J., Munro, W.J. and Nemoto, K., 2013. Quantum error correction for beginners. Reports on Progress in Physics, 76(7), p.076001. [11] Panteleev, P. and Kalachev, G., 2021. Degenerate quantum LDPC codes with good finite length performance. Quantum, 5, p.585. [12] Ryan, W. and Lin, S., 2009. Channel codes: classical and modern. Cambridge university press. [13] MacKay, D.J., Mitchison, G. and McFadden, P.L., 2004. Sparse-graph codes for quantum error correction. IEEE Transactions on Information Theory, 50(10), pp.2315-2330. [14] Nielsen, M.A. and Chuang, I., 2002. Quantum computation and quantum information. [15] Kuo, K.Y. and Lai, C.Y., 2022. Exploiting degeneracy in belief propagation decoding of quantum codes. npj Quantum Information, 8(1), p.111. [16] Matuschak, A. and Nielsen, M. (1970) Quantum computing for the very curious, Quantum Country. Available at: https://quantum.country/qcvc (Accessed: May 6, 2023). 19 [17] Gottesman, D., 2010, April. An introduction to quantum error correction and fault-tolerant quantum computation. In Quantum information science and its contributions to mathemat- ics, Proceedings of Symposia in Applied Mathematics (Vol. 68, pp. 13-58). [18] Preskill, J. (1999) Chapter 7 quantum error correction - particle theory group, Caltech. Available at: http://theory.caltech.edu/ preskill/ph229/notes/chap7.pdf (Accessed: May 6, 2023). [19] RAVEENDRAN, Nithin; VASIĆ, Bane. Trapping sets of quantum LDPC codes. Quan- tum, 2021, 5: 562. [20] CRIGER, Ben; ASHRAF, Imran. Multi-path summation for decoding 2D topological codes. Quantum, 2018, 2: 102. [21] Wang, Y.J., Sanders, B.C., Bai, B.M. and Wang, X.M., 2012. Enhanced feedback itera- tive decoding of sparse quantum codes. IEEE transactions on information theory, 58(2), pp.1231-1241. [22] Rigby, A., Olivier, J.C. and Jarvis, P., 2019. Modified belief propagation decoders for quantum low-density parity-check codes. Physical Review A, 100(1), p.012330. [23] Rigby, A.R., Olivier, J.C., Myburgh, H.C., Xiao, C. and Salmon, B.P., 2018. Augmented decoders for LDPC codes. EURASIP Journal on Wireless Communications and Network- ing, 2018, pp.1-9. [24] Nachmani, E., Be’ery, Y. and Burshtein, D., 2016, September. Learning to decode linear codes using deep learning. In 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton) (pp. 341-346). IEEE. [25] Roffe, J., 2019. Quantum error correction: an introductory guide. Contemporary Physics, 60(3), pp.226-245. [26] Gottesman, D., 2013. Fault-tolerant quantum computation with constant overhead. arXiv preprint arXiv:1310.2984. [27] Panteleev, P. and Kalachev, G., 2022, June. Asymptotically good quantum and locally testable classical LDPC codes. In Proceedings of the 54th Annual ACM SIGACT Sym- posium on Theory of Computing (pp. 375-388). [28] Tillich, J.P. and Zémor, G., 2013. Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength. IEEE Transactions on Infor- mation Theory, 60(2), pp.1193-1202. [29] Kitaev, A., 2006. Anyons in an exactly solved model and beyond. Annals of Physics, 321(1), pp.2-111. [30] Lai, C.Y. and Kuo, K.Y., 2021. Log-domain decoding of quantum LDPC codes over bi- nary finite fields. IEEE Transactions on Quantum Engineering, 2, pp.1-15. [31] Davey, M.C. and MacKay, D.J., 1998, June. Low density parity check codes over GF (q). In 1998 Information Theory Workshop (Cat. No. 98EX131) (pp. 70-71). IEEE. 20 DEPARTMENT OF ELECTRICAL ENGINEERING CHALMERS UNIVERSITY OF TECHNOLOGY Gothenburg, Sweden www.chalmers.se www.chalmers.se List of Acronyms Nomenclature List of Figures List of Tables Introduction Background Classical setup Classical LDPC Classical BP Quantum setup Quantum Digitization No cloning for quantum states Wave-function collapse Stabilizer codes Classical codes vs Quantum codes Methods Minimum decimation Maximum decimation Pruned decimation Results Minimum decimation Maximum decimation Pruned decimation Complexity and performance Conclusion Bibliography