T 数与深度

两篇论文，一篇报”$4n$ 个 T 门”，另一篇报”$3n$ 个 T 门、深度 $O(\log n)$“——你没法说后者更好，因为它们量的根本不是同一件事。更要命的是：即使你在某个指标上赢了，墙钟时间也可能变长，因为每个 T 门都要排队等一个魔法态。本词条说清这两个指标为什么不可互换，以及在什么条件下该优化哪一个。

两个指标量的是不同的东西

门代价模型已经列过这组指标，这里只强调 $T_c$ 与 $d_{\text{depth}}$ 的分工：

• T 数 $T_c$ 是非 Clifford 门的总量。它决定的是”总共要向工厂要多少个 $|T⟩$“，进而决定工厂规模和它每秒要产多少。
• 深度 $d_{\text{depth}}$ 是最长依赖链上的门层数。它决定的是”线路自己跑完要多久”，中间没有工厂的份。

把这两句话并排读一遍就能看出：$T_c$ 对应供给侧的总需求，$d_{\text{depth}}$ 对应执行侧的时间。二者之间没有换算式——$T_c$ 再大也可以完全并行执行，$d_{\text{depth}}$ 再小也不能少要一个 $|T⟩$。

降低 T 数的三条路，每条都有代价

路线一：把 Toffoli 换成相对相位 Toffoli。 这是最常见、也最受限的一条。rccx 存入只要 4 个 T 门、擦除 0 个，整条加法器的 T 数可以精确减半。但它有硬性使用条件：只能出现在”之后紧跟反计算”的位置上。把它挪到别处就失效，而失效的代价不是报错，是悄悄多出来的 T 门。因此用相对相位门换来的 T 数下降，通常伴随更高的 Toffoli 密度和更紧的结构约束——线路的门总数反而可能上升。

路线二：并行化，进位结构变复杂。 把串行的进位链拆成并行前缀树，深度从 $O(n)$ 降到 $O(\log n)$，但每个节点的 Toffoli 数上升，辅助位也从常数回到 $O(n)$。这条路线是降深度、升比特数、升 T 数。把它叫作”优化”之前，先确认你的瓶颈真的在深度上。

路线三：结构性改进（真正减少逻辑操作数）。 例如把常数进位在编译期算好、去掉恒为零的高位进位。这类改进能同时降 $T_c$ 和深度，但它属于线路设计层面的事，算术复杂度几卷讨论的就是它。本词条关心的是：一旦这部分被手工优化完，剩下的空间通常不大。

工厂吞吐才是墙钟时间的真瓶颈

一个 $|T⟩$ 态必须被制备出来、测量、被线路消费——这是一个串行的交付过程。工厂每秒交付 $r$ 个，线路总共要 $T_c$ 个，于是有一个下限：

$$t_{\text{supply}}=\frac{T_c}{r}$$

这个量与线路深度无关。把深度从 $O(n)$ 压到 $O(\log n)$，$T_c$ 一个也不会少，$t_{\text{supply}}$ 一个秒也不会降。反过来，把 $T_c$ 压掉一半，$t_{\text{supply}}$ 直接减半，而线路可能根本没在跑。

于是总时间是两者的较大者：

$$t_{\text{wall}}=\max (d_{\text{depth}}\cdot d\cdot {\tau }_{\text{cycle}},T_c/r)$$

真正的”最优设计”是让两项大致相等：

$$d_{\text{depth}}\cdot d\cdot {\tau }_{\text{cycle}}\approx \frac{T_c}{r}$$

• 左边远大于右边：工厂大部分时间在空转，线路太长。此时该做的是降深度，降 $T_c$ 帮不上忙。
• 右边远大于左边：线路早就跑完了，工厂还在吐态。此时该做的是降 $T_c$ 或加大 $r$，降深度是白费。

同样 4 个 T 门：串成一条链 T 深度 4，分两对并行则 T 深度 2

图中两行的 T 数相同，深度差一倍。若工厂吞吐 $r$ 有限，右边更早用完魔法态；若 $r$ 很大而线路本身很慢，左边也不会因此更贵。哪一行更好，取决于 $r$——这就是两个指标不可互换的全部理由。

T 门宽度：第三个被忽略的量

还有一个更细的量：同一层里有多少个 T 门在等（T 门宽度 $w$）。$w$ 决定工厂瞬时要交付多少个态，$T_c/w$ 决定要交付多少批。相对相位门密集的线路 $T_c$ 更小但 $w$ 可能更大——总量少了、瞬时压力集中了，对工厂的批处理缓冲要求更高，而对总产能要求更低。报成本的时候只报 $T_c$ 不报 $w$，等于只报了一半。

一张可复现的判据

观察到的现象	瓶颈在哪	该动什么	不该动什么
线路跑完后工厂还在出货	供给侧	$T_c$、$r$、工厂批大小	深度、辅助位
工厂长期空转、线路在等	执行侧	深度、并行结构、${\tau }_{\text{cycle}}$	$T_c$
静态比特数超预算	比特侧	寄存器宽度、辅助位回零、码型与码距	深度
换成并行结构后总时间没变	说明原来就是供给侧瓶颈	回到 $T_c$ 与 $r$	继续加大并行度

这张表的用法是：先测出哪一项是瓶颈，再决定优化方向。跳过这一步去优化一个非瓶颈指标，是算术线路工程里最常见的时间浪费。

论文依据

• Reinhold 等 2020，Error-corrected gates on an encoded qubit —— 把”非 Clifford 门成本 ↔ 逻辑比特与周期”直接联系起来：受控门需要额外的辅助位且辅助位错误是主要误差源，说明少算 T 门并不等于少花辅助位资源。这是”两个指标不可互换”在物理层面的实证。
• Fowler 等 2012，Surface codes —— 给出 T 门在表面码架构下的实现路径与所需码距，说明 $T_c$ 与码距 $d$ 通过”每个 T 门要一个码距长的注入过程”耦合，而 $d_{\text{depth}}$ 只按轮次线性累加——两者的增长方式不同。
• Steiger 等 2018，ProjectQ —— 其资源计数插件在同一份 IR 上分别统计门数、比特数与深度，实践上支持”这两类指标必须分开报”的做法。
• Childs 与 van Dam 2010，Quantum algorithms for algebraic problems —— 算法级综述，把复杂度账本按查询复杂度与算术深度分列，其记账惯例同样是这两个量分开呈现。
• Montanaro 2016，Quantum algorithms: an overview —— 从算法层面说明调用次数与单次代价是两项独立的乘数，佐证”单次调用便宜”不等于”全线路便宜”。

延伸阅读

• 资源账本：$t_{\text{wall}}=\max (\cdot ,\cdot )$ 这条式子的逐环来源
• 门代价模型：T 数、深度、辅助位、线路规模、工厂吞吐这五个量的分工
• 容错成本模型：码距怎么从目标错误率反推
• 线路优化：为什么对已手工优化的算术线路，通用优化常常收不到钱