技术摘要：基于各向同性界的 Toffoli 层精确 T 计数

1. 问题陈述

在 Clifford+$T$ 框架内，$T$ 门的数量是容错量子计算的主要成本指标，因为每个 $T$ 门都需要一个蒸馏的魔态（magic state）。虽然编译器可以提供 $T$ 计数的上界，但确定紧致的下界对于资源评估至关重要。现有的可高效计算的下界（如稳定子零度/stabilizer nullity）通常过于宽松。例如，对于单个 Toffoli 门（或 CCZ），稳定子零度预测的成本为 3，而精确的 $T$ 计数为 7。类似地，对于 $m$ 个不相交 CCZ 门的层，零度建议的成本为 $3m$，但已知的构造需要 $6m+1$。

本文解决了在对角级三阶门（即在 $\mathbb{Z}_8$ 上相位多项式次数最多为 3 的门）中，高效可计算的下界与真实 $T$ 计数之间的差距，特别关注并行 Toffoli 层及相关结构。

2. 方法论

该方法的核心是源自无 Hadamard $\{CNOT, T\}$ 电路中相位多项式结构的各向同性约束（isotropy constraint）。

• 相位多项式与剩余项： 对角门 $U$ 在 $n$ 个量子比特上施加相位 $\omega^{\phi(x)}$，其中 $\phi: \mathbb{F}_2^n \to \mathbb{Z}_8$。在 $\{CNOT, T\}$ 电路中，该相位是奇数项的校验和。$T$ 计数对应于相位多项式表示中具有奇数系数的校验项数量（即“剩余项”/residue）。
• 矩形式与各向同性： 本文基于包含特定量子比特三元组的奇数校验项数量，定义了三次矩形式（cubic moment form） $T_{abc}$。对于“纯三次”（pure-cubic）门（无线性或二次项），记录哪些 $T$ 门接触每个量子比特的向量构成矩阵 $Y$ 的列。
• 各向同性约束： 核心见解是，对于纯三次门，$Y$ 的列构成了 $\mathbb{F}_2^t$ 的一个全各向同性子空间（totally isotropic subspace）（其中 $t$ 是 $T$ 门的数量）。这意味着每一列的权重均为偶数，且每对列的重叠也是偶数。
• 维度界限： $\mathbb{F}_2^t$ 中的全各向同性子空间的维度至多为 $t/2$。通过分析三次矩形式的根基（radical/kernel），作者推导出了合成矩阵秩的下界，从而转化为对 $t$ 的下界。
• 奇偶性步骤： 一个次要的奇偶性论证增加了额外的约束，使非退化纯三次门的界限提高了 1。

由此产生的下界被称为各向同性底限（isotropy floor），可通过 $O(n^3)$ 时间内的高斯消元法计算，使其成为高效可计算的。

3. 核心贡献与结果

A. 并行 Toffoli 层的精确 T 计数

本文证明了 $m$ 个不相交 CCZ 门（并行 Toffoli 层的对角核心）在任何具有干净辅助量子比特的 Hadamard-free Clifford+$T$ 电路中，恰好需要 $6m + 1$ 个 $T$ 门。

• 意义： 这与 Campbell 和 Howard 的构造相匹配。据作者所知，这是第一个针对一般 $m$ 情况证明最优性的证明（此前仅已知 $m=1$ 和 $m=2$ 的情况）。
• 对比： 稳定子零度仅给出 $3m$，低估了近两倍的成本。

B. 各向同性底限

作者定义了一个通用的下界 $\delta(U) \ge 2(n - d^*) - r$，其中：

• $n$ 是量子比特数量。
• $d^*$ 是完整矩张量根基的维度（通过 $O(n^3)$ 计算）。
• $r$ 是二次矩矩阵的秩。
• 对于纯三次门，该公式简化为 $\delta(U) \ge 2(n - d) + 1$（其中 $d$ 是三次根基维度）。
• 该界限绝不会低于稳定子零度 $\nu = n - d^*$，并且对于非 Clifford 纯三次门，它等于 $2\nu + 1$。

C. 重叠与扇出层

本文将这些结果扩展到块之间共享量子比特的层：

• 线性重叠： 如果块最多共享一个量子比特，则成本为 $6m + 1 - 2s$，其中 $s$ 是共享关联的数量。
• 扇出（Fan-out）： 对于 $m$ 个共享单个控制量子比特的 CCZ 门，其精确成本为 $4m + 3$。这恢复了无辅助量子比特电路的已知最优计数，并将此结论扩展到了具有干净辅助量子比特的电路。

D. 应用与认证

• Toffoli 网络： 该底限可以认证目标不再作为控制位重复使用的合成 Toffoli 网络（无错配/mismatch-free）。
• 域乘法： 对于 GF($2^k$) 乘法算谕（oracles），该底限提供了 $6k + 1$ 的下界。对于 $k=2$ (GF(4))，其精确计数被证明为 17。
• 优化器认证： 当应用于 TODD 优化器对 24 个基准电路的输出时，各向同性底限在 311 个合并的相位多项式块中认证了 193 个为最优（相比之下，稳定子零度仅能认证 113 个）。在可解码块上，该底限与真实 $T$ 计数的误差在 2 以内。

E. 扩展与局限性

• 内部 Hadamard 门： 在特定条件下（例如，Hadamard 形成临时的 AND 块并被酉变换撤销），该界限对含有内部 Hadamard 门的电路也成立。
• 测量与前馈： 对于无测量电路，比零度高出两倍的改进（$2\nu + 1$）仍然成立。在使用自适应前馈的情况下，可证明的界限会降至零度界限 $\nu$，正如 Jones 门（Jones gadget）实现 CCZ 仅需 4 个 $T$ 门所展示的那样。
• 更高阶： 基于各向同性的论证可以推广到 $k$ 阶门，但紧致性结果是针对 3 阶门特定的。对于 $k \ge 4$，基于根基的界限存在无界的松弛。

4. 意义与主张

本文声称提供了第一个高效可计算的下界，该下界在稳定子零度偏差达两倍的门族中是精确的。

• 最优性： 它确立了并行 Toffoli 层（$6m+1$）和扇出层（$4m+3$）的精确 $T$ 计数。
• 效率： 该界限是多项式时间可计算的（$O(n^3)$），不同于指数级的精确方法（Reed-Muller 解码）。
• 紧致性： 该底限在所有 $n \le 5$ 的纯三次类中都是精确的，并在 $n=6$ 的约 39.4% 的纯三次门中保持精确。
• 资源评估： 该底限作为资源评估的严格证书，缩小了已知构造与重要的基本单元（如域乘法和相位算谕）的理论下界之间的差距。

作者明确指出，该底限并非“魔幻单调函数”（magic monotone），这使得它在单调函数（如零度）失效的地方能够保持精确，但也限制了它在处理带有自适应前馈或特定内部 Hadamard 结构的电路时的适用性。