2. 匹配与完美匹配基础
在进入最小权重完美匹配译码的具体实现之前，必须先把图论层面的几个概念钉死：什么是匹配、什么是完美匹配、权重如何定义、最小权重完美匹配（Minimum Weight Perfect Matching，MWPM）在形式上要求什么，以及这些数学对象如何与量子纠错中的译码问题一一对应。本节的任务不是介绍算法，而是建立一套精确的语言，使得后续章节中出现的每一个术语都有明确的数学含义。
匹配与完美匹配
设有一个无向图 G = (V, E)，其中 V 是顶点集合，E 是边集合。图中的一个匹配（matching）M 是边集 E 的一个子集，满足条件：M 中任意两条边不共享端点。换句话说，每个顶点在匹配 M 中至多与一条边关联。这个约束的直观含义是“一对一配对”——一个顶点不能同时被两条匹配边占用。
如果顶点 v 与 M 中的某条边关联，称 v 被匹配（matched）；否则称 v 为未匹配顶点（unmatched vertex）或自由顶点（free vertex）。匹配的大小通常用匹配边的数量 |M| 来衡量。
在此基础上，完美匹配（perfect matching）要求更强：M 覆盖 V 中的每一个顶点，即不存在自由顶点。一个完美匹配必然包含恰好 |V|/2 条边，因此完美匹配存在的必要条件是 |V| 为偶数。注意，完美匹配是相对于整个顶点集而言的；如果只要求覆盖某个指定子集 S ⊆ V 中的所有顶点，则称为完美匹配于 S，此时 S 之外的顶点允许自由。这一区分在译码中极为关键，因为实际需要配对的往往只是“缺陷”顶点集合，而非全图顶点。
权重与最小权重完美匹配
仅有拓扑结构不足以描述译码问题中的“代价”。为此给每条边 e ∈ E 赋予一个实数权重 w(e)。匹配的权重定义为其中所有边的权重之和：
W(M) = Σe ∈ M w(e)
最小权重完美匹配问题即：在所有完美匹配中，寻找使 W(M) 最小的那个匹配 M*。形式化地，
M* = argminM 为完美匹配 W(M)
权重可以为正、为零，在部分场景下甚至允许为负（例如用负权重表示“优先选择”的边）。当权重全为正时，MWPM 倾向于选择边数少且单边代价低的配对方案；当图中存在多条等权路径时，最优解可能不唯一，但最小权重值是唯一的。实际实现中通常要求图是连通的且完美匹配存在，否则需要先做连通分量分解或引入虚拟顶点。
从图论到译码：映射关系
在基于匹配的量子纠错译码（如表面码的 MWPM 译码）中，图论对象与物理对象之间存在明确的对应关系。理解这层映射，是把抽象定义落到实现代码上的前提。
- 顶点对应检测事件（detection event）或缺陷（defect）：在综合征测量中，相邻两次测量结果发生翻转的位置被标记为缺陷顶点。稳定子测量得到的综合征比特串中，值为 1 的位置即为需要配对的顶点。
- 边对应两个缺陷之间的一条可能的错误链（error chain），即连接两个缺陷的物理错误路径。
- 权重对应这条错误链的“代价”，通常取为该路径上单比特错误概率的负对数似然，即 w(e) = −log p(e)，其中 p(e) 是该路径发生的概率。概率越低的路径权重越大，从而在最小化总权重时被自然回避。
- 完美匹配对应一种将所有缺陷两两配对的完整解释方案；最小权重完美匹配则对应最可能的错误模式（在独立错误假设下）。
需要强调的是，译码器输出的并不是“哪个物理比特出错”，而是“哪些缺陷被配对、沿哪条路径连接”。最终的纠错操作由这些配对路径的对称差决定。因此，MWPM 求解的是“缺陷配对”这一层问题，而非直接求解物理错误。
形式化定义与实现要点
把上述内容整理成可直接用于实现的形式。给定图 G = (V, E)、权重函数 w: E → ℝ，以及需要配对的顶点子集 S ⊆ V（|S| 为偶数），译码问题要求找到 S 上的一个完美匹配 M*，使得 Σe∈M* w(e) 最小。实现时需要注意以下几点：
- 顶点集的选择：只把综合征为 1 的位置放入 S，其余顶点不参与配对。若 |S| 为奇数，说明综合征不满足奇偶校验约束，通常意味着测量错误或边界处理有误，需要先排查。
- 边集的构造：理论上任意两缺陷之间都存在一条最短路径作为候选边，但实际实现中通常只保留距离较近的边以控制图规模。边权取该最短路径上各段权重之和。
- 权重的数值稳定性：w = −log p 在 p 接近 0 时会趋于无穷大，实现中需设置权重上限或对概率做截断，避免数值溢出。
- 边界条件：表面码存在边界，缺陷可以与边界配对。实现中通常引入虚拟边界顶点，把“与边界配对”转化为普通的顶点配对问题。
一个可手算的示例
考虑 4 个缺陷顶点 {A, B, C, D}，两两之间的候选边权重如下表（示例数据，用于说明计算过程，非实测结果）：
| 边 | AB | AC | AD | BC | BD | CD |
|---|---|---|---|---|---|---|
| 权重 | 1.0 | 2.5 | 3.0 | 1.8 | 2.2 | 1.4 |
4 个顶点的完美匹配共有 3 种：{AB, CD}、{AC, BD}、{AD, BC}。分别计算总权重：
- {AB, CD}：1.0 + 1.4 = 2.4
- {AC, BD}：2.5 + 2.2 = 4.7
- {AD, BC}：3.0 + 1.8 = 4.8
因此最小权重完美匹配为 {AB, CD}，总权重 2.4。这个例子虽然规模极小，但它完整展示了 MWPM 的判定逻辑：枚举所有完美匹配、计算总权重、取最小者。实际译码中缺陷数量可达数十到数百，枚举不可行，必须依赖 blossom 等多项式时间算法，但判定标准始终是这条“总权重最小”的准则。
掌握本节的定义后，后续讨论算法实现、图规模优化和边界处理时，才能准确判断每一步操作对应的是顶点集、边集还是权重函数的变换，而不至于在实现细节中迷失方向。