css-factor-graph-decoding

---
name: css-factor-graph-decoding
description: "CSS quantum error correction syndrome decoding via factor-graph formulation and belief propagation. Use when: implementing CSS code decoders, comparing joint BP vs four-state BP for syndrome decoding, formulating QEC decoding as factor graph inference, designing belief propagation decoders for stabilizer codes. Keywords: CSS code, syndrome decoding, factor graph, belief propagation, QEC decoder, Tanner graph, stabilizer code."
---

# CSS Factor-Graph Syndrome Decoding

> Factor-graph formulation of CSS syndrome decoding unifying joint BP and four-state BP approaches, showing their equivalence through state relabeling.

## Metadata
- **Source**: arXiv:2605.05132
- **Author**: Kenta Kasai
- **Published**: 2026-05-06

## Core Methodology

### Key Insight
CSS codes have two independent check matrices (X and Z stabilizers) imposing binary parity-check constraints on Pauli error components. The posterior probability factors as a binary factor graph with **two Tanner graphs coupled by local joint prior** at each qubit.

### Technical Framework

**Factor Graph Structure:**
1. Two Tanner graphs: one for X-checks, one for Z-checks
2. Coupled via local joint prior P(e_X, e_Z) at each qubit node
3. Retains channel correlation between X and Z error components

**Two Equivalent Formulations:**

1. **Joint BP**: Run sum-product on binary factor graph with coupled Tanner graphs
   - Each qubit has two binary variables (e_X, e_Z)
   - Messages flow along both Tanner graphs
   - Local prior couples the two variables

2. **Four-State BP**: Single factor graph with 4-state Pauli labels {I, X, Y, Z}
   - Each edge carries message over 4 states
   - Equivalent to joint BP after relabeling: (e_X, e_Z) → Pauli state

**Equivalence Proof:** After relabeling the four local Pauli states and marginalizing irrelevant binary components, both algorithms compute identical posterior weights, messages, and beliefs.

## Implementation Guide

### Joint BP Algorithm
```
For each iteration:
  1. X-graph: send messages along X-Tanner graph (binary BP)
  2. Z-graph: send messages along Z-Tanner graph (binary BP)
  3. Couple: at each qubit, update joint prior P(e_X, e_Z)
  4. Marginalize: compute posterior P(e_X, e_Z | syndrome)
  5. Decode: choose most likely Pauli error
```

### Four-State BP Algorithm
```
For each iteration:
  1. Initialize: messages m(σ) for σ ∈ {I, X, Y, Z}
  2. Check nodes: parity-check constraints on Pauli labels
  3. Variable nodes: combine incoming messages with channel prior
  4. Update: send new messages along edges
  5. Decode: argmax over 4 Pauli states
```

## Applications
- CSS code decoder design (surface codes, LDPC codes)
- Comparing decoder performance across formulations
- Understanding channel correlation exploitation in QEC
- Syndrome extraction optimization for fault-tolerant QC

## Pitfalls
- Joint BP requires careful handling of correlated noise models
- Four-state BP has higher per-message complexity (4 states vs 2)
- Both formulations assume independent error events between qubits
- Convergence not guaranteed for graphs with short cycles

## Related Skills
- css-syndrome-decoding
- quantum-error-correction-methods
- lottery-bp-decoding
- iceberg-error-detection