Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2007.11069 · ACM Annual International Conference on Mobile Computing and Networking (MobiCom)

Towards quantum belief propagation for LDPC decoding in wireless networks

Srikar Kasi, Kyle Jamieson

Published Sep 18, 2020• 32 citations
arXivHTMLPDF

Abstract

We present Quantum Belief Propagation (QBP), a Quantum Annealing (QA) based decoder design for Low Density Parity Check (LDPC) error control codes, which have found many useful applications in Wi-Fi, satellite communications, mobile cellular systems, and data storage systems. QBP reduces the LDPC decoding to a discrete optimization problem, then embeds that reduced design onto quantum annealing hardware. QBP's embedding design can support LDPC codes of block length up to 420 bits on real state-of-the-art QA hardware with 2,048 qubits. We evaluate performance on real quantum annealer hardware, performing sensitivity analyses on a variety of parameter settings. Our design achieves a bit error rate of 10--8 in 20 μs and a 1,500 byte frame error rate of 10--6 in 50 μs at SNR 9 dB over a Gaussian noise wireless channel. Further experiments measure performance over real-world wireless channels, requiring 30 μs to achieve a 1,500 byte 99.99% frame delivery rate at SNR 15-20 dB. QBP achieves a performance improvement over an FPGA based soft belief propagation LDPC decoder, by reaching a bit error rate of 10--8 and a frame error rate of 10--6 at an SNR 2.5--3.5 dB lower. In terms of limitations, QBP currently cannot realize practical protocol-sized (e.g., Wi-Fi, WiMax) LDPC codes on current QA processors. Our further studies in this work present future cost, throughput, and QA hardware trend considerations.

DOI
10.1145/3372224.3419207

Related papers

Quantum-enhanced belief propagation for LDPC decoding

Sheila M. Perez-Garcia, Ashley Montanaro

Decoding low-density parity-check codes is critical in many current technologies, such as fifth-generation (5G) wireless networks and satellite communications. The belief propagation algorithm allows for fast decoding due to the low density of these codes. However, there is scope for improvement to this algorithm both in terms of its computational cost when decoding large codes and its error-correcting abilities. Here, we introduce the quantum-enhanced belief propagation (QEBP) algorithm, in which the Quantum Approximate Optimization Algorithm (QAOA) acts as a pre-processing step to belief propagation. We perform exact simulations of syndrome decoding with QAOA, whose result guides the belief propagation algorithm, leading to faster convergence and a lower block error rate (BLER). In addition, through the repetition code, we study the possibility of having shared variational parameters between syndromes and, in this case, code lengths. We obtain a unique pair of variational parameters for level-1 QAOA by optimizing the probability of successful decoding through a transfer matrix method. Then, using these parameters, we compare the scaling of different QAOA post-processing techniques with code length.

arXiv:2412.08596•Dec 11, 2024•1 citation

A Decomposition Mapping based Quantized Belief Propagation Decoding for 5G LDPC Codes

Hangxuan Cui, Khoa Le, Fakhreddine Ghaffari +3 more

Since the degree-1 variable nodes (VNs) in the low-density parity-check (LDPC) codes for the 5th generation (5G) mobile communications are very sensitive to be erroneous, the quantized min-sum (QMS) and offset min-sum (QOMS) decodings suffer from poor error-correction performance due to the imprecise estimation of the check-to-variable (C2V) message magnitudes. For this reason, this paper proposes a decomposition mapping based quantized belief propagation (DM-QBP) decoding for 5G LDPC codes. In order to reduce the computation complexity, the check node (CN) update function is realized by look-up tables (LUTs). Furthermore, a decomposition method is presented to eliminate the high memory cost of using large tables without performance loss. Therefore, the CN update function can be implemented based only on simple mappings and fixed-point additions. Simulation results show that, the DM-QBP decoder considerably outperforms the state-of-the-art ones for several 5G LDPC codes. With a small number of quantization bits, its performance is even better than the floating-point OMS decoding in some cases.

International Symposium on Communications and Information Technologies•Sep 1, 2019•0 citations

Quantum Approximate Optimization for Decoding of Low-Density Parity-Check Codes

Krishnakanta Barik, Goutam Paul

Decoding Low-Density Parity-Check (LDPC) codes is a fundamental problem in coding theory, and Belief Propagation (BP) is one of the most popular methods for LDPC code decoding. However, BP may encounter convergence issues and suboptimal performance, especially for short-length codes and in high-noise channels. The Quantum Approximate Optimization Algorithm (QAOA) is a type of Variational Quantum Algorithm (VQA) designed to solve combinatorial optimization problems by minimizing a problem-specific cost function. In this paper, we present a QAOA-based decoding framework for LDPC codes by formulating a decoding cost function that incorporates both parity-check constraints and soft channel reliability information. The resulting optimization problem is solved using QAOA to search for low-energy configurations corresponding to valid codewords. We test the proposed method through extensive numerical experiments and compare its performance with BP decoding. The experimental results demonstrate that the QAOA-based decoder achieves a higher probability of correctly recovering the transmitted codeword than BP across multiple experimental settings.

quant-pharXiv:2602.21124•IEEE International Conference on Quantum Control, Computing and Learning (qCCL)•Feb 25, 2026•0 citations

A Reconstruction-Computation-Quantization (RCQ) Approach to Node Operations in LDPC Decoding

Linfang Wang, Richard D. Wesel, Maximilian Stark +1 more

This paper proposes a finite-precision decoding method for low-density parity-check (LDPC) codes that features the three steps of Reconstruction, Computation, and Quantization (RCQ). Unlike Mutual-Information-Maximization Quantized Belief Propagation (MIM-QBP), RCQ can approximate either belief propagation or Min-Sum decoding. MIM-QBP decoders do not work well when the fraction of degree-2 variable nodes is large. However, sometimes a large fraction of degree-2 variable nodes is used to facilitate a fast encoding structure, as seen in the IEEE 802.11 standard and the DVB-S2 standard. In contrast to MIM-QBP, the proposed RCQ decoder may be applied to any off-the-shelf LDPC code, including those with a large fraction of degree-2 variable nodes. Simulations show that a 4-bit Min-Sum RCQ decoder delivers frame error rate (FER) performance within 0.1 dB of floating point belief propagation (BP) for the IEEE 802.11 standard LDPC code in the low SNR region. The RCQ decoder actually outperforms floating point BP and Min-Sum in the high SNR region were FER less than 10-5. This paper also introduces Hierarchical Dynamic Quantization (HDQ) to design the time-varying non-uniform quantizers required by RCQ decoders. HDQ is a low-complexity design technique that is slightly sub-optimal. Simulation results comparing HDQ and optimal quantization on the symmetric binary-input memoryless additive white Gaussian noise channel show a mutual information loss of less than 10-6bits, which is negligible in practice.

arXiv:2005.07259•Globecom•Dec 1, 2020•11 citations

Mutual Information-Maximizing Quantized Belief Propagation Decoding of Regular LDPC Codes

Xuan He, Kui Cai, Zhen Mei +2 more

In this paper, we propose a class of finite alphabet iterative decoder (FAID), called mutual information-maximizing quantized belief propagation (MIM-QBP) decoder, for decoding regular low-density parity-check (LDPC) codes. Our decoder follows the reconstruction-calculation-quantization (RCQ) decoding architecture that is widely used in FAIDs. We present the first complete and systematic design framework for the RCQ parameters, and prove that our design with sufficient precision at node update is able to maximize the mutual information between coded bits and exchanged messages. Simulation results show that the MIM-QBP decoder can always considerably outperform the state-of-the-art mutual information-maximizing FAIDs that adopt two-input single-output lookup tables for decoding. Furthermore, with only 3 bits being used for each exchanged message, the MIM-QBP decoder can outperform the floating-point belief propagation decoder at the high signal-to-noise ratio regions when testing on high-rate LDPC codes with a maximum of 10 and 30 iterations.

arXiv:1904.06666•Apr 14, 2019•6 citations

On Mutual Information-Maximizing Quantized Belief Propagation Decoding of LDPC Codes

Xuan He, Kui Cai, Zhen Mei

A severe problem for mutual information-maximizing lookup table (MIM-LUT) decoding of low-density parity-check (LDPC) code is the high memory cost for using large tables, while decomposing large tables to small tables deteriorates decoding error performance. In this paper, we propose a systematic method, called mutual information- maximizing quantized belief propagation (MIM-QBP) decoding, to remove the lookup tables used for MIM-LUT decoding. Our method leads to a very practical decoder, namely the MIM-QBP decoder, which can be implemented based only on simple mappings and additions. Simulation results show that the proposed MIM-QBP decoder can outperform the state-of-the-art MIM-LUT decoder. Moreover, the MIM-QBP decoder with only 3 bits per message can outperform the floating-point belief propagation (BP) decoder at high signal-to-noise ratio (SNR) regions with a maximum of 10 iterations.

Globecom•Dec 1, 2019•25 citations
We present Quantum Belief Propagation (QBP), a Quantum Annealing (QA) based decoder design for Low Density Parity Check (LDPC) error control codes, which have found many useful applications in Wi-Fi, satellite communications, mobile cellular systems, and data storage systems. QBP reduces the LDPC decoding to a discrete optimization problem, then embeds that reduced design onto quantum annealing hardware. QBP's embedding design can support LDPC codes of block length up to 420 bits on real state-of-the-art QA hardware with 2,048 qubits. We evaluate performance on real quantum annealer hardware, performing sensitivity analyses on a variety of parameter settings. Our design achieves a bit error rate of 10--8 in 20 μs and a 1,500 byte frame error rate of 10--6 in 50 μs at SNR 9 dB over a Gaussian noise wireless channel. Further experiments measure performance over real-world wireless channels, requiring 30 μs to achieve a 1,500 byte 99.99% frame delivery rate at SNR 15-20 dB. QBP achieves a performance improvement over an FPGA based soft belief propagation LDPC decoder, by reaching a bit error rate of 10--8 and a frame error rate of 10--6 at an SNR 2.5--3.5 dB lower. In terms of limitations, QBP currently cannot realize practical protocol-sized (e.g., Wi-Fi, WiMax) LDPC codes on current QA processors. Our further studies in this work present future cost, throughput, and QA hardware trend considerations.
Decoding low-density parity-check codes is critical in many current technologies, such as fifth-generation (5G) wireless networks and satellite communications. The belief propagation algorithm allows for fast decoding due to the low density of these codes. However, there is scope for improvement to this algorithm both in terms of its computational cost when decoding large codes and its error-correcting abilities. Here, we introduce the quantum-enhanced belief propagation (QEBP) algorithm, in which the Quantum Approximate Optimization Algorithm (QAOA) acts as a pre-processing step to belief propagation. We perform exact simulations of syndrome decoding with QAOA, whose result guides the belief propagation algorithm, leading to faster convergence and a lower block error rate (BLER). In addition, through the repetition code, we study the possibility of having shared variational parameters between syndromes and, in this case, code lengths. We obtain a unique pair of variational parameters for level-1 QAOA by optimizing the probability of successful decoding through a transfer matrix method. Then, using these parameters, we compare the scaling of different QAOA post-processing techniques with code length.
Since the degree-1 variable nodes (VNs) in the low-density parity-check (LDPC) codes for the 5th generation (5G) mobile communications are very sensitive to be erroneous, the quantized min-sum (QMS) and offset min-sum (QOMS) decodings suffer from poor error-correction performance due to the imprecise estimation of the check-to-variable (C2V) message magnitudes. For this reason, this paper proposes a decomposition mapping based quantized belief propagation (DM-QBP) decoding for 5G LDPC codes. In order to reduce the computation complexity, the check node (CN) update function is realized by look-up tables (LUTs). Furthermore, a decomposition method is presented to eliminate the high memory cost of using large tables without performance loss. Therefore, the CN update function can be implemented based only on simple mappings and fixed-point additions. Simulation results show that, the DM-QBP decoder considerably outperforms the state-of-the-art ones for several 5G LDPC codes. With a small number of quantization bits, its performance is even better than the floating-point OMS decoding in some cases.
Decoding Low-Density Parity-Check (LDPC) codes is a fundamental problem in coding theory, and Belief Propagation (BP) is one of the most popular methods for LDPC code decoding. However, BP may encounter convergence issues and suboptimal performance, especially for short-length codes and in high-noise channels. The Quantum Approximate Optimization Algorithm (QAOA) is a type of Variational Quantum Algorithm (VQA) designed to solve combinatorial optimization problems by minimizing a problem-specific cost function. In this paper, we present a QAOA-based decoding framework for LDPC codes by formulating a decoding cost function that incorporates both parity-check constraints and soft channel reliability information. The resulting optimization problem is solved using QAOA to search for low-energy configurations corresponding to valid codewords. We test the proposed method through extensive numerical experiments and compare its performance with BP decoding. The experimental results demonstrate that the QAOA-based decoder achieves a higher probability of correctly recovering the transmitted codeword than BP across multiple experimental settings.
This paper proposes a finite-precision decoding method for low-density parity-check (LDPC) codes that features the three steps of Reconstruction, Computation, and Quantization (RCQ). Unlike Mutual-Information-Maximization Quantized Belief Propagation (MIM-QBP), RCQ can approximate either belief propagation or Min-Sum decoding. MIM-QBP decoders do not work well when the fraction of degree-2 variable nodes is large. However, sometimes a large fraction of degree-2 variable nodes is used to facilitate a fast encoding structure, as seen in the IEEE 802.11 standard and the DVB-S2 standard. In contrast to MIM-QBP, the proposed RCQ decoder may be applied to any off-the-shelf LDPC code, including those with a large fraction of degree-2 variable nodes. Simulations show that a 4-bit Min-Sum RCQ decoder delivers frame error rate (FER) performance within 0.1 dB of floating point belief propagation (BP) for the IEEE 802.11 standard LDPC code in the low SNR region. The RCQ decoder actually outperforms floating point BP and Min-Sum in the high SNR region were FER less than 10-5. This paper also introduces Hierarchical Dynamic Quantization (HDQ) to design the time-varying non-uniform quantizers required by RCQ decoders. HDQ is a low-complexity design technique that is slightly sub-optimal. Simulation results comparing HDQ and optimal quantization on the symmetric binary-input memoryless additive white Gaussian noise channel show a mutual information loss of less than 10-6bits, which is negligible in practice.
In this paper, we propose a class of finite alphabet iterative decoder (FAID), called mutual information-maximizing quantized belief propagation (MIM-QBP) decoder, for decoding regular low-density parity-check (LDPC) codes. Our decoder follows the reconstruction-calculation-quantization (RCQ) decoding architecture that is widely used in FAIDs. We present the first complete and systematic design framework for the RCQ parameters, and prove that our design with sufficient precision at node update is able to maximize the mutual information between coded bits and exchanged messages. Simulation results show that the MIM-QBP decoder can always considerably outperform the state-of-the-art mutual information-maximizing FAIDs that adopt two-input single-output lookup tables for decoding. Furthermore, with only 3 bits being used for each exchanged message, the MIM-QBP decoder can outperform the floating-point belief propagation decoder at the high signal-to-noise ratio regions when testing on high-rate LDPC codes with a maximum of 10 and 30 iterations.
A severe problem for mutual information-maximizing lookup table (MIM-LUT) decoding of low-density parity-check (LDPC) code is the high memory cost for using large tables, while decomposing large tables to small tables deteriorates decoding error performance. In this paper, we propose a systematic method, called mutual information- maximizing quantized belief propagation (MIM-QBP) decoding, to remove the lookup tables used for MIM-LUT decoding. Our method leads to a very practical decoder, namely the MIM-QBP decoder, which can be implemented based only on simple mappings and additions. Simulation results show that the proposed MIM-QBP decoder can outperform the state-of-the-art MIM-LUT decoder. Moreover, the MIM-QBP decoder with only 3 bits per message can outperform the floating-point belief propagation (BP) decoder at high signal-to-noise ratio (SNR) regions with a maximum of 10 iterations.