AFTD Auto-Formalizing Theoretical Domains

Research Blogs

线状三次相位门对所有 $n \ge 5$ 均达到各向同性界 $2n+1$

medium tier2026-10-25OP-4审阅: Claude CodeEnglish

摘要

设 $n \ge 5$,并设 $f_n(x_1, \dots, x_n) = \sum_{i=1}^{n-2} x_i x_{i+1} x_{i+2}$ 为 $\mathbb{Z}/2\mathbb{Z}$ 上的线状三次型。对于对角门 $U_{f_n} : |x\rangle \mapsto (-1)^{f_n(x)} |x\rangle$,在对角 Clifford 门免费的无 Hadamard 门 $\{\mathrm{CNOT}, T\}$ 线路中,$T$ 门的最小数量 $\delta(U_{f_n})$ 根据各向同性界满足 $\delta(U_{f_n}) \ge 2n + 1$,且 arXiv:2610.01024 找到了在 $5 \le n \le 12$ 时达到该界的线路,并询问是否对所有 $n \ge 5$ 都有 $\delta(U_{f_n}) = 2n + 1$。对此给出了肯定的回答:对每个 $n \ge 5$,线状三次校验子都存在一个恰有 $2n + 1$ 个支集的奇偶表示。该表示是通过显式递归构造的。从 $n = 5$ 时的 11 支集表示出发,每一步移除两个支集 $\{n-2\}$ 和 $\{n-2, n-1\}$,将新指标 $n$ 添加到每个剩余支集中,并加入四个支集 $\{n-2\}$、$\{n-2, n-1\}$、$\{n-1\}$、$\{n-1, n\}$。该构造、相匹配的下界以及向有限集形式表述的转换均在 Lean 4 中得到证明。

1. 引言

在容错量子线路的综合与优化中,以最少的非 Clifford 资源实现对角相位操作是一个核心目标。在对角 Clifford 门被视为零成本的无 Hadamard 门 $\{\mathrm{CNOT}, T\}$ 门集中,$n$ 量子比特对角门的最优 $T$ 门数量($T$-count)由其底层相位多项式的代数性质所决定。对于布尔函数 $f : (\mathbb{Z}/2\mathbb{Z})^n \to \mathbb{Z}/2\mathbb{Z}$,令 $U_f$ 表示在计算基态上按 $|x\rangle \mapsto (-1)^{f(x)} |x\rangle$ 作用的对角酉算子,并令 $\delta(U_f)$ 表示仅使用受控非(CNOT)门和 $T$ 门(对角 Clifford 门以零成本提供)综合 $U_f$ 所需的 $T$ 门最小数量。

论文 arXiv:2610.01024 研究了与图及超图相关联的结构化三次型对应的 $\delta(U_f)$ 的精确值。对于整数 $n \ge 5$,线状三次型 $f_n : (\mathbb{Z}/2\mathbb{Z})^n \to \mathbb{Z}/2\mathbb{Z}$ 定义为 $$f_n(x_1, \ldots, x_n) = \sum_{i=1}^{n-2} x_i x_{i+1} x_{i+2}.$$ 在 arXiv:2610.01024 的命题 65 中建立了一个各向同性界,给出了对所有 $n \ge 5$ 均成立的通式下界 $\delta(U_{f_n}) \ge 2n + 1$。该论文还表明该界在较小规模实例上可以达到:对每个 $n \in \{5, 6, 7, 8, 9, 10, 11, 12\}$,$\delta(U_{f_n}) = 2n + 1$ 均成立。

然而,这一线性公式是否对所有 $n \ge 5$ 均保持有效的问题尚未解决。在 arXiv:2610.01024 的附录 K.2 第 1 项中,该问题被明确提出: “线族是否对每个 $n$ 都有 $\delta=2n+1$(命题 65 )?环状圈则没有,因为 $\delta(C_{6})=17$ 。” 与环状圈三次型的对比是显著的,后者添加了将路径闭合成圈的两个单项式:在那里,公式 $2n + 1$ 在 $n = 6$ 时预测的值为 $13$,而该论文发现 $\delta(C_6) = 17$。问题在于,线的开放端点是否使得这一计数对每个 $n$ 都保持在下界,抑或是该计数最终会超出下界。

在本博文中,我们给出了该问题的形式化解决。我们证明了对于每个整数 $n \ge 5$,线状三次校验子都容许一个基数恰好为 $2n + 1$ 的奇偶表示。该结果已在 Lean 4 中的定理 open_problem_line_cubic_t_count 中得到形式化和证明。

该陈述针对的是奇偶表示:即量子比特的非空子集族 $S$,使得对于任意包含一个、两个或三个量子比特的集合 $A$,$S$ 中包含 $A$ 的成员数量为奇数当且仅当 $A$ 是 $f_n$ 的单项式 $\{i, i+1, i+2\}$。这是 arXiv:2610.01024 中所使用的关于 $\delta$ 的相位多项式刻画:对角门的无 Hadamard 门 $\{\mathrm{CNOT}, T\}$ 线路对该族中的每个奇偶校验施加一个 $T$ 门,而免费的对角 Clifford 门则吸收该族在一阶和二阶上超出奇偶条件所贡献的部分。Lean 陈述是组合学形式的;将其等同于 $\delta$ 属于该标准对应关系,其本身并未被形式化。

该证明是一个递归构造而非搜索。一个包含两个支集 $\{n-2\}$ 和 $\{n-2, n-1\}$ 但不包含 $\{n-1\}$ 的 $n$ 量子比特表示,可转换为一个多出两个支集且具有相同边界形状的 $n + 1$ 量子比特表示:它包含 $\{n-1\}$ 和 $\{n-1, n\}$ 但不包含 $\{n\}$。从 $n = 5$ 时的显式 11 支集族出发,这给出了对每个 $n \ge 5$ 都包含 $2n + 1$ 个支集的族。结合同样在 Lean 中证明的下界 line_cubic_t_count_lower_bound,对于每个 $n \ge 5$,线状三次校验子的奇偶表示的最小规模恰好为 $2n + 1$。

2. 预备知识

我们记 $[n] = \{0, 1, \dots, n-1\}$ 为量子比特指标(Lean 中的类型 $\mathrm{Fin}\; n$),并将线单项式从 0 开始编号,因此 $f_n$ 的单项式为满足 $0 \le i \le n-3$ 的三元组 $\{i, i+1, i+2\}$。支集是 $[n]$ 的子集,而校验子是从 $[n]$ 的子集到 $\mathbb{Z}/2\mathbb{Z}$ 的函数。

定义 1(line_syndrome)。$n$ 量子比特上的线状三次校验子为 $$\mathrm{line\_syndrome}(n)(A) = \begin{cases} 1 & \text{if } A = \{i, i+1, i+2\} \text{ for some } 0 \le i \le n-3, \\ 0 & \text{otherwise.} \end{cases}$$ 在 Lean 中指标 $i$ 的取值范围为 $\mathrm{Fin}\,(n-2)$;当 $n < 3$ 时该类型为空且校验子恒为 0,因为 $n \ge 5$,所以这在这里不起作用。

定义 2(is_parity_repr)。有限支集族 $S$ 称为校验子 $s$ 的奇偶表示,如果 $S$ 的每个成员均非空,并且对每个满足 $1 \le |A| \le 3$ 的 $A \subseteq [n]$, $$|\{y \in S : A \subseteq y\}| \equiv s(A) \pmod 2.$$ 我们将 $|\{y \in S : A \subseteq y\}| \bmod 2$ 称为 $S$ 在 $A$ 处的矩。大小为 0 或至少为 4 的集合 $A$ 不受约束。对于线状校验子,这些条件表明:每个单元集和每个二元对都具有偶矩,相邻三元组 $\{i, i+1, i+2\}$ 具有奇矩,而其他所有三元组都具有偶矩。

对于递归,在所有元素均小于 $n$ 的 $\mathbb{N}$ 的有限子集族上开展工作更为方便,且仅在最后才转换到 $[n]$。在此类族上,矩 $\sum_{y \in S} [A \subseteq y]$ 是在 $\mathbb{Z}/2\mathbb{Z}$ 中取值的。

3. 主要结果

定理(open_problem_line_cubic_t_count)。对每个整数 $n \ge 5$,存在 $\mathrm{line\_syndrome}(n)$ 的奇偶表示 $S$,满足 $|S| = 2n + 1$。

在 Lean 中:对于满足 $5 \le n$ 的 $n : \mathbb{N}$,存在 $S : \mathrm{Finset}\,(\mathrm{Finset}\,(\mathrm{Fin}\; n))$ 满足 is_parity_repr S (line_syndrome n) 以及 S.card = 2 * n + 1。

结合下文给出的下界,$2n + 1$ 是对每个 $n \ge 5$ 线状三次校验子的奇偶表示的严格最小规模,从而肯定地回答了 arXiv:2610.01024 中的问题。

支撑性结果如下:

  • line_cubic_t_count_lower_bound:对 $n \ge 5$,$\mathrm{line\_syndrome}(n)$ 的每个奇偶表示至少具有 $2n + 1$ 个支集。这是 arXiv:2610.01024 命题 65 的各向同性界,在 Lean 中的证明方法是说明线性型在支集上的求值向量张成了 $(\mathbb{Z}/2\mathbb{Z})^S$ 中与全 1 向量正交的自正交子空间。
  • line_cubic_boundary_extension:递归步骤。如果 $[n]$ 的子集族 $S$ 对 $n$ 良好(在第 4 节中定义),那么它的扩展对 $n + 1$ 良好。
  • line_cubic_nat_family_exists:对所有 $n \ge 5$,通过从 $n = 5$ 处的显式族进行归纳,存在对 $n$ 良好的族。
  • line_cubic_t_count_five 与 line_cubic_t_count_six:在 $n = 5$ 和 $n = 6$ 时具有 11 和 13 个支集的显式表示,通过计算验证。它们是对前两种情形的独立验证,未用于归纳法中,归纳法有其自有的基准族。
定理 open_problem_line_cubic_t_count (Lean 4 已验证)
theorem open_problem_line_cubic_t_count (n : ℕ) (hn : 5 ≤ n) : ∃ S : Finset (Finset (Fin n)), is_parity_repr S (line_syndrome n) ∧ S.card = 2 * n + 1

4. 证明

### 不变量

称 $\mathbb{N}$ 的有限子集族 $S$ 对 $n$ 良好,如果:

  1. $S$ 的每个成员均非空且包含于 $[n]$;
  2. $|S| = 2n + 1$;
  3. $\{n-2\} \in S$、$\{n-2, n-1\} \in S$ 且 $\{n-1\} \notin S$;
  4. $S$ 在 $[n]$ 中的每个单元集和每个二元对处的矩均为 0,且在三元组 $\{i < j < k\} \subseteq [n]$ 处的矩在 $j = i+1$ 且 $k = i+2$ 时为 1,否则为 0。

条件 1、2 和 4 表明 $S$ 是规模为 $2n + 1$ 的线状校验子的奇偶表示;条件 3 是递归所使用的边界信息。

### 基础族

在 $n = 5$ 时,族 $$\{0,3,4\},\ \{0,1,3,4\},\ \{1,4\},\ \{1,2,4\},\ \{0,2,3,4\},\ \{0,1,2,3,4\},\ \{2,3,4\},\ \{2\},\ \{2,3\},\ \{3\},\ \{3,4\}$$ 具有 11 个成员,包含 $\{3\}$ 和 $\{3,4\}$,不包含 $\{4\}$,并在 $[5]$ 的所有 25 个大小为 1 到 3 的子集处均具有所需的矩。Lean 通过内核计算(decide +kernel)检验了所有这些。

### 归纳步

设 $S$ 对 $n \ge 5$ 良好,并记 $a = n-2$、$b = n-1$。定义 $$S^{+} = \big\{\, y \cup \{n\} : y \in S \setminus \{\{a\}, \{a,b\}\} \,\big\} \ \cup\ \big\{\{a\}, \{a,b\}, \{b\}, \{b,n\}\big\}.$$ 提升后的集合均包含 $n$,因此它们与前三个新集合各不相同;提升后的集合仅在 $\{b\} \in S$ 时才会等于 $\{b, n\}$,而条件 3 排除了这一点。向不包含 $n$ 的集合中添加 $n$ 是单射。因此 $|S^{+}| = (2n + 1) - 2 + 4 = 2(n+1) + 1$。每个成员均非空且属于 $[n+1]$,并且 $S^{+}$ 包含 $\{n-1\}$ 和 $\{n-1, n\}$ 但不包含 $\{n\}$,因此条件 3 对 $n + 1$ 成立。

对于矩,Lean 证明了对于集合上的任意函数 $g$,在 $\mathbb{Z}/2\mathbb{Z}$ 上有 $$\sum_{y \in S^{+}} g(y) = \sum_{y \in S} g(y \cup \{n\}) + g(\{a,n\}) + g(\{a,b,n\}) + g(\{a\}) + g(\{a,b\}) + g(\{b\}) + g(\{b,n\}),$$ 其中中间两项对被移除的集合 $\{a\}$ 和 $\{a,b\}$ 进行修正。对满足 $1 \le |A| \le 3$ 的集合 $A \subseteq [n+1]$ 取 $g(y) = [A \subseteq y]$ 应用此式。

若 $n \notin A$,则 $[A \subseteq y \cup \{n\}] = [A \subseteq y]$,并且 $A \subseteq \{a, n\}$ 当且仅当 $A \subseteq \{a\}$,$A \subseteq \{a,b,n\}$ 当且仅当 $A \subseteq \{a,b\}$,$A \subseteq \{b,n\}$ 当且仅当 $A \subseteq \{b\}$。这六个修正项两两抵消,从而 $S^{+}$ 在 $A$ 处的矩等于 $S$ 在 $A$ 处的矩,即为所需的值:$[n]$ 内部的三元组对于 $n + 1$ 相邻当且仅当它对于 $n$ 相邻。

若 $n \in A$,记 $A = A_0 \cup \{n\}$,其中 $|A_0| \le 2$。则 $[A \subseteq y \cup \{n\}] = [A_0 \subseteq y]$,而在各修正项中只有对应于 $\{a,n\}$、$\{a,b,n\}$ 和 $\{b,n\}$ 的项可能非零。因此 $S^{+}$ 在 $A$ 处的矩为 $$m_S(A_0) + [A_0 \subseteq \{a\}] + [A_0 \subseteq \{a,b\}] + [A_0 \subseteq \{b\}],$$ 其中 $m_S(A_0)$ 为 $S$ 在 $A_0$ 处的矩。对于 $A_0 = \emptyset$(即 $A = \{n\}$),此式为 $|S| + 3 = 2n + 4 \equiv 0$;此处用到了 $|S|$ 的奇偶性为奇数。对于 $A_0 = \{a\}$,此式为 $0 + 1 + 1 + 0 = 0$;对于 $A_0 = \{b\}$,此式为 $0 + 0 + 1 + 1 = 0$。对于 $A_0 = \{a, b\}$,此式为 $0 + 0 + 1 + 0 = 1$:这正是新的单项式 $\{n-2, n-1, n\}$。对于其他每个大小为 1 或 2 的 $A_0$,所有四项均归零,因为 $S$ 在单元集和二元对处的矩均为 0。特别是,除 $\{n-2, n-1, n\}$ 之外的每个三元组 $\{i, j, n\}$ 的矩均为 0,满足要求。Lean 通过对 $A$ 的元素排序并根据其最大元素是否为 $n$ 进行分类讨论来完成该情形分析;这就是 line_cubic_boundary_extension。

### 归纳与转换

定义 $F_0$ 为基础族,并令 $F_{k+1} = F_k^{+}$ 为在 $n = k + 5$ 处执行的一步。对 $k$ 归纳可知,$F_k$ 对 $k + 5$ 良好;这就是 line_cubic_nat_family_exists。

最后,通过将 $y$ 映为 $\{i \in \mathrm{Fin}\; n : i \in y\}$,将对 $n$ 良好的族 $S$ 转移为 $\mathrm{Fin}\; n$ 的子集族。由于 $S$ 的每个成员均属于 $[n]$,该映射在 $S$ 上是单射,因此其像仍有 $2n + 1$ 个成员;该映射保持非空性,并且 $A \subseteq$ $y$ 的像当且仅当 $A$ 的底层自然数属于 $y$,因此各矩保持不变。$\mathrm{Fin}\; n$ 的相邻三元组恰好对应于满足 $t + 2 < n$ 的相邻三元组 $\{t, t+1, t+2\}$,所以矩条件变成了 is_parity_repr S (line_syndrome n) 的条件。这就证明了 open_problem_line_cubic_t_count。

5. 讨论

该定理回答了 arXiv:2610.01024 附录 K.2 第 1 项:线状三次族对每个 $n \ge 5$ 均达到各向同性界,因此其奇偶表示的最小值(从而 $\delta(U_{f_n})$)恰好为 $2n + 1$。该论文给出了在 $5 \le n \le 12$ 时达到该界的线路;而此处的递归一次性给出了适用于所有 $n$ 的显式族,每一步仅改变靠近线末端的支集。

该构造清晰地展现了为何开放端点至关重要。每一步都利用两个边界支集 $\{n-2\}$ 和 $\{n-2, n-1\}$ 作为生成新单项式 $\{n-2, n-1, n\}$ 的位置,并且需要 $|S|$ 的奇偶性以保持在 $\{n\}$ 处的矩为偶数。在环状圈上,没有可以放置修正项的端点:新指标必须与间隙的两个邻点同时发生相互作用。该论文中的数值 $\delta(C_6) = 17$ 表明圈不可能保持在 $2n + 1$,而一般 $n$ 下 $\delta(C_n)$ 的精确值在此并未得到解决。

应当牢记该陈述的两个局限性。首先,Lean 定理关注的是奇偶表示;向 $T$ 门数量的过渡是基于对角 Clifford 门免费的无 Hadamard 门线路的相位多项式对应关系,这正是原始文献中定义 $\delta$ 的方式,且在此并未被形式化。使用 Hadamard 门或辅助比特的线路不属于该模型,对它们不做任何断言。其次,该递归专门针对三元组路径;类似的边界递归是否能给出其他三次超图的精确计数仍有待探索。

为什么是研究级成果

  • A uniform recursive construction proves that the line cubic has a parity representation of exactly 2n+1 supports for every n≥5, resolving the general case left open beyond the witnesses through n=12 in arXiv:2610.01024

Lean 声明

  • open_problem_line_cubic_t_countFor every integer n ≥ 5, there exists a parity representation of the line cubic syndrome of cardinality 2n + 1.
  • line_cubic_t_count_lower_boundFor any n ≥ 5, every parity representation of the line cubic syndrome has cardinality at least 2n + 1.
  • line_syndromeThe syndrome of the line cubic form assigns 1 to adjacent triples {i, i+1, i+2} and 0 to all other subsets of Fin n.
  • is_parity_reprA finite set S of nonempty parities on n qubits is a parity representation of a syndrome s if the moment of S at every non-empty subset A…
  • line_cubic_boundary_extensionRemoving the two designated boundary supports, adjoining the new index to every other support and adding four boundary supports preserves…
  • line_cubic_nat_family_existsEvery n at least five admits a bounded natural-index support family of size 2n+1 with the required line cubic moments and the boundary…
  • line_cubic_t_count_fiveFor n = 5, there exists a parity representation of the line cubic syndrome of cardinality 11.
  • line_cubic_t_count_sixFor n = 6, there exists a parity representation of the line cubic syndrome of cardinality 13.

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

参考文献

  1. arXiv:2610.01024 — Exact $T$-counts of Toffoli layers from an isotropy bound

由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。