PyMatching：一个使用最小权重完美匹配解码量子码的 Python 包

oscar.higgott.18@ucl.ac.uk

---

摘要

本文介绍 PyMatching，一个用于使用最小权重完美匹配（MWPM）算法解码量子纠错码的快速开源 Python 包。PyMatching 包含标准 MWPM 解码器以及一个变体，我们称之为局部匹配（local matching），它将每个综合征缺陷限制在局部邻域内与另一个缺陷匹配。局部匹配的解码性能在实践中与标准 MWPM 解码器几乎相同，同时将计算复杂度大约降低为二次方。我们对 PyMatching 的性能进行了基准测试，表明对于量子纠错模拟中通常考虑的规模，局部匹配比使用 NetworkX 或 Blossom V 实现的全 MWPM 算法快几个数量级。PyMatching 及其依赖项均为开源，可用于解码任何综合征缺陷成对出现的量子码，使用简单的 Python 接口。PyMatching 支持加权边、钩状错误（hook errors）、边界和测量错误，实现了容错量子计算中的快速解码和模拟。

---

1 引言

量子纠错码对于保护大规模量子计算机免受噪声影响是必要的。使用任何量子纠错码所需的一个重要软件组件是解码器（decoder），它接收一组检查算符测量结果（称为综合征 syndrome）作为输入，并尝试找到一个校正算符来消除可能发生的任何错误。

解决解码问题的一种方法是尝试最小权重解码（minimum-weight decoding），即找到与综合征一致的最小错误。对于一般的量子码，最小权重解码问题没有已知的解决方案，因为该问题已知是 NP-完全的 [1, 2, 3, 4]。然而，对于一大类量子码，最小权重解码问题（对于 $X$ 或 $Z$ 错误）可以借助 Edmonds 的开花算法（blossom algorithm）[5] 高效求解，该算法用于在图中找到最小权重完美匹配（minimum-weight perfect matching, MWPM）。可以使用 MWPM 解码的量子纠错码包括环面码和表面码 [6]、子系统表面码 [7]、二维双曲码 [8] 和子系统双曲码 [9]、三维环面码和表面码（对于 $X$ 错误）[10]、XZZX 表面码 [10] 以及一些罗盘码（compass codes）[11]，包括重型六边形码（heavy hexagon code）[12]。MWPM 还可以用作三维环面码 [13] 和规范色码（gauge color code）[14] 单次解码的子程序，以及用于解码色码 [15]、分形拓扑码（fracton topological codes）[16]、斐波那契码（Fibonacci code）[17] 和具有噪声综合征测量的重复码。

MWPM 的快速实现通常对于量子纠错模拟至关重要，因为准确估计逻辑错误率可能需要使用大量蒙特卡罗试验。开花算法的高效实现由 Blossom V [18] 和 Lemon [19] C++ 库提供。然而，开花算法只是 MWPM 解码器中的一个子程序，因为还需要路径查找算法。MWPM 解码器的实现包括 Autotune [20] 和 qecsim [21]，两者都针对环面码和表面码的特定变体量身定制。

本文介绍 PyMatching，一个用于使用 MWPM 解码器解码量子纠错码的快速、开源 Python 包。PyMatching 包含完整的 MWPM 解码器以及 MWPM 的一个变体，称为局部匹配（local matching），与精确匹配相比，它具有显著改善的计算复杂度，同时在实践中保持大致相同的解码性能。虽然核心算法是用 C++ 实现的，但功能通过简单的 Python 接口提供。此外，PyMatching 可用于解码任何可以应用 MWPM 解码器的量子码，而不是针对特定的量子码或噪声模型量身定制。PyMatching 的源代码可以在 Github 上找到¹，comprehensive documentation 也可获取²。PyMatching 在开源 Apache 2.0 软件许可证下分发。

¹ https://github.com/oscarhiggott/PyMatching
² https://pymatching.readthedocs.io/

---

2 背景

Pauli 群 ${\mathcal{P}}_n$ 的元素是 Pauli 算符 $X,Y,Z$ 的 $n$ 重张量积。一个**稳定子码（stabiliser code）**由稳定子群 $\mathcal{S}$ 定义，$\mathcal{S}$ 是 ${\mathcal{P}}_n$ 的一个不包含 $-I$ 的阿贝尔子群。稳定子码的码空间 $\mathcal{T}(\mathcal{S})$ 是 $\mathcal{S}$ 元素的联合 $+1$-本征空间：

T(S):={∣ψ⟩ s.t. S∣ψ⟩=∣ψ⟩∀S∈S}(1)\mathcal{T}(\mathcal{S}) := \left\{ |\psi\rangle \ \text{s.t.}\ S|\psi\rangle = |\psi\rangle \quad \forall S \in \mathcal{S} \right\} \qquad (1)T(S):={∣ψ⟩ s.t. S∣ψ⟩=∣ψ⟩∀S∈S}(1)

当使用稳定子码进行纠错时，会测量一组生成元 $S_1,S_2,\dots ,S_r\in \mathcal{S}$，称为检查算符（check operators），以获得综合征。给定一个 Pauli 错误 $E\in {\mathcal{P}}_n$，其综合征 $\sigma (E)$ 是一个二元向量，其第 $i$ 个元素 $\sigma (E{)}_i=0$ 如果 $E{S}_i=S_{i}E$，而 $\sigma (E{)}_i=1$ 如果 $E{S}_i=-S_{i}E$。$\mathcal{S}$ 在 ${\mathcal{P}}_n$ 中的中心化子 $C(\mathcal{S})$ 是与 $\mathcal{S}$ 的每个元素对易的 Pauli 算符集合，因此不可检测的逻辑错误是 $C(\mathcal{S})\setminus \mathcal{S}$ 的一个元素。Pauli 算符 $P\in {\mathcal{P}}_n$ 的权重是其非平凡作用的量子比特数，稳定子码的最小距离是 $C(\mathcal{S})\setminus \mathcal{S}$ 中任何算符的最小权重。

一个 CSS 稳定子码的稳定子群允许一组生成元 $S_1,S_2,\dots ,S_r\in \mathcal{S}$，每个生成元满足 Si∈{I,X}⊗n∪{I,Z}⊗nS_i \in \{I, X\}^{\otimes n} \cup \{I, Z\}^{\otimes n}Si​∈{I,X}⊗n∪{I,Z}⊗n。

给定一个错误 $E\in {\mathcal{P}}_n$，解码器使用其综合征 $\sigma (E)$ 选择一个校正算符 $R\in {\mathcal{P}}_n$ 应用于被损坏的状态 $E|\phi ⟩$。如果 $RE\in \mathcal{S}$ 则解码器成功，否则失败。如果校正 $R$ 与综合征一致，则 $RE\in C(\mathcal{S})$，如果 $RE\in C(\mathcal{S})\setminus \mathcal{S}$ 则发生逻辑错误。因此，如果解码器返回陪集 [E]:={ES∣∀S∈S}[E] := \{ES \mid \forall S \in \mathcal{S}\}[E]:={ES∣∀S∈S} 的任何元素，则解码器成功。我们可以将所有与综合征一致的可能错误集合 {EM:M∈C(S)}\{EM : M \in C(\mathcal{S})\}{EM:M∈C(S)} 分割为形如 $[E\bar{P}]$ 的不相交陪集的并集，其中 $\bar{P}\in C(\mathcal{S})\setminus \mathcal{S}$。**最大似然解码器（maximum likelihood decoder）**然后找到最可能的陪集，给定一个为每个 Pauli 错误 $E\in {\mathcal{P}}_n$ 分配概率 $\pi (E)$ 的错误模型。虽然最优，但最大似然解码通常实现效率不高（且通常已知是 #P-完全的 [4]），尽管对于表面码可以使用 BSV 解码器 [22] 很好地近似。

最小权重解码器（minimum weight decoder）则找到与综合征一致的最小权重错误。虽然最小权重解码的性能不如最大似然解码，但最小权重完美匹配（MWPM）解码器可以有效地（对于 $Z$ 或 $X$ 错误）求解某些重要量子码族的最小权重解码问题。

---

3 最小权重完美匹配解码器

我们现在考虑解码 CSS 稳定子码的 Pauli $Z$ 错误 E∈{I,Z}⊗nE \in \{I, Z\}^{\otimes n}E∈{I,Z}⊗n 的问题。注意，我们可以使用相同的方法解码 Pauli $X$ 错误，并且 MWPM 也可以轻松适应解码某些非 CSS 码（如 XZZX 表面码 [10]）。我们用 $\mathbf{s}$ 表示错误 E∈{I,Z}⊗nE \in \{I, Z\}^{\otimes n}E∈{I,Z}⊗n 发生后对应于 $X$ 检查算符的综合征向量。$s[i]=1$ 如果 $X$ 检查算符 $S_i$ 与 $E$ 反对易，$s[i]=0$ 否则。我们将与 $E$ 反对易的 $X$ 检查算符集合称为缺陷（defects）。我们还定义一个二元噪声向量 $\mathbf{e}$，其中 $e[i]=1$ 如果错误 E∈{I,Z}E \in \{I, Z\}E∈{I,Z} 对量子比特 $i$ 非平凡作用，$e[i]=0$ 否则。

当每个单量子比特 $Z$ 算符与两个 $X$ 稳定子反对易时，可以使用最小权重完美匹配（MWPM）解码器。当满足此性质时，我们可以定义一个匹配图（matching graph） $G$，其中 $G$ 的每个节点与一个 $X$ 检查算符相关联，每条边与一个单量子比特 $Z$ 错误相关联。每个错误 E∈{I,Z}⊗nE \in \{I, Z\}^{\otimes n}E∈{I,Z}⊗n 然后对应于一个称为 1-链的边子集，每个综合征对应于与缺陷相关联的节点子集。$Z$ 错误的最小权重解码然后对应于找到以缺陷节点为边界的最小 1-链。如果每个量子比特 $i$ 遭受 $Z$ 错误的概率 $p_i$ 不同，那么我们可以为每条边分配权重 $w_i=\log ((1-p_i)/p_i)$ [6]。我们看到错误 $E$ 发生的概率

$$p(E)=\prod _i(1-p_i{)}^{1-e[i]}{p}_i^{e[i]}=\prod _i(1-p_i)\prod _i{\left(\frac{p_i}{1-p_i}\right)}^{e[i]}(2)$$

满足 $\log (p(E))={\sum }_i\log (1-p_i)-{\sum }_i{w}_{i}e[i]$，因此更可能的错误具有更低的权重。

作为示例，距离 10 的平面表面码的 $X$（站点）检查算符的匹配图如图 1a 所示。（图片说明：图 1 展示了距离 10 表面码的最小权重完美匹配解码器的各个阶段：(a) 匹配图，(b) 错误示例，© 综合征图，(d) 最小权重完美匹配，(e) 校正结果。）在边界处，单量子比特 $Z$ 错误仅与一个检查算符反对易，我们还添加边界节点（用空心方块表示），所有边界节点通过权重为零的边相互连接。图 1b 显示了一个错误示例（红色边）和相应的缺陷（蓝色星）。MWPM 解码器在测量检查算符后的下一步是构建一个综合征图（syndrome graph） $V$，对于 $\mathbf{s}$ 中的每个缺陷都有一个节点。在 MWPM 解码器的完整实现中，$V$ 包含每对节点之间的边，形成一个完全图。$V$ 中每条边 $(u,v)$ 的权重由原始匹配图 $G$ 中相应检查算符之间的最短路径长度给出。图 1c 显示了表面码综合征图的示例。Boost 图库实现的 Dijkstra 算法用于查找源节点与所有其他节点之间最短路径的复杂度为 $O(N\log (N)+M)$，其中图有 $N$ 个顶点和 $M$ 条边 [23]。为了构建综合征图，我们必须为每个缺陷求解 $G$ 中的单源最短路径问题。

下一步是求解 $V$ 中的最小权重完美匹配问题。图的匹配（matching）是一组边，使得匹配中没有两条边共享公共顶点，完美匹配（perfect matching）是包含图中所有顶点的匹配。图的最小权重完美匹配是具有最小权重的完美匹配（匹配的权重是其边权重之和）。此问题可以使用开花算法（blossom algorithm）[5] 求解，高效实现由 Lemon [19] 和 Blossom V [18] C++ 图库提供。图 1d 显示了图 1c 中综合征图的最小权重完美匹配。对于匹配中的每条边 $(u,v)$，$G$ 中从 $u$ 到 $v$ 的最小权重路径然后包含在解码器输出的校正中（见图 1e）。我们将 MWPM 解码器的这个标准版本称为精确匹配（exact matching），解码器输出的解保证是最小权重解。当综合征测量本身有噪声时，测量会重复 $O(L)$ 次，使用差分综合征（连续测量的奇偶性）在 3D 匹配图上进行解码 [6]。

对于综合征 $\mathbf{s}$ 和具有 $N$ 个顶点和 $M$ 条边的匹配图 $G$，使用 Dijkstra 算法构建综合征图的复杂度为 $O(s(N\log (N)+M))$。然后在完全综合征图上运行开花算法的复杂度为 $O(s^3\log (s))$。由于我们可以取 $s=O(N)$（其中 $N=|G|$）和 $M=\beta N$（对于某个常数 $\beta$，假设我们的码是 LDPC），则 Dijkstra 步骤的运行时间为 $O(N^2\log (N))$，开花步骤的复杂度为 $O(N^3\log (N))$。对于距离 $L$ 的表面码的 2D 匹配图，解码器的运行时间由开花算法主导，总体运行时间为 $O(L^6\log (L))$。

注意，MWPM 解码器不仅限于解码稳定子码中的 Pauli 错误。给定一个 $r\times n$ 二元奇偶校验矩阵 $\mathbf{H}$，其中每列的权重为二，以及综合征向量 $\mathbf{s}\in {\mathbb{F}}_2^r$，MWPM 将找到满足 $\mathbf{He}=\mathbf{s}$ 的最小权重噪声向量 $\mathbf{e}\in {\mathbb{F}}_2^n$，权重为 ${\sum }_i{w}_{i}e[i]$，其中 $\mathbf{w}\in {\mathbb{R}}^{+}$ 是与第 $i$ 位相关联的非负权重。

---

4 局部匹配

除了精确匹配之外，PyMatching 还包括我们称为**局部匹配（local matching）**的 MWPM 解码器变体。在局部匹配中，首先引入于参考文献 [9]，综合征图不再被选为缺陷的完全图，而是仅包含边的子集，从而降低算法的计算复杂度。局部匹配解码器有一个参数 $m$，决定综合征图的稀疏程度。我们用 $V_m$ 表示为局部匹配构造的参数为 $m$ 的综合征图。我们通过从 $G$ 中的每个缺陷向其 $m$ 个最近缺陷添加边来构造 $V_m$（这里 $G$ 中两个节点 $u$ 和 $v$ 之间的距离 $d(u,v)$ 由它们之间最短路径的长度给出）。$V_m$ 中每条边 $(u,v)$ 的权重同样由 $G$ 中的距离 $d(u,v)$ 给出。

为了构造 $V_m$，我们使用 Dijkstra 算法的变体，我们称之为局部 Dijkstra 算法（local Dijkstra algorithm），用于找到 $G$ 中缺陷 $i$ 的 $m$ 个最近缺陷的距离。局部 Dijkstra 算法在算法 1 中给出，也可以在参考文献 [9] 中找到。与 Dijkstra 算法的区别在于局部 Dijkstra 算法跟踪 $G$ 中已检查的缺陷，并在检查 $m$ 个缺陷后停止（当使用 $\text{ExtractMin}$ 从优先队列 $Q$ 中移除顶点时检查顶点，见算法 1）。我们还跟踪每次使用算法中更新过的距离 $\mathbf{d}$ 和前驱 $\mathbf{p}$ 数组的哪些元素，以便在下次使用解码器之前只需重置这些元素（而不是在 $O(|G|)$ 时间内重置每个数组）。假设 $m$ 不太小，我们发现对于典型用例，$V_m$ 以高概率是连通的（对于 $m>10$，我们凭经验发现 $V_m$ 在 2D 和 3D 匹配图中几乎保证连通）。然而，$V_m$ 仍然可能断开连接，特别是对于小的 $m$，如果其任何连通分量包含奇数个缺陷，则即使总体综合征的奇偶性是偶的，也无法找到匹配。为了防止这个罕见问题发生，我们在运行开花算法之前检查 $V_m$ 是否断开连接。如果 $V_m$ 断开连接，我们将 $m$ 增加 1 并重新计算综合征图，重复直到综合征图连通。图 2 显示了使用 $m=5$ 的局部匹配解码器构造的综合征图，使用与图 1c 中相同的综合征，其中显示了完整匹配使用的完全综合征图。（图片说明：图 2 展示了使用 $m=5$ 的局部匹配解码器的综合征图，对应图 1 中的综合征。）对于小的 $m$，局部匹配不能保证找到最小权重解，然而如第 5 节所示，它是精确匹配的非常好的近似，同时具有降低的计算复杂度。由于局部匹配中的综合征图有 $s=O(N)$ 个顶点和 $O(Nm)$ 条边，局部匹配解码器的开花步骤的复杂度为 $O(N^{2}m\log (N))$。局部 Dijkstra 步骤的运行时间取决于缺陷在 $G$ 中的分布。假设缺陷均匀分布，使得 $G$ 中只有 $O(mN/s)$ 个顶点被局部 Dijkstra 算法检查。如果我们进一步假设 $G$ 具有有界度（对于 LDPC 码确实如此）且 $N/s=O(1)$（假设某个固定错误率），则局部 Dijkstra 算法在此情况下的运行时间等价于在具有 $O(m)$ 个顶点和 $O(m)$ 条边的有界度图上运行标准 Dijkstra 算法，每个源顶点的运行时间为 $O(m\log (m))$，导致构建综合征图所需的总运行时间为 $O(Nm\log (m))$。对于用于解码距离 $L$ 表面码的 2D 匹配图，由开花算法主导的总运行时间为 $O(L^{4}m\log (L))$。

算法 1：局部 Dijkstra 算法

函数 LocalDijkstra(G, s, m, i):
    对于每个 u ∈ G, d[u] = ∞, p[u] = u;
    d[i] = 0;
    初始化优先队列 Q;
    Q.insert(i);
    初始化空的已发现缺陷列表 l;
    当 Q 非空且 length(l) < m 时执行:
        u = Q.ExtractMin();  // 检查顶点 u
        如果 s[u] = 1 则:
            l.Insert(u);
        对于 G 中 u 的每个邻接顶点 v 执行:
            如果 weight(u,v) + d[u] < d[v] 则:
                d[v] = weight(u,v) + d[u];
                p[v] = u;
                如果 d[v] 之前等于 ∞ 则:
                    Q.Insert(v);
                否则:
                    Q.DecreaseKey(v);

以前曾考虑过降低 MWPM 解码器计算复杂度的类似策略。参考文献 [24] 中提出的解码器最初仅在表面码匹配图的 3D 晶格中几何接近的顶点之间连接综合征图。虽然该方法对于平面表面码被证明是有效的，但它更难推广到双曲码 [8]，且缺陷之间的欧几里得距离没有考虑它们之间最短路径上的边权重。参考文献 [25] 中的方法仍然构造完全综合征图，但仅对彼此在选定阈值距离 $c$ 内的节点使用 Dijkstra 算法精确计算边权重。虽然此方法降低了使用 Dijkstra 算法计算最短路径的复杂度，但完全综合征图仍然输入到开花算法，而我们的局部匹配解码器的综合征图本身是稀疏的。此外，设置适当的阈值 $c$ 需要分析匹配图中的边权重。虽然这些替代方法在应用的特定上下文中是有效的，但我们的局部匹配解码器提供了更大的灵活性，因为它不需要针对量子码的特定几何形状或匹配图中的边权重进行定制。

运行时的进一步改进可以通过使用不依赖开花算法的解码器来实现。特别值得注意的是Union-Find 解码器[26]，其运行时间几乎与节点数成线性关系，且由于其简单性，也适合在硬件中快速实现 [27]。Union-Find 解码器通常比 MWPM 具有更低的阈值，表面码的阈值为 $9.9\%$，而 MWPM 为 $10.3\%$，尽管最近在发展具有改进阈值的 Union-Find 变体方面取得了进展 [28, 29, 30]。无论这些发展如何，我们预计 MWPM 在可预见的未来仍将是用于基准测试解码器和量子纠错码性能的有用解码器。

---

5 基准测试

5.1 性能

局部匹配解码器用于构建综合征图的邻居数 $m$ 的参数化允许在速度和接近精确匹配的程度之间进行权衡。通过设置 $m=|\mathbf{s}|-1$，其中 $|\mathbf{s}|$ 是综合征的汉明权重，我们以更高的计算复杂度为代价恢复了精确匹配。通过将 $m$ 设置为一个小的常数，我们获得改进的计算复杂度，并且仍然找到完美匹配，但完美匹配的权重不再保证是最小的。然而，如本节中的基准测试所示，局部匹配输出的解仍然可以与精确匹配以非常高的概率一致，即使对于小的 $m$。

图 3 显示了 2D 环面码的阈值如何随局部匹配解码器的 $m$ 变化。所有阈值使用晶格尺寸 $L=24,28,32,36$ 估计。对于完美的综合征测量，阈值快速收敛到 $m\ge 12$ 时的 $0.10321(1)$，与精确匹配的预期值一致 [31]。有趣的是，对于 $m=6,7,8$，局部匹配的阈值实际上略高于精确匹配，图 4a 显示在阈值附近固定 $p$ 的逻辑错误率对于 $m=8$ 也低于精确匹配。这表明局部匹配对于小 $m$ 的近似误差不一定降低解码性能，反而可以在某些情况下利用码的简并性来提高性能。对于噪声综合征测量（唯象噪声模型），局部匹配在 $m\ge 16$ 时稳定在约 $0.0292$ 的阈值，也与精确匹配一致 [31]。在图 4 中，逻辑错误率显示为 $m$ 的函数，我们看到对于 $m\ge 16$，无论是完美综合征测量还是使用 3D 匹配图的唯象错误模型，逻辑错误率都稳定为常数。

（图片说明：
图 3：使用晶格尺寸 $L=24,28,32,36$ 和参考文献 [31] 的临界指数方法确定的 2D 环面码局部匹配解码器的阈值作为 $m$ 的函数。(a) 使用具有完美综合征测量的独立噪声模型，虚线显示使用完整（精确）匹配的阈值的 $1\sigma$ 上下界。(b) 使用唯象噪声模型，综合征测量和单量子比特 $Z$ 错误以相同概率 $p$ 发生。综合征测量重复 $L$ 次，在 3D（2D + 时间）匹配图上进行解码。
图 4：2D 环面码局部匹配解码器中使用的邻居数 $m$ 的逻辑错误率。(a) $L=60$ 的环面码，$p=0.1$，完美综合征测量（2D 匹配图）。(b) $L=20$ 的环面码，$p=0.029$，噪声综合征测量（唯象噪声模型），$L$ 次综合征重复（3D 匹配图）。）

为了更好地理解局部匹配如何近似精确匹配，我们还分析了局部匹配的近似误差（approximation error），定义为局部匹配解的权重与精确匹配解的权重不同的运行比例。从图 5 可以看出，近似误差随 $m$ 指数减小，并且随 $p$ 减小。对于完美综合征测量，$m\ge 20$ 时近似误差小于 $10^{-6}$。对于唯象噪声模型在阈值附近，近似误差下降更慢，在 $m=20$ 时仍约为 $10^{-3}$。然而，近似误差仅为局部匹配和精确匹配之间逻辑错误率差异的上界，如图 3b 和图 4b 所示，对于 $m\ge 16$，我们未观察到随 $m$ 变化的逻辑错误率和阈值的统计学显著差异。

（图片说明：图 5：$L=20$ 环面码局部匹配解码器的近似误差作为邻居数 $m$ 的函数。近似误差定义为局部匹配权重与精确匹配权重不同的运行比例。标记为 2D 的图假设完美综合征测量，而标记为 3D 的图假设 $L=20$ 轮噪声综合征测量（唯象噪声模型）。）

5.2 速度

如图 6a 所示，PyMatching 可以比 NetworkX 实现的最小权重完美匹配解码器快几个数量级。这种加速部分是由于 PyMatching 中的核心算法使用优秀的 Lemon [19] 和 Boost Graph 库用 C++ 实现的。然而，使用局部匹配算法而不是精确匹配也有一个缩放优势，导致 $m=20$ 的经验确定运行时缩放约为 $O(L^{2.1})$（略差于节点数的线性），而 NetworkX 为 $O(L^{4.4})$。这些经验确定的运行时间大大优于精确匹配的 $O(L^6\log (L))$ 和局部匹配的 $O(L^{4}m\log (L))$ 的预期最坏情况运行时间。这表明对于量子纠错中通常出现的匹配图，开花算法的典型运行时间远好于其最坏情况复杂度。事实上，对于局部匹配和精确匹配，经验确定的缩放与解码器仅综合征图构建阶段（Dijkstra 或局部 Dijkstra）的预期复杂度相似。我们在局部匹配中观察到的随 $L$ 的运行时缩放也与参考文献 [32] 中使用的匹配变体观察到的缩放相似，尽管参考文献 [32] 中使用的实现专门针对表面码。

（图片说明：
图 6：使用 2.8 GHz Intel Core i5 CPU 的 PyMatching 环面码运行时间。(a) PyMatching 实现 $m=20$ 的环面码局部匹配的运行时，使用独立噪声模型（$p=0.05$）和完美综合征测量。为比较，还显示了使用 NetworkX 实现完整匹配的运行时。(b) 使用每边翻转概率为 $p=0.05$ 的 3D 环面匹配图的 PyMatching 运行时比较。局部匹配和完整匹配分别用实线和虚线表示。使用 Lemon 图库（如 PyMatching 最新版本所用）进行开花算法的结果以绿色显示，使用 Blossom V 库的结果以蓝色显示。）

量子纠错社区中常用的 C++ 开花算法实现是 Blossom V 库，其性能优异 [18]。然而，Blossom V 没有宽松的软件许可证，因此 PyMatching 不使用它。PyMatching 改用 Lemon C++ 库，它也有高效的开花算法实现，但具有宽松的、开源的许可证（Boost 许可证）[19]。在图 6b 中，我们比较了 PyMatching 使用 Lemon 和 Blossom V C++ 库进行精确匹配和局部匹配（$m=20$）的性能，用于解码 $p=0.05$ 的 3D 环面匹配图。对于大 $L$ 的局部匹配，Blossom V 库仅比 Lemon 快约 $10\text{–}20\%$，对于精确匹配 Blossom V 快约 $20\text{–}30\%$。虽然这表明使用 Blossom V 代替 Lemon 可以获得小的性能改进，但我们仅在 PyMatching 中使用 Lemon，因为它具有宽松的、开源的许可证。图 6b 还表明，对于环面码和唯象噪声模型，当 $L>7$ 时局部匹配快于精确匹配，对于容错模拟中通常考虑的晶格尺寸 $L\ge 20$，局部匹配比精确匹配快一个数量级以上。对于非常小的匹配图，精确匹配可能略快，因为 PyMatching 为精确匹配预计算所有节点对之间的最短路径，但为局部匹配实时计算最短路径。在图 7 中，我们展示了 PyMatching 的运行时如何随 $m$ 变化。我们发现，对于 $m\ge 20$，运行时间随 $m$ 线性缩放，对于 2D 环面码使用唯象噪声模型，在阈值处和阈值以下都是如此，这与第 4 节中找到的预期运行时间 $O(L^{4}m\log (L)+L^{2}m\log (m))$（在对数因子内）一致。所有时序分析均使用 2.8 GHz Intel Core i5 处理器完成。

（图片说明：图 7：$L=20$ 环面码不同 $m$ 值的 PyMatching 运行时，对应三个不同的错误概率 $p$。Pauli $Z$ 错误和综合征测量错误都以概率 $p$ 发生，在 3D 匹配图上进行解码（$L$ 次综合征测量重复）。）

---

6 使用

在本节中，我们将给出一些如何使用 PyMatching 的示例，并引导读者查阅文档以获取更详细的示例。虽然 PyMatching 的算法是用 C++ 编写的，但所有核心功能都可通过提供简单接口的 Python 绑定使用。PyMatching Python 包可以使用命令 pip install pymatching 从 Python 包索引下载和安装。向 PyMatching 输入量子码的最简单方式是使用检查矩阵（check matrix）。检查矩阵 $\mathbf{H}$ 是一个二元矩阵，仅当第 $i$ 个检查算符对第 $j$ 个量子比特非平凡作用时元素 $H_{ij}$ 非零。第一步是构造一个 pymatching.Matching 对象，如下所示，以重复码为例：

import numpy as np
from pymatching import Matching

H = np.array([
    [1,1,0,0,0],
    [0,1,1,0,0],
    [0,0,1,1,0],
    [0,0,0,1,1]
])
m = Matching(H)

注意，检查矩阵 $\mathbf{H}$ 也可以作为 scipy.sparse 矩阵提供，这对于更大的码更节省内存。然后可以使用 Matching.decode 方法使用 PyMatching 解码二元综合征 $\mathbf{s}$：

noise = np.array([0,0,1,1,0])
s = H @ noise % 2
c = m.decode(s)

校正 $\mathbf{c}$ 也是一个二元 NumPy 数组，仅当校正算符对量子比特 $i$ 非平凡作用时 $c$ 的第 $i$ 个元素非零。

默认情况下，PyMatching 使用 $m=30$ 的局部匹配算法，但这可以在解码时通过指定 num_neighbours 参数来更改。例如，要在局部匹配中使用 $m=40$，我们可以使用：

c = m.decode(s, num_neighbours=40)

PyMatching 还可以通过设置 num_neighbours=None 来实现精确匹配。当使用此选项时，匹配图中所有节点对之间的最短路径在首次调用 decode 时计算并存储，然后在后续调用 decode 时重用。虽然存储所有节点对之间的最短路径加速了精确匹配，但对于非常大的匹配图，内存需求可能过高。注意，也可以通过将 num_neighbours 设置为比缺陷数 $|\mathbf{s}|-1$ 小一的值（或任何更大的整数）来使用精确匹配，因为局部匹配在此极限下与精确匹配相同。虽然使用此方法的内存需求低于设置 num_neighbours=None，但计算复杂度更高，因为所有缺陷之间的距离都是实时计算的。通常建议使用局部匹配，num_neighbours 设置为小的常数，因为它对于除最小匹配图之外的所有情况都快于精确匹配，并且具有适度的内存需求，同时保持几乎相同的解码性能。

PyMatching 还可用于处理加权边、重复噪声综合征测量、边界节点和钩状错误（hook errors）（匹配图中单条边对应多个量子比特错误）。为了帮助处理这些用例，PyMatching 允许使用 NetworkX 图而不是检查矩阵来构造 Matching 对象。例如，再次使用量子重复码示例，我们可以通过首先构造相应的 NetworkX 图来构造 Matching 对象：

import networkx as nx
p = 0.2
w = np.log((1-p)/p)
g = nx.Graph()
g.add_edge(0, 1, qubit_id=0, weight=w, error_probability=p)
g.add_edge(1, 2, qubit_id=1, weight=w, error_probability=p)
g.add_edge(2, 3, qubit_id=2, weight=w, error_probability=p)
g.add_edge(3, 4, qubit_id=3, weight=w, error_probability=p)
g.add_edge(4, 5, qubit_id=4, weight=w, error_probability=p)

这里每条边对应一个以概率 $p=0.2$ 遭受错误的量子比特，并被分配权重 $\log ((1-p)/p)$。使用这种方法，我们现在可以添加一个钩状错误（hook error），其中单个故障可以导致多个量子比特上的错误。此钩状错误对应于匹配图中量子比特 id 现在是整数集合的边，我们还将给它一个不同的错误概率 $p_2=0.12$：

p2 = 0.12
w2 = np.log((1-p2)/p2)
g.add_edge(2, 4, qubit_id={2, 3}, weight=w2, error_probability=p2)

由于节点 0 和 5 仅与一条边关联且不对应于稳定子，我们将指定它们是边界节点：

g.node[0]['is_boundary'] = True
g.node[5]['is_boundary'] = True

然后使用权重为零且不对应于错误的边界边连接这些边界节点：

g.add_edge(0, 5, weight=0.0, qubit_id=-1, error_probability=0.0)

现在可以使用以下命令构造与此图对应的 Matching 对象：

m = Matching(g)

如果指定了边界节点且提供给 m.decode(s) 的综合征具有奇校验，则 PyMatching 在解码时会翻转其中一个边界节点，以确保匹配图中的缺陷具有偶校验（否则完美匹配不存在）。如果为图中的每条边都指定了可选的错误概率属性，则 PyMatching 还可以用于模拟随机噪声模型，其中每条边以其相应的错误概率独立翻转，使用 m.add_noise() 方法。利用所有这些附加功能，PyMatching 可用于模拟和解码稳定子测量调度中的电路级噪声模型，并在参考文献 [9] 中用于此目的。

---

7 结论

在本文中，我们介绍了 PyMatching，一个用于使用最小权重完美匹配（MWPM）解码器解码量子纠错码的快速、开源 Python 包。PyMatching 使用标准 MWPM 解码器的一个变体，称为局部匹配，该变体仅允许综合征图中的节点与其最近邻居匹配。我们在本文中呈现的基准测试表明，PyMatching 实现的局部匹配对于大匹配图可以比使用 NetworkX 或 Blossom V [18] 实现精确 MWPM 快几个数量级，同时保持几乎相同的解码性能。虽然可以通过针对特定码定制解码器来进一步优化（例如，通过在简单方晶格中使用曼哈顿距离或平移对称性代替 Dijkstra 搜索），但 PyMatching 被设计为灵活的，能够高效解码任何适合 MWPM 解码的量子纠错码。我们希望这种速度和灵活性的结合将使 PyMatching 成为量子纠错研究人员的有价值工具，节省编程时间和计算资源。

---

8 致谢

作者感谢 Unitary Fund 和工程与物理科学研究委员会 [资助号 EP/L015242/1] 的支持。作者还感谢 Will Zeng、Nathan Shammah、Mike Vasmer 和 Craig Gidney 的有益讨论，以及 Nikolas Breuckmann 和 Dan Browne 对稿件的反馈。我们感谢在完成本工作中使用 UCL Myriad 高性能计算设施（Myriad@UCL）及相关支持服务。

---

参考文献

[1] Min-Hsiu Hsieh and Fran¸cois Le Gall. Np-hardness of decoding quantum error-correction codes.
Physical Review A, 83(5):052331, 2011.
13
[2] Kao-Yueh Kuo and Chung-Chin Lu. On the hardness of decoding quantum stabilizer codes
under the depolarizing channel. In 2012 International Symposium on Information Theory and
its Applications, pages 208–211. IEEE, 2012.
[3] Kao-Yueh Kuo and Chung-Chin Lu. On the hardnesses of several quantum decoding problems.
Quantum Information Processing, 19(4):1–17, 2020.
[4] Pavithran Iyer and David Poulin. Hardness of decoding quantum stabilizer codes. IEEE Trans-
actions on Information Theory, 61(9):5209–5223, 2015.
[5] Jack Edmonds. Paths, trees, and flowers. Canadian Journal of mathematics, 17:449–467, 1965.
[6] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. Topological quantum memory.
Journal of Mathematical Physics, 43(9):4452–4505, 2002.
[7] Sergey Bravyi, Guillaume Duclos-Cianci, David Poulin, and Martin Suchara. Subsystem surface
codes with three-qubit check operators. arXiv preprint arXiv:1207.1443, 2012.
[8] Nikolas P Breuckmann and Barbara M Terhal. Constructions and noise threshold of hyperbolic
surface codes. IEEE transactions on Information Theory, 62(6):3731–3744, 2016.
[9] Oscar Higgott and Nikolas P Breuckmann. Subsystem codes with high thresholds by gauge
fixing and reduced qubit overhead. arXiv preprint arXiv:2010.09626, 2020.
[10] J Pablo Bonilla-Ataides, David K Tuckett, Stephen D Bartlett, Steven T Flammia, and Ben-
jamin J Brown. The xzzx surface code. arXiv preprint arXiv:2009.07851, 2020.
[11] Muyuan Li, Daniel Miller, Michael Newman, Yukai Wu, and Kenneth R Brown. 2d compass
codes. Physical Review X, 9(2):021041, 2019.
[12] Christopher Chamberland, Guanyu Zhu, Theodore J Yoder, Jared B Hertzberg, and Andrew W
Cross. Topological and subsystem codes on low-degree graphs with flag qubits. Physical Review
X, 10(1):011022, 2020.
[13] Armanda O Quintavalle, Michael Vasmer, Joschka Roffe, and Earl T Campbell. Single-shot error
correction of three-dimensional homological product codes. arXiv preprint arXiv:2009.11790,
2020.
[14] Benjamin J Brown, Naomi H Nickerson, and Dan E Browne. Fault-tolerant error correction
with the gauge color code. Nature communications, 7(1):1–8, 2016.
[15] Aleksander Kubica and Nicolas Delfosse. Efficient color code decoders in d ≥ 2 dimensions from
toric code decoders. arXiv preprint arXiv:1905.07393, 2019.
[16] Benjamin J Brown and Dominic J Williamson. Parallelized quantum error correction with
fracton topological codes. Physical Review Research, 2(1):013303, 2020.
[17] Georgia M Nixon and Benjamin J Brown. Correcting spanning errors with a fractal code. IEEE
Transactions on Information Theory, 2021.
[18] Vladimir Kolmogorov. Blossom v: a new implementation of a minimum cost perfect matching
algorithm. Mathematical Programming Computation, 1(1):43–67, 2009.
14
[19] Bal´azs Dezs˝o, Alp´ar J¨uttner, and P´eter Kov´acs. Lemon–an open source c++ graph template
library. Electronic Notes in Theoretical Computer Science, 264(5):23–45, 2011.
[20] Austin G Fowler, Adam C Whiteside, Angus L McInnes, and Alimohammad Rabbani. Topo-
logical code autotune. Physical Review X, 2(4):041003, 2012.
[21] David Kingsley Tuckett. Tailoring surface codes: Improvements in quantum error correction
with biased noise. PhD thesis, University of Sydney, 2020. (qecsim: https://github.com/
qecsim/qecsim).
[22] Sergey Bravyi, Martin Suchara, and Alexander Vargo. Efficient algorithms for maximum like-
lihood decoding in the surface code. Physical Review A, 90(3):032326, 2014.
[23] Jeremy Siek, Andrew Lumsdaine, and Lie-Quan Lee. The boost graph library: user guide and
reference manual. Addison-Wesley, 2002.
[24] Austin G Fowler, Adam C Whiteside, and Lloyd CL Hollenberg. Towards practical classical
processing for the surface code. Physical review letters, 108(18):180501, 2012.
[25] Xiaosi Xu, Qi Zhao, Xiao Yuan, and Simon C Benjamin. High-threshold code for modular
hardware with asymmetric noise. Physical Review Applied, 12(6):064006, 2019.
[26] Nicolas Delfosse and Naomi H Nickerson. Almost-linear time decoding algorithm for topological
codes. arXiv preprint arXiv:1709.06218, 2017.
[27] Poulami Das, Christopher A Pattison, Srilatha Manne, Douglas Carmean, Krysta Svore, Moin-
uddin Qureshi, and Nicolas Delfosse. A scalable decoder micro-architecture for fault-tolerant
quantum computing. arXiv preprint arXiv:2001.06598, 2020.
[28] Shilin Huang, Michael Newman, and Kenneth R Brown. Fault-tolerant weighted union-find
decoding on the toric code. Physical Review A, 102(1):012419, 2020.
[29] Kai Meinerz, Chae-Yeun Park, and Simon Trebst. Scalable neural decoder for topological
surface codes. arXiv preprint arXiv:2101.07285, 2021.
[30] Mark Shui Hu and David Elkouss. Quasilinear time decoding algorithm for topological codes
with high error threshold. 2020.
[31] Chenyang Wang, Jim Harrington, and John Preskill. Confinement-higgs transition in a dis-
ordered gauge theory and the accuracy threshold for quantum memory. Annals of Physics,
303(1):31–58, 2003.
[32] Austin G Fowler, Adam C Whiteside, and Lloyd CL Hollenberg. Towards practical classical
processing for the surface code: timing analysis. Physical Review A, 86(4):042313, 2012.

---

---

---

[1] Min-Hsiu Hsieh 和 Francois Le Gall。解码量子纠错码的 NP-难度。Physical Review A, 83(5):052331, 2011。

[2] Kao-Yueh Kuo 和 Chung-Chin Lu。关于在退极化信道下解码量子稳定子码的难度。In 2012 International Symposium on Information Theory and its Applications, pages 208-211. IEEE, 2012.

[3] Kao-Yueh Kuo 和 Chung-Chin Lu。关于几个量子解码问题的难度。Quantum Information Processing, 19(4):1-17, 2020.

[4] Pavithran Iyer 和 David Poulin。解码量子稳定子码的难度。IEEE Transactions on Information Theory, 61(9):5209-5223, 2015.

[5] Jack Edmonds。路径、树和花。Canadian Journal of mathematics, 17:449-467, 1965.

[6] Eric Dennis, Alexei Kitaev, Andrew Landahl, 和 John Preskill。拓扑量子存储器。Journal of Mathematical Physics, 43(9):4452-4505, 2002.

[7] Sergey Bravyi, Guillaume Duclos-Cianci, David Poulin, 和 Martin Suchara。具有三量子比特检查算符的子系统表面码。arXiv preprint arXiv:1207.1443, 2012.

[8] Nikolas P Breuckmann 和 Barbara M Terhal。双曲表面码的构造和噪声阈值。IEEE transactions on Information Theory, 62(6):3731-3744, 2016.

[9] Oscar Higgott 和 Nikolas P Breuckmann。通过规范固定和减少量子比特开销实现高阈值的子系统码。arXiv preprint arXiv:2010.09626, 2020.

[10] J Pablo Bonilla-Ataides, David K Tuckett, Stephen D Bartlett, Steven T Flammia, 和 Benjamin J Brown。XZZX 表面码。arXiv preprint arXiv:2009.07851, 2020.

[11] Muyuan Li, Daniel Miller, Michael Newman, Yukai Wu, 和 Kenneth R Brown。2D 罗盘码。Physical Review X, 9(2):021041, 2019.

[12] Christopher Chamberland, Guanyu Zhu, Theodore J Yoder, Jared B Hertzberg, 和 Andrew W Cross。具有标志量子比特的低度图上的拓扑和子系统码。Physical Review X, 10(1):011022, 2020.

[13] Armanda O Quintavalle, Michael Vasmer, Joschka Roffe, 和 Earl T Campbell。三维同调积码的单次纠错。arXiv preprint arXiv:2009.11790, 2020.

[14] Benjamin J Brown, Naomi H Nickerson, 和 Dan E Browne。使用规范色码进行容错纠错。Nature communications, 7(1):1-8, 2016.

[15] Aleksander Kubica 和 Nicolas Delfosse。在 $d\ge 2$ 维中从环面码解码器高效解码色码。arXiv preprint arXiv:1905.07393, 2019.

[16] Benjamin J Brown 和 Dominic J Williamson。使用分形拓扑码并行量子纠错。Physical Review Research, 2(1):013303, 2020.

[17] Georgia M Nixon 和 Benjamin J Brown。使用分形码纠正跨越错误。IEEE Transactions on Information Theory, 2021.

[18] Vladimir Kolmogorov。Blossom V：最小成本完美匹配算法的新实现。Mathematical Programming Computation, 1(1):43-67, 2009.

[19] Balazs Dezso, Alpar Juttner, 和 Peter Kovacs。Lemon——一个开源 C++ 图模板库。Electronic Notes in Theoretical Computer Science, 264(5):23-45, 2011.

[20] Austin G Fowler, Adam C Whiteside, Angus L McInnes, 和 Alimohammad Rabbani。拓扑码自动调谐。Physical Review X, 2(4):041003, 2012.

[21] David Kingsley Tuckett。定制表面码：量子纠错中的改进。博士论文，悉尼大学，2020。（qecsim: https://github.com/qecsim/qecsim）

[22] Sergey Bravyi, Martin Suchara, 和 Alexander Vargo。表面码中最大似然解码的高效算法。Physical Review A, 90(3):032326, 2014.

[23] Jeremy Siek, Andrew Lumsdaine, 和 Lie-Quan Lee。Boost 图库：用户指南和参考手册。Addison-Wesley, 2002.

[24] Austin G Fowler, Adam C Whiteside, 和 Lloyd CL Hollenberg。迈向表面码的实用经典处理。Physical review letters, 108(18):180501, 2012.

[25] Xiaosi Xu, Qi Zhao, Xiao Yuan, 和 Simon C Benjamin。用于具有非对称噪声的模块化硬件的高阈值码。Physical Review Applied, 12(6):064006, 2019.

[26] Nicolas Delfosse 和 Naomi H Nickerson。拓扑码的几乎线性时间解码算法。arXiv preprint arXiv:1709.06218, 2017.

[27] Poulami Das, Christopher A Pattison, Srilatha Manne, Douglas Carmean, Krysta Svore, Moinuddin Qureshi, 和 Nicolas Delfosse。用于容错量子计算的可扩展解码器微架构。arXiv preprint arXiv:2001.06598, 2020.

[28] Shilin Huang, Michael Newman, 和 Kenneth R Brown。环面码上的容错加权 Union-Find 解码。Physical Review A, 102(1):012419, 2020.

[29] Kai Meinerz, Chae-Yeun Park, 和 Simon Trebst。拓扑表面码的可扩展神经解码器。arXiv preprint arXiv:2101.07285, 2021.

[30] Mark Shui Hu 和 David Elkouss。具有高错误阈值的拓扑码准线性时间解码算法。2020.

[31] Chenyang Wang, Jim Harrington, 和 John Preskill。无序规范理论中的禁闭-希格斯跃迁和量子存储器的精度阈值。Annals of Physics, 303(1):31-58, 2003.

[32] Austin G Fowler, Adam C Whiteside, 和 Lloyd CL Hollenberg。迈向表面码的实用经典处理：时序分析。Physical Review A, 86(4):042313, 2012.