Quantum Message Passing Convergence and Vanishing Block-Error Probability for Random LDPC Codes
Abstract
Belief propagation with quantum messages (BPQM) is a quantum algorithm that decodes classical codes transmitted over classical--quantum channels. It realizes optimal decoding on tree factor graphs over pure-state classical-quantum channels. However, this tree-based analysis does not ensure vanishing block-error probability for LDPC Tanner graphs with cycles. In this work, we construct a two-stage BPQM decoder for random q-ary LDPC codes over symmetric q-ary pure-state channels, where q is prime, and prove that its ensemble-average block-error probability vanishes as the blocklength N tends to infinity. For regular ensembles with dv≥3, fidelity bounds yield double-exponential decay of the average symbol-error probability throughout the BPQM success region. We apply depth-ℓ BPQM to coordinates with tree neighbourhoods and treat the remaining coordinates as erasures. With a suitable ℓ=Θ(loglog N), a noncommutative union bound controls the BPQM decoding errors, while the minimum-distance property guarantees erasure recovery. We also extend the analysis to finite-support irregular ensembles. These results are relevant to quantum algorithms based on Regev's reduction, where coherent decoding uncomputes a codeword register. Decoded quantum interferometry (DQI) uses a closely related Fourier-based framework that reduces sparse max-LINSAT optimization problems to LDPC decoding problems on pure-state channels. Our results justify the use of BPQM in the decoding step of DQI and of coding-theoretic algorithms based on Regev's reduction whenever the code is drawn from one of the random LDPC ensembles analyzed here and the induced memoryless symmetric pure-state channel lies in the BPQM success region. Curiously, our numerical results indicate that DQI+BPQM achieves a satisfaction ratio that closely matches that of simulated annealing.
Related
- Why Multi-Layer Message Passing Works: Completeness Theory for Graph Neural Network Interatomic Potentials
- Geometry-Aware Simplicial Message Passing
- Message-passing graph persistence
- Learned Score-Based Turbo Message Passing for Channel Recovery From Spatially Compressed Measurements
- Efficient Message Passing for Partial Differential Equation Priors
BibTeX
@misc{mandal2026quantum,
title = {{Quantum Message Passing Convergence and Vanishing Block-Error Probability for Random LDPC Codes}},
author = {Avijit Mandal and Christophe Piveteau and Joseph M. Renes and Henry D. Pfister},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.05857},
eprint = {2609.05857},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05857},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Message Passing Convergence and Vanishing Block-Error Probability for Random LDPC Codes
AU - Avijit Mandal
AU - Christophe Piveteau
AU - Joseph M. Renes
AU - Henry D. Pfister
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2609.05857
UR - https://arxiv.org/abs/2609.05857
AB - Belief propagation with quantum messages (BPQM) is a quantum algorithm that decodes classical codes transmitted over classical--quantum channels. It realizes optimal decoding on tree factor graphs over pure-state classical-quantum channels. However, this tree-based analysis does not ensure vanishing block-error probability for LDPC Tanner graphs with cycles. In this work, we construct a two-stage BPQM decoder for random q-ary LDPC codes over symmetric q-ary pure-state channels, where q is prime, and prove that its ensemble-average block-error probability vanishes as the blocklength N tends to infinity. For regular ensembles with d_v≥3, fidelity bounds yield double-exponential decay of the average symbol-error probability throughout the BPQM success region. We apply depth-ℓ BPQM to coordinates with tree neighbourhoods and treat the remaining coordinates as erasures. With a suitable ℓ=Θ(loglog N), a noncommutative union bound controls the BPQM decoding errors, while the minimum-distance property guarantees erasure recovery. We also extend the analysis to finite-support irregular ensembles. These results are relevant to quantum algorithms based on Regev's reduction, where coherent decoding uncomputes a codeword register. Decoded quantum interferometry (DQI) uses a closely related Fourier-based framework that reduces sparse max-LINSAT optimization problems to LDPC decoding problems on pure-state channels. Our results justify the use of BPQM in the decoding step of DQI and of coding-theoretic algorithms based on Regev's reduction whenever the code is drawn from one of the random LDPC ensembles analyzed here and the induced memoryless symmetric pure-state channel lies in the BPQM success region. Curiously, our numerical results indicate that DQI+BPQM achieves a satisfaction ratio that closely matches that of simulated annealing.
ER -