Recurrent Bipartite Graph Neural Networks for QC-MDPC Error Decoding in McEliece Cryptosystems

Parth Rajeshkumar Tandel; Elisabeth Fink

cs.CROct 28, 2026

Recurrent Bipartite Graph Neural Networks for QC-MDPC Error Decoding in McEliece Cryptosystems

Authors: Parth Rajeshkumar Tandel, Elisabeth Fink

Organizations: Middlesex University, Department of Computer Science, Hendon, London NW4 4BT, UK

Abstract

As the advent of large-scale quantum computing threatens classical encryption, Quasi-Cyclic Moderate Density Parity-Check (QC-MDPC) codes have emerged as a foundational element of Post-Quantum Cryptography (PQC). However, decoding these relatively dense codes using classical Belief Propagation algorithms often leads to failures caused by short graph cycles that stall the decoder. In cryptographic applications, these failures are severe security vulnerabilities that leak secret key information. To address this, this paper proposes a Recurrent Bipartite Graph Neural Network (R-BGNN) as proof of concept. By integrating Gated Recurrent Units (GRUs) into the message-passing framework and employing a multi-topology curriculum training strategy, the R-BGNN actively learns to break limit-cycle oscillations. Evaluated across 20 unseen matrix topologies, the proposed architecture significantly outperforms classical Bit-Flipping and Min-Sum baselines, reducing the Decoding Failure Rate (DFR) by 63.7% at moderate noise levels ( $t=10$ ) while converging in fewer iterations.

Figures & tables

Architecture	Literature	Weight Granularity & Parameter Complexity	Scalability across Lengths $n$	Secret Key Graph Preserved?	Primary Application Domain
Deep Unrolled BP	[ 17 ]	Per-edge per-layer: $\mathcal{O}(E\times L_{\max})$	No (Hard-coded to fixed graph)	Yes	High-Density Algebraic Block Codes
Attentive SNNMS (A-SNNMS)	[ 10 ]	Per-layer shared: $\mathcal{O}(L_{\max})$	No (Requires retraining per code size)	Yes	Telecommunication LDPC (5G / Wi-Fi 6)
Edge-Weighted GNN (EW-GNN)	[ 18 ]	MLP edge weight generator: $\mathcal{O}(1)$ constant	Yes (Transferable across $n$ )	Yes	Short Block Communication Codes
Neural Enhanced BP (NEBP)	[ 21 ]	Factor Graph GNN refinement: $\mathcal{O}(GNN)$	Partial (Graph-dependent)	Yes	Non-Gaussian / Bursty Noise Channels
Differentiable Factor Graph	[ 22 ]	Gradient optimization of binary matrix $H$	N/A (Code design tool)	Alters matrix $H$	Differentiable Short Code Design

Table 1: Summary of various architectures

Figure 1: A random sample binary Parity-Check Matrix, $N=254,r=127,W=14,d=7$ (black dots represent set bits)

Figure 2: Check-Node Intersection Frequency plot showing 1000+ intersections of more than two shared Variable Nodes

Figure 3: Tanner Subgraph showing 4-cycles (edges in red form cycles)

Component	Hyperparameter / Configuration	Parameter Count
Variable Node Embedding	$\text{Linear}(1\to 64)\to\text{SiLU}\to\text{Linear}(64\to 64)$	4,288
Check Node Embedding	$\text{Linear}(1\to 64)\to\text{SiLU}\to\text{Linear}(64\to 64)$	4,288
V2C Message MLP	$\text{Linear}(128\to 128)\to\text{SiLU}\to\text{Linear}(128\to 64)\to\text{SiLU}$	24,768
C2V Message MLP	$\text{Linear}(128\to 128)\to\text{SiLU}\to\text{Linear}(128\to 64)\to\text{SiLU}$	24,768
Check Node Memory	$\text{GRUCell}(\text{Input}:64,\text{Hidden}:64)$	24,960
Variable Node Memory	$\text{GRUCell}(\text{Input}:64,\text{Hidden}:64)$	24,960

Table 2: R-BGNN Architectural Hyperparameters

Figure 4: Performance of Decoding Failure Rate (DFR) waterfall curves illustrating the R-BGNN (evaluated across 20 unseen QC-MDPC matrices).

Figure 5: Bit Error Rate (BER) trajectories evaluated across 20 unseen QC-MDPC matrices

Figure 6: Average iterations required for convergence

Figure 7: Residual error distribution at (a) $t=7$ , (b) $t=8$ , (c) $t=9$ , (d) $t=10$ . The hard-decision Bit-Flipping decoder exhibits severe absorbing-state behavior, leaving dense clusters of unresolvable bits. Conversely, the proposed R-BGNN successfully navigates the dense graph topology alongside Min-Sum having comparatively lesser residual errors.

Figure 8: Principal Component Analysis (PCA) projection of the final R-BGNN latent space.

Error-Correcting Codes

See all 35 papers

Neural Minimum Weight Perfect Matching for Quantum Error Codes
Jan 1, 2026Yotam Peled, David Zenati, Eliya NachmaniNeural Decoding Quantum Error Correction
School of Electrical and Computer Engineering (ECE), Ben-Gurion University, Beer Sheva, Israel.
Maximum Likelihood Decoding of Quantum Error Correction Codes
May 17, 2026Hanyan Cao, Ge Yan, Yuxuan Du +1Quantum Error Correction Quantum Error Correction Decoding
1Science, Mathematics and Technology Cluster, Singapore University of Technology and Design, 8 Somapah Road, 487372, Singapore · College of Computing and Data Science, Nanyang Technological University, Singapore, Singapore · School of Physical and Mathematical Sciences, Nanyang Technological University,2026 Singapore, Singapore
Scalable Neural Decoders for Practical Fault-Tolerant Quantum Computation
Apr 9, 2026Andi Gu, J. Pablo Bonilla Ataides, Mikhail D. Lukin +1Quantum LDPC Codes Quantum Error Correction Decoding
Department of Physics, Harvard University, Cambridge, MA 02138, USA · Harvard Quantum Initiative, Harvard University, Cambridge, MA 02138, USA

Jan 1, 2026J/K move · Enter open · S save

Neural Minimum Weight Perfect Matching for Quantum Error Codes

Yotam Peled, David Zenati, Eliya Nachmani

School of Electrical and Computer Engineering (ECE), Ben-Gurion University, Beer Sheva, Israel.

Neural Decoding Quantum Error Correction Combinatorial Optimization Quantum Error Correction Decoding

Open paper AskPDF arXiv

Realizing the full potential of quantum computation requires Quantum Error Correction (QEC). QEC reduces error rates by encoding logical information across redundant physical qubits, enabling errors to be detected and corrected. A common decoder used for this task is Minimum Weight Perfect Matching (MWPM) a graph-based algorithm that relies on edge weights to identify the most likely error chains. In this work, we propose a data-driven decoder named Neural Minimum Weight Perfect Matching (NMWPM). Our decoder utilizes a hybrid architecture that integrates Graph Neural Networks (GNNs) to extract local syndrome features and Transformers to capture long-range global dependencies, which are then used to predict dynamic edge weights for the MWPM decoder. To facilitate training through the non-differentiable MWPM algorithm, we formulate a novel proxy loss function that enables end-to-end optimization. Our findings on the toric code under depolarizing noise demonstrate thresholds of 17.9% and 10.95%, nearing the 18.9% and 11.0% maximum likelihood bounds, highlighting the advantage of hybrid decoders that combine the predictive capabilities of neural networks with the algorithmic structure of classical matching.

Abstract

Error-Correcting Codes

Explore similar work

Neural Minimum Weight Perfect Matching for Quantum Error Codes

Maximum Likelihood Decoding of Quantum Error Correction Codes

Scalable Neural Decoders for Practical Fault-Tolerant Quantum Computation