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

• Surface-code decoders must achieve low logical error rates within quantum coherence times, requiring extremely low computational complexity.Source: §I · p. 1
• 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.Source: §I · p. 1
• 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.Source: §I · p. 1
• 17.5% is L-NBP’s depolarizing-noise threshold, exceeding MWPM (14.5%) and BP-OSD (16.5%).Source: §I · pp. 1–2
• 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.Source: §I · p. 2
• L-NBP combines a lightweight logical classifier with linear-complexity neural BP, contrasting with higher-complexity post-processing and high-capacity neural decoders.Source: A. Related Work · p. 2

• Quantum BP iteratively passes log-likelihood-ratio messages over a Tanner graph with physical-qubit variable nodes and stabilizer check nodes.Source: B. Quantum BP and NBP Decoders · p. 3
• Posterior LLRs quantify each physical qubit’s belief for identity relative to X, Y, or Z errors.Source: B. Quantum BP and NBP Decoders · p. 3
• A syndrome mismatch produces a flagged failure, while a matching syndrome with a residual logical operator produces an unflagged failure.Source: B. Quantum BP and NBP Decoders · p. 3
• 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.Source: B. Quantum BP and NBP Decoders · p. 3
• NBP replaces fixed message sums with trainable weighted sums and is trained to estimate the physical error pattern.Source: B. Quantum BP and NBP Decoders · p. 3

• Logical-level decoding focuses on estimating the logical operator because the exact physical error is not the final QEC objective.Source: C. Logical-Level Decoding · p. 3
• The recovery is constructed deterministically as Ê = L̂T(s), combining the estimated logical operator with the pure error fixed by the measured syndrome.Source: C. Logical-Level Decoding · pp. 3–4
• For one logical qubit, the decoder performs four-way classification over Ī, X̄, Z̄, and Ȳ.Source: C. Logical-Level Decoding · p. 4
• L-NBP runs NBP on the measured syndrome, converts posterior LLRs into a soft syndrome, and predicts the logical operator.Source: §III · p. 4, Figure 2 · p. 4

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

• L-NBP composes an NBP module that produces posterior beliefs with a logical classifier that converts them into a soft syndrome and output logits.Source: B. L-NBP Decoding · p. 5
• All components are piecewise differentiable, allowing end-to-end training through the logical classifier into the NBP module.Source: B. L-NBP Decoding · p. 5
• The decoder is optimized with a logical-level cross-entropy loss rather than an additional physical-level loss for the NBP module.Source: B. L-NBP Decoding · p. 5
• 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.Source: B. L-NBP Decoding · p. 5, Figure 3 · p. 5

• The visualization tracks 1000 d = 9, p = 0.05 soft-syndrome samples across four training stages and colors them by logical operator.Source: C. Qualitative Analysis via t-SNE… · p. 5, Figure 4 · p. 6
• Early in training, samples from the four logical operators are heavily overlapped and largely indistinguishable.Source: C. Qualitative Analysis via t-SNE… · p. 5
• By the end of training, the soft syndrome forms increasingly compact and well-separated clusters for the logical operators.Source: C. Qualitative Analysis via t-SNE… · pp. 5–6, Figure 4 · p. 6

• Phenomenological and circuit-level models repeat syndrome measurements over multiple rounds and include faulty syndrome observations.Source: D. Extension to Multi-Round… · p. 6
• The multi-round BP input uses detectors dr = sr ⊕ sr−1 and jointly estimates per-round data errors on an extended stabilizer matrix.Source: D. Extension to Multi-Round… · p. 6
• L-NBP computes the final soft syndrome by combining per-round error contributions through the same stabilizer connections and min-sum aggregation.Source: D. Extension to Multi-Round… · p. 6
• The resulting soft syndrome has length m = n − 1 regardless of the number of rounds, acting as a syndrome-history compressor.Source: D. Extension to Multi-Round… · pp. 6–7
• 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.Source: D. Extension to Multi-Round… · p. 7
• Circuit-level L-NBP extracts the soft syndrome with the same procedure used for phenomenological noise and passes it to the same logical classifier.Source: D. Extension to Multi-Round… · pp. 6–7

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.Source: A. LER Comparison · p. 7, Figure 5 · p. 7

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.Source: A. LER Comparison · p. 7

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.Source: A. LER Comparison · p. 8, Figure 6 · p. 8

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.Source: A. LER Comparison · p. 8, Figure 6 · p. 8

• L-NBP preserves overall linear O(n) complexity because soft-syndrome extraction and logical classification each scale linearly with code length.Source: B. Complexity Analysis · p. 8, Figure 7 · p. 9
• MWPM is omitted from the FLOPs comparison because its combinatorial matching is not directly measurable in FLOPs.Source: B. Complexity Analysis · p. 8
• 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.Source: B. Complexity Analysis · pp. 8–9
• 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.Source: §V · p. 9

• 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.Source: Appendix A · p. 9
• 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.Source: Appendix A · p. 9
• 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.Source: Appendix A · p. 10
• A damping step mixes updated messages with previous-iteration messages to improve convergence on graphs with short cycles.Source: Appendix A · p. 10
• 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.Source: Appendix A · p. 10

• L-NBP training uses Adam for 1000 epochs, with learning rate 10^-4, cosine annealing, Xavier initialization, and a batch size of 256.Source: Appendix B · p. 10
• 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.Source: Appendix B · p. 10
• 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.Source: Appendix B · p. 10
• 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.Source: Appendix C · p. 10

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.Source: Figure 8 · p. 11
• 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.Source: Appendix D · p. 11
• Hard residual-syndrome processing remains poor because hard decisions block gradients through NBP and discard information useful for logical classification.Source: Appendix D · p. 11
• Independently training and freezing NBP before classifier training performs poorly, showing that NBP must be optimized jointly for the logical objective.Source: Appendix D · p. 11