VBE 进位链

所有量子算术线路的祖先。VBE 网络第一次把”从加法一路搭到模幂”的量子线路显式写了出来，让 Shor 类算法的辅助位预算第一次成为可讨论的对象。它采用的进位方式是教科书式的——每一位配一根进位线，进位由受控非门逐位传递。这个设计有三个后果：深度 $O(n)$、辅助比特 $O(n)$、以及必须在最后把整条进位链反计算回零。前两个后果被后来的所有工作攻击，第三个后果则一直保留到今天。

网络的骨架

VBE 方案的核心构件是受控加法器（controlled adder，$CA$）：给定控制比特 $c$ 与加数 $b$，它把

$$|c⟩|b⟩⟼|c⟩|b+c\cdot 2^i⟩$$

也就是说，控制位为 1 时给加数加上一个已知常量 $2^i$。注意这里的 $2^i$ 是编译期就定下来的常量，不是另一个量子寄存器——这正是 VBE 方案与后来所有方案的分水岭。

把 $n$ 个这样的 $CA$ 单元串起来，再加上最后一级的进位加法，就得到加法网络。整个模幂线路则是把乘法、模归约这两类网络套进指数寄存器控制的迭代里。

VBE 进位链：每位一根显式进位线

$O(n)$ 辅助比特的来源

进位在数学上是 $c_{i+1}=\mathrm{maj}(a_i,b_i,c_i)$，一个三输入布尔函数。在量子线路里它必须被实现为酉，即 CNOT/Toffoli 的组合，而布尔函数的计算代价是这个方案的主要开销。

VBE 的选择是：让每一位的进位成为一根独立的线。进位 $c_{i+1}$ 由 $c_i$、$a_i$、$b_i$ 共同决定，用两个受控非门串起来即可传递。代价直接可见——$n$ 比特加法需要 $n$ 根进位线，而且因为输入寄存器 $a$、$b$ 在加法后通常还要保留（或者需要被反计算），进位线的初值必须是 $|0⟩$ 且末态也必须回到 $|0⟩$，才能把空间交还给下游模块。QA001 明确指出，以可逆方式完成模幂所需的辅助内存随被分解数的规模线性增长——这正是这套设计的账单。

为什么这个缺陷值得写一篇词条

三个后续事实让 VBE 的缺陷变得具体：

一、辅助比特在容错时代是最贵的资源。 在有噪声中等规模量子（NISQ）阶段，比特有限但可以靠纠错换；进入量子纠错时代后，一个逻辑比特意味着一整块物理比特与反复的纠错周期。于是”省 $O(n)$ 根辅助线”从工程细节变成首要目标。CDKM（cdkm-adder）正是针对这一点的直接回应：它把进位暂时存在加数寄存器的高位上，把 $O(n)$ 根辅助线压到 1 根。

二、深度 $O(n)$ 从未被真正解决。 从 VBE 到今天，串行进位这一族的深度始终是 $O(n)$。想压深度就要走进位先行（carry-lookahead-adders）或并行前缀（kutin-parallel-prefix）路线，而这两条路线都要付回 $O(n)$ 辅助比特。QA011 给出了一个绕开这个二择一的新解：无辅助位、$O({\log }^{2}n)$ 深度。

三、反计算在真实资源估算里占了大头。 QA009 给出一个具体数字：测量基反计算相对相位 Toffoli 辅助位最多可占整条线路深度的 30%。这条结论把”加法器有多深”与”整个算法要跑多久”直接连了起来。

架构视角下的 VBE

VBE 方案还有一个当代视角：串行进位在一维最近邻架构上其实相当友好，因为信息只沿一条线传。但一维布局下，进位的串行依赖直接变成 $O(n)$ 深度下界，没有任何调度手段可以绕过。

QA030 证明了更一般的结论：在 $k$ 维最近邻架构上，任何精确加法器的深度下界是 $\Omega (n^{1/k})$。这是对所有”把 $O(\log n)$ 深度搬上真实硬件”设想的第一次严肃回应——$\log n$ 是全连通假设下的界，在受限连接上不成立。QA029 给出的二维方案把这个下界做到 $\Theta (\sqrt{n})$，代价是 $O(n)$ 比特；QA028 再把二维实现的常数从 $140\sqrt{n}$ 压到 $92\sqrt{n}$。QA017 则走了另一条路：用测量基计算模型（MBQC）里的”单位时间传态”能力绕过最近邻延迟，使 QCLA 在最近邻架构上达到 $\Theta (\log n)$ 深度，代价是簇态规模大一个数量级。

论文依据

• Vedral–Barenco–Ekert 1995 —— 本词条的唯一原始来源。给出从加法到模幂的显式量子网络构造，并证明可逆模幂所需辅助内存随被分解数规模线性增长；“每位一根进位线”的设计与这条账单都出自此文。
• Cuccaro–Draper–Kutin–Moulton 2004 —— 明确以”先前加法线路需要线性多个辅助比特”作为出发点，给出只需单个辅助比特的新进位链；本词条”辅助比特在容错时代最贵”一节即以此为对照。
• Paler–Oumarou–Basmadjian 2021 —— 给出测量基反计算可占整条线路深度 30% 这一数字，以及在实用宽度下进位链优于进位先行的实证结论。
• Remaud–Vandaele 2025 —— 首个精确的无辅助位次线性深度加法器，$O({\log }^{2}n)$ 深度；本词条”深度 $O(n)$ 从未被真正解决”一节引用的新解。
• Choi–Van Meter 2008 —— 证明 $k$ 维最近邻架构上精确加法器的深度下界为 $\Omega (n^{1/k})$。
• Choi–Van Meter 2010 —— 二维 NTC 架构上的 $\Theta (\sqrt{n})$ 深度脉动式加法器，$O(n)$ 比特。
• Saeedi–Shafaei–Pedram 2013 —— 把二维最近邻加法器的总深度从 $140\sqrt{n}+k_1$ 降到 $92\sqrt{n}+k_2$。
• Trisetyarso–Van Meter 2009 —— 测量基 QCLA（MBQCLA），用簇态传输绕开最近邻延迟；本词条”架构视角”一节的第三条路径。

延伸阅读

• cdkm-adder —— 直接针对本文缺陷的解法
• kutin-parallel-prefix —— 串行进位的并行化尝试
• adder-taxonomy —— 三条路线的整体坐标
• 算术线路总览 —— VBE 网络在整条算法链里的位置