Logical Neural Belief Propagation for Linear-Complexity Decoding of Surface Codes

Hee-Youl Kwak; Seong-Joon Park; Dae-Young Yun; Eliya Nachmani; Jae-Won Kim

Source-linked AI summary

Logical Neural Belief Propagation for Linear-Complexity Decoding of Surface Codes

Hee-Youl Kwak, Seong-Joon Park, Dae-Young Yun, Eliya Nachmani, Jae-Won Kim

arXiv:2608.27682v1Aug 27, 2026quant-phcs.IT

TL;DR

Quantum error-correction decoders need high logical accuracy and efficient scaling, but conventional BP has limited accuracy on surface codes. L-NBP combines neural BP with logical-level classification and achieves competitive accuracy with linear complexity, including a 17.5% depolarizing-noise threshold and much lower circuit-level complexity than BP-OSD.

Problem
Quantum error-correction decoders must achieve low logical error rates with very low complexity, while conventional BP remains limited in surface-code accuracy and threshold behavior.
Method
L-NBP trains an NBP module and logical classifier end-to-end so posterior beliefs become a continuous soft syndrome for logical-operator prediction.
Results
L-NBP matches or outperforms BP-OSD and MWPM, reaches a 17.5% depolarizing-noise threshold, and matches BP-OSD accuracy at distance 9 under circuit-level noise using about 0.2% of its complexity.
Takeaways & Limitations
Logical-level classification lets L-NBP retain BP’s linear complexity while achieving high accuracy across the evaluated surface-code noise models.

Abstract

from arXiv · show

Quantum error correction (QEC) requires decoders that achieve high logical accuracy while scaling efficiently with the code length. Belief propagation (BP) is attractive for its linear decoding complexity, but conventional BP decoders often fail to reach sufficient logical accuracy on surface codes. We propose Logical Neural Belief Propagation (L-NBP), a BP-based neural decoder that redirects the decoding objective from physical-level decoding to logical-level decoding. L-NBP first runs a neural BP (NBP) module that produces posterior beliefs, and a logical classifier then transforms these beliefs into a continuous-valued soft syndrome and predicts the logical operator. Because all components in L-NBP are trainable by backpropagation, L-NBP is trained end-to-end, so that the NBP module learns to extract soft syndromes that are favorable for logical classification. On surface codes, L-NBP matches or outperforms the BP with ordered-statistics decoding (BP-OSD) and minimum-weight perfect matching (MWPM) while retaining the linear complexity of BP, and achieves a threshold of $17.5\%$ under depolarizing noise. Moreover, under circuit-level noise, L-NBP matches the accuracy of BP-OSD on the distance-$9$ surface code while requiring only $0.2\%$ of its complexity. These results show that combining BP, neural weights, and logical-level decoding enables scalable and high-accuracy quantum decoding.

I. INTRODUCTION

Surface-code decoders must combine low logical error rates with extremely low complexity. L-NBP addresses BP’s accuracy limitations by training neural BP for logical-level classification while retaining linear complexity.

Surface-code decoders must achieve low logical error rates within quantum coherence times, requiring extremely low computational complexity.
BP scales linearly with code length but lacks sufficient surface-code accuracy because of short cycles and quantum degeneracy.Standalone BP and NBP also lack clear threshold behavior.
L-NBP redirects decoding from physical-error recovery to logical-operator prediction using neural BP and a trainable logical classifier.The classifier converts posterior beliefs into a soft syndrome before predicting the logical operator.
17.5% is L-NBP’s depolarizing-noise threshold, exceeding MWPM (14.5%) and BP-OSD (16.5%).
At distance 9 under circuit-level noise, L-NBP matches BP-OSD and Relay-BP accuracy while requiring about 0.2% and 0.06% of their respective complexities.Its compact soft-syndrome representation preserves linear O(n) complexity per round.
L-NBP combines a lightweight logical classifier with linear-complexity neural BP, contrasting with higher-complexity post-processing and high-capacity neural decoders.

B. Quantum BP and NBP Decoders

Quantum BP estimates physical errors by iterative message passing over a Tanner graph, while NBP introduces trainable message weights. Decoding outcomes are classified by syndrome consistency and the residual operator’s stabilizer or logical status.

Quantum BP iteratively passes log-likelihood-ratio messages over a Tanner graph with physical-qubit variable nodes and stabilizer check nodes.
Posterior LLRs quantify each physical qubit’s belief for identity relative to X, Y, or Z errors.
A syndrome mismatch produces a flagged failure, while a matching syndrome with a residual logical operator produces an unflagged failure.
Decoding succeeds when the estimated syndrome matches the measured syndrome and the residual operator is a stabilizer.The logical error rate sums flagged and unflagged failure probabilities.
NBP replaces fixed message sums with trainable weighted sums and is trained to estimate the physical error pattern.

C. Logical-Level Decoding

Logical-level decoding estimates the logical operator rather than the exact physical error, then combines it with a syndrome-determined pure error to form recovery. L-NBP implements this through neural BP beliefs, a soft syndrome, and logical classification.

Logical-level decoding focuses on estimating the logical operator because the exact physical error is not the final QEC objective.
The recovery is constructed deterministically as Ê = L̂T(s), combining the estimated logical operator with the pure error fixed by the measured syndrome.
For one logical qubit, the decoder performs four-way classification over Ī, X̄, Z̄, and Ȳ.
L-NBP runs NBP on the measured syndrome, converts posterior LLRs into a soft syndrome, and predicts the logical operator.

A. Logical Classifier

The logical classifier converts NBP posterior beliefs into a continuous soft syndrome and predicts one of four logical operators. Learnable aggregation, normalization, and a lightweight neural network make the representation suitable for logical classification.

The NBP module supplies posterior LLRs representing beliefs about whether estimated errors commute or anticommute with stabilizers.
Edge-wise posterior LLRs are aggregated at each check node using the min-sum rule to form soft syndromes.
Soft syndromes across iterations are combined with trainable weights, then normalized by a learnable temperature and passed through tanh.
The resulting soft syndrome combines NBP beliefs with the measured syndrome, takes values in [−1, 1], and encodes decision confidence through its magnitude.
A single-hidden-layer MLP maps the soft syndrome to four logits, and the largest logit determines the predicted logical operator and final recovery.

B. L-NBP Decoding

L-NBP composes neural belief propagation with a logical classifier and trains both stages jointly. Redirecting optimization toward logical classification yields lower LER than NBP and surpasses BP-OSD in the reported d = 9 experiment.

L-NBP composes an NBP module that produces posterior beliefs with a logical classifier that converts them into a soft syndrome and output logits.
All components are piecewise differentiable, allowing end-to-end training through the logical classifier into the NBP module.
The decoder is optimized with a logical-level cross-entropy loss rather than an additional physical-level loss for the NBP module.
At p = 0.05 for the d = 9 surface code, NBP improves on BP but saturates, whereas L-NBP achieves a larger improvement and surpasses BP-OSD.

C. Qualitative Analysis via t-SNE Visualization

t-SNE visualizations show the L-NBP soft-syndrome representation becoming progressively more separable by logical operator during training. By the end, the four classes form compact, clearly separated clusters.

The visualization tracks 1000 d = 9, p = 0.05 soft-syndrome samples across four training stages and colors them by logical operator.
Early in training, samples from the four logical operators are heavily overlapped and largely indistinguishable.
By the end of training, the soft syndrome forms increasingly compact and well-separated clusters for the logical operators.

D. Extension to Multi-Round Measurement Models

L-NBP extends to phenomenological and circuit-level noise by processing multi-round detector information with an extended stabilizer matrix and compressing it into a fixed-size soft syndrome. This preserves the same logical-classifier interface while avoiding the larger circuit-level fault graph.

Phenomenological and circuit-level models repeat syndrome measurements over multiple rounds and include faulty syndrome observations.
The multi-round BP input uses detectors dr = sr ⊕ sr−1 and jointly estimates per-round data errors on an extended stabilizer matrix.
L-NBP computes the final soft syndrome by combining per-round error contributions through the same stabilizer connections and min-sum aggregation.
The resulting soft syndrome has length m = n − 1 regardless of the number of rounds, acting as a syndrome-history compressor.
Under circuit-level noise, L-NBP operates on the smaller extended stabilizer matrix rather than the detector error model, which has one column per circuit-level fault mechanism.
Circuit-level L-NBP extracts the soft syndrome with the same procedure used for phenomenological noise and passes it to the same logical classifier.

IV. SIMULATION RESULTS

Across code-capacity, phenomenological, and circuit-level noise, L-NBP matches or exceeds strong decoders while preserving a low iteration budget and favorable accuracy–complexity trade-offs. It achieves clear threshold behavior and substantially lower complexity than BP-OSD.

LER Comparison: L-NBP matches or exceeds BP-OSD and MWPM across code-capacity, phenomenological, and circuit-level noise models.The comparison uses LER, with code-capacity at d = 13 and the other models at d = 9.
Circuit-Level Noise: 60 iterations: L-NBP is only slightly worse than Relay-BP under circuit-level noise despite Relay-BP using up to 18,080 iterations.The circuit-level comparison reports LER per round.
Threshold Behavior: 17.5% threshold: L-NBP exhibits clear threshold behavior under the code-capacity model, unlike NBP.NBP degrades as code distance increases and shows no threshold.
Accuracy–Complexity Trade-off: 0.89 M FLOPs at a 17.5% threshold: L-NBP achieves the best accuracy–complexity trade-off among the compared decoders at d = 13.BP-OSD reaches a 16.5% threshold at 1.95 M FLOPs, while QECCT and AMBP require substantially more computation.

B. Complexity Analysis

L-NBP preserves linear complexity while matching or outperforming more expensive decoders across noise models. Its advantage grows with code length, especially against BP-OSD under phenomenological and circuit-level noise.

L-NBP preserves overall linear O(n) complexity because soft-syndrome extraction and logical classification each scale linearly with code length.
MWPM is omitted from the FLOPs comparison because its combinatorial matching is not directly measurable in FLOPs.
0.2% of BP-OSD complexity is required by L-NBP at d = 9 under circuit-level noise, a 99.8% reduction.L-NBP uses the compact extended stabilizer matrix, while BP-OSD operates on the much larger HDEM.
L-NBP maintains linear complexity while matching or outperforming superlinear-complexity MWPM and BP-OSD decoders across noise models.Under code-capacity noise, it attains a 17.5% threshold and the best reported accuracy–complexity trade-off.

Appendix A: BP and NBP Message Update Rules

The NBP appendix defines trainable message updates built on quantum BP structure. Weighted extrinsic combinations, syndrome-aware check-node updates, damping, and fixed prior initialization form the message-passing procedure.

Initial prior LLRs are assigned from the noise model, with each Pauli error occurring at probability p/3 under depolarizing noise.The implementation uses a fixed initialization p = 0.1 because the exact physical error rate is often unavailable.
At each iteration, messages are exchanged between variable nodes and check nodes for each error type.Variable-node messages begin from initialized messages and are updated using incoming check-node information.
Check-node messages incorporate the measured syndrome bit through a min-sum rule, while variable-node updates use weighted extrinsic combinations.Only stabilizers that anticommute with the error type contribute to the extrinsic sum.
A damping step mixes updated messages with previous-iteration messages to improve convergence on graphs with short cycles.
NBP replaces plain variable-node and posterior sums with weighted sums controlled by trainable parameters θN.Classical BP fixes these weights to one, while weighted BP uses a single fixed scaling factor for check-node messages.

Appendix B: Training and Evaluation Details

The appendix specifies the training protocol, circuit-level evaluation setup, and ablations testing how soft syndromes and end-to-end training affect logical decoding. Results support jointly trained soft-syndrome processing over hard or independently trained alternatives.

L-NBP training uses Adam for 1000 epochs, with learning rate 10^-4, cosine annealing, Xavier initialization, and a batch size of 256.
60 BP iterations and a logical-classifier hidden dimension h = 256 are used, with iteration sampling interval Δ = 10.For d = 9 code-capacity training, one epoch takes about 30 seconds and the full run roughly 8 hours on an NVIDIA RTX A5000 GPU.
Threshold estimates use at least 10^5 Monte Carlo trials and continue until at least 1000 logical failures are collected.The threshold is defined as the crossing point among logical-error-rate curves for different code distances.
The circuit-level experiment uses Stim’s rotated surface-code memory circuit with R = d syndrome-extraction rounds and depolarizing errors after Clifford gates.Reset and measurement flip probabilities are set to p, with single- and two-qubit Pauli probabilities p/3 and p/15.
Ablation Study: Only the E2E-trained L-NBP soft syndrome forms compact, well-separated clusters by logical operator in the t-SNE visualization.The comparison includes measured hard syndromes, untrained BP soft syndromes, and independently trained NBP soft syndromes.
Ablation Study: 2.3 × 10^-2 logical error rate is achieved by the standalone MLP variant that directly classifies the measured hard syndrome at d = 11.This is substantially worse than the L-NBP baseline, indicating that direct lightweight MLP classification is insufficient.
Ablation Study: Hard residual-syndrome processing remains poor because hard decisions block gradients through NBP and discard information useful for logical classification.
Ablation Study: Independently training and freezing NBP before classifier training performs poorly, showing that NBP must be optimized jointly for the logical objective.