稀疏的检查，
不衰减的码率 Sparse checks,
a rate that does not decay

记号：n = 物理比特数，k = 逻辑比特数，r = 独立检查的条数，于是 k = n − r（与《从高考数学到 Toric Code》4.4 节的记法相同，也就是编码论的 [[n, k, d]]），d = 码距，即能骗过全部检查的最轻逻辑算符的重量（同一教程 5.8 节）。 c = 只与检查的大小和伸展范围有关的常数。

Notation: n = number of physical qubits; k = number of logical qubits and r = number of independent checks, so k = n − r (the notation of “From High-School Math to the Toric Code”, §4.4, i.e. the coding-theory [[n, k, d]]); d = the code distance, the weight of the lightest logical operator that fools every check (§5.8 there). c = a constant depending only on the size and reach of the checks.

本教程的主角是一个乘法：把两条经典码相乘，得到一个量子码。为了让这件事不显得突然，先在实验台上看一个你已经很熟的例子——《Surface Code · 高中数学版》的表面码 [[13,1,3]] 恰好是两条长 3 的重复码的乘积。先不必看懂每一格的含义，只需注意四件事：格子分成四块，比特在两块对角的格里，X 检查和 Z 检查各占一块，而 n = 3·3 + 2·2 = 13 正是那里的 d² + (d−1)²。

This tutorial's protagonist is a multiplication: multiply two classical codes and get a quantum code. So that this does not feel abrupt, first look at a familiar example on the bench — the surface code [[13,1,3]] of “The Surface Code · High-School Edition” is exactly the product of two length-3 repetition codes. Do not try to read every cell yet; notice four things: the grid splits into four blocks, qubits sit in the two diagonal blocks, X checks and Z checks occupy one block each, and n = 3·3 + 2·2 = 13 is that tutorial's d² + (d−1)².

一条经典线性码由一个 m × n 的 0/1 矩阵 H 定义：合法的码字 c 是所有满足 Hc = 0（mod 2）的比特串——每一行是一条奇偶检查（《从高考数学到 Toric Code》2.3 节的两盏灯就是 H 的两行）。它的参数写成单方括号 [n,k,d]：k = n − rank H 个信息比特，d = 最轻的非零码字的重量。例：三位重复码的 H 有两行 (1, 1, 0) 与 (0, 1, 1)，秩 2，所以 k = 3 − 2 = 1；满足 Hc = 0 的非零串只有 111，重量 3，于是它是 [3,1,3]。「低密度LDPC = low-density parity-check：H 的每行每列的 1 都不超过一个与 n 无关的常数。Gallager 1962 年引入。」指 H 的每行每列 1 的个数有界。Gallager 在 1962 年就证明：随机的稀疏 H 几乎总是给出好码good code：一族码 k ≥ R·n 且 d ≥ δ·n，R、δ 为正常数。编码率 k/n 与相对距离 d/n 都不随 n 趋于零。——k 与 d 都与 n 成比例——而且稀疏性让它可以用局域的消息传递（BP）译码。

A classical linear code is defined by an m × n 0/1 matrix H: the valid codewords c are all bit strings with Hc = 0 (mod 2) — every row a parity check (the two lamps of “From High-School Math to the Toric Code”, §2.3 are two rows of H). Its parameters are written with single brackets [n,k,d]: k = n − rank H information bits, d = the weight of the lightest nonzero codeword. Example: the three-bit repetition code has H with rows (1, 1, 0) and (0, 1, 1), rank 2, so k = 3 − 2 = 1; the only nonzero string with Hc = 0 is 111, of weight 3, so it is a [3,1,3] code. “Low-densityLDPC = low-density parity-check: every row and column of H has at most a constant number of 1s, independent of n. Introduced by Gallager in 1962.” means the number of 1s per row and column of H is bounded. Gallager proved in 1962 that a random sparse H almost always gives a good codeA family with k ≥ R·n and d ≥ δ·n for positive constants R, δ; rate k/n and relative distance d/n both stay away from zero. — k and d both proportional to n — and sparsity lets it be decoded by local message passing (BP).

量子 CSS 码需要两个矩阵 H_X、H_Z，都要稀疏，还要满足 H_XH_Zᵀ = 0。就是这个额外条件让问题变难：随便取两个随机稀疏矩阵，它们几乎肯定不对易。1996 年 Calderbank 与 Shor 证明随机 CSS 码可以是好码，但那些检查是稠密的（每条碰约一半比特），无法测量。稀疏且好——「好的 qLDPC 码是否存在」——成了公开猜想，从 Tillich 与 Zémor 2009 年的 d ∝ √n（第 2 章）开始步步逼近，直到 2021 年 Panteleev 与 Kalachev、2022 年 Leverrier 与 Zémor 分别给出渐近好的构造（第 5 章）。

A quantum CSS code needs two matrices H_X, H_Z, both sparse, and also H_XH_Zᵀ = 0. That extra condition is what makes the problem hard: two random sparse matrices almost never commute. In 1996 Calderbank and Shor showed that random CSS codes can be good, but their checks are dense (each touching about half the qubits) and cannot be measured. Sparse and good — “do good qLDPC codes exist?” — became an open conjecture, approached step by step from Tillich and Zémor's d ∝ √n in 2009 (Ch. 2) until Panteleev and Kalachev in 2021 and Leverrier and Zémor in 2022 gave asymptotically good constructions (Ch. 5).

用表面码保护 K 个逻辑比特到目标错误率，需要约 K·d² 个物理比特，而 d 要随电路规模的对数增长：一个有 N 步的电路，要让每个逻辑比特每步的失败率 A(p/p_th)^⌈d/2⌉ 小于约 1/N，d 就得正比于 ln N。于是物理比特数是逻辑比特数的「多项式对数」倍（ln N 的某个幂次），规模越大越亏。Gottesman 在 2013 年证明：如果有一族合适的码率恒定的 qLDPC 码，其带噪症状纠错满足阈值与残余错误条件，那么在他的计算与连接假设下，容错量子计算的开销overhead：物理比特数与逻辑比特数之比。表面码约为 d² 并随规模的对数增长；好的 qLDPC 码让它趋于常数。可以是一个常数——每个逻辑比特只需固定个数的物理比特，与电路多大无关。Fawzi、Grospellier 与 Leverrier 2018 年用量子扩展码把这条路走通到线性时间译码。这就是「好」的全部意义：它把「一百万个物理比特能做多大的计算」从对数级差距变成常数级。

Protecting K logical qubits to a target error rate with surface codes needs about K·d² physical qubits, and d must grow with the logarithm of the circuit size: for a circuit of N steps, keeping each logical qubit’s per-step failure A(p/p_th)^⌈d/2⌉ below about 1/N needs d proportional to ln N. The physical count is then a “polylogarithmic” multiple of the logical count (some power of ln N), worse the larger the computation. Gottesman proved in 2013 that given suitable constant-rate qLDPC families whose noisy-syndrome correction meets the required threshold and residual-error conditions, under his computational and connectivity assumptions, the overheadThe ratio of physical to logical qubits. About d² for surface codes, growing with the log of the scale; good qLDPC codes make it approach a constant. of fault-tolerant computation can be a constant — a fixed number of physical qubits per logical qubit, however large the circuit. Fawzi, Grospellier and Leverrier carried this through to linear-time decoding with quantum expander codes in 2018. That is the whole point of “good”: it turns “how large a computation can a million physical qubits run” from a logarithmic gap into a constant one.

《BB 码 · 高中数学版》1.1 节的 BPT 界（k·d² ≤ c·n）已经排除了二维局域的好码：好码要求 k·d² ∝ n³，远超 c·n。

The BPT bound of “BB Codes · High-School Edition”, §1.1 (k·d² ≤ c·n) already rules out good 2D local codes: good codes need k·d² ∝ n³, far above c·n.

Delfosse、Beverland 与 Tremblay 2021 年进一步问：码本身非局域，但只用二维局域电路去测量它的检查，要付出什么？他们的深度下界只管一类码，叫局部扩展码把「共用一条检查的两个比特」连一条边，得到比特之间的图（收缩 Tanner 图）。若这张图里任何不超过总数固定比例的比特集合，向外连出的边数都至少是集合大小的固定倍数，这族码就是局部扩展的。：把共用一条检查的两个比特连一条边，要求这张图里任何「不太大」（不超过全体的某个固定比例）的比特集合向外连出的边数，至少是集合大小的固定倍数。他们的结论（论文推论 1）对电路也有限定，只针对二维局域 Clifford 症状提取电路。比特排在一块共 N 个比特（数据比特与辅助比特都算）的二维方形网格上；每一步只能做单比特或两比特的 Clifford 门（CNOT、Hadamard 这类把 Pauli 算符变成 Pauli 算符的门）和单比特或两比特的 Pauli 测量，而且只作用在相距不超过固定距离的比特上；允许按先前测量结果的奇偶性做 Pauli 修正（经典通信不受距离限制）。对局部扩展码的这类电路，深度至少是 n/√N 的常数倍（n 是码长）。含非 Clifford 门的电路不在这个结论里。

Delfosse, Beverland and Tremblay asked in 2021 what it costs to measure the checks of a nonlocal code with a 2D local circuit only. Their depth bound covers one class of codes, local-expander codesJoin two qubits by an edge when they share a check; this gives a graph on the qubits (the contracted Tanner graph). A code family is local-expander if in this graph every set of qubits up to a fixed fraction of all of them has at least a fixed multiple of its own size in outgoing edges.: join two qubits by an edge when they share a check, and demand that every “not too large” set of qubits (up to a fixed fraction of all of them) has outgoing edges at least a fixed multiple of its size. Their result (Corollary 1 of the paper) also restricts the circuits, to 2D local Clifford syndrome-extraction circuits. The qubits sit on a 2D square grid of N qubits in total (data and ancilla qubits both counted); each step may apply only one- and two-qubit Clifford gates (gates such as CNOT and Hadamard that map Pauli operators to Pauli operators) and one- and two-qubit Pauli measurements, and only on qubits within a fixed distance of each other; Pauli corrections conditioned on the parity of earlier outcomes are allowed (classical communication has no range limit). For such circuits on local-expander codes the depth is at least a constant times n/√N (n the code length). Circuits with non-Clifford gates are outside this result.

表面码不在此列：一块 L × L 的比特区域向外的边只与周长成正比（∝ L），与区域大小 L² 之比 ∝ 1/L，趋于零；它的症状电路深度本来就是常数，论文正是拿它说明「局部扩展」这个假设去不掉。深度要不要增长，还取决于 N 怎么随 n 变：辅助比特与码长同量级（N ∝ n）时，深度至少 ∝ n/√n = √n；他们也给出了用 N ∝ n² 个比特、深度有界的电路，与下界不矛盾（此时 n/√N 是常数）。他们的电路级模拟用一族码率 1/25 的超图积码，码与译码器都不变：全连接时阈值约 10⁻³，二维局域电路在错误率低到 10⁻⁶ 时仍看不到阈值。所以想用扩展型的 qLDPC 码又不付出深度或比特数的代价，就需要长程连接：两层耦合（BB）、可移动原子、光子互联，或者分层地用表面码模拟（第 5 章的 hierarchical 码）。下图把「性价比」k·d²/n 放在一起比：

The surface code is not covered: an L × L block of qubits has outgoing edges proportional only to its perimeter (∝ L), and their ratio to its size L² is ∝ 1/L, which tends to zero; its syndrome circuit has constant depth, and the paper uses exactly this to show that the local-expansion assumption cannot be dropped. Whether the depth must grow also depends on how N scales with n: with ancillas of the same order as the code length (N ∝ n) the depth is at least ∝ n/√n = √n; they also give bounded-depth circuits using N ∝ n² qubits, which is consistent with the bound (n/√N is then a constant). Their circuit-level simulations use a family of hypergraph-product codes of rate 1/25 with the same code and decoder in both settings: about 10⁻³ threshold with full connectivity, and no threshold visible for the 2D local circuit down to error rates of 10⁻⁶. So using expander-type qLDPC codes without paying in depth or qubit count requires long-range connections: two coupling layers (BB), movable atoms, photonic links, or a hierarchical simulation by surface codes (the hierarchical codes of Ch. 5). The chart below compares the figure of merit k·d²/n:

设 H₁ 是 m₁ × n₁、H₂ 是 m₂ × n₂ 的经典检查矩阵。量子比特放在两块：n₁n₂ 个「比特 × 比特」格和 m₁m₂ 个「检查 × 检查」格，共 n = n₁n₂ + m₁m₂。X 检查放在 m₁n₂ 个「检查 × 比特」格，Z 检查放在 n₁m₂ 个「比特 × 检查」格。用《BB 码 · 高中数学版》2.2 节的克罗内克积（⊗）写出两个矩阵：

Let H₁ be an m₁ × n₁ and H₂ an m₂ × n₂ classical check matrix. Qubits go in two blocks: n₁n₂ “bit × bit” cells and m₁m₂ “check × check” cells, n = n₁n₂ + m₁m₂ in all. X checks sit at the m₁n₂ “check × bit” cells, Z checks at the n₁m₂ “bit × check” cells. With the Kronecker product of “BB Codes · High-School Edition”, §2.2 (⊗) the two matrices read:

读法：一条 X 检查由 H₁ 的一条检查 c 和 H₂ 的一个比特 b 标记。它在「比特 × 比特」块里碰的是 (c 碰到的那些 H₁ 比特) × b——沿一列复制了 H₁ 的一条检查；在「检查 × 检查」块里碰的是 c × (碰到 b 的那些 H₂ 检查)——沿一行复制了 H₂ 的一个比特的邻居。所以每条量子检查的重量 = 一条经典检查的重量 + 一个经典比特的度；因子稀疏，积就稀疏。Z 检查把两个角色交换。到实验台上点任意一条检查，看它的腿如何分布在一行和一列上：

Reading it: an X check is labelled by a check c of H₁ and a bit b of H₂. In the “bit × bit” block it touches (the H₁ bits c touches) × b — a check of H₁ copied along a column; in the “check × check” block it touches c × (the H₂ checks touching b) — the neighbours of one bit of H₂ copied along a row. So every quantum check's weight = one classical check's weight + one classical bit's degree; sparse factors give a sparse product. Z checks swap the two roles. Click any check on the bench and watch its legs spread along one row and one column:

用 (A ⊗ B)(C ⊗ D) = AC ⊗ BD 分块相乘：

Multiply block by block with (A ⊗ B)(C ⊗ D) = AC ⊗ BD:

两个混合项一模一样，在 GF(2)只有 0 和 1 两个数、按 1 + 1 = 0 运算的数域；「mod 2 算术」的正式名字。 里相加抵消。这和《BB 码 · 高中数学版》里 BB 码的 AB + BA = 0 是同一件事的两种写法：那里靠「多项式对易」，这里靠「作用在不同因子上的算符对易」。第二块比特（检查 × 检查）不是装饰：没有它，第二个抵消项就不存在。

The two mixed terms are identical and cancel in GF(2)The number system with only 0 and 1, where 1 + 1 = 0; the formal name of mod-2 arithmetic.. This is the same fact as the AB + BA = 0 of BB codes in “BB Codes · High-School Edition” in another notation: there it rests on “polynomials commute”, here on “operators acting on different factors commute”. The second qubit block (check × check) is not decoration: without it the second cancelling term would not exist.

每条经典码有两个维数：k = n − rank H（码本身）和 kᵀ = m − rank H（「转置码」：满足 Hᵀv = 0 的向量 v 构成的码，其维数就是检查之间线性关系的条数）。超图积的逻辑比特数是

Every classical code has two dimensions: k = n − rank H (the code itself) and kᵀ = m − rank H (the “transpose code”: the vectors v with Hᵀv = 0, whose dimension counts the linear relations among the checks). The hypergraph product's number of logical qubits is

实验台的读数同时显示公式预言的 k 与秩计算得到的 k——两者永远相等。《Surface Code · 高中数学版》里表面码 k = 1、环面码 k = 2 的差别，在这里变成了一句话：开链的检查彼此独立（kᵀ = 0），闭链多一条恒等式（kᵀ = 1）。用 Hamming [7,4,3] 做两个因子：k = 4·4 + 0·0 = 16，n = 49 + 9 = 58，得 [[58,16,3]]——58 个比特存 16 个，检查重量最多 3 + 4 = 7。

The bench's readout shows both the formula's predicted k and the k from the rank computation — they always agree. The surface-code tutorial's difference between surface k = 1 and toric k = 2 becomes one sentence here: the open chain's checks are independent (kᵀ = 0), the closed chain has one more identity (kᵀ = 1). Using Hamming [7,4,3] for both factors: k = 4·4 + 0·0 = 16, n = 49 + 9 = 58, giving [[58,16,3]] — 58 qubits storing 16, with check weight at most 3 + 4 = 7.

先补一个定义。转置码（2.3 节）也有距离：dᵀ 是满足 Hᵀv = 0 的非零向量 v 里最轻的重量；kᵀ = 0 时这样的 v 不存在，dᵀ 就不参与比较。例：K₅ 的关联矩阵（第 3 章）里，Hᵀv = 0 要求每条边的两个端点取值相同，只有「五个顶点全选」一个非零解，所以 dᵀ = 5。然后是距离公式。Tillich 与 Zémor 证明：k₁k₂ 那个扇区里最轻的逻辑算符重 min(d₁, d₂)，k₁ᵀk₂ᵀ 那个扇区里最轻的重 min(d₁ᵀ, d₂ᵀ)，d 是非空扇区里的最小值——两个扇区都非空时 d = min(d₁, d₂, d₁ᵀ, d₂ᵀ)；某个扇区为空（比如 kᵀ = 0）时，它的两个距离不参与。

One definition first. A transpose code (§2.3) has a distance too: dᵀ is the smallest weight of a nonzero vector v with Hᵀv = 0; when kᵀ = 0 there is no such v and dᵀ takes no part in the comparison. Example: for the incidence matrix of K₅ (Chapter 3), Hᵀv = 0 demands that the two ends of every edge carry the same value, so the only nonzero solution is “all five vertices”, and dᵀ = 5. Now the distance formula. Tillich and Zémor proved that the lightest logical operator in the k₁k₂ sector has weight min(d₁, d₂) and the lightest in the k₁ᵀk₂ᵀ sector has weight min(d₁ᵀ, d₂ᵀ); d is the minimum over the non-empty sectors — d = min(d₁, d₂, d₁ᵀ, d₂ᵀ) when both are non-empty, while an empty sector (e.g. kᵀ = 0) contributes nothing.

上界一半可以直接造出来。把 H₁ 的一个最轻码字 c（重 d₁）铺在「比特 × 比特」块的第 j 列上：第 i 行第 j 列的格放 Z 当且仅当 cᵢ = 1，记作 Z_列。它与每条 X 检查都对易：X 检查在这一列上碰到的正是 H₁ 的一行，与 c 重叠偶数次。它还不是检查的乘积，理由是能找到一个与所有检查对易、却与它反对易的算符。取 H₂ 的一个码字 u（这要求 k₂ ≥ 1），把列 j 选在 uⱼ = 1 的位置，再挑一个 cᵢ = 1 的行 i，把 u 铺在第 i 行上放 X，记作 X_行。X_行 与每条 Z 检查对易（Z 检查在这一行上碰到的是 H₂ 的一行，与 u 重叠偶数次）；X_行 与 Z_列 只在格 (i, j) 上重叠，一次，所以反对易。任何检查的乘积都与 X_行 对易，Z_列 却不，所以 Z_列 不是检查的乘积，是一个重 d₁ 的逻辑算符。把两个因子的角色交换，同样把 H₂ 的一个最轻码字沿一行铺开放 X，得到重 d₂ 的逻辑算符（这次要求 k₁ ≥ 1）。例：两个因子都取三位重复码 [[1,1,0],[0,1,1]]，得到表面码 [[13,1,3]]；c = u = 111，Z_列 是第 1 列的三个 Z，X_行 是第 1 行的三个 X，两者只在左上角的格相交。所以 d 不会超过这几个数。反过来「任何逻辑算符至少这么重」是 Tillich 与 Zémor 定理的另一半，证明要细致地拆分一个逻辑算符在两块上的部分，本页不展开（见延伸阅读里他们的原文）。

The upper-bound half can be built directly. Lay a lightest codeword c of H₁ (weight d₁) along column j of the bit × bit block: the cell in row i, column j carries Z exactly when cᵢ = 1; call this Z_col. It commutes with every X check: on that column an X check meets exactly one row of H₁, which overlaps c an even number of times. It is also not a product of checks, because there is an operator that commutes with every check but anticommutes with it. Take a codeword u of H₂ (this needs k₂ ≥ 1), choose the column j where uⱼ = 1, pick a row i with cᵢ = 1, and lay u along row i carrying X; call this X_row. X_row commutes with every Z check (on that row a Z check meets one row of H₂, which overlaps u an even number of times), and X_row and Z_col overlap only in cell (i, j), once, so they anticommute. Every product of checks commutes with X_row and Z_col does not, so Z_col is not a product of checks: it is a logical operator of weight d₁. Swapping the roles of the two factors, a lightest codeword of H₂ laid along a row with X is a logical of weight d₂ (this time k₁ ≥ 1 is needed). Example: with both factors the three-bit repetition code [[1,1,0],[0,1,1]] you get the surface code [[13,1,3]]; c = u = 111, Z_col is the three Z's of column 1, X_row the three X's of row 1, and they meet only in the top-left cell. So d cannot exceed these numbers. The converse, “every logical is at least this heavy”, is the other half of the Tillich–Zémor theorem; its proof has to split a logical carefully into its parts on the two blocks, and this page does not reproduce it (see their paper in the reading list).

现在代入好的经典 LDPC 码：n₁ = n₂ = N，k₁ ∝ N，d₁ ∝ N，且转置码也好。那么 n = N² + m² ∝ N²（m 是每个因子的检查条数，与 N 成正比），k ∝ N² ∝ n，d ∝ N ∝ √n。这就是超图积的档次：正码率，距离 √n——把表面码的 k = 1 提升到 k ∝ n，代价是 d 从 √n（表面码 d ≈ √n 也是这个量级）没有再往上走。用 Hamming 做因子的 [[58,16,3]] 里，d = min(3, 3, —, —) = 3。

Now insert good classical LDPC codes: n₁ = n₂ = N, k₁ ∝ N, d₁ ∝ N, transposes good as well. Then n = N² + m² ∝ N² (m, each factor’s number of checks, is proportional to N), k ∝ N² ∝ n, d ∝ N ∝ √n. That is the hypergraph product's league: positive rate, distance √n — lifting the surface code's k = 1 to k ∝ n while d stays at the √n scale the surface code already had. In the Hamming-factor [[58,16,3]], d = min(3, 3, —, —) = 3.

两条开链重复码（(L−1) × L 矩阵）的超图积是 [[L² + (L−1)², 1, L]]：《Surface Code · 高中数学版》的未旋转表面码。两条闭链（L × L 循环矩阵，多一条恒等式，kᵀ = 1）的超图积是 [[2L², 2, L]]：《从高考数学到 Toric Code》的环面码。QEC-Bank 的 surface 条目正是用 HGP(rep_L, rep_L) 构造的，它的 tour 页「看见超图积」就是把每条检查解读为「H₁ 的一条关系 × H₂ 的一个比特」。整个系列的起点，原来就是这个乘法的最小例子。

The hypergraph product of two open repetition chains ((L−1) × L matrices) is [[L² + (L−1)², 1, L]]: the unrotated surface code of “The Surface Code · High-School Edition”. That of two closed chains (L × L circulants, one extra identity, kᵀ = 1) is [[2L², 2, L]]: the toric code of “From High-School Math to the Toric Code”. The QEC-Bank's surface entry is built as HGP(rep_L, rep_L), and its tour page “see the hypergraph product” reads every check as “one relation of H₁ × one bit of H₂”. The whole series began, it turns out, with the smallest example of this multiplication.

QEC-Bank 条目 hgp_7_2_2 用五条稳定子给出一个 7 比特、k = 2、d = 2 的码：三条 Z 型（ZZ····Z、··Z·Z·Z、···Z·ZZ）和两条 X 型（·XXX··X、X···XXX）。它是两条最小的奇偶校验码相乘：H₁ = [1 1]（1 × 2）与 H₂ = [1 1 1]（1 × 3），n = 2·3 + 1·1 = 7，k = 1·2 + 0·0 = 2，d = min(2, 2) = 2。按 2.1 节的公式亲手写一遍：把「比特 × 比特」格 (a, b)（a = 1, 2 是 H₁ 的比特，b = 1, 2, 3 是 H₂ 的比特）编号为 1–6（(1,1)=1、(1,2)=2、(1,3)=3、(2,1)=4、(2,2)=5、(2,3)=6），唯一的「检查 × 检查」格编号 7。H_X = [H₁ ⊗ I₃ | H₂ᵀ] 有 3 行，给出三条 X 检查 X₁X₄X₇、X₂X₅X₇、X₃X₆X₇（每条沿一列复制 H₁ 的 [1 1]，再加上格 7）；H_Z = [I₂ ⊗ H₂ | H₁ᵀ] 有 2 行，给出两条 Z 检查 Z₁Z₂Z₃Z₇、Z₄Z₅Z₆Z₇（每条沿一行复制 H₂ 的 [1 1 1]）。每条 X 检查与每条 Z 检查恰好共享 2 个比特，所以都对易。QEC-Bank 条目列出的是同一个码把 X 与 Z 的角色对调、比特重新编号后的样子（三条三腿的 Z 型、两条四腿的 X 型），参数完全一样。更小的 [1 1] × [1 1] 给出 [[5,1,2]]，但只有一个逻辑比特；n ≤ 6 且 d ≥ 2 的超图积都到不了 k = 2（不要求 d ≥ 2 的话，H₁ = H₂ = [0] 这种没有任何检查的因子会给出 [[2,2,1]]）。它只能探测一个错误、不能纠正。它的价值是教学上的：七个比特就能看清「比特 × 比特」与「检查 × 检查」两块、以及每条检查沿一行一列复制的结构。

The QEC-Bank entry hgp_7_2_2 gives a 7-qubit code with k = 2, d = 2 from five stabilizers: three Z-type (ZZ····Z, ··Z·Z·Z, ···Z·ZZ) and two X-type (·XXX··X, X···XXX). It is the product of the two smallest parity-check codes: H₁ = [1 1] (1 × 2) and H₂ = [1 1 1] (1 × 3), so n = 2·3 + 1·1 = 7, k = 1·2 + 0·0 = 2, d = min(2, 2) = 2. Write it out with the formula of §2.1: number the “bit × bit” cells (a, b) (a = 1, 2 the bits of H₁, b = 1, 2, 3 those of H₂) as 1–6 ((1,1)=1, (1,2)=2, (1,3)=3, (2,1)=4, (2,2)=5, (2,3)=6) and the single “check × check” cell as 7. H_X = [H₁ ⊗ I₃ | H₂ᵀ] has 3 rows, the three X checks X₁X₄X₇, X₂X₅X₇, X₃X₆X₇ (each copies H₁’s [1 1] along a column, plus cell 7); H_Z = [I₂ ⊗ H₂ | H₁ᵀ] has 2 rows, the two Z checks Z₁Z₂Z₃Z₇, Z₄Z₅Z₆Z₇ (each copies H₂’s [1 1 1] along a row). Every X check shares exactly 2 qubits with every Z check, so all commute. The QEC-Bank entry lists the same code with the roles of X and Z swapped and the qubits renumbered (three three-leg Z-type checks, two four-leg X-type ones); the parameters are identical. The smaller [1 1] × [1 1] gives [[5,1,2]] with a single logical qubit; no hypergraph product with n ≤ 6 and d ≥ 2 reaches k = 2 (drop d ≥ 2 and the check-free factors H₁ = H₂ = [0] give [[2,2,1]]). It detects one error without correcting any. Its value is pedagogical: with seven qubits one can see the “bit × bit” and “check × check” blocks and the row-and-column copying of every check.

QEC-Bank 的 tillichzemor 条目用一个结构化的 3 × 4 种子矩阵：三阶循环矩阵 C = I₃ + S₃ 右边补一列全 1，即 [C | 1]（S₃ 是《BB 码 · 高中数学版》2.1 节的 3 × 3 循环移位矩阵，I₃ 是单位矩阵）。它的秩是 3（满行秩，kᵀ = 0），k = 4 − 3 = 1。自乘的超图积：n = 4·4 + 3·3 = 25，k = 1·1 + 0 = 1，QEC-Bank 穷举得 d = 3，证据等级 verified。实验台上选「TZ 种子」做两个因子可以复算。它比表面码 [[13,1,3]] 多用 12 个比特却只换来同样的 [[·,1,3]]——这说明超图积的好坏完全取决于因子：随便挑的因子只给出平庸的码，要好的经典 LDPC 码才有正码率。

The QEC-Bank's tillichzemor entry uses a structured 3 × 4 seed: the order-3 circulant C = I₃ + S₃ with an all-ones column appended, i.e. [C | 1] (S₃ is the 3 × 3 cyclic-shift matrix of “BB Codes · High-School Edition”, §2.1, I₃ the identity). Its rank is 3 (full row rank, kᵀ = 0), k = 4 − 3 = 1. Squared by the hypergraph product: n = 4·4 + 3·3 = 25, k = 1·1 + 0 = 1, and the QEC-Bank enumerates d = 3, grade verified. Choose “TZ seed” for both factors on the bench to recompute it. It spends 12 more qubits than the surface code [[13,1,3]] for the same [[·,1,3]] — showing that a hypergraph product is only as good as its factors: arbitrary factors give mediocre codes, and positive rate needs good classical LDPC codes.

Leverrier、Tillich 与 Zémor 2015 年提出量子扩展码quantum expander code：两条经典扩展码（因子图是扩展图的 LDPC 码）的超图积。在因子图足够扩展的条件下，线性时间的 small-set-flip 译码器能纠正每一个重量不超过 c√n 的对抗性错误（c 是常数）。：用因子图是扩展图的经典码做超图积。扩展图是「任何小集合的邻域都成比例地大」的图——下面的实验台里，环上半径 r 的球只有 2 条向外的边，随机 3-正则图上的球边界随球一起长。在量子码里，这条性质换来一个「警报下限」，但要先去掉稳定子：一个稳定子（检查的乘积）本身就是一个不亮任何检查的错误，所以「少量错误必然惊动很多检查」对错误本身不成立。正确的量是约化重量：把错误乘上各种稳定子，能达到的最小重量。Leverrier、Tillich 与 Zémor 证明（他们论文的推论 9）：约化重量低于某个 ∝ √n 的门槛时，亮起的检查数至少是约化重量的 1/3。于是一个只看局部的译码器（small-set-flip：反复找一小组比特，翻转后亮起的检查变少）总有路可走，并能在线性时间里纠正每一个重量不超过 c√n 的错误。这里 c 是由因子图的度数与扩展参数决定的常数；定理要求因子图的度数固定、两侧都足够扩展。

Leverrier, Tillich and Zémor proposed quantum expander codesThe hypergraph product of two classical expander codes (LDPC codes whose factor graph is an expander). When the factor graph expands enough, the linear-time small-set-flip decoder corrects every adversarial error of weight at most c√n (c a constant). in 2015: hypergraph products of classical codes whose factor graph is an expander. An expander is a graph in which every small set has a proportionally large neighbourhood — on the bench below, a radius-r ball on the cycle has only 2 outgoing edges, while on a random 3-regular graph the ball's boundary grows with the ball. In a quantum code this property buys an “alarm floor”, but only after stabilizers are removed: a stabilizer (a product of checks) is itself an error that lights no check, so “few errors disturb many checks” is false for the error as such. The right quantity is the reduced weight: the smallest weight the error reaches after multiplying it by any stabilizer. Leverrier, Tillich and Zémor proved (Corollary 9 of their paper) that when the reduced weight is below a threshold ∝ √n, the number of lit checks is at least one third of the reduced weight. So a purely local decoder (small-set-flip: repeatedly find a small set of qubits whose flip reduces the lit checks) never runs out of moves, and it corrects every error of weight at most c√n in linear time. Here c is a constant set by the factor graph's degrees and expansion parameters; the theorem assumes fixed degrees and enough expansion on both sides of the factor graph.

QEC-Bank 的 quantum_expander 条目（T2）给出两个确定性的有限见证，因为原论文的扩展图是概率性构造、没有确定性的生成器。「量子扩展码」这个名字属于渐近家族；这两个小见证只是关联矩阵的超图积，并不自带扩展性保证，small-set-flip 的定理不直接适用于它们。第一个用 K₅完全图 K₅：5 个顶点、任意两点之间都有一条边，共 10 条边。顶点–边关联矩阵：行是顶点，列是边，每条边的两个端点处填 1。 的顶点–边关联矩阵（5 × 10，秩 4，k₁ = 6，k₁ᵀ = 1）：n = 100 + 25 = 125，k = 36 + 1 = 37，穷举 d = 3，得 [[125,37,3]]。

The QEC-Bank's quantum_expander entry (T2) ships two deterministic finite witnesses, because the original expanders are probabilistic with no deterministic generator. The name “quantum expander code” belongs to the asymptotic family; these two small witnesses are simply hypergraph products of incidence matrices, carry no expansion guarantee, and the small-set-flip theorem does not directly apply to them. The first uses the vertex–edge incidence matrix of K₅The complete graph on 5 vertices: every pair joined by an edge, 10 edges in all. Its vertex–edge incidence matrix has a row per vertex, a column per edge, and a 1 at the two endpoints of each edge. (5 × 10, rank 4, k₁ = 6, k₁ᵀ = 1): n = 100 + 25 = 125, k = 36 + 1 = 37, exhaustive d = 3, giving [[125,37,3]].

第二个用四阶仿射平面 AG(2,4) 的直线–点关联矩阵。AG(2,4) 是一个有限的「平面」：16 个点是坐标 (x, y)，x、y 取自四元域 GF(4)。GF(4) 有四个元素 0、1、α、α + 1：加法逐位 mod 2（所以 1 + 1 = 0，任何元素加自己都得 0），乘法遇到 α² 就换成 α + 1（于是 α·(α + 1) = α² + α = 1，(α + 1)² = α）。它不是「mod 4 的整数」：mod 4 里 2·2 = 0，直线 y = 2x 与 y = 0 会在 x = 0 和 x = 2 两处相交，两条不同的直线交于两点，这就不是平面了；GF(4) 里每个非零元素都能做除法，两条不同的直线最多交于一点。直线是满足 y = ax + b 或 x = c 的点集（a、b、c 取遍 GF(4)），共 16 + 4 = 20 条，每条 4 个点，每个点在 5 条直线上（4 种斜率各一条，再加一条竖线）。例：直线 y = αx + 1 经过 (0, 1)、(1, α + 1)、(α, α)、(α + 1, 0)；比如 x = α 时 y = α² + 1 = α + 1 + 1 = α。

The second uses the line–point incidence of the affine plane AG(2,4). AG(2,4) is a finite “plane”: its 16 points are coordinates (x, y), with x and y taken from the four-element field GF(4). GF(4) has four elements 0, 1, α, α + 1: addition is bitwise mod 2 (so 1 + 1 = 0, and every element plus itself gives 0), and in multiplication α² is replaced by α + 1 (so α·(α + 1) = α² + α = 1 and (α + 1)² = α). It is not “integers mod 4”: mod 4 has 2·2 = 0, and the lines y = 2x and y = 0 would meet at both x = 0 and x = 2, two distinct lines sharing two points, which is no plane; in GF(4) every nonzero element can be divided by, so two distinct lines meet in at most one point. The lines are the point sets with y = ax + b or x = c (a, b, c ranging over GF(4)), 16 + 4 = 20 lines of 4 points each, every point on 5 lines (one for each of the 4 slopes, plus one vertical). Example: the line y = αx + 1 passes through (0, 1), (1, α + 1), (α, α), (α + 1, 0); for instance at x = α, y = α² + 1 = α + 1 + 1 = α.

关联矩阵的行是直线、列是点（20 × 16，秩 9，k₁ = 7，k₁ᵀ = 11）：n = 256 + 400 = 656，k = 49 + 121 = 170。距离可以直接由 2.4 节的公式得到：这条经典码的最轻非零码字重 6，它的转置码最轻重 5（都能用计算机逐个试遍 2¹⁶ 与 2²⁰ 个向量来确认），两个扇区都非空，d = min(6, 6, 5, 5) = 5，得 [[656,170,5]]。本页对两个因子都现场复算了秩与 k；它们的 k·d²/n 分别是 2.7 与 6.5（第 1 章的柱状图）。Fawzi、Grospellier 与 Leverrier 2018 年正是用这一族码证明了常数开销的容错计算。

The incidence matrix has lines as rows and points as columns (20 × 16, rank 9, k₁ = 7, k₁ᵀ = 11): n = 256 + 400 = 656, k = 49 + 121 = 170. The distance follows directly from the formula of §2.4: the lightest nonzero codeword of this classical code weighs 6 and that of its transpose code 5 (both can be confirmed by a computer trying all 2¹⁶ and 2²⁰ vectors), both sectors are non-empty, and d = min(6, 6, 5, 5) = 5, giving [[656,170,5]]. This page recomputes rank and k for both factors live; their k·d²/n are 2.7 and 6.5 (Chapter 1's bar chart). Fawzi, Grospellier and Leverrier used exactly this family in 2018 to prove constant-overhead fault-tolerant computation.

QEC-Bank 里还有几个 T1 见证：cyclic_hgp [[7,2,?]]（用循环因子做的超图积，Aydin、Delfosse 与 Tham 2025），quantum_tensor_product [[21,9,3]]（Fan 等 2016 的张量积码），check_product [[14,8,2]] 与 classical_product [[16,2,4]]（更一般的积构造）。它们的 d 有的穷举验证、有的仍是问号——QEC-Bank 用「?」而不是猜测填空，这是本系列一直强调的诚实。

The QEC-Bank also holds several T1 witnesses: cyclic_hgp [[7,2,?]] (a hypergraph product with cyclic factors, Aydin, Delfosse and Tham 2025), quantum_tensor_product [[21,9,3]] (the tensor-product codes of Fan et al. 2016), check_product [[14,8,2]] and classical_product [[16,2,4]] (more general product constructions). Some of their d are exhaustively verified, others remain question marks — the QEC-Bank writes “?” rather than guessing, the honesty this series keeps insisting on.

回看超图积的 H₁ ⊗ I_n₂：H₁ 的每个元素 1 被换成一整块单位矩阵 I_n₂——同一条检查在 n₂ 个副本里一字不差地重复。提升积lifted product（Panteleev–Kalachev）：底矩阵的元素取自一个环 R（如循环矩阵、群代数），积构造里的 ⊗ 用环的乘法实现，转置附带环的反演（x ↦ x⁻¹）。超图积是 R = GF(2) 的特例。把这个 I 换成任意的置换矩阵，甚至它们的和：底矩阵的元素不再是 0/1，而是BB 教程那个环 R 里的多项式。每个副本于是被平移了不同的量，检查之间有了「错位」。对易性仍然成立——只要环是可交换的，2.2 节的两个混合项依旧相同、依旧抵消（转置要附带把 x 换成 x⁻¹，即反向平移，正如《BB 码 · 高中数学版》2.3 节的 Aᵀ）。

Look back at the hypergraph product's H₁ ⊗ I_n₂: every entry 1 of H₁ becomes a whole identity block I_n₂ — the same check repeated verbatim across n₂ copies. The lifted productPanteleev–Kalachev: base-matrix entries are taken from a ring R (circulants, a group algebra), the ⊗ of the product construction is realised by ring multiplication, and transposes carry the ring's involution (x ↦ x⁻¹). The hypergraph product is the special case R = GF(2). replaces that I by any permutation matrix, or a sum of them: base-matrix entries are no longer 0/1 but polynomials in the ring R of “BB Codes · High-School Edition”. Each copy is now translated by a different amount, so the checks are “staggered”. Commutation still holds — as long as the ring is commutative, §2.2's two mixed terms remain identical and cancel (the transpose must carry x → x⁻¹, a reversed translation, just like the Aᵀ of “BB Codes · High-School Edition”, §2.3).

取两个 1 × 1 的底矩阵 [a] 与 [b]，a、b 是环 R = GF(2)[x, y]/(x^l − 1, y^m − 1) 里的多项式。按超图积的模板：n = 1·1 + 1·1 = 2 个「格」，每格提升成 lm 个比特（环 R 的维数），共 2lm；H_X = [a | b]，H_Z = [bᵀ | aᵀ]。这就是《BB 码 · 高中数学版》的 BB 码——两个多项式、两层比特、交换转置，全部从提升积的模板里掉出来。只用一个变量 x（R = GF(2)[x]/(x^l − 1)）就是广义 bicycle 码（这一族可以追溯到 MacKay 等 2004 年的工作，Kovalev 与 Pryadko 2012 年称之为「MacKay 等的广义 bicycle 码」；Panteleev 与 Kalachev 2019 年给出了一批性能很好的短码实例），再退回 b = aᵀ 就是 MacKay 的 bicycle 码。下面的实验台是BB 教程的构造器，预设为 gross：请把它读成「两个 1 × 1 底矩阵的提升积」。

Take two 1 × 1 base matrices [a] and [b] with a, b polynomials in the ring R = GF(2)[x, y]/(x^l − 1, y^m − 1). By the hypergraph template: n = 1·1 + 1·1 = 2 “cells”, each lifted into lm qubits (the dimension of R), 2lm in all; H_X = [a | b], H_Z = [bᵀ | aᵀ]. This is the BB code of “BB Codes · High-School Edition” — two polynomials, two layers, swapped transposes, all falling out of the lifted-product template. With a single variable x (R = GF(2)[x]/(x^l − 1)) it is a generalized bicycle code (the family goes back to the work of MacKay et al. in 2004 — Kovalev and Pryadko in 2012 call them “generalized bicycle codes by MacKay et al.” — and Panteleev and Kalachev in 2019 constructed a set of short examples that perform very well), and with b = aᵀ MacKay's bicycle code. The bench below is the BB tutorial's constructor preset to gross: read it as “the lifted product of two 1 × 1 base matrices”.

超图积用两条长 N、各有 m 条检查的因子造出 N² + m² 个比特，码率被「积」摊薄：k ≈ (RN)² 里的 R² 是两个码率相乘。提升积把「乘积结构」塞进了环的平移里：底矩阵可以很小（1 × 1、2 × 3……），每个格子提升成 |G|群 G 的元素个数（群的阶）。 个比特（G 是提升用的群，环 R = GF(2)[G] 的维数就是 |G|），n = (n₁n₂ + m₁m₂)·|G|。gross 码 n = 2·72 = 144、k = 12、d = 12。同样不超过 144 个比特的超图积连 d = 12 都做不到：d 取的是非空扇区里的经典距离，要 d ≥ 12，两个因子（或两个转置码）的长度都至少是 12，光「比特 × 比特」（或「检查 × 检查」）一块就要 12 × 12 = 144 个比特，另一块至少还要 1 个。（单比码率，超图积并不差：HGP(Hamming, Hamming) 的 16/58 比 gross 的 1/12 还高，但它的 d 只有 3。）这就是为什么有限尺寸下最好的 qLDPC 块几乎都来自提升积或它的两块群代数亲戚（《BB 码 · 高中数学版》的秩亏损分析就是提升积在 1 × 1 时的 k 公式）。

A hypergraph product spends N² + m² qubits on two length-N factors with m checks each, and the “product” dilutes the rate: the R² in k ≈ (RN)² is two rates multiplied. The lifted product tucks the product structure into the ring's translations: base matrices can be tiny (1 × 1, 2 × 3, …), each cell lifted into |G|The number of elements of the group G (its order). qubits (G the lifting group; the ring R = GF(2)[G] has dimension |G|), n = (n₁n₂ + m₁m₂)·|G|. The gross code has n = 2·72 = 144, k = 12 and d = 12. A hypergraph product with at most 144 qubits cannot even reach d = 12: d is a classical distance of a non-empty sector, so d ≥ 12 needs both factors (or both transpose codes) to have length at least 12, which makes the “bit × bit” (or “check × check”) block alone 12 × 12 = 144 qubits, with at least one more in the other block. (On rate alone the hypergraph product is not bad: HGP(Hamming, Hamming) has 16/58, more than gross’s 1/12, but its d is only 3.) This is why the best finite-size qLDPC blocks almost all come from lifted products or their two-block group-algebra relatives (the rank-deficit analysis of “BB Codes · High-School Edition” is the lifted product's k formula in the 1 × 1 case).

《BB 码 · 高中数学版》6.6 节说过，固定项数、无限放大环面的 BB 码渐近是坏的（Postema 与 Kokkelmans 2025）：可交换的 Z_l × Z_m 太「规则」，低重量的逻辑算符总能沿某个方向铺开。突破来自换环：Panteleev 与 Kalachev 2021 年用非阿贝尔群的群代数做提升——让一个因子从左乘、另一个从右乘，左乘与右乘总是对易，所以 H_XH_Zᵀ = 0 不靠交换律也成立——底矩阵取自扩展图上的经典 Tanner 码，证明所得的量子码族是渐近好的——k ∝ n 且 d ∝ n——从而解决了 qLDPC 猜想；同一篇论文顺带解决了经典编码论里「局部可测试码」的一个多年猜想。非阿贝尔性让平移不再两两对易，逻辑算符找不到可以「铺开」的方向；扩展性则保证：一个错误去掉稳定子成分之后若仍然较轻，它惊动的检查数与这个「约化重量」成比例（稳定子本身不亮任何检查，所以必须先去掉，见 3.4 节）。这两个成分下一章会以另一种形式再出现。

“BB Codes · High-School Edition”, §6.6 noted that BB codes with a fixed number of terms on an ever-larger torus are asymptotically bad (Postema and Kokkelmans 2025): the commutative Z_l × Z_m is too “regular”, and low-weight logicals can always spread along some direction. The breakthrough came from changing the ring: in 2021 Panteleev and Kalachev lifted over the group algebra of a non-abelian group — one factor acting by left multiplication, the other by right multiplication, which always commute, so H_XH_Zᵀ = 0 survives without commutativity — with base matrices taken from classical Tanner codes on expander graphs, and proved the resulting quantum family asymptotically good — k ∝ n and d ∝ n — settling the qLDPC conjecture; the same paper also settled a long-standing conjecture about locally testable codes in classical coding theory. Non-commutativity leaves logicals no direction to “spread” along; expansion guarantees that an error which is still light after its stabilizer part is removed lights a number of checks proportional to this “reduced weight” (a stabilizer itself lights no check, which is why it must be removed first; see §3.4). Both ingredients return in another guise in the next chapter.

经典的 Tanner 码Tanner code：在一张图的每个顶点上放一条小的局部码，要求与该顶点相连的比特满足这条局部码。图是扩展图时，得到好的经典 LDPC 码（Sipser–Spielman）。把一条小码「贴」在一张大图的每个顶点上：比特住在边上，每个顶点要求它周围的比特构成局部码的一个码字。Leverrier 与 Zémor 2022 年的量子版把舞台换成 Dinur 等人的左右 Cayley 复形。它由一个群 G（群见 4.4 节的补课）和两小组群元素 A、B 造出，分三步。① 顶点有两类，各是 G 的一份拷贝：V₀ 里的顶点记作 (h, 0)，V₁ 里的记作 (h, 1)，h 取遍 G，共 2|G| 个顶点。② 边只连不同类的顶点：(h, 0) 与 (ah, 1) 之间连一条 A 边（a ∈ A，从左边乘 a），(h, 0) 与 (hb, 1) 之间连一条 B 边（b ∈ B，从右边乘 b）。③ 正方形是四个顶点 (g, 0)、(ag, 1)、(gb, 1)、(agb, 0)，两条 A 边、两条 B 边围成一圈（下图）。

A classical Tanner codePlace a small local code at every vertex of a graph and require the bits attached to that vertex to satisfy it. When the graph is an expander this gives good classical LDPC codes (Sipser–Spielman). “glues” a small code onto every vertex of a large graph: bits live on edges, and each vertex demands that its surrounding bits form a codeword of the local code. Leverrier and Zémor's 2022 quantum version changes the stage to the left-right Cayley complex of Dinur et al. It is built from a group G (groups: see the catch-up in §4.4) and two small sets A and B of group elements, in three steps. ① There are two classes of vertices, each a copy of G: the vertices of V₀ are written (h, 0), those of V₁ are written (h, 1), with h ranging over G, 2|G| vertices in all. ② Edges join only vertices of different classes: (h, 0) and (ah, 1) are joined by an A-edge (a ∈ A, multiplying by a on the left), (h, 0) and (hb, 1) by a B-edge (b ∈ B, multiplying by b on the right). ③ A square is the four vertices (g, 0), (ag, 1), (gb, 1), (agb, 0), bounded by two A-edges and two B-edges (figure below).

对 A、B 的要求：各自对取逆封闭（a 在 A 里，a⁻¹ 也在），大小同为 Δ；两张 Cayley 图（h 连 ah 的图、h 连 hb 的图）都是扩展图，而且是谱意义下接近最优的那种（这也保证了 A、B 各自反复相乘能走遍整个群，即它们是生成元）；再加一个「完全不共轭」条件：对所有 g、a、b，ag ≠ gb。最后这条保证一个正方形的四个顶点互不相同：两个 V₁ 顶点 ag 与 gb 不同就是这条本身；两个 V₀ 顶点若相同，agb = g 即 ag = gb⁻¹，而 b⁻¹ 也在 B 里，同样被排除。反例：G 可交换且 a = b⁻¹ 时（比如整数 mod 7 的加法，a = 1、b = −1，这时 agb 就是 g + 1 − 1 = g），「正方形」塌掉。

The conditions on A and B: each is closed under inverses (if a is in A, so is a⁻¹), both have the same size Δ; the two Cayley graphs (h joined to ah, and h joined to hb) are expanders, of the spectrally near-optimal kind (which also makes A and B each generators: repeated products of either reach the whole group); and a “total no-conjugacy” condition: ag ≠ gb for all g, a, b. The last one makes the four vertices of a square distinct: the two V₁ vertices ag and gb differ by the condition itself; the two V₀ vertices coincide only if agb = g, i.e. ag = gb⁻¹, and b⁻¹ is also in B, so that is excluded too. Counterexample: in a commutative G with a = b⁻¹ (say the integers mod 7 under addition, a = 1, b = −1, where agb is g + 1 − 1 = g) the “square” collapses.

量子比特住在正方形上，每个正方形一个。从一个 V₀ 顶点出发，(a, b) 的 Δ² 种选法各给一个正方形，所以每个顶点周围恰好 Δ² 个比特，可以排成一张 Δ × Δ 的表：行标 a、列标 b。每个正方形有两个 V₀ 顶点，被数了两次，所以 n = Δ²|G|/2。检查放在顶点上，由两条小的经典码决定：C_A 是长为 Δ 的二元线性码，它的 Δ 个比特位用 A 的元素编号（每个 a ∈ A 一位）；C_B 同样长为 Δ，比特位用 B 的元素编号。V₀ 顶点周围那张表上，张量码 C_A ⊗ C_B（每一列是 C_A 的码字、每一行是 C_B 的码字）的每个码字给一条 X 检查，作用在码字取 1 的那些比特上；V₁ 顶点上，两个对偶码上标 ⊥ 读「对偶码」：与 C 的每个码字都正交（逐位相乘再求和为 0，mod 2）的全部向量组成的码。的张量积 C_A^⊥ ⊗ C_B^⊥（不是张量码本身的对偶）的每个码字给一条 Z 检查。

Qubits live on squares, one per square. From a V₀ vertex, each of the Δ² choices of (a, b) gives one square, so every vertex has exactly Δ² qubits around it, which can be arranged in a Δ × Δ table: rows labelled by a, columns by b. Each square has two V₀ vertices and is counted twice, so n = Δ²|G|/2. Checks sit on vertices and are fixed by two small classical codes: C_A is a binary linear code of length Δ whose Δ bit positions are labelled by the elements of A (one position per a ∈ A); C_B likewise has length Δ, with positions labelled by B. On the table around a V₀ vertex, every codeword of the tensor code C_A ⊗ C_B (every column a codeword of C_A, every row a codeword of C_B) gives an X check acting on the qubits where the codeword is 1; on a V₁ vertex, every codeword of the tensor product of the dual codesSuperscript ⊥, read “dual code”: all vectors orthogonal to every codeword of C (bitwise product summed to 0 mod 2). C_A^⊥ ⊗ C_B^⊥ (not the dual of the tensor code itself) gives a Z check.

算一个。取 Δ = 3，A = {a₁, a₂, a₃}，B = {b₁, b₂, b₃}，C_A 与 C_B 都取长为 3 的偶校验码 {000, 110, 101, 011}（真正的构造要用 Δ 大得多、距离也大的小码，这里只演示记账）。固定一个 V₀ 顶点 v₀ = (g, 0)，把选 (a, b) 得到的正方形 {(g,0), (ag,1), (gb,1), (agb,0)} 上的比特记作 q(a, b)。取 u = 110 ∈ C_A、v = 101 ∈ C_B，张量积 u ⊗ v 在 (a, b) 格上的值是 u_a · v_b，列成下表。每一行是 v 或 000，都在 C_B 里；每一列是 u 或 000，都在 C_A 里，所以 u ⊗ v 是张量码的码字（张量码由这样的乘积张成，这里维数 2 × 2 = 4）。它有四个 1，于是给出 v₀ 上的一条 X 检查 X_q(a₁,b₁) X_q(a₁,b₃) X_q(a₂,b₁) X_q(a₂,b₃)，重量 4。对易也可以在这里核对：C_A^⊥ = C_B^⊥ = {000, 111}，经 B 边 b₁ 相邻的 V₁ 顶点上的 Z 检查（取 111 ⊗ 111）在 b₁ 那一列上是 111，与 X 检查在这一列上的 110 重叠 2 次，偶数。

Work one. Take Δ = 3, A = {a₁, a₂, a₃}, B = {b₁, b₂, b₃}, and let C_A and C_B both be the length-3 even-weight code {000, 110, 101, 011} (the real construction needs a much larger Δ and small codes of large distance; this only shows the bookkeeping). Fix a V₀ vertex v₀ = (g, 0) and write q(a, b) for the qubit on the square {(g,0), (ag,1), (gb,1), (agb,0)} chosen by (a, b). Take u = 110 ∈ C_A and v = 101 ∈ C_B; the tensor product u ⊗ v has value u_a · v_b in cell (a, b), tabulated below. Every row is v or 000, both in C_B; every column is u or 000, both in C_A; so u ⊗ v is a codeword of the tensor code (which is spanned by such products, of dimension 2 × 2 = 4 here). It has four 1s, and so gives the X check X_q(a₁,b₁) X_q(a₁,b₃) X_q(a₂,b₁) X_q(a₂,b₃) on v₀, of weight 4. Commutation can be checked here too: C_A^⊥ = C_B^⊥ = {000, 111}; the Z check (from 111 ⊗ 111) on the V₁ vertex joined to v₀ by the B-edge b₁ is 111 on the column b₁, which overlaps the X check’s 110 on that column twice, an even number.

为什么对易：一条 X 检查（在 V₀ 顶点 v₀）与一条 Z 检查（在 V₁ 顶点 v₁）要有公共比特，v₀ 与 v₁ 必须相邻。若它们由 B 边相连（v₁ = v₀ 右乘 b），公共的正方形恰好是 b 固定、a 取遍 A 的那一列；X 检查在这一列上是 C_A 的码字，Z 检查在这一列上是 C_A^⊥ 的码字，两者按定义正交，重叠偶数次。由 A 边相连时换成一行、C_B 与 C_B^⊥，道理相同。

Why they commute: an X check (at a V₀ vertex v₀) and a Z check (at a V₁ vertex v₁) can share qubits only if v₀ and v₁ are adjacent. If they are joined by a B-edge (v₁ is v₀ multiplied by b on the right), the shared squares are exactly the column with that b fixed and a ranging over A; on this column the X check is a codeword of C_A and the Z check a codeword of C_A^⊥, orthogonal by definition, so they overlap an even number of times. For an A-edge it is a row, with C_B and C_B^⊥, by the same argument.

当两张 Cayley 图是扩展图、局部码满足一个「鲁棒性」条件时，他们证明所得的码族是渐近好的：k ∝ n 且 d ∝ n。Leverrier 与 Zémor 随后给出能纠正线性权重错误的线性时间译码器；Dinur、Hsieh、Lin 与 Vidick 同年用相近的构造得到另一族自带线性时间译码器的好码。QEC-Bank 的 quantum_tanner 条目是一个 T1 见证：n = 392、k = 48，本页无法验证的 d 记为「?」——这个「?」是诚实的：小实例的距离没有被穷举，渐近定理也不给出具体的数。

When the two Cayley graphs are expanders and the local codes satisfy a “robustness” condition, they proved the family asymptotically good: k ∝ n and d ∝ n. Leverrier and Zémor then gave a linear-time decoder that corrects errors of linear weight; the same year Dinur, Hsieh, Lin and Vidick obtained another good family from a closely related construction, with linear-time decoding built in. The QEC-Bank's quantum_tanner entry is a T1 witness: n = 392, k = 48, and the d this page cannot verify is recorded as “?” — an honest mark: the small instance's distance has not been enumerated, and the asymptotic theorem gives no concrete number.

超图积是「两条码相乘」；Bravyi 与 Hastings 2013 年的同调积homological product：把两个 CSS 码各看作一个链复形（《BB 码 · 高中数学版》4.4 节折叠盒里的 R → R² → R），取两个复形的张量积得到新的复形，再读出量子码。因子是随机码时，得到常数码率、线性距离、检查重量约 √n 的码。是「两个量子码相乘」：把两个 CSS 码各写成链复形，取张量积。用两个随机的量子码做因子，他们得到了第一族常数码率、线性距离的量子码，检查重量约 √n——不再是 LDPC，但比此前「检查重量 ∝ n」的随机码前进了一大步，也是通往好 qLDPC 码路上的重要中继。QEC-Bank 有三个小见证：homological_product [[25,1,4]]、square_homological_product [[25,1,4]]、double_homological_product [[33,1,4]]，d 均穷举验证。

A hypergraph product multiplies “two codes”; Bravyi and Hastings' 2013 homological productView two CSS codes as chain complexes (the fold in “BB Codes · High-School Edition”, §4.4: R → R² → R), take the tensor product of the complexes, and read off a quantum code. With random factor codes this gives constant rate, linear distance and check weight about √n. multiplies “two quantum codes”: write each CSS code as a chain complex and take their tensor product. With two random quantum codes as factors they obtained the first family with constant rate and linear distance at check weight about √n — no longer LDPC, but a big step past random codes with check weight ∝ n, and an important waypoint toward good qLDPC codes. The QEC-Bank has three small witnesses: homological_product [[25,1,4]], square_homological_product [[25,1,4]] and double_homological_product [[33,1,4]], all with exhaustively verified d.

Hastings 2016 年把环面码搬到高维流形上。在高维环面 Tⁿ 上，若一个关于最小体积曲面的几何猜想成立，就得到检查重量只有对数级、距离达到 n^1−ε（ε 任意小）的 CSS 码。在高维球面的积 Sⁿ × Sⁿ 上——这正是 QEC-Bank 条目名字里的「超球积」——则无条件地得到另一族码：检查重量对数级，距离 ∝ √n，并且作为「量子局部可测试码」有逆多对数级的健全性（离码字越远的态，随机抽一条检查抓到它的概率越大）。前者把「用几何造码」推到了接近线性距离的边缘，后者的价值在可测试性而不在距离。QEC-Bank 的 hypersphere_product 见证是 [[128,2,8]]（k = 2 来自两个球面因子各贡献一个逻辑比特；d 为文献声称）。

Hastings in 2016 moved toric codes onto high-dimensional manifolds. On high-dimensional tori Tⁿ, assuming a geometric conjecture about minimal-volume surfaces, this gives CSS codes with only logarithmic check weight and distance n^1−ε for arbitrarily small ε. On products of hyperspheres Sⁿ × Sⁿ — the “hypersphere product” in the QEC-Bank entry’s name — it gives, unconditionally, a different family: logarithmic check weight, distance ∝ √n, and an inverse-polylogarithmic soundness as a “quantum locally testable code” (the farther a state is from the code, the likelier a random check catches it). The first took “codes from geometry” to the brink of linear distance; the second’s value lies in testability rather than distance. The QEC-Bank’s hypersphere_product witness is [[128,2,8]] (k = 2 because each sphere factor contributes one logical qubit; d claimed from the literature).

三个 T1 条目代表三种「让 qLDPC 上机」的思路。lacross（Pecorari 等 2024，[[34,4,?]]）为长程连接的中性原子阵列设计高码率码，把检查的非局域性匹配到原子阵列真实能做的耦合模式上。SC-qLDPC（Hagiwara 与 Imai 2011，[[42,4,?]]）把经典编码论里的「空间耦合」搬到准循环量子码上，让检查沿一条带状结构逐段耦合。hierarchical（Pattison 等 2023，[[35,2,?]]）走另一条路：把一个 qLDPC 码与表面码级联，用局域门模拟非局域检查，以时间换连接——正是第 1 章 Delfosse–Beverland–Tremblay 界所允许的那种代价。三者的 d 在 QEC-Bank 里都是问号：构造可执行、n 与 k 可复算，距离尚无证书。

Three T1 entries stand for three ways of “getting qLDPC onto hardware”. lacross (Pecorari et al. 2024, [[34,4,?]]) designs high-rate codes for long-range-connected neutral-atom registers, matching the checks' nonlocality to the coupling patterns atom arrays can actually realise. SC-qLDPC (Hagiwara and Imai 2011, [[42,4,?]]) transplants classical coding theory's “spatial coupling” onto quasi-cyclic quantum codes, coupling checks segment by segment along a band. hierarchical codes (Pattison et al. 2023, [[35,2,?]]) take another road: concatenate a qLDPC code with surface codes and simulate the nonlocal checks with local gates, trading time for connectivity — exactly the price Chapter 1's Delfosse–Beverland–Tremblay bound permits. All three have d as a question mark in the QEC-Bank: constructions executable, n and k recomputable, distance without a certificate.

本章只讲 BP 与 OSD 的要点。从概率推断讲起的完整讲解、逐步演示的 BP 与 OSD 实验台、各阶 OSD 与实际参数、电路级的探测器错误模型，见《BP-OSD 译码器 · 高中数学版》。

This chapter gives only the gist of BP and OSD. The full treatment, from probabilistic inference to step-by-step BP and OSD benches, the OSD orders, the parameters used in practice and circuit-level detector error models, is in “The BP-OSD Decoder · High-School Edition”.

在 Tanner 图上，每个比特带一个先验：以概率 p 出错，用对数似然比 ln((1−p)/p) 表示（《译码器 · 高中数学版》1.3 节的权重）。一轮 BP 分两步。检查到比特：一条亮着的检查告诉它的每个比特「除你之外，其他人看起来都没错，所以大概是你」；一条没亮的检查告诉大家「你们里出错的个数是偶数」。比特到检查：每个比特把自己收到的所有意见（除了问话的那条检查）加起来回传。几轮后，每个比特把全部意见加上先验做硬判决；若判决出的错误恰好解释所有警报，停止。「意见」具体怎么算有两种常用规则。和积（sum-product）规则按概率精确合并：检查发给比特 i 的消息 = (−1)^症状 × 2 artanh(∏ tanh(m_j/2))，乘积取遍其余比特发来的消息 m_j。在没有圈的图上，用和积规则跑足轮数（让每条消息传遍整棵树）之后，算出的正是每个比特单独出错的精确概率（逐比特最可能的取值），这还不等于押整类错误的最大似然译码。最小和（min-sum）是它的省算版，下面马上用到；它即使在树上也只是近似。qLDPC 的 Tanner 图有很多圈，这时两种规则都只是近似。

手算一个。三位重复码，检查 C1 = b1 ⊕ b2、C2 = b2 ⊕ b3；症状是 C1 亮、C2 不亮；p = 0.1，每个比特的先验 ln 9 ≈ +2.2（正 = 相信没错）。消息用不带缩放因子的最小和规则来算（下面的实验台用的是另一种变体，见本节末）：检查 C 发给比特 i 的消息 = (−1)^{C 的症状} × （C 的其余比特发来的消息的符号之积）× （这些消息里绝对值最小的那个）。症状取 1（亮）或 0（不亮）。读法：绝对值是其余比特里最不可靠的那个的可靠度，一条推理链只和最弱的一环一样可靠；符号在数「检查亮着」与「其余比特里有几个相信自己错了」，合起来是奇数，就告诉 i「你大概错了」（负）。

例：一条没亮的检查连着 b1、b2、b3，b2 发来 −3（它相信自己错了），b3 发来 +1.5。它对 b1 说 (+1) × (−1)(+1) × min(3, 1.5) = −1.5：出错的个数得是偶数，b2 已经错了，所以 b1 大概也错了，但把握只有 b3 那么强。只看「亮不亮」定符号会给出 +1.5，方向正好反了。精确的和积规则给出 −2 artanh(tanh(1.5) × tanh(0.75)) ≈ −1.31：符号相同，最小和把把握估高了一点（最小和一贯如此，因为它只看最弱的一环、忽略其余环节也不完全可靠）。

回到重复码：下面用到的传入消息都是正的，符号只由亮不亮决定。第一轮：C1 对 b1 说 −2.2（它另一个比特 b2 的可靠度是 2.2），b1 的总意见 2.2 − 2.2 = 0，打平。b2 从 C2 听到 +2.2，于是第二轮它告诉 C1 的可靠度是 2.2 + 2.2 = 4.4，C1 再对 b1 说 −4.4：b1 的总意见 2.2 − 4.4 = −2.2，判为出错。b2 的总意见是 2.2（先验）− 2.2（C1）+ 2.2（C2）= +2.2，没错；b3 也是没错。判决「只有 b1 错」正好解释症状，停止。这张图没有圈，每条检查又只连两个比特（「其余比特」只有一个，取最小值不丢信息），所以这里最小和与和积给出同样的数：b1 的 −2.2 就是精确值 ln(0.1/0.9)，因为与症状相容的只有「b1 错」和「b2、b3 都错」两种，后验概率之比 0.9 : 0.1。

下面的实验台用归一化最小和：把上面的最小和消息再乘一个固定因子 α = 0.8，抵消最小和的过度自信；比如上一段例子里的 −1.5 变成 −1.2。它是近似规则，给出的数字不是精确概率。

On the Tanner graph every qubit carries a prior: in error with probability p, expressed as the log-likelihood ratio ln((1−p)/p) (the weight of “Decoders · High-School Edition”, §1.3). One BP round has two steps. Check to qubit: a lit check tells each of its qubits “everyone but you looks fine, so it is probably you”; an unlit check tells everyone “an even number of you are in error”. Qubit to check: each qubit sums all opinions it received (except from the check asking) and sends that back. After a few rounds each qubit adds all opinions to its prior and takes a hard decision; if the decided error explains every alarm, stop. There are two common rules for computing an opinion. The sum-product rule combines probabilities exactly: the message a check sends to qubit i = (−1)^syndrome × 2 artanh(∏ tanh(m_j/2)), the product running over the messages m_j from its other qubits. On a cycle-free graph, sum-product run for enough rounds (until every message has crossed the whole tree) gives exactly the probability that each qubit individually is in error (the most likely value bit by bit), which is still not the class-level maximum-likelihood decoding. Min-sum is its cheaper approximation, used right below; it is approximate even on a tree. On qLDPC Tanner graphs, full of cycles, both rules are only approximate.

Work one by hand. The three-bit repetition code with checks C1 = b1 ⊕ b2 and C2 = b2 ⊕ b3; the syndrome has C1 lit and C2 unlit; p = 0.1, so each bit’s prior is ln 9 ≈ +2.2 (positive = believed fine). Messages use the min-sum rule without a scaling factor (the bench below uses a variant, see the end of this section): the message check C sends to bit i = (−1)^{syndrome of C} × (product of the signs of the messages from C’s other bits) × (the smallest absolute value among those messages). The syndrome is 1 (lit) or 0 (unlit). How to read it: the size is the reliability of the least reliable other bit, since a chain of reasoning is only as reliable as its weakest link; the sign counts “the check is lit” plus “how many other bits believe they are wrong”, and if the total is odd it tells i “you are probably wrong” (negative).

Example: an unlit check on b1, b2, b3 receives −3 from b2 (b2 believes it is wrong) and +1.5 from b3. It tells b1 (+1) × (−1)(+1) × min(3, 1.5) = −1.5: the number of errors must be even, b2 is already wrong, so b1 is probably wrong too, but only as surely as b3 is right. Setting the sign from “lit or not” alone would give +1.5, exactly the wrong direction. The exact sum-product rule gives −2 artanh(tanh(1.5) × tanh(0.75)) ≈ −1.31: the same sign, with min-sum a little overconfident (it always is, because it looks only at the weakest link and ignores that the other links are not fully reliable either).

Back to the repetition code: every incoming message used below is positive, so the sign depends only on lit or unlit. Round one: C1 tells b1 −2.2 (its other bit b2 has reliability 2.2), and b1’s total is 2.2 − 2.2 = 0, a tie. b2 hears +2.2 from C2, so in round two it reports reliability 2.2 + 2.2 = 4.4 to C1, which now tells b1 −4.4: b1’s total is 2.2 − 4.4 = −2.2, decided wrong. b2’s total is 2.2 (prior) − 2.2 (C1) + 2.2 (C2) = +2.2, fine; b3 is fine too. The decision “only b1 is wrong” explains the syndrome; stop. This graph has no cycles and every check has only two bits (a single “other bit”, so taking the minimum loses nothing), so here min-sum and sum-product give the same numbers: b1’s −2.2 is the exact value ln(0.1/0.9), because only two errors fit the syndrome, “b1 wrong” and “b2 and b3 both wrong”, with posterior odds 0.9 : 0.1.

The bench below uses normalized min-sum: every min-sum message above is multiplied by a fixed factor α = 0.8 to offset min-sum’s overconfidence; the −1.5 of the example above becomes −1.2. It is an approximate rule, and its numbers are not exact probabilities.

第一个敌人是短圈：四步的圈（比特–检查–比特–检查回到起点）就是两条检查共用两个比特。消息沿圈绕一圈又回到自己手里，同一条证据被重复计算，信心被自我放大。要分清是哪张图。把 X 检查与 Z 检查画进同一张图，任何 CSS 码都满是四步圈：一条 X 检查与一条 Z 检查只要有重叠，就必须重叠偶数个（至少 2 个）比特才能对易；在超图积里每对有重叠的 X、Z 检查恰好重叠 2 个。但本实验台的 BP 只用一种检查：它读 Z 检查的症状、找 X 错误，在只有 Z 检查的 Tanner 图上传消息。这张图有没有四步圈，取决于因子。用 2.1 节的记号，两条 Z 检查共用两个比特只有两种可能：它们在同一行，且 H₂ 里有两行共用两列；或者它们在「检查 × 检查」块的同一列，且 H₁ 里有两列共用两行。所以 HGP(rep₃, rep₃)（表面码）的 Z 图没有四步圈：重复码的两行最多共用一列，两列最多共用一行。Hamming [7,4,3] 的 3 × 7 矩阵把 7 个非零三位向量各用一次作列，列 110 与 111 共用前两行；于是 HGP(Hamming, Hamming) 的 Z 图有 30 对共用两个比特的检查（7 × 3 + 3 × 3，本页的核对脚本逐对数过）。

The first enemy is short cycles: a four-step cycle (qubit–check–qubit–check back to the start) is two checks sharing two qubits. A message travels round and returns to its sender, the same evidence is counted twice, and confidence amplifies itself. Be clear about which graph. Draw X checks and Z checks in one graph and every CSS code is full of four-step cycles: an X check and a Z check that overlap at all must overlap in an even number (at least 2) of qubits to commute, and in a hypergraph product every overlapping X/Z pair overlaps in exactly 2. But the BP on this bench uses one check type only: it reads the Z-check syndrome to find X errors and passes messages on the Tanner graph of the Z checks alone. Whether that graph has four-step cycles depends on the factors. In the notation of §2.1, two Z checks can share two qubits in only two ways: they lie in the same row and two rows of H₂ share two columns, or they lie in the same column of the check × check block and two columns of H₁ share two rows. So the Z graph of HGP(rep₃, rep₃) (the surface code) has no four-step cycle: two rows of a repetition code share at most one column, and two columns share at most one row. The 3 × 7 Hamming [7,4,3] matrix uses each of the 7 nonzero three-bit vectors once as a column, so columns 110 and 111 share the first two rows; HGP(Hamming, Hamming) therefore has 30 pairs of Z checks sharing two qubits (7 × 3 + 3 × 3, counted pair by pair by this page's check script).

第二个敌人是量子特有的退化：两个不同的错误若相差一个稳定子，效果完全相同，译码器选哪个都对——但 BP 不知道这一点，它把置信在两个等价错误之间对半分，硬判决时两边都不选，或者各选一半，得到一个既不是 A 也不是 B 的混合，症状清不掉。到实验台上选 HGP(Hamming, Hamming) [[58,16,3]] 多试几次「BP 跑完」，看这两种失败长什么样：

The second enemy is quantum-specific degeneracy: two different errors differing by a stabilizer have identical effect and either is a correct answer — but BP does not know this; it splits belief between the two equivalent errors, and at the hard decision picks neither or half of each, producing a hybrid that is neither A nor B and leaves the syndrome uncleared. On the bench choose HGP(Hamming, Hamming) [[58,16,3]] and press “Run BP to the end” several times to see both failures:

Panteleev 与 Kalachev 2019 年的解法：BP 卡住时不丢掉它的输出，而是把它当作排序。按 BP 给出的「出错可能性」从高到低排列比特，取前 rank(H) 个线性独立的列作为「可能出错的位置」，在这些位置上解线性方程 He = s（高斯消元），其余位置设为 0。这总能给出一个消掉症状的修正；译码成功当且仅当残差是稳定子——BP 的排序越准，这件事越常发生，但没有保证。这就是 OSDordered-statistics decoding：按可靠度排序后在基集上解 He = s。0 阶只解一次，没被选中的 n − rank(H) 个位置（非主元位置）全设为 0。更高阶让非主元位置也可以取 1：把非主元位置按同一个 BP 排序排好（最可能出错的在前）。组合扫描 OSD（OSD-CS）试遍「只翻其中一个」的所有情形，以及「在前 λ 个里翻两个」的所有情形（Roffe 等取 λ = 60），每种情形都重新解出主元位置，最后留下总重量最小的解。——本页只实现最简单的 0 阶。按实验台的「OSD 收尾」，再用「蒙特卡洛」比较 BP 单独与 BP+OSD 的失败次数：OSD 把「无答案」变成「有答案」，答案的对错取决于码的退化程度与 OSD 的阶数。Roffe、White、Burton 与 Campbell 2020 年把 BP+OSD 跑遍整个 qLDPC 版图，用组合扫描阶的 OSD 让环面码达到约 9.9% 的码容量阈值——与《译码器 · 高中数学版》里匹配译码的 10.3% 只差一点。

Panteleev and Kalachev's 2019 remedy: when BP stalls, keep its output as an ordering. Sort qubits by BP's “probability of error” from high to low, take the first rank(H) linearly independent columns as the “likely error positions”, solve the linear system He = s on them (Gaussian elimination) and set the rest to 0. This always yields a repair that clears the syndrome; decoding succeeds exactly when the residual error is a stabilizer — the better BP's ordering, the more often that happens, but there is no guarantee. That is OSDOrdered-statistics decoding: solve He = s on a basis set chosen in reliability order. Order 0 solves once and sets the n − rank(H) positions that were not chosen (the non-pivot positions) all to 0. Higher orders let non-pivot positions be 1 as well: sort the non-pivot positions by the same BP ordering (most likely in error first). Combination-sweep OSD (OSD-CS) tries every case “flip exactly one of them” and every case “flip two among the first λ” (Roffe et al. use λ = 60), re-solves the pivot positions for each case, and keeps the solution of smallest total weight. — this page implements only the simplest order 0. Press “Finish with OSD” on the bench, then “Monte-Carlo” to compare failures of BP alone and BP+OSD: OSD turns “no answer” into “an answer”, and whether the answer is right depends on the code's degeneracy and the OSD order. Roffe, White, Burton and Campbell ran BP+OSD across the whole qLDPC landscape in 2020, reaching about 9.9% code-capacity threshold on the toric code with combination-sweep OSD — just below the 10.3% for matching in “Decoders · High-School Edition”.

量子扩展码（第 3 章）有一个不需要消息传递的译码器：反复寻找一小组比特（在一条检查的支撑范围内），翻转它们能让亮起的检查数严格减少，就翻；直到没有这样的小组。Leverrier、Tillich 与 Zémor 证明，只要因子图的度数固定、两侧都足够扩展，这个贪心过程在线性时间内纠正每一个重量不超过 c√n 的对抗性错误（c 是由度数与扩展参数决定的常数）。原因是 3.4 节的警报下限：约化重量低于一个 ∝ √n 的门槛时，亮起的检查至少是约化重量的 1/3，所以只要还有警报，就总能找到能减少警报的翻转；剩下的稳定子成分不亮检查，也不需要纠正。Fawzi、Grospellier 与 Leverrier 进一步证明它对随机错误也有阈值，并由此得到常数开销的容错计算。它是《译码器 · 高中数学版》里并查集译码器精神的远亲：局部、几乎不算术、靠图的结构保证正确。

Quantum expander codes (Ch. 3) have a decoder that needs no message passing: repeatedly look for a small set of qubits (within one check's support) whose flip strictly reduces the number of lit checks, and flip it; stop when no such set remains. Leverrier, Tillich and Zémor proved that when the factor graph has fixed degrees and enough expansion on both sides, this greedy procedure corrects every adversarial error of weight at most c√n in linear time (c a constant set by the degrees and expansion parameters). The reason is the alarm floor of §3.4: when the reduced weight is below a threshold ∝ √n, the lit checks number at least one third of the reduced weight, so as long as any alarm is on, a flip that reduces alarms exists; the stabilizer part left over lights no check and needs no correction. Fawzi, Grospellier and Leverrier further showed it has a threshold against random errors, hence constant-overhead fault tolerance. It is a distant cousin of the union-find decoder of “Decoders · High-School Edition” in spirit: local, almost arithmetic-free, correct by virtue of the graph's structure.

《译码器 · 高中数学版》的五个限定项在这里同样适用，且更重要，因为 qLDPC 的数字常常跨模型混用。可核对的几条：环面码 + BP-OSD + 完美测量 ≈ 9.9%（Roffe 等 2020）；BB 家族 + 深度 7 电路 + 电路级噪声 + BP-OSD ≈ 0.8%（Bravyi 等 2024，译码器教程账本的语法）；量子扩展码 + small-set-flip 在随机噪声下存在阈值（Fawzi–Grospellier–Leverrier 2018，是存在性证明而非具体数字）。任何「qLDPC 码的阈值是 X%」若不带模型，都是不完整的句子。此外，qLDPC 译码还有一个匹配没有的实时性难题：BP 的迭代与 OSD 的高斯消元都比匹配重，几百比特的码在每微秒一轮的节拍下，译码器的速度本身就是研究前沿（《译码器 · 高中数学版》4.1 节的吞吐问题）。

The five qualifiers of “Decoders · High-School Edition” apply here too, and matter more, because qLDPC numbers are often mixed across models. The checkable ones: toric code + BP-OSD + perfect measurement ≈ 9.9% (Roffe et al. 2020); the BB family + depth-7 circuit + circuit-level noise + BP-OSD ≈ 0.8% (Bravyi et al. 2024, in the grammar of the decoder tutorial's ledger); quantum expander codes + small-set-flip have a threshold under random noise (Fawzi–Grospellier–Leverrier 2018, an existence proof rather than a number). Any “the qLDPC threshold is X%” without its model is an incomplete sentence. qLDPC decoding also carries a real-time problem matching does not: BP's iterations and OSD's Gaussian elimination are heavier than matching, and for codes of a few hundred qubits at one round per microsecond, decoder speed is itself a research frontier (the throughput problem of “Decoders · High-School Edition”, §4.1).

复盘整条推理链：LDPC 是稀疏，好是 k ∝ n 且 d ∝ n；经典世界随机即可，量子世界要构造，回报是常数开销，代价是长程连接（第 1 章）→ 超图积用 ⊗ 拼出对易的 H_X、H_Z，Künneth 给 k，四个经典距离的最小值给 d；重复码 × 重复码就是表面码（第 2 章）→ [[7,2,2]]、[[25,1,3]]、量子扩展码 [[125,37,3]] 与 [[656,170,5]]：因子决定一切（第 3 章）→ 提升积把 0/1 换成环上的多项式，1 × 1 底矩阵给出 BB，非阿贝尔群给出好码（第 4 章）→ 量子 Tanner 码、同调积、超球积与为硬件裁剪的家族（第 5 章）→ BP 在短圈与退化上卡住，OSD 收尾，扩展码有局部翻转，阈值仍需五个限定项（第 6 章）。从《从高考数学到 Toric Code》的第一页走到这里，你手里已经有了当代量子纠错的全部主线：编码、译码、逻辑门、高码率码。

Replaying the chain: LDPC means sparse, good means k ∝ n and d ∝ n; classically randomness suffices, quantumly one must construct, the payoff is constant overhead and the price long-range connectivity (Ch. 1) → the hypergraph product assembles commuting H_X, H_Z with ⊗, Künneth gives k, the minimum of four classical distances gives d, and repetition × repetition is the surface code (Ch. 2) → [[7,2,2]], [[25,1,3]], quantum expander codes [[125,37,3]] and [[656,170,5]]: the factors decide everything (Ch. 3) → the lifted product replaces 0/1 by ring polynomials, 1 × 1 base matrices give BB, non-abelian groups give good codes (Ch. 4) → quantum Tanner codes, homological and hypersphere products, and hardware-tailored families (Ch. 5) → BP stalls on short cycles and degeneracy, OSD finishes, expander codes have local flips, and thresholds still need five qualifiers (Ch. 6). From the first page of “From High-School Math to the Toric Code” to here, you hold the whole main line of contemporary quantum error correction: encoding, decoding, logical gates, high-rate codes.

三条继续走的路。其一，把好码搬上机器：长程耦合的超导、可移动原子、光子互联，各自要为非局域检查付出不同的代价，《BB 码 · 高中数学版》6.6 节讲的「昆仑」实验（2025 年，一台 32 个长程耦合超导比特的处理器上跑 [[18,4,4]] BB 码）是第一步。其二，单发译码（single-shot：每轮只测一次症状，就能把测量错误和数据错误一起纠正到足够好，不必等多轮）：高维超图积等码可以只测一轮症状就纠正测量错误，省掉《译码器 · 高中数学版》的 d 轮重复。其三，qLDPC 上的逻辑门：如何对高码率块里的某几个逻辑比特做门而不打扰其余的——手术、自同构、码切换，都在进行中。入口文献见下。

Three roads onward. One, good codes on machines: long-range-coupled superconductors, movable atoms, photonic links each pay a different price for nonlocal checks; the “Kunlun” experiment of “BB Codes · High-School Edition”, §6.6 (2025: an [[18,4,4]] BB code on a processor of 32 long-range-coupled superconducting qubits) is a first step. Two, single-shot decoding (measure the syndrome once per round and still correct measurement and data errors well enough, without waiting for many rounds): codes such as higher-dimensional hypergraph products can correct measurement errors from a single syndrome round, dispensing with the d repetitions of “Decoders · High-School Edition”. Three, logical gates on qLDPC: how to gate a few logical qubits inside a high-rate block without disturbing the rest — surgery, automorphisms and code switching are all in progress. Entry points below.