最小权重完美匹配（MWPM）简介

发布时间：2026/6/11 20:06:59

一、什么是 MWPM最小权重完美匹配Minimum-Weight Perfect Matching是图论中的经典优化问题给定一个带权无向图G(V,E)G(V,E)G(V,E)其中每条边eee有一个非负权重w(e)w(e)w(e)MWPM 的目标是找到一个完美匹配perfect matching使得匹配中所有边的权重之和最小。完美匹配的定义一组边的集合使得图中每个顶点恰好被覆盖一次即每个顶点只属于匹配中的一条边。二、MWPM 与量子纠错的关系在量子纠错码特别是表面码和环面码中MWPM 是解码的核心算法量子纠错概念对应的图论概念XXX检查算符测量点图的顶点node单量子比特ZZZ错误图的边edge综合征 哪些检查算符反对易缺陷点defects找到最可能的错误模式找最小权重完美匹配边的权重wilog⁡1−pipiw_i \log\frac{1-p_i}{p_i}wi​logpi​1−pi​​为什么权重这样设计因为权重与错误概率直接相关p(E)∏i(1−pi)∏i(pi1−pi)e[i](2)p(E) \prod_i (1-p_i) \prod_i \left(\frac{p_i}{1-p_i}\right)^{e[i]} \qquad (2)p(E)i∏​(1−pi​)i∏​(1−pi​pi​​)e[i](2)取对数后log⁡p(E)const−∑iwie[i]\log p(E) \text{const} - \sum_i w_i e[i]logp(E)const−∑i​wi​e[i]权重越小 → 概率越大。三、MWPM 解码的完整流程以一个距离-5 表面码为例步骤 1构建匹配图Matching Grapho ── o ── o ── o ── o (边界节点用空心 ○ 表示) | | | | | 每个 ○ 是一个 X-检查算符 o ── o ── o ── o ── o 每条 ─ 对应一个量子比特 | | | | | Z 错误发生在边上 o ── o ── o ── o ── o | | | | | o ── o ── o ── o ── o | | | | | o ── o ── o ── o ── o在边界处单个ZZZ错误只与一个检查算符反对易所以添加边界节点用空心方块 □ 表示边界节点之间用权重为 0 的边连接。步骤 2测量综合征 → 确定缺陷点假设以下错误发生了红色边o ══ o ── o ── o ══ o ═ 发生 Z 错误的边 | | | | | o ── o ── o ══ o ── o ★ 缺陷点蓝色星 | | | | | (两个相邻错误共享的算符不会缺陷) o ── o ══ o ── o ── o | | | | | o ── o ── o ── o ══ o ◻ | | | | | o ══ o ── o ── o ── o ◻ ◻───◻ (边界节点权重0)步骤 3构建综合征图Syndrome Graph缺陷点之间两两连边权重 原图中最短路径距离。缺陷点★A, ★B, ★C, ★D共 4 个★A ──3── ★B | \ / 2 \4 / 5 | \ / ★D ──6── ★C步骤 4运行开花算法找 MWPM尝试所有可能的完美匹配匹配方案边权重之和(A-B) (C-D)3 6 9← 最小(A-C) (B-D)4 ? 更大(A-D) (B-C)2 5 7← 实际最小算法会选择权重和最小的匹配。步骤 5输出校正对匹配中的每对缺陷取最短路径上的边作为校正操作。四、精确匹配 vs 局部匹配特性精确匹配Exact Matching局部匹配Local Matching综合征图完全图所有缺陷两两相连每个缺陷只连接mmm个最近邻居时间复杂度O(N3log⁡N)O(N^3 \log N)O(N3logN)瓶颈在开花O(N2mlog⁡N)O(N^2 m \log N)O(N2mlogN)表面码解码O(L6log⁡L)O(L^6 \log L)O(L6logL)O(L4mlog⁡L)O(L^4 m \log L)O(L4mlogL)解码性能最优最小权重保证几乎相同近似误差10−610^{-6}10−6适用场景小规模、需要精确结果大规模模拟推荐m20∼30m20\sim30m20∼30经验规律当m≥16m \geq 16m≥16时局部匹配与精确匹配的逻辑错误率没有统计学差异。五、用 PyMatching 实现的代码示例importnumpyasnpfrompymatchingimportMatching# 1. 定义检查矩阵5-qubit 重复码示例Hnp.array([[1,1,0,0,0],# 检查算符 S1: 测量 qubit 0 和 1[0,1,1,0,0],# S2: 测量 qubit 1 和 2[0,0,1,1,0],# S3: 测量 qubit 2 和 3[0,0,0,1,1],# S4: 测量 qubit 3 和 4])# 2. 创建 Matching 对象mMatching(H)# 3. 模拟错误qubit 2 和 3 发生 Z 错误noisenp.array([0,0,1,1,0])syndromeH noise%2# 结果: [0, 1, 0, 1]# 4. 解码使用局部匹配默认 m30correctionm.decode(syndrome)print(f校正结果:{correction})# 输出: [0, 0, 1, 1, 0]# 5. 验证解码是否成功recovery(correctionnoise)%2is_successall(H recovery%20)print(f解码成功:{is_success})# True六、直观理解MWPM 解码的核心思想可以概括为“把 syndrome 中的缺陷点两两配对使得配对的总’代价’最小。每对缺陷之间的路径就是需要纠正的错误位置。”就像快递配送问题你有NNN个包裹要送缺陷点要把它们两两配对送到同一个目的地使得总行驶距离最短。MWPM 就是找到这个最优配对方案。