比较器与相等判定

量子比较器没有必要是一个独立原语：无符号大小关系直接读减法（或加法减偏移）的最高位进位即可，相等判定就是关系线归约到零位。所以文献里很少有”比较器线路”这种独立成果——不是因为它不重要，而是因为它太容易被别的原语吸收了。真正有专门优化文献的近邻是前导零检测器，它在归一化里承担”有效位到哪儿为止”的问题。本词条先给出这两条构造的推导，然后如实说明一处文献空白。

一、大小关系 = 借位

设 $a,b$ 都是 $n$ 比特无符号整数。无符号比较 $a\ge b$ 等价于

$$a-b\ge 0⟺a+(\neg b)+1\ge 2^n$$

右边是加法器的进位输出（carry-out）。所以比较的实现是：做一次减法（用 negadd：取负加加法），读最高位之外的进位位。这一步是纯数学事实，不依赖任何文献：

$$\text{carry-out}=1⟺a\ge b$$

比较 = 减法的进位读出；相等 = 归约到 0 位

图里 $t$ 上的取反加加一就是 negadd（见modular-subtraction-negation），比较的成本因此完全等于一次减法加一位输出的读取。这条推导也说明了为什么归约里的条件减法”免费”得到判据：它本来就要做一次减法，顺手读进位就行。

二、相等判定的三条等价形式

在量子线路里，“相等”有三种常见写法，成本不同：

1. 无符号相等：如上，$a=b⟺\neg (a\ge b)\wedge \neg (b\ge a)$，即两次比较取反与。但实际上直接算 $a-b$ 并检查结果是否为 0 只需一次减法加一次零检测。
2. 归约到零位：计算 $z=a-b$，判断 $z=0$。由于是模 $2^n$ 运算（进位丢弃），$z=0$ 精确刻画相等。这需要一条零检测线路。
3. 或门组合：$a=b⟺\neg (a\oplus b)$ 里的任一位为 1——即对异或结果做”任一位为 1”的检测。

零检测本身就是”或”的实现，而”或”与”多数”、“阈值”、“计数”这一族布尔函数在量子线路里有一份共同的无界 fan-out 视角（Høyer 与 Špalek）——这是本卷能引到的关于比较/归约族函数的唯一一条有明确出处的结构性文献。

三、前导零检测器：真正有专门优化文献的近邻

前导零检测器（leading zero detector）问的是：“这段定点表示里，第一个 1 在哪一位？“也就是把一串前导零转成一个位置数。它在模归约与归一化路线里是关键子线路——归约之后往往需要知道结果的有效位宽度，以便为后续的定点运算准备寄存器。

Orts 等给出了前导零检测器电路的优化实现，把这一子线路定位为模归约/归一化的核心部件。这是本词条能引到的、关于这一族”位计数/检测”子线路的专门文献。

摘要未获取

本站未取得 QM012 的摘要原文（Crossref 与 OpenAlex 无摘要字段，Semantic Scholar 标注摘要被出版方 elide）。因此本词条只引用其可从标题与元数据确认的范围——前导零检测器的优化实现、面向模归约与归一化——不转述其门数、深度或比特数结论。

前导零检测：把首个 1 的位置作为输出

这张图只画骨架：真正的实现在不同文献里形态差别很大（有的用树形加法器统计前缀，有的用进位链）。本站不给出具体门型序列——那需要 QM012 的原文，而摘要都未获取。

四、如实说明：这处空白的范围

文献空白

专门的”量子比较器线路” T 数最优文献，本轮未能核实到。 检索覆盖 arXiv API、Crossref、DataCite 后，可引的只有两条旁证：

可引内容	来源	它不能支持什么
前导零检测器的优化实现，归一化/归约的关键子线路	[[sources/QM012	Orts 等（2022）]]
无界 fan-out 视角下 parity, mod[q], And, Or, majority, threshold[t], exact[t], counting 可常数深度逼近	[[sources/QM007	Høyer 与 Špalek（2005）]]

因此本词条不给出任何”比较器的最优 T 数是……”式的陈述。

Høyer 与 Špalek 那篇的定位尤其需要说清楚，因为它最容易被误用。它的真实标题是 “Quantum Fan-out is Powerful”（Crossref 记录 10.4086/toc.2005.v001a005 的 title 字段为空，实际标题取自期刊官网的 citation_title）。此前流传的 “Quantum multiplier and division circuits” 是一条被证伪的标题，不得据此引用。它证明的是：在无界 fan-out 模型下，一整族布尔函数可以常数深度逼近；而比较与归约族函数（Or、mod[q]、exact[t]、counting）正在这族里。它的模型假设（无界 fan-out、固定门基）与容错线路的实际假设差别很大，因此只能作为结构直觉的来源，不能作为成本数字的来源。

论文依据

• Orts、Ortega、Combarro、Rúa 与 Garzón（2022） —— 前导零检测器电路的优化实现，定位为模归约与归一化路线的关键子线路；本站未取得摘要，不转述其具体数字。
• Høyer 与 Špalek（2005） —— “Quantum Fan-out is Powerful”：在有界 fan-in、无界 fan-out 的固定基模型（$QN{C}_f^0$）下，parity, mod[q], And, Or, majority, threshold[t], exact[t], counting 可多项式小误差常数深度逼近；放宽到任意单比特门后可做成精确的 log-star 深度；排序、算术、相位估计与任意模的 QFT 也可常数深度逼近。
• Zhang 等（2025） —— 其 Barrett 归约的判据来自条件减法的进位，说明比较在归约里是”顺手获得”而非独立成本；通用归约 T 深度约 $O(2^n)$，Barrett 归约 $O(n^2)$。

未核实项

专门的量子比较器线路 T 数最优文献未核实到。参考资料中不含任何声称此方向结果的条目。

延伸阅读

• modular-subtraction-negation —— 比较所依赖的 negadd。
• modular-reduction —— 归约里的判据从哪来。
• in-place-multiplication —— 另一个”用存活期换成本”的视角。
• 浮点数算术 —— 浮点加法五段流水线的第①段（指数比较）与第④段（前导零计数），都是本词条比较器线路的放大版。