王座上的算法：Shor II（电路与成本）

先备导航：你需要 037（Shor 思路）、036（QFT 电路）、031（相位回踢）、023（通用门集与数酵母）、024（电路图）。

下一篇预告：039《为什么 Shor 不会立刻杀死 RSA：工程现实》。

王座上的算法：Shor II（电路与成本）

上篇把 Shor 拆成了四步流程图，其中三步是现成零件，只欠一台自定义机器：模运算黑箱——把 a^x mod N（a 的 x 次方除以 N 的余数）做成一个量子门。本篇下车间：看它怎么造、整台机器的门数账单怎么算、以及"数酵母"（023 篇）在王座级电路上数出什么天文数字。

造黑箱：逐位平方流水线

任务看着吓人，工厂里却是老工艺。算 a^x mod N，经典世界的聪明办法不是连乘 x 次，而是逐位平方：

a^x = a 的"二进制各位加权"之积——x 的第 0 位是 1 就乘一个 a，第 1 位是 1 就乘一个 a²，第 2 位是 1 就乘一个 a⁴……而 a²、a⁴、a⁸ 全部由反复平方得到（平方 1 次、2 次、3 次）。n 位的 x，只需 n 次"平方"加 n 次"按位选用"，不必连乘 2^n 次。

量子版照搬流水线：x 寄存器的每一位当控制线（022 篇的 CNOT 思想——"这位是 1 才动作"），y 寄存器当工作台；依次挂 n 个受控模块——第 i 个模块"若 x 第 i 位为 1，则 y 乘以 a^(2^i) mod N"。x 寄存器是叠加的，全部 2^n 个指数的余数一次流水线全部加工（031 篇宪法再次生效：不是"同时跑 2^n 条流水线"，是一台流水线作用在所有输入的叠加上）。

黑箱的成本账单：每个受控模块是一次 n 比特的模乘（内部又是一串门），n 个模块合计约 n³ 个门——n 是 N 的比特数。n³ 听着大，对照经典分解的指数级，它是多项式：这就是"指数变多项式"那句话在电路层的实物形态。

总账单：两笔大项，一种硬通货

整台 Shor 机器的门数账单：

• 模运算黑箱：约 n³ 个门（大头，流水线长度摆在那）；
• QFT：约 n² 个门（036 篇：n 个 H 加受控相位门编队，小头）；
• 杂项（初始化、测量、经典收尾）：忽略不计。

把具体数字代进去感受量级（时效标注：2026-11 视角，估算本身在演进）：拆一个 2048 位的 RSA 模数（现实世界的主流规格），n≈2048，n³≈百亿门。2019 年的著名资源估算：约两千万个含噪物理比特、跑八小时；2025 年的新估算：压到百万比特以内、一周量级——六年时间，参数松了二十倍。趋势说明估算会持续变化，但量级没有变：百万物理比特起步。今天最好的机器是千比特级——差三个数量级。

一台机器，多张面孔：相位估计

037 篇说过 Shor 的核心是"QFT 吃周期"，本篇补上它的通用名字：相位估计——给定一个量子操作 U 和它的一个特征态，估计 U 附在该态上的特征相位。幂序列的周期 r，在"乘 a 的模 N 操作"里恰是这个操作的特征相位（周期与相位差一个 2^k 的比例，连分数把比例拉回来）。

这张"通用名片"是 Shor 留下的最大遗产：任何"操作自带隐藏相位"的问题都能接上同一台相位估计机——041 篇它将以本名立传；批五的量子化学里，分子的基态能量正是一个操作的特征相位——化学家要的"精确能量"，与密码学家要的"周期 r"，走的是同一台机器的两条产线。王座算法真正登基的范围，比"破解 RSA"宽得多。

车间视角的三个提醒

一，门数不是运行时间。电路上标着 n³ 个门，但每个门都有错误率（006 篇），连乘起来电路越深、成品率越低——所以资源估算里有"物理比特"与"逻辑比特"两层（第六批的主角）。账单要看"含税价"。

二，NISQ 时代数的是保真度，容错时代数酵母。今天的机器没有纠错（030 篇提过 NISQ），电路的约束是"总错误率别淹没信号"——浅电路尚可，Shor 这种 n³ 深度在含噪机器上必死。这不是悲观，是预算：所以全世界的路线图都写着同一句话——先纠错，再 Shor。

三，小 Shor 是可以真跑的。037 篇开头的 N=15 例，完整电路约用 5~7 个比特、几十个门——030 篇的两条跑道绰绰有余：免费模拟器秒跑，真机免费档也烧得起。想亲手看"周期变频率峰"，这是全专栏性价比最高的一次上机。

把类比拆掉

"流水线"类比借了哪里：

• 不像之一：工厂流水线的工件是实体，逐件通过；量子流水线的"工件"是同一份叠加里的所有分支——流水线只开一条，所有订单同时在线上（031 篇宪法）。类比负责"逐位加工的次序"，别负责"多条并行"。
• 不像之二：流水线造完就出厂；量子流水线出口还站着 QFT 与测量两道关——门数只是半张账单，噪声、纠错、酵母价才是另一半。看电路图读成本，永远两张单一起看。

带走的行李

1. 模运算黑箱=逐位平方流水线：x 寄存器每位一条控制线，n 个受控模乘模块，约 n³ 个门——"指数变多项式"在电路层的实物。 2. 总账单：模幂 n³ + QFT n²；容错时代按酵母（T 门）计价——拆 2048 位 RSA 的估算从两千万比特（2019）演进到百万比特（2025），量级未破（2026-11 视角）。 3. Shor 是相位估计的特例：同一台机器的第二条产线是化学基态能量（批五）；上机建议——N=15 的小 Shor 用 5~7 比特，免费跑道即可亲跑。

下一站的钩子：百万比特、容错、酵母蒸馏——把这几个词放回语境，就该回答那个每年都被问一遍的问题："RSA 到底哪天被拆？"答案比新闻标题冷静得多，也比它有意思得多。039《为什么 Shor 不会立刻杀死 RSA：工程现实》。

#量子计算 #从硬币到纠错 #Shor算法 #相位估计