Quantum Message Passing for Factor Graphs over Finite Abelian Groups

1. Problem Statement

The paper addresses the challenge of decoding classical information transmitted over Classical-Quantum (CQ) channels using factor graphs. While classical belief propagation (BP) is highly effective for decoding sparse-graph codes (like LDPC, polar, and turbo codes) on classical channels, extending these methods to quantum channels is difficult.

• The Core Difficulty: Optimal decoding of CQ channels often requires collective measurements on long blocks of quantum states, which are computationally intractable to describe and implement.
• Existing Limitations: Previous approaches, such as Belief Propagation with Quantum Messages (BPQM), were largely restricted to binary alphabets or specific symmetric $q$-ary channels (cyclic groups like $\mathbb{Z}_q$) where the channel states possess circulant Gram matrices.
• The Gap: There was no unified framework for quantum message passing over arbitrary finite abelian groups (including non-cyclic groups like $\mathbb{Z}_2 \times \mathbb{Z}_2$) and for general local constraints defined by homomorphisms between these groups.

2. Methodology

The authors develop a rigorous framework based on Group-Covariant Pure-State Channels (PSCs). The methodology relies on the symmetry properties of the channel and the algebraic structure of the underlying group.

A. Character Basis Diagonalization

• Group-Covariant PSCs: The input alphabet is a finite abelian group $G$. The output states $\{|\psi_g\rangle\}_{g \in G}$ transform covariantly under a unitary representation of $G$.
• Gram Matrix Properties: The Gram matrix $\Gamma_W$ (containing pairwise overlaps $\langle \psi_g | \psi_{g'} \rangle$) of such a channel is $G$-circulant.
• Key Insight: For abelian groups, the character basis of the dual group $\hat{G}$ diagonalizes the Gram matrix. Consequently, the channel is fully characterized (up to isometric equivalence) by an eigen list $\lambda = \{\lambda_\chi\}_{\chi \in \hat{G}}$, where $\lambda_\chi$ are the eigenvalues corresponding to the characters of $\hat{G}$.

B. Heralded Mixtures

The authors introduce the concept of Heralded Mixtures of Group-Covariant PSCs.

• In many local operations, the output is not a single PSC but a mixture of several PSCs, distinguished by a classical "herald" register (a side information register).
• A message is defined as an ensemble $\{(p_x, W_x)\}$, where $p_x$ is a probability and $W_x$ is a PSC characterized by its eigen list.

C. Local Factor Analysis

The paper derives explicit update rules for five primitive factor types found in factor graphs. The central result is that these operations preserve the class of heralded mixtures of PSCs:

1. Check Factor (Parity): Combines two PSCs. The output is a heralded mixture indexed by the dual group $\hat{G}$. The update rule involves a convolution-like operation on the eigen lists of the inputs.
2. Equality Factor: Enforces that inputs are identical. The output remains a single PSC (a degenerate mixture). The update rule is a point-wise product (convolution in the dual domain) of the input eigen lists.
3. Homomorphism Factor: Maps inputs via a group homomorphism $\phi: G_1 \to G_2$. The output is a heralded mixture indexed by the cosets of the image of the dual map.
4. Marginalization Factor: Sums out a variable. This forces the discarded dual coordinate to become a classical herald, resulting in a mixture of PSCs on the remaining group.
5. Automorphism Factor: Relabels group elements. This acts as a permutation on the character basis, preserving the single PSC structure.

3. Key Contributions

1. Generalized Framework: Extends BPQM from cyclic groups ($\mathbb{Z}_q$) to arbitrary finite abelian groups. This allows for decoding codes over non-cyclic alphabets and more complex constraints.
2. Closure Property: Proves that the class of heralded mixtures of group-covariant PSCs is closed under all local factor operations. This establishes a closed quantum message-passing calculus for tree-structured factor graphs.
3. Explicit Update Rules: Derives exact mathematical formulas for updating the eigen lists and herald registers for all primitive factors.
4. Unified Decoding Architecture: Demonstrates that standard code families (Polar, LDPC, Convolutional, Turbo) can be decomposed into these primitive factors, allowing them to be decoded using the same unified quantum message-passing rules.
5. Density Evolution (DE): Adapts the density evolution technique to track the evolution of eigen lists and herald distributions, enabling the analysis of asymptotic decoding thresholds.

4. Results

• Theoretical Validation: Theorem 22 proves that exact quantum message passing on any tree factor graph constructed from these primitives yields a message that is a finite heralded mixture of PSCs.
• Code Applications:
  • Polar Codes: The polar kernel decomposition (automorphism, check, equality) fits naturally into the framework.
  • LDPC/Group Codes: Tanner graphs over abelian groups are shown to be assemblies of equality and homomorphism factors.
  • Convolutional/Turbo Codes: The framework provides a finite-state-machine recursion for trellis decoding, generalizing the BCJR algorithm to the quantum domain.
• Numerical Simulations:
  • The authors implemented Density Evolution for Turbo codes over $\mathbb{Z}_3$.
  • Results show the DE threshold (the point where decoding succeeds with high probability) approaches the Holevo capacity (the theoretical limit).
  • For a rate-1/3 Turbo code, the DE threshold was found to be $\lambda_{DE} \approx 2.641$, while the Holevo limit was $\lambda_H \approx 2.728$, demonstrating the efficacy of the approach.
  • Heatmaps of success probability over the eigen list simplex visualize the decoding performance regions.

5. Significance

• Bridging Theory and Practice: This work provides the first rigorous, constructive framework for quantum decoding of codes over general abelian groups, moving beyond the binary and cyclic constraints of previous literature.
• Algorithmic Efficiency: By reducing the complex quantum state evolution to the manipulation of eigen lists (vectors of size $|G|$) and classical heralds, the framework offers a computationally tractable method for quantum decoding, avoiding the exponential complexity of full state vector simulation.
• Foundation for Quantum Error Correction: The ability to handle non-cyclic groups and general homomorphisms is crucial for future quantum error correction schemes that may utilize higher-dimensional or non-standard algebraic structures.
• Unification: It unifies the decoding of diverse code families (Polar, LDPC, Turbo) under a single "Quantum Belief Propagation" paradigm, suggesting that the structural advantages of classical message passing can be fully realized in the quantum domain through symmetry-adapted representations.

In summary, this paper establishes that symmetry (specifically group covariance) is the key to tractable quantum decoding. By leveraging the character basis of finite abelian groups, the authors transform the intractable problem of quantum state discrimination into a manageable algebraic problem of updating eigen lists, enabling the design of optimal decoders for a wide class of quantum communication systems.