PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Message Passing Convergence and Vanishing Block-Error Probability for Random LDPC Codes

Avijit Mandal, Christophe Piveteau, Joseph M. Renes, Henry D. Pfister

arXiv:2609.05857v1quant-phcs.ITmath.IT

TL;DR

Tree-based BPQM analyses do not establish vanishing block-error probability for finite LDPC graphs with cycles, where repeated quantum messages cannot be copied. This paper constructs a two-stage decoder for random LDPC ensembles and proves that its ensemble-average block-error probability vanishes in the BPQM success region.

  • Problem

    Earlier BPQM analyses characterize symbol-error performance on computation trees but do not establish vanishing block-error probability for finite LDPC codes with cycles, where repeated quantum messages cannot be copied.

    Source: §1 · p. 3

  • Method

    A two-stage decoder applies BPQM to coordinates with tree neighbourhoods and recovers the remaining coordinates using parity constraints.

    Source: §1 · p. 4

  • Results

    The complete decoder’s ensemble-average block-error probability tends to zero for every channel in the BPQM success region; for regular d_v ≥ 3 ensembles, average symbol-error probability decays doubly exponentially with iterations.

    Source: §1 · p. 4

  • Takeaways & Limitations

    The decoder works directly with random LDPC ensembles, avoiding a large-girth code-selection requirement that would restrict computational instances.

    Source: §1 · p. 4

    The analysis considers symmetric q-ary pure-state channels; regular ensembles are restricted to positive design rate, so d_v < d_c.

    Source: §1 · p. 1, §4.1 · p. 19

Abstract

from arXiv · show

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\geq3$, fidelity bounds yield double-exponential decay of the average symbol-error probability throughout the BPQM success region. We apply depth-$\ell$ BPQM to coordinates with tree neighbourhoods and treat the remaining coordinates as erasures. With a suitable $\ell=\Theta(\log\log 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.

1 Introduction

Tree-based BPQM analysis does not establish vanishing block-error probability on cyclic LDPC graphs, where quantum messages cannot simply reuse channel outputs. This work constructs a two-stage decoder and proves vanishing ensemble-average block-error probability for random q-ary LDPC codes over symmetric pure-state channels in the BPQM success region.

1 Introduction

  • On tree factor graphs, BPQM compresses incoming quantum messages into a sufficient statistic and achieves optimal symbol-error probability, but cycles obstruct exact reuse of messages because of no-cloning.Earlier density-evolution analyses characterize computation-tree symbol-error performance, not vanishing block-error probability for finite LDPC codes.Source: §1 · p. 3
  • For regular random-coefficient computation trees, coefficient-uniform fidelity bounds give doubly exponential decay of average symbol-error probability throughout the BPQM success region.The paper also derives the exact density-evolution recursion for variable-node degree dv and check-node degree dc.Source: §1 · p. 4
  • Depth-ℓ BPQM with ℓ = Θ(log log N) makes the probability of any first-stage decoding error tend to zero, while minimum distance enables recovery of cyclic-neighbourhood coordinates as erasures.The noncommutative union bound controls BPQM errors, and the erased-coordinate count is below the sampled code's minimum distance with probability tending to one.Source: §1 · p. 4
  • The complete two-stage decoder has ensemble-average block-error probability tending to zero for every channel in the BPQM success region.The decoder applies BPQM on tree neighbourhoods and recovers the remaining coordinates as erasures.Source: §1 · p. 4
  • The vanishing block-error guarantee supports coherent decoding in Regev's reduction and DQI, where decoding erases a codeword register before subsequent Fourier processing.DQI associates sparse max-LINSAT instances with LDPC codes, while Regev-based formulations use decoding to uncompute a codeword register.Source: §1 · pp. 2, 4
  • The analysis extends to finite-support irregular ensembles, where density evolution averages over random degrees and nonzero edge coefficients.A likelihood-ratio comparison extends the tree estimate to the finite ensemble; the argument uses local tree neighbourhoods and parity-constraint recovery rather than requiring large girth.Source: §1 · p. 4

2 Preliminaries

The preliminaries set notation and specify the symmetric q-ary pure-state channels and decoding quantities used in the analysis.

2 Preliminaries

  • The preliminaries recall channel and error/fidelity results for symmetric q-ary pure-state channels, including channel-combining rules used later.The cited results are restated in the paper's notation without reproducing their existing proofs.Source: §2 · p. 5

2.1 Notation

  • The notation fixes [m] as {0, ..., m − 1}, uses bold lowercase for vectors, and treats q as prime with symbols identified with the finite field Fq.Unless stated otherwise, symbol arithmetic is over Fq.Source: §2.1 · p. 5

2.2 Symmetric Pure State Channels

  • A symmetric q-ary pure-state channel has a circulant Gram matrix, whose ordered eigen list determines the channel up to isometric equivalence.The normalized eigen list is a probability distribution; the preliminaries also relate the symmetric Holevo information, channel fidelity, and pretty good measurement error to these quantities.Source: §2.2 · pp. 5–6

3 BPQM on tree factor graphs

This section develops operational BPQM on tree factor graphs, establishing how its quantum messages and node operations support decoding a selected symbol. It also describes the final measurement and uses coefficient-aware density evolution to characterize the decoder’s success region.

3 BPQM on tree factor graphs

  • For a target symbol, BPQM combines incoming check messages with its physical channel and applies the PGM; the node rules yield a density-evolution recursion for symbol-error probability.Check-node outputs include orthogonal herald registers specifying conditional symmetric channels; bit and multiplication outputs have trivial heralds.Source: §3 · pp. 7–8, §3.2 · p. 11

3.1 BPQM unitaries

  • Check-node unitaries are independent of input eigen lists, bit-node unitaries depend on conditional eigen lists, and multiplication acts as a herald-free Fourier-basis permutation.For nonzero multiplication factors, the eigen-list permutation leaves fidelity unchanged.Source: §3 · p. 10, §3.1 · p. 11

3.2 Heralded Mixtures of Symmetric PSCs

  • BPQM messages on trees remain finite heralded mixtures of symmetric q-ary pure-state channels, and the PGM on the selected symbol’s root output is optimal.This closure holds when leaf messages belong to the class and node updates are composed from check-, bit-, and multiplication-node operations.Source: §3.2 · pp. 13–14

3.3 Operational BPQM on a tree factor graph

  • Operationally, BPQM applies node unitaries from the leaves toward the target, measures the final qudit optimally, and retains herald and other output registers for the reverse circuit.Operations on disjoint tree components can be applied in parallel, and decoding another symbol uses the adjoints in reverse order.Source: §3.3 · pp. 14–15
  • The final PGM estimates the root symbol from the retained qudit; preceding adjoint operations restore the register layout but do not undo measurement disturbance.The physical channel output is combined with the incoming message before the PGM is applied.Source: §3.3 · pp. 15–16

3.4 Density evolution on a regular tree

  • Density evolution tracks message distributions through independent computation-tree branches, with node updates determining the next iteration and asymptotic symbol-error probability.It identifies the BPQM success region in the space of channels.Source: §3.4 · p. 16
  • With random nonzero edge coefficients, coefficient trajectories are uniform over their support because relative labels are uniform and descendant branches are independent.The trajectory records normalized relative edge coefficients and the labels of their descendant subtrees.Source: §3.4 · p. 17
  • Each trajectory defines an effective channel recursively by combining the incoming branch channels subject to the normalized parity-check equation.The tensor product over disjoint descendant subtrees is implemented through binary check-node and multiplication operations.Source: §3.4 · p. 17
  • The fidelity bounds make the two convergence conditions defining the regular-tree BPQM success region equivalent, without requiring a scalar ordering of q-ary pure-state channels.The region depends on the regular ensemble.Source: §3.4 · p. 18

4 BPQM Decoding of Regular LDPC Codes

The section explains why ordinary computation-tree decoding does not directly extend to cyclic LDPC graphs and presents a two-stage decoder that uses tree neighborhoods and erasure recovery. Its local BPQM measurement errors are independent of the transmitted codeword.

4 BPQM Decoding of Regular LDPC Codes

  • The section extends tree-level BPQM to finite regular LDPC codes by decoding on cycle-free neighborhoods and recovering the remaining coordinates from parity constraints.The Tanner graph may be a multigraph, with parallel edges counted in node degrees.Source: §4 · p. 18, §4.1 · p. 18

4.1 Regular LDPC codes

  • The regular ensemble is formed by uniformly matching variable- and check-node sockets and independently assigning each matched edge a uniform nonzero q-ary coefficient.Positive design rate requires dv < dc.Source: §4.1 · pp. 18–19

4.2 Cycles and approximate cloning

  • Cyclic Tanner graphs do not decompose into a single tree circuit, and a direct quantum computation-tree construction would reuse nonorthogonal channel outputs, which the no-cloning theorem precludes.Approximate cloning and cycle-merging alternatives alter channels or increase message dimensions, so they do not yield the exact tree-channel recursion.Source: §4.1 · p. 19, §4.2 · p. 19

4.3 BPQM with erasure recovery

  • The two-stage decoder applies BPQM to cycle-free depth-ℓ neighborhoods, treats other coordinates as erasures, and recovers them from parity checks.When the BPQM estimates are correct and the erasure system has a unique solution, Gaussian elimination recovers the transmitted codeword.Source: §4.3 · pp. 19–20

4.4 Codeword Independence of local BPQM measurements

  • The sequential local BPQM decoder has the same block-error probability for every transmitted codeword, by covariance of the channel and BPQM node operations.The covariance property applies to the symbol-error probabilities and hence the block-error probability.Source: §4.4 · pp. 20–21

5 Double-Exponential Decay of the Symbol-Error Probability on a Tree

The section derives fidelity bounds for BPQM on regular computation trees and uses them to establish double-exponential symbol-error decay. The result holds throughout the BPQM success region for regular degrees with dv ≥ 3.

5 Double-Exponential Decay of the Symbol-Error Probability on a Tree

  • For dv ≥ 3, the average symbol-error probability on a regular computation tree decays doubly exponentially throughout the BPQM success region.The theorem supplies constants A, β > 0 and a starting iteration after which the bound applies.Source: §5 · p. 21, §5.1 · p. 23

5.1 Fidelity Bounds

  • Fidelity bounds for heralded messages and arbitrary node degrees yield a scalar recursion that proves the root symbol-error decay.The scalar bound is useful because the number of conditional eigen lists grows exponentially with depth.Source: §5.1 · p. 21, §5 · p. 21
  • Uniform bounds over nonzero edge factors control bit-node and check-node channel combinations, allowing the incoming coefficient trajectories to be averaged in the recursion.The exact combined fidelity may depend on the factors, while the stated upper bound is uniform over them.Source: §5.1 · p. 23

6 Vanishing Block-Error Probability in the BPQM Success Region

For regular random q-ary LDPC ensembles with dv ≥ 3, the decoder achieves vanishing ensemble-average block-error probability in the BPQM success region. It combines depth-ℓ BPQM on tree neighborhoods with erasure recovery, choosing ℓ to control both decoding errors and the omitted set.

6.1 Erasure Recovery

  • An erased coordinate set B is uniquely recoverable when its parity-check submatrix has full column rank; the minimum-distance criterion supplies this condition when the erasure set is sufficiently small.If the known coordinates are decoded correctly, the erased values can then be recovered from the parity checks.Source: §6.1 · pp. 25–26

6.2 Counting Tree Neighbourhoods

  • At the chosen depth, the fraction of coordinates with cyclic neighborhoods tends to zero in probability, while the regular ensemble has a linear minimum-distance estimate for dv ≥ 3.The neighborhood-counting estimate applies when α2^ℓ = o(N).Source: §6.2 · pp. 26–27

6.3 Vanishing Block-Error Probability

  • With ℓ(N) = ⌊τ log log N⌋ for τ > 1/log(dv −1), the ensemble-average block-error probability vanishes for channels in RegBPQM(dv, dc).The proof combines double-exponential symbol-error decay, a noncommutative union bound, and minimum-distance erasure recovery.Source: §6.3 · p. 28
  • The block-error conclusion also holds in probability over sampled codes: the chance that a code's conditional block-error probability exceeds any fixed positive value tends to zero.This follows from the vanishing ensemble-average block-error bound.Source: §6.3 · p. 30

A Irregular LDPC Codes

The irregular-ensemble extension averages BPQM messages over random computation-tree degrees and establishes vanishing block-error probability under a linear-distance condition.

A Irregular LDPC Codes

  • For finite-support irregular degree distributions, the analysis averages BPQM messages over computation-tree degrees to obtain an irregular fidelity recursion and decay estimate.The ensemble uses edge-perspective degree distributions for local computation trees.Source: A Irregular LDPC Codes · pp. 30–31
  • The irregular-ensemble block-error argument uses neighborhood counting and erasure recovery under a linear-distance condition.The stated conclusion is vanishing block-error probability for the irregular ensemble.Source: A Irregular LDPC Codes · p. 30
  • In the local weak limit, edge-rooted computation trees have variable and check degrees distributed according to the edge-perspective distributions, while a root variable has distribution L.Independent uniform nonzero edge coefficients induce the multiplication channels after check-equation normalization.Source: A Irregular LDPC Codes · p. 31

A.1 Fidelity evolution on an irregular tree

The irregular-tree analysis averages BPQM fidelity over sampled degree trees and edge-coefficient trajectories. Within the ensemble’s BPQM success region, the average symbol-error probability decays doubly exponentially with depth.

A.1 Fidelity evolution on an irregular tree

  • The exact effective channel is determined by an edge-perspective degree tree and the normalized coefficient trajectories induced by sampled edge coefficients.The analysis averages over the degree tree and coefficient trajectories, distinguishing it from the regular-ensemble analysis.Source: §A.1 · p. 31
  • The irregular-tree fidelity recursion combines degree-averaged check-node and variable-node updates, with the success-region limits equivalent by Eq. (24).The proof applies the regular-tree induction with the minimum variable degree parameter replacing dv − 1.Source: §A.1 · pp. 31–32
  • Within the irregular ensemble’s BPQM success region, the average symbol-error probability decays doubly exponentially with tree depth.The bound averages over both degree trees and coefficient trajectories.Source: §A.1 · pp. 31–32

A.2 Vanishing Block-Error Probability

For finite-support irregular LDPC ensembles with linear minimum distance with high probability, the decoder has vanishing ensemble-average block-error probability when the channel lies in the ensemble’s BPQM success region. The proof combines tree-based BPQM estimates, neighborhood counting, and recovery of erased coordinates.

A.2 Vanishing Block-Error Probability

  • The proof combines irregular-tree BPQM error estimates with neighborhood counting and minimum-distance erasure recovery.The sequential-measurement argument bounds decoding errors on tree neighborhoods; the linear-distance assumption supports recovery of the remaining coordinates.Source: §A.2 · pp. 33–35
  • For finite-support degree distributions, the number of sockets exposed by a depth-ℓ neighborhood is bounded, enabling a comparison of its degree-tree distribution with the tree ensemble.The comparison applies when Mℓ = o(N).Source: §A.2 · p. 33
  • For finite-support irregular ensembles with dη ≥3 and linear minimum distance with high probability, the decoder’s ensemble-average block-error probability tends to zero in the BPQM success region.The theorem chooses depth ℓ(N) = ⌊τ log log N⌋, with τ > 1/log(dη −1).Source: §A.2 · p. 34

B Numerical Visualization of the BPQM Success Region

For the (3, 12) regular ensemble and symmetric ternary pure-state channels, the paper numerically estimates a BPQM success region using a finite-iteration fidelity criterion. This criterion certifies convergence but does not rigorously characterize the full region.

B Numerical Visualization of the BPQM Success Region

C Minimum-Distance Criterion for Erasure Recovery

Minimum distance ensures the erased coordinates can be recovered uniquely from the parity constraints when the unerased coordinates are correct. Gaussian elimination then recovers the transmitted restriction on the erased coordinates.

C Minimum-Distance Criterion for Erasure Recovery

  • If HB lacked full column rank, a nonzero vector in its null space would produce a nonzero codeword supported on the erased coordinates, contradicting minimum distance.Therefore HB has full column rank.Source: C Minimum-Distance Criterion for… · p. 37
  • The transmitted restriction to the erased coordinates satisfies the recovery system because the transmitted word obeys Hc = 0.The system’s right-hand side is determined by the unerased-coordinate restriction.Source: C Minimum-Distance Criterion for… · p. 37
  • If the unerased-coordinate estimates are correct, the parity constraints yield a system whose unique solution is the transmitted erased-coordinate restriction.Full column rank of HB ensures uniqueness, and Gaussian elimination recovers the solution.Source: C Minimum-Distance Criterion for… · p. 37

AI Statement

The authors used ChatGPT and Codex for manuscript presentation and numerical-result scripts, while conceiving and developing the main ideas and results and independently verifying the work.

AI Statement

  • The authors conceived and developed the main ideas and results, independently verified the mathematical arguments, numerical results, and interpretations, and take responsibility for the manuscript.They identify doubly exponential decay of PGM error under BPQM and vanishing block-error probability for the BPQM-plus-Gaussian-elimination decoder among those results.Source: AI Statement · p. 37
  • ChatGPT, using GPT-5.6 Sol and earlier GPT model versions, was used to improve manuscript clarity and presentation.Source: AI Statement · p. 37
  • Codex was used to refine scripts that generated the numerical results.Source: AI Statement · p. 37

Related papers

Loading 2609.05857v1…