MWPM decoder | NotionNext BLOG

This note is written in two languages, Chinese and English.

[1]Y. Wu and L. Zhong, “Fusion Blossom: Fast MWPM Decoders for QEC.” arXiv, May 14, 2023. Accessed: Sep. 21, 2023. [Online]. Available: http://arxiv.org/abs/2305.08307

最小权重完美匹配解码器

Minimum Weight Perfect Matching Decoder

完美匹配

图的完美匹配是指一个无向图中的一组边，使得每个顶点都恰好与其中的一条边相连。换句话说，每个顶点都与图中的某一条边配对，且每条边都只与一个顶点配对。

具体来说，对于一个无向图 G=(V, E)，其中 V 表示顶点的集合，E 表示边的集合。如果存在一个边的子集 M，满足下列条件，则称 M 为 G 的完美匹配：

M 中的边都是 G 中的边；

M 中的任意两条边互不相邻，即它们没有公共的顶点；

M 中的边覆盖了 G 中的每个顶点，即每个顶点都与 M 中的某条边相连。

在一个完美匹配中，每个顶点都有且只有一条边与之相连，且所有的顶点都被匹配上了。

⚠️ 匹配：是边的集合

Perfect Matching

A perfect matching in a graph refers to a set of edges in an undirected graph, in which each vertex is connected to exactly one of those edges. In other words, each vertex is paired with a specific edge in the graph, and each edge is only paired with one vertex.

Specifically, for an undirected graph G=(V, E), where V represents the set of vertices and E represents the set of edges. If there exists a subset M of edges that satisfies the following conditions, then M is called a perfect matching of G:

All edges in M are edges in G;

Any two edges in M are not adjacent, meaning they do not share a common vertex;

All vertices in G are covered by the edges in M, meaning each vertex is connected to one of the edges in M.

In a perfect matching, each vertex has exactly one edge connected to it, and all vertices are matched.

⚠️ Matching: A set of edges.

Perfect Matching -- from Wolfram MathWorld

最小权重

实现完美匹配的边的集合中，所有边的权重之和要在所有的完美匹配中最小。

Minimum Weight

In the set of edges that achieve a perfect match, the sum of weights of all edges should be the minimum among all perfect matches.

QEC流程

QEC Process

Figure 6. The general procedure for active recovery in a quantum error correction code

表面码错误

Surface code errors

解码问题怎么转化成MWPM问题?

How to convert the decoding problem into the MWPM (Maximum Weighted Perfect Matching) problem?

MWPM decoder的流程

The process of the MWPM decoder is as follows:

整数线性规划→ 松弛成线性规划→ 转成对偶的线性规划→求解线性规划→取整获得最初所需的整数解

Integer linear programming → Relaxation to linear programming → Conversion to dual linear programming → Solving the linear programming problem → Rounding to obtain the initial desired integer solution

Fusion blossom algo insights：

解码图划分成子图，再递归融合。子图之间没有依赖关系时可以实现并行算法。

Decoding the graph is divided into subgraphs, and then recursively merged. Parallel algorithms can be implemented when there is no dependency between subgraphs.

并行的方式：

Parallel Ways:

评估结果：

主要和最近的结果Sparse Blossom 进行对比，单线程较大，但是可以并行，多线程优于Sparse Blossom。

Evaluation Results:

The main comparison is with the recent results of Sparse Blossom. In terms of single-thread performance, it is larger but can be parallelized. However, when it comes to multi-threading, it outperforms Sparse Blossom.