BP+OSD 译码

BP+OSD 是量子 LDPC 码的事实标准译码器：置信传播（belief propagation，BP）在 Tanner 图上做快速消息传递，量子简并性却让它陷入特有的失败模式；Panteleev 与 Kalachev 在 2019 年提出用有序统计译码（ordered statistics decoding，OSD）兜底——用 BP 的软信息选可靠基底、一次高斯消去保证输出恒满足综合征。Roffe 等 2020 年将其系统化并开源为 ldpc 包。它随 qLDPC 复兴成为标配：BB 码 $[[144,12,12]]$ 的原始基准即用 BP+OSD；2025–2026 年沿并行化、列表化与调度学习多个方向继续演进。

消息传递与调度

BP 在 Tanner 图上交替更新变量节点与校验节点的对数似然比（LLR）消息（即经典 LDPC 码的和积算法，见belief-propagation）。CSS 码把量子问题拆成两个经典问题：$s_x=H_{Z}x$ 与 $s_z=H_{X}z$；非 CSS 码用整体二进制化 $H=(H_X|H_Z)$，其相容性由 $H_X{H}_Z^{\mathsf{T}}+H_Z{H}_X^{\mathsf{T}}=0$ 保证Panteleev & Kalachev 2019 (arXiv)。调度有两族：flooding（全部节点并行更新，硬件友好）与串行 schedule（逐节点更新，收敛行为不同——VibeLSD 正是利用了这一点）。

split-belief：BP 在量子码上的失败模式

量子简并性给 BP 制造了经典码上不存在的失败模式，可一行推导。设 syndrome $\mathbf{s}$ 有两个同权重、同后验的最概然错误 ${\mathbf{x}}_1,{\mathbf{x}}_2$（它们必然同类：${\mathbf{x}}_1+{\mathbf{x}}_2\in \ker H$）。BP 的逐位边缘分布对两类不分轩轾——两个解都拿到高后验，于是输出它们的”平均”：

$${\mathbf{x}}_{BP}={\mathbf{x}}_1+{\mathbf{x}}_2⟹H{\mathbf{x}}_{BP}=H{\mathbf{x}}_1+H{\mathbf{x}}_2=\mathbf{s}+\mathbf{s}=0\ne \mathbf{s}.$$

split belief 导致 BP 不收敛：输出的逐位硬判决根本不满足综合征Roffe et al. 2020 (PRR)。量子 Tanner 图的 4-环（同一比特同时出现在 $X$ 与 $Z$ 校验的乘积冗余里）让消息回路雪上加霜。历史上的一揽子修补——随机扰动、增强反馈、矩阵增广——都在治标；Panteleev–Kalachev 的判断是：与其修补 BP，不如承认它失败后再启动一个保证合法的后处理器。

OSD：高斯消去兜底

OSD-0 的三步Roffe et al. 2020 (PRR)：

1. 按 BP 软判决的可靠度（$|\mathrm{LLR}|$）对列排序，选出满列秩的可靠信息集 $[S]$（$H_{[S]}$ 可逆）；
2. 高斯消去求 $H_{[S]}^{-1}$；
3. 基位取 ${\mathbf{e}}_{[S]}=H_{[S]}^{-1}\mathbf{s}$，其余位 $[T]$ 置零——输出恒满足综合征，一定把系统拉回码空间。

代价是输出未必最概然。高阶 OSD 在 $[T]$ 中翻转低可靠位的组合再重解基位；Panteleev–Kalachev 版对最不可靠的 $w$ 位枚举 $2^w$ 个候选，选最小权重者Panteleev & Kalachev 2019 (arXiv)；Roffe 等的 combination sweep（CS） 改为贪心逐位翻转，$\lambda =60$ 的预算下优于全枚举Roffe et al. 2020 (PRR)。

qLDPC 基准数字

• Panteleev–Kalachev 用 BP+OSD 译 $[[1270,28]]$ 广义自行车/超积码，性能优于 $[[1201,1,25]]$ 表面码配近最优 MPS 译码——qLDPC 首次在码率与距离上双赢Panteleev & Kalachev 2019 (arXiv)；
• BP+OSD-CS 在 toric 码上阈值 $9.9\pm 0.2\%$，接近 MWPM 的 10.3%；半拓扑码大块长下阈值逼近 toricRoffe et al. 2020 (PRR)；
• IBM 的 BB 码原始论文以 BP+OSD 为默认译码器（含电路级噪声扩展），gross code 的 0.8% 阈值与 $p=10^{-3}$ 时 $2\times 10^{-7}$ 每周期逻辑错误率均在此配置下取得Bravyi et al. 2023 (Nature)；
• GB 码的综合征还受一个小 BCH 码保护，天然利于容错测量Panteleev & Kalachev 2019 (arXiv)。

2025–2026 年演进

BP 系在后 OSD 时代继续分化：全并行 BP 变体在 HPCA 2025 上报告可超越 BP+OSDWang et al. 2025 (HPCA)；beam search 译码器把 OSD 的候选搜索改为束搜索Ye et al. 2025 (arXiv)；面向相关错误的译码框架（Nature Communications）处理空间关联噪声Maan et al. 2025 (Nat. Commun.)；学习式 BP 调度用神经网络学消息传递顺序Moradi et al. 2026 (arXiv)；多基底 BP 列表译码在不同校验基底间并行采样Rabeti & Mahdavifar 2026 (arXiv)；Microsoft 的改进 BP 报告无需 OSD 后处理即可实时译码量子存储器Müller et al. 2025 (arXiv)。最引人注目的是 VibeLSD：用多达 64 个不同串行 schedule 的 BP 集成打破色码 Tanner 图的对称性（trapping set），再以局部统计译码（LSD，OSD 的并行替代，最坏 $O(n^3)$、实用平均亚线性）后处理保证满足综合征——颜色码第一次在 SI1000 噪声 $p=10^{-4}$ 下达到与表面码+PyMatching 相同的量子比特足迹Koutsioumpas et al. 2025 (arXiv)。

图:VibeLSD 译码下颜色码的量子比特足迹演进——串行调度 BP 集成+局部统计译码后处理,使色码(Bell-flagged 综合征提取)在相同逻辑错误率下与表面码+PyMatching 足迹几乎相同,显著优于此前最优(来源:QE266)

延伸阅读

• qldpc-overview
• bivariate-bicycle
• tanner-graphs
• belief-propagation
• neural-network-decoding