fanout 架构

fanout(扇出)架构把经典 RAM 的寻址方式直接量子化:第 k 个地址比特经 CNOT 级联控制整层开关。它是 Giovannetti–Lloyd–Maccone 架构二分法中"直接但脆弱"的一支,也是 bucket-brigade 诞生的反面动因。

机制回顾:把经典译码器原样量子化

经典 RAM 用 $n={\log }_{2}N$ 位地址访问 $N=2^n$ 个存储单元,寻址靠一棵译码树:地址第 $k$ 位决定第 $k$ 层走左还是右。fanout 架构把这套结构原样搬进量子世界:第 $k$ 个地址比特 $a_k$ 经 CNOT 级联扇出,控制第 $k$ 层的 $2^k$ 个开关($k=1,\dots ,n$),全树合计

${\sum }_{k=1}^n{2}^k=2^{n+1}-2=2N-2$

个开关。(层号约定注记:若按”根部只有 1 个总开关、第 $k$ 层 $2^{k-1}$ 个”计数,总数为 $N-1$;两种口径差一个因子 2,不影响任何 $\Theta$ 结论。成本口径用后者,本词条随 分类学用前者。)一次查询分三步 GLM 2008 (PRA):

1. 扇出复制:把每个地址比特 $a_k$ 的取值经 CNOT 级联铺满第 $k$ 层全部 $2^k$ 个开关的控制端;
2. 总线读出:量子总线从根进入,逐层经过被寻址路径上的 $n$ 个开关,与目标单元相干交换数据;
3. 逆序 uncompute:撤除全部扇出,开关控制端复位,地址寄存器与树解纠缠。

其账目为:查询深度 $O(n)$(器件口径,见下节”三种调度”)、量子比特与门数均为 $O(N)$、不保真度标度 $\sim N\epsilon$ GLM 2008 (PRA)。对经典数据,这本是顺理成章的设计:地址比特是导线上的确定电平,“复制到整层”只是一根金属走线,不花任何相干性。问题出在量子地址上。复制基矢取值的 CNOT 并不违反不可克隆定理——它复制的是计算基矢的值,不是未知叠加态本身——但它把地址寄存器的叠加纠缠进了全部 $2N-2$ 个开关,叠加因此被摊在一组宏观组件上。fanout 的全部麻烦都从这个纠缠开始。

一个地址比特的最小扇出成本

引理(扇出门数下界)。 把单个比特的计算基矢取值从 1 个量子比特相干复制到 $m$ 个量子比特,至少需要 $m-1$ 个两比特门。

证明。 称一个量子比特”持有副本”,若在计算基矢的每个分支下它的取值都与源比特相同;记持有者集合为 $S$,$|S|=1$ 为初值。考察任一 CNOT(控制 $c$、目标 $t$):执行后 $t$ 的取值变为 $x_c\oplus x_t$。要使 $t$ 加入 $S$,必须对所有分支都有 $x_c\oplus x_t=x_c$,即 $t$ 原本恒为 $0$ 且 $c\in S$;此时恰有一个新成员加入,$|S|$ 增 1。其余情形($c\notin S$、$t$ 取值非恒零、或 $t$ 已在 $S$ 中)$|S|$ 不增。故每个 CNOT 使 $|S|$ 至多增 1,从 1 数到 $m$ 至少要 $m-1$ 个。平衡二叉复制树恰好用 $m-1$ 个,下界紧。$■$

第 $k$ 层的 $m=2^k$,扇出成本 $2^k-1$;全树复制门数

$G_{\mathrm{copy}}={\sum }_{k=1}^n(2^k-1)=(2N-2)-n=\Theta (N).$

若按”每个开关计一枚置位 CNOT、不扣每层首次复制”的粗口径,即为 ${\sum }_k{2}^k=2N-2$——共识策略与 QRAM 总览写的 $G_{\mathrm{fanout}}=2N-2$ 就是这个口径。数值:$n=20$ 时 $2N-2=2097150$、精确复制门数 $2097130$;$n=30$ 时 $2N-2=2147483646$。总线一侧,电路版 fanout 中每个存储单元都须具备与总线受控交换数据的能力,$N$ 个受控交换型门必须”在场”(装机口径);每个分支里真正激发的只有路径上的 $n$ 个(流量口径)。两个口径混用是文献里门数常数漂移的常见来源。

深度账的三种调度

“第 $k$ 层的 $2^k$ 个开关同时扳动”在物理器件图像里是一层并行动作——GLM 深度 $O(n)$ 的账目按此口径。但把它翻译成”每门至多涉及两个量子比特、一个量子比特每步至多参与一个操作”(独占激活,exclusive activation)的门级电路时,这一步不再免费:深度取决于复制怎么调度。

调度	每层复制深度	总深度	额外辅助比特
串行扇出($a_k$ 独任控制)	$2^k-1$	${\sum }_k(2^k-1)=2N-2-n=\Theta (N)$	0
树复制(开关控制端中转)	$\lceil {\log }_2{2}^k\rceil =k$	$O(n)$(各层复制树作用在不相交比特集上,并发)	0(占用开关控制端)
全局多目标门	$1$	$n$	0

三种读法。其一,串行口径是”逻辑层 fanout 只能串行”的准确含义(Gokhale 语 Gokhale et al. 2020):$2^k-1$ 个 CNOT 共享同一控制比特 $a_k$,独占激活下只能逐个执行。其二,树复制把每层复制深度压到 $k$、各层并发后总深度 $O(n)$,代价是开关控制端必须先写入、查询后逆序清理,且布线须支持树状 CNOT 连接。其三,全局多目标门——离子阱全局 Mølmer–Sørensen(GMS)门、超导和频驱动——把”单控制多目标”压成一个物理步骤,每层一步、共 $n$ 步,这是 Gokhale et al. 2020 复活论证的出发点(第 5 节)。GLM 的 $O(n)$ 属器件口径;传统门模型下直接把器件账翻译成电路,深度会退化到 $\Theta (N)$。同一架构、两本深度账,引用时必须分清。

推导一:门数与宽度——记在流量栏的 $\Theta (N)$

装机账(存量):开关 $2N-2$ 个、存储单元 $N$ 个、总线与地址寄存器,宽度 $W=\Theta (N)$(分类学给 $W=2N-2-n$ 的逐步推导)。门账(流量):每个分支中实际执行的纠缠两体门为复制 $(2N-2-n)$ 个加总线 $n$ 个,

$G_{\mathrm{branch}}=(2N-2-n)+n=2N-2=\Theta (N),$

查询结束的逆序 uncompute 把复制部分再翻倍;装机在场门(复制 $2N-2-n$ 加总线接口 $N$)同量级。GLM 摘要的总论断——”$n$ 位地址的 RAM/qRAM 设计需要 $O(2^n)$ 个两比特逻辑门” GLM 2008 (PRA)——在 fanout 上以 $2N-2$ 的常数精确兑现:fanout 是这个普适下界的朴素达成者,省不掉、也不多付。

与 bucket-brigade 的差别不在存量而在流量:两棵树都是 $\Theta (N)$ 个组件、搭建一次;fanout 每次查询把全部开关重新扳动一遍,$\Theta (N)$ 记在流量栏,bucket-brigade 只激活一条路径、流量栏是 $O({\log }^{2}N)$(三口径账见 成本口径)。存量/流量之辨是 分类学”主动/被动”二分之外的另一根坐标轴。

推导二:宏观叠加与 union bound——$\epsilon =O(2^{-n})$

复制网络把叠加摊成猫态

逐层看复制做了什么。第 $k$ 层扇出完成后,$a_k$ 与该层 $2^k$ 个控制端构成 $2^k+1$ 比特的 GHZ/猫态(cat state):

$\frac{1}{\sqrt{2}}\left(\right|0{⟩}^{\otimes (2^k+1)}+\left|1{⟩}^{\otimes (2^k+1)}\right).$

猫态相干项的退相干速率以”两个分支取值不同的比特数”计:环境与其中任意一个比特发生一次 which-path 作用就把相干项压低 ${\mathrm{e}}^{-{\epsilon }_{\mathrm{store}}T}$;$m=2^k+1$ 个比特等价于 $m$ 条独立的环境通道,退相干速率 $\approx m{\epsilon }_{\mathrm{store}}$——猫态比单比特脆 $m$ 倍(教科书级标准结果)。全树对层求和:

${\Gamma }_{\mathrm{decoh}}\approx {\sum }_{k=1}^n{2}^k{\epsilon }_{\mathrm{store}}=(2N-2){\epsilon }_{\mathrm{store}}.$

这就是”宏观叠加”(macroscopic superposition)在 fanout 里的精确含义:不是某个组件特别脆弱,而是脆弱性随进入叠加的组件数线性放大;GLM 所说 fanout 型 qRAM 中单个门退相干即可显著损伤平均保真度,机制即此 GLM 2008 (PRL)。bucket-brigade 的对应量只有 $O(n)$:等待态节点不与地址纠缠,不进入任何猫态。

union bound 与每分支暴露计数

设单门错误率 $\epsilon$、各门错误独立。关键观察是激活比(activation ratio——分支中被实际执行的开关操作占总开关数的比例)为 $1$:复制网络的每颗 CNOT 不看地址取值、在每个分支中都执行;每个分支真正”路过”的只有 $n$ 个路由开关。于是每分支暴露的错误通道数为

$G_{\mathrm{branch}}=\underset{\text{复制 CNOT,全分支执行}}{\underbrace{(2N-2-n)}}+\underset{\text{路由门}}{\underbrace{n}}\approx 2N-2.$

记 $G=2N-2$。单次查询不保真度 $1-F$ 的上端由 union bound(联合界,$\mathrm{Pr}[{\bigcup }_i{E}_i]\le {\sum }_i\mathrm{Pr}[E_i]$)给出;下端由”无任何门出错”的概率给出,而

$\mathrm{Pr}(\text{至少一门出错})=1-(1-\epsilon {)}^G,1-{\mathrm{e}}^{-\epsilon G}\le 1-(1-\epsilon {)}^G\le G\epsilon ,$

(中间一步用 $(1-\epsilon {)}^G\le {\mathrm{e}}^{-\epsilon G}$,右端即联合界。)复制 CNOT 的错误必然污染输出,故两端同时夹住 $1-F$:

$1-{\mathrm{e}}^{-\epsilon (2N-2)}\le 1-F\le (2N-2)\epsilon .$

只要 $\epsilon (2N-2)\ll 1$,两端重合于 $(2N-2)\epsilon$:误差账逐门线性累加,没有任何指数折扣。要求 $1-F\le \delta$,解出

$\epsilon \le \frac{\delta }{2N-2}=\Theta \left(2^{-n}\right),$

正是 GLM 的结论:单门误差必须随规模按 $O(2^{-n})$ 缩小,大规模下”必然屈服于噪声与退相干” GLM 2008 (PRA)。数值上 ${\epsilon }_{\mathrm{req}}\approx 2^{-(n+4.3)}$(常数来自 $\delta =0.1$ 与因子 2):每加一位地址,要求收紧一半。

GLM 首篇还给出更细的退化图景:若每条线上各坏一个门,保真度随层数按 $2^{-k}$ 衰减 GLM 2008 (PRL)。一个计数式读法:第 $k$ 层有一条线携带坏门时,恰有一半分支的路由经过它而被污染;逐层累乘,未被坏层触及的分支份额按 $2^{-k}$ 收缩——与”激活比 $=1$、无折扣累加”的图像一致。

对照 bucket-brigade 架构:其第 $\ell$ 层节点只被 $2^{-\ell }$ 的分支触碰,层内 $2^{\ell }$ 个节点与触碰比例逐层相消,每层贡献恰好一个 $\epsilon$,总账 ${\log }_{2}N\cdot \epsilon$(逐层推导见 查询语义)。两架构每分支错误之比

$\frac{(2N-2)\epsilon }{n\epsilon }=\frac{2N-2}{n}\approx \frac{2^{n+1}}{n}$

是指数对线性:$n=20$ 时约 $1.0\times 10^5$,$n=30$ 时约 $7.2\times 10^7$,$n=50$ 时约 $4.5\times 10^{13}$。

精细化(常数因子)。 逐门记账还可以更细:复制 CNOT 在全部分支执行,单颗出错污染全部分支,权重 $1$;第 $k$ 层某颗路由门出错只污染控制端取值与其动作匹配的那一半分支(另一半里它施行恒等操作),权重 $1/2$。加权合计 $1-F\lesssim (2N-2-n)\epsilon +(2N-2)\cdot \epsilon /2\approx 3N\epsilon$。可见 fanout 误差账的标度(随 $N$ 线性)对记账口径稳健,常数在 $2$ 与 $3$ 之间漂移;文献引用的均是 $O(N\epsilon )$ 级 GLM 2008 (PRA)。

存储退相干:第二重 $N$ 依赖

上面的账只数了门操作。开关控制端在整个查询期间持有依赖分支的取值——等待总线经过、再等待 uncompute——持有时长 $T$;每个控制端贡献存储退相干 ${\epsilon }_{\mathrm{store}}T$,这样的控制端有 $2N-2$ 个:

$1-F_{\mathrm{store}}\lesssim (2N-2){\epsilon }_{\mathrm{store}}T.$

取 $T\sim n$(总线逐层穿越),即得 $1-F\sim N\log N$ 标度——与 Hann 等对一般噪声信道(含去极化与相干误差)证明的 fanout 分档一致 Hann 2021(严格证明的依据是组件间有限纠缠而非逐门计数,见 噪声韧性;严格界的常数是 $4$,$T$ 为查询步数)。这条记账版推导给出了 $N\log N$ 的物理来源:门误差乘组件数,存储误差再乘持有时长;bucket-brigade 两项都只随路径长度 $O(n)$ 增长,因为等待态节点不携带分支信息。误差局域化(error localization)——单个坏组件只毁掉指数少的分支——在 fanout 中完全缺席(误差局域化)。

数值算例:$N=2^{20}/2^{30}/2^{50}$

取单查询预算 $\delta =0.1$,${\epsilon }_{\mathrm{req}}=\delta /(2N-2)$:

$n$	$N$	开关数 $2N-2$	${\epsilon }_{\mathrm{req}}$	对数形式
20	$2^{20}$(1 MiB 表)	$2097150$	$\approx 4.8\times 10^{-8}$	$\approx 2^{-24.3}$
30	$2^{30}$(1 GiB 表)	$2147483646$	$\approx 4.7\times 10^{-11}$	$\approx 2^{-34.3}$
50	$2^{50}$(1 PiB 表)	$\approx 2.25\times 10^{15}$	$\approx 4.4\times 10^{-17}$	$\approx 2^{-54.3}$

对照硬件:当前超导量子寻址路由的平均路由保真度为 95.3%,即 $\epsilon \approx 4.7\times 10^{-2}$ Miao 2025——距 $n=20$ 的要求差约六个数量级,距 $n=50$ 差约十五个,且差距每加一位地址翻倍。取同一 $\epsilon =10^{-3}$ 看单查询失真,fanout 为 $(2N-2)\epsilon \approx 2.1\times 10^3$、$2.1\times 10^6$、$2.3\times 10^{12}$(界早已饱和失效,无任何保护),bucket-brigade 为 $n\epsilon =2\%,3\%,5\%$ GLM 2008 (PRA)——同一棵树,两种命运。再乘算法层:用作 Grover 预言机需 $Q\approx (\pi /4)\sqrt{N}$ 次查询、误差按查询数线性累积,

$\epsilon \lesssim \frac{1}{Q(2N-2)}=O\left(2^{-3n/2}\right),$

$n=20$ 时约 $6\times 10^{-10}$(成本口径推导五的同源结论):搜索类用法把指数墙再推高半个指数。

推导三:与 bucket-brigade 逐项对比

账目	fanout	bucket-brigade(qutrit)	依据
树组件(存量)	$2N-2$ 开关	$N-1$ 节点	GLM 2008 (PRA)
每查询扳动/激活	$2N-2$(全部)	$\le n+1$(一条路径)	GLM 2008 (PRL)
每查询纠缠两体门	$\approx 2N-2$	$n(n+1)/2$(串行口径)	GLM 2008 (PRL)
深度(门级)	串行 $\Theta (N)$;全局门 $n$	串行 $n(n+1)/2$;流水线 $O(n)$	Gokhale et al. 2020
误差(GLM 口径)	$\sim N\epsilon$	${\log }_{2}N\cdot \epsilon$	GLM 2008 (PRA)
误差(一般噪声)	$\sim N\log N$	$\le 4\epsilon T\log N$	Hann 2021
干预(路径独立性)	$\Omega (N)$/查询	$\Omega (N)$/查询	Jaques-Rattew
传统 CSS 纠错后	(不动点)	退化为 fanout 式	Arunachalam et al. 2015

逐行推导或指引:

• 激活行。 fanout 每层 $2^k$ 个开关全部扳动,合计 $2N-2$;bucket-brigade 任意时刻至多 $n+1$ 个节点激活(均匀叠加下期望恰为 $n$,${\sum }_k{2}^k\cdot 2^{-k}=n$,推导见 成本口径口径 A)。任何树路由方案的激活数下界是 $n$——被选叶子的数据必须跨越 $n$ 层、每层至少一个节点携带分支信息——fanout 超出该下界 $\Theta (N/\log N)$ 倍(分类学)。
• 门行。 fanout 的 $2N-2$ 来自复制下界(引理)加总线;bucket-brigade 的 $n(n+1)/2$ 来自”第 $i$ 个地址比特经 $i$ 层接力、总线读出再走 $n$ 步”的三角和。两者分别是”纠缠两体门 $O(N)$ vs $O({\log }^{2}N)$“这一 GLM 名句的精确化 GLM 2008 (PRL) GLM 2008 (PRA)。
• 深度行。 fanout 的两本深度账见”三种调度”;bucket-brigade 串行深度同为三角和,但门级并行化与地址流水线可把摊销深度压回 $O(n)$(见 电路级优化)。全局多目标门对 bucket-brigade 同样有利,但接力语义本身已把每层操作数限到 $O(1)$,改善幅度小于 fanout 侧的指数级。
• 误差行(一般噪声)。 fanout 的 $\sim N\log N$ 是 Hann 分档中的最大档,bucket-brigade 的 $4\epsilon T\log N$ 是最小档(严格推导见 评价指标与 噪声韧性);两者之差就是”误差局域化”的有无(误差局域化)。
• 干预行。 两架构同罪:路径独立性要求控制系统在查询前给全部可能被激活的节点供能,叠加查询的干预账是 $\Omega (N)$,与路由动力学无关(推导见 成本口径推导三)。fanout 与 bucket-brigade 的分野在相干侧(哪些组件被拉进叠加),不在干预与能量侧——把两者混为一谈会高估 bucket-brigade 的节能。
• 纠错行。 对 bucket-brigade 施加传统 CSS 纠错,症状提取与恢复须触及全部节点,激活轮廓被抬回全树——fanout 是朴素容错的”退化终点” Arunachalam et al. 2015。这一行是下节”参照系”地位的理论根据之一。

一句话总结:fanout 把误差账单押在组件总数上(${\epsilon }_{\mathrm{req}}\sim 2^{-n}$),bucket-brigade 把它押在路径长度上(${\epsilon }_{\mathrm{req}}\sim 1/n$ 量级);指数对线性的差距,是 QRAM 架构学全部后续创新的出发点。

复活:全局多目标门下的再入局

fanout 并非全无价值。Gokhale 等(2020)指出,“一个量子比特每步最多参与一个操作”的独占激活是电路模型的结构冒险,并非多数硬件的真实约束:离子阱 GMS 门、超导和频驱动等全局相互作用可以一步完成单控制多目标 CNOT,“逻辑层只能串行”的 fanout 在物理层是一步 Gokhale et al. 2020。据此,基于 fanout 的显式存储可实现 $O(n)$ 深度、零辅助比特——第 2 节调度表的第三行;NISQ 工作负载的建模给出运行时间的渐近优势与 7–24% 的误差削减 Gokhale et al. 2020。并行性常数方面,共享控制的电路无论并行多少个,单比特门恒 5 层、Toffoli 恒 12 层、SWAP test 恒 14 层——深度不随并行度增长,这是全局门”免费并行”的直接体现。

要划清的是这条复活的边界:它重算的是深度账,不是误差账。 全局多目标门把 $\Theta (N)$ 个两体相互作用压进一个物理时间步,但参与相互作用的组件总数仍是 $\Theta (N)$,每查询的错误通道数不减——Hann 口径下 $\sim N\log N$ 的不保真度标度原样保留 Hann 2021(QRAM 总览持同一论断)。速度与深度归 fanout,噪声韧性归 bucket-brigade,两本账不可互相抵偿。

小规模实证与清醒面。离子阱建模中 $N=8$ 时同时 fanout 保真度 98.8%(串行 97.5%);IBM Paris 处理器上首次演示超导同时 fanout,GHZ 态 $|000⟩/|111⟩$ 占比 31%/29%(串行 42%/36%),同时执行快约 2 倍 Gokhale et al. 2020。需要清醒的是:超导 PoC 的保真度反而低于串行——它的价值在速度与深度,而非噪声;星型拓扑与频率工程在现有器件(最大连通度 3)上不可用,作者提出的调频共频、棋盘频率等方案均未验证 Gokhale et al. 2020。更小规模下 fanout 是现实选择:$n=3$ 时 $2N-2=14$ 个开关毫无负担,IBM Brisbane 上的实测访问时长为 84,560/185,240/380,120 dt(1/2/3 地址位),快于桶队的 84,560/289,680/596,280 dt Tan, Xu & Szefer 2024——浅而宽在 NISQ 尺度是真实优势;同一组数据也说明两种架构在执行时序上可区分,构成侧信道攻击面(见 QRAM 安全性)。

讨论:为什么 fanout 仍是”最坏情形参照系”

1. 基线语义。 fanout 是”不做任何架构发明”的默认——经典译码器的直接量子化。任何新 QRAM 提案的第一个对比对象就是它:相对 fanout 省掉了什么?若答案是”没省”,方案不成立。GLM 二分法、综述对照表、实验论文的基准电路,都从 fanout 开表 GLM 2008 (PRA) Jaques-Rattew。
2. 误差谱的上端锚点。 一般噪声分档里 fanout $\sim N\log N$ 是最差档 Hann 2021。“至少不比 fanout 差”是架构提议的最低门槛;Hann 系的混合方案(fanout 骨架加 $M$ 块桶队子树,$\sim N\log N+M{\log }^{2}N$)正是在这条谱系上做插值(见 噪声韧性)。
3. 朴素容错的不动点。 CSS 整体纠错把 bucket-brigade 的激活轮廓抬回全树 Arunachalam et al. 2015——无差别的容错自动把任何架构变回 fanout 式的全组件激活。fanout 因此刻画了”架构信息被纠错抹平后”的残余成本;任何容错 QRAM 方案必须说明自己如何避开这个归并(十八年时间线的纠错悖论一节)。
4. 干预最坏口径。 全树供能、全开关相干控制是干预与能量账的最坏情形 Jaques-Rattew;对 QRAM 可行性的批判以此为靶最直接,而 fanout 恰好是它的化身。
5. 教学与安全基准。 时序与高能态攻击以 fanout/bucket-brigade 为两极基准 Tan, Xu & Szefer 2024;理解 fanout 的失败条件,是理解 bucket-brigade 与噪声韧性论证的起点——本站多条推导(激活比、逐层相消、有限纠缠)都以”fanout 中该项为 1”作对照项。

账目的适用边界。 fanout 的坏账压在三个前提上:地址处于叠加、每门至多两个量子比特、组件须长时间保持相干。放松任何一个,结论随之松动:地址经典化(测量后译码)时它就是普通译码器,无相干要求;全局多目标门可用时深度账翻新(上节);$N$ 很小(NISQ)时 $2N-2$ 个门不算负担。$\epsilon =O(2^{-n})$ 是”大规模叠加寻址 + 传统门模型”下的结论——引用这条判据时,先确认自己站在同样的前提下。

延伸阅读

• bucket-brigade 架构
• 电路级优化
• 噪声韧性
• QRAM 分类学
• 成本口径:激活门、干预与能量
• 查询语义:路由与读出
• QRAM 总览:定义、三要素与存在理由
• 误差局域化
• QRAM 安全性