最小权重完美匹配译码

最小权重完美匹配译码（minimum-weight perfect matching，MWPM）是表面码族的事实标准译码算法。Dennis、Kitaev、Landahl 与 Preskill 在 2002 年证明：把综合征缺陷当节点、把单比特错误当边，最概然错误链近似等于图上的最小权重完美匹配，而这个问题有 Edmonds 1965 年给出的多项式算法。2023 年的 sparse blossom 算法把实测速度推到单核每轮微秒级，使匹配译码第一次跟得上超导综合征提取节拍；其固有代价是忽略 X/Z 错误相关与码的简并性，去极化噪声下与最优译码可差两个数量级。

匹配图构造：为什么边权是 $\log \frac{1-p}{p}$

以相位错误（$Z$，触发 $X$ 型检查）为例。每个数据比特恰与两个 $X$ 稳定子反对易，故单个 $Z$ 错误恰翻转两个缺陷——错误链与缺陷配对一一对应。构造匹配图：节点为翻转的检查（缺陷），边为可能的单比特错误（含边界节点，粗糙边界互连权重为 0），边权取

$$w_i=\log \frac{1-p_i}{p_i},$$

其中 $p_i$ 是第 $i$ 个错误机制的概率。一行推导：i.i.d. 噪声下错误集 $E$ 的概率为

$$P(E)\propto \prod _i(\frac{p_i}{1-p_i}{)}^{e_i}⟹\log P(E)=\text{const}-\sum _i{w}_i{e}_i,$$

即更概然的错误链总匹配权重更小——最小权重匹配≈最大似然（在”每个余等价类取最小代表元”的非简并近似下）Higgott 2021 (arXiv)。测量也出错时，把轮数当时间维，得到 3D 时空图上的匹配（见surface-code）；$X/Z$ 在原格与对偶格上分别独立匹配Dennis et al. 2002 (J. Math. Phys.)。一般化表述：任何列重为 2 的校验矩阵加非负边权，MWPM 译码就是求 $H\mathbf{e}=\mathbf{s}$ 的最小权解。

Edmonds blossom：奇环收缩的直觉

一般图匹配比二部图难在奇环：沿奇环增广会破坏配对。Edmonds 的 blossom 算法把奇环收缩成一个”花”（blossom）超节点，使其对外表现为普通节点；同时给每个节点 $v$ 配对偶变量 $y_v$，只有”紧”（tight）边 $y_u+y_v=w_{u,v}$ 才允许进入交替树，增广路径的搜索变成对偶变量的同步增长Dennis et al. 2002 (J. Math. Phys.)（算法原始文献为 Edmonds 1965，Canad. J. Math. 17, 449）。加权情形最坏 $O(N^3)$（$N$ 为缺陷数）。

图:sparse blossom 解一次匹配的"自画像"——探测图上交替树区域生长的完整事件流:区域从检测事件出发生长、相遇成边、奇环收成 blossom(浅色团块)、最终塌缩成匹配边;每个检测事件恰好落入一个区域(来源:QE260)

探测图与 local matching

朴素的”完全探测图”做法先对每对缺陷跑 Dijkstra 最短路作为边权、再在完全图上跑 blossom，对距离 $d=L$ 的表面码是 $O(L^6\log L)$。Higgott 的 PyMatching 论文提出 local matching：探测图只连每个缺陷最近 $m$ 个邻居，复杂度降到 $O(L^{4}m\log L)$；$m\gtrsim 16$ 时阈值与精确匹配一致（0.10321(1)，现象学 0.0292），$m=6\sim 8$ 时甚至略高于精确匹配——局部性限制意外利用了简并性，把同类的多条链当作同一解Higgott 2021 (arXiv)。PyMatching 的适用码族清单覆盖 toric/表面码、子系统表面码、2D 双曲、3D toric（$X$）、XZZX、compass/heavy-hex、色码（作子程序）、fracton 与含噪 repetition 码。

sparse blossom：单核微秒级

经典 blossom 在完全图上最坏 $O(N^3\log N)$、经验约 $O(N^2)$，大数据集上不可用。Higgott 与 Gidney 的 sparse blossom 直接在探测图（detector graph）上解匹配，不做全源 Dijkstra、不显式建完全图：把交替树生长改写成区域生长（region growing）事件队列，flooder/shrinker/blossom 三种结构只触碰与本次匹配相关的边，每轮探测事件数正比于缺陷数；块分解（block decomposition）支持增量与流水化解码，使每图解码时间与轮数解耦Higgott & Gidney 2023 (arXiv)。关键数字：0.1% 电路级去极化噪声下，$d=17$ 表面码 $X+Z$ 两基单核译码低于 1 µs/轮，约每核每秒一百万个错误——分钟级完成过去要 HPC 集群数小时的模拟，这也是 PyMatching 2 的内核。同期平行工作 fusion blossom（Rust 的 mwpm 库，被 Google 实验与 sinter 基准采用）思想同源Wu & Zhong 2023 (arXiv)。

图:匹配译码与 Union-Find 译码的几何对比——两者都是"从缺陷出发的区域生长",区别在 blossom 区域记录对偶变量并支持奇环收缩与交替树增广,而 Union-Find 簇只做并查集合并(来源:QE260)

局限与补救

MWPM 的精度天花板来自两处近似：(i) 忽略 $X/Z$ 相关——$Y$ 错误同时出现在两套匹配图里，独立匹配无法利用这一相关。Bravyi–Suchara–Vargo 的基准显示去极化噪声下 MPS 译码比匹配译码好两个数量级以上Bravyi, Suchara & Vargo 2014 (PRA)；(ii) 忽略简并性——类概率不等价于最小代表元概率。补救谱系：correlated MWPM 在两图间共享 $Y$ 边信息（AlphaQubit 论文中的 MWPM-Corr 基线即此类Bausch et al. 2024 (Nature)）；K-最小权重匹配（K-MWM）采样 $K$ 个低权重匹配近似类概率，架起匹配与 ML 之间的桥Lin 2025 (PRA)。速度侧的极限仍在推进：2026 年已出现 sparse blossom 的亚常数摊销时间版本Mikami & Yamasaki 2026 (arXiv)。

延伸阅读

• decoding-overview
• union-find-decoding
• tensor-network-decoding
• real-time-decoding
• surface-code