虚拟 QRAM 与系统架构

Xu 等(MICRO 2023)给出首个 QRAM 端到端系统架构,核心是"虚拟 QRAM":像经典虚拟内存换页一样,用 O(M) 物理比特查询远大于 M 的虚拟地址空间,并首次解决 QRAM 的 2D 布图与非对称纠错问题。

机制回顾:分页、两段式与 load-once

要查询的表 $D:\{0,1{\}}^n\to \{0,1\}$ 共 $N=2^n$ 项,目标语义是把叠加地址与数据相干纠缠(查询语义的三寄存器合同见 查询语义:路由与读出):

$Q_D:{\sum }_{i=0}^{N-1}{\alpha }_i|i{⟩}_A|0{⟩}_B⟼{\sum }_{i=0}^{N-1}{\alpha }_i|i{⟩}_A|D_i{⟩}_B.$

物理 QRAM 装不下 $O(N)$ 个比特时,把经典内存切成 $K=2^k$ 个连续页(page),每页 $M=2^m$ 格,满足 $k+m=n$。$n$ 位虚拟地址随之拆成两段:高 $k$ 位是页号(SQC 宽度,由顺序查询电路 sequential query circuit (SQC) 处理),低 $m$ 位是页内偏移(QRAM 宽度,由容量 $M$ 的 bucket-brigade 路由树处理,树机制见 桶队架构 与 GLM 2008)。整套构造出自 Xu et al. 2023。

一次虚拟查询分两段循环执行。地址装载段(整个查询只做一次):$m$ 个低位地址比特按桶队规程依次路由进树(纯 SWAP/CSWAP/CX 网络),随后在叶子上准备数据节点。数据检索段(对每页 $p=0,\dots ,2^k-1$ 各一遍):类控 SWAP 把页 $p$ 的经典数据写进叶数据节点(双轨编码 dual-rail encoding:$x_{p,j}=0/1$ 写作 $|10⟩/|01⟩$);$m$ 层 CX 阵列把双轨数据逐级压缩到根节点;一个以 $k$ 个高位比特为控制的 MCX 在”页号 $=p$“的分支上把根节点数据抄进总线;再逆序卸载,树回到标准态换下一页。load-once 性质指低位地址只在开头装载、结尾卸载各一次——此前混合设计(Hann 等的按块混合架构)每查一页都要重新装载一次树,$2^k$ 页就是 $2^k$ 次装载 Hann 2021 Xu et al. 2023。这一差别是 T 账指数改进的主因(推导二)。

三项系统优化贯穿全文的账目,按论文表 1 记:

• 地址比特回收(address qubit recycling):检索段期间树内部路由器闲置,让它们兼任数据比特,内部路由器的双轨数据节点整个省掉;比特数从 $6\cdot 2^m+k$ 降到 $4\cdot 2^m+k$。算术自洽的分解:$6\cdot 2^m\approx 2\cdot 2^m$(双轨路由器)+ $4\cdot 2^m$(叶与内部的数据节点各 $2\cdot 2^m$),回收恰好砍掉内部那 $2(2^m-1)$ 个。
• lazy data swapping:相邻页同一偏移的数据相同($x_i\oplus x_{i+2^m}=0$)时卸载-重装是冗余的,可跳过;均匀数据下跳过概率 $1/2$,类控 SWAP 从 $2^{m+k-1}$ 个降到 $2^{m+k-2}$ 个——论文把节省量记为 $O(2^{n-1})$ 量级(常数因子 $1/2$ 被大 $O$ 吸收)。
• 地址流水线(address pipelining):装载深度从 $m^2+(m+1)\cdot 2^k$ 降到 $m+(m+1)\cdot 2^k$,推导见下一节。

推导一:虚拟查询的幺正等价性

“虚拟 QRAM 等价于一次大 QRAM 查询”不是比喻,而是可以逐行验证的算符恒等式。把它写严格,同时也就写清了它成立的边界条件。

页查询算符与受控分解

固定记号:地址 $i=(y,j)$,高位 $y\in \{0,1{\}}^k$ 是页号、低位 $j\in \{0,1{\}}^m$ 是页内偏移,数据 $x_{y,j}=D_{(y,j)}$。小 QRAM(树 + 总线 + 辅助)定义”单页检索”算符

$V_p:|j⟩|0{⟩}_{\mathrm{bus}}⟼|j⟩|x_{p,j}{⟩}_{\mathrm{bus}},$

由类控双轨写入、CX 压缩阵列、根部 MCX 与逆序卸载构成。把它对高位比特做受控化:

$C_p={\sum }_{y=0}^{2^k-1}|y⟩⟨y|\otimes V_p^{(y)},V_p^{(y)}=\{\begin{array}{ll}{V}_p,& y=p,\\ 1,& y\ne p.\end{array}$

物理上 $C_p$ 就是”第 $p$ 轮页检索”:MCX 的 $k$ 个控制(高位比特)自动保证只有页号恰为 $p$ 的振幅被写入。

三条引理

引理 1($C_p$ 酉)。 每个固定 $y$ 的块上,$V_p^{(y)}$ 是计算基上的置换——双轨写入、CX 阵列、MCX、卸载全是经典可逆操作,把基态映到基态;分块酉的直和仍酉。

引理 2(页循环可交换)。 取 $p\ne p^{\prime }$,在块 $y$ 上比较 $V_p^{(y)}{V}_{p^{\prime }}^{(y)}$ 与 $V_{p^{\prime }}^{(y)}{V}_p^{(y)}$:$y\notin \{p,p^{\prime }\}$ 时两者都是 $1\cdot 1$;$y=p$ 时是 $V_p\cdot 1=1\cdot V_p$;$y=p^{\prime }$ 对称。所有块可交换,故 $[C_p,C_{p^{\prime }}]=0$。推论:页检索的经典执行顺序无关紧要——虚拟化不需要任何”量子页调度”,任意固定页序(乃至任意相干实现的页序)给出同一个总幺正。

引理 3(总幺正实现 $Q_D$)。 记装载段为 $U_{\mathrm{load}}$(只作用于低位比特与树,是 Clifford 网络),全查询为

$U=U_{\mathrm{load}}^{†}{C}_{2^k-1}{C}_{2^k-2}\cdots C_1{C}_0{U}_{\mathrm{load}}.$

对基态分量逐项追踪。由线性性,只需看单项 ${\alpha }_{y,j}|y,j{⟩}_A|0{⟩}_B$:$U_{\mathrm{load}}$ 把低位 $j$ 装进树,总线仍 $|0⟩$;轮到 $C_y$ 时,MCX 控制满足”页号 $=y$“,双轨数据 $x_{y,j}$ 被压到根并抄进总线,随后卸载把树复原;之前各轮 $C_{p<y}$ 对该分量恒等(MCX 不触发,数据写入与卸载在同一轮内自消),之后各轮 $C_{p>y}$ 亦然。净效果:

$C_{2^k-1}\cdots C_0{\sum }_{y,j}{\alpha }_{y,j}|y,j⟩|0⟩={\sum }_{y,j}{\alpha }_{y,j}|y,j⟩|x_{y,j}⟩.$

再经 $U_{\mathrm{load}}^{†}$ 把树清空复位、低位比特回位,即得 $Q_D$。$■$

等价成立的三个前提

等价性推导暴露了三个必须守住的边界条件,它们也是本方案与”真大 QRAM”的实质差距所在:

1. 干净总线。 若总线初态是 $|\varphi ⟩\ne |0⟩$,第 $C_y$ 轮的 MCX 把 $X^{x_{y,j}}$ 作用在 $|\varphi ⟩$ 上而非制备 $|x_{y,j}⟩$;整个等价只在”读入全新寄存器”的 QRACM 语义下成立(主动/被动与地址-数据四分类的定位见 分类学:四分类与主动/被动)。
2. 全程相干。 $2^k$ 轮页检索必须作为同一个幺正演化执行;任何一处中途测量高位页号都会把叠加塌缩成经典随机访问。虚拟化省的是硬件宽度,不省相干性预算——这是它与经典虚拟内存最深的差别:经典换页可以中断、可以缺页处理,量子换页的每一页都必须”在场”。
3. 卸载完备。 每轮的逆序卸载必须精确复原树。若有残余(如某个 CX 漏配),第 $y$ 页的数据残迹会经下一轮的 CX 阵列泄入其他分支,引理 3 的逐项追踪随即失效。

与经典虚拟内存的对应关系可以逐项对上:页表 $y\mapsto$ 页 $y$ 是恒等映射,SQC 扮演 MMU(地址翻译),类控 SWAP 扮演换页 I/O;但”缺页”在这里不是异常处理而是常态——每个地址分量都要把属于自己的页搬进物理 QRAM 一遍,这正是深度账里 $2^k$ 因子的来源。

推导二:深度账:$(m+1)\cdot 2^k$ 与 Clifford+T 记账

地址装载:从三角和到流水线

朴素调度下,第 $\ell +1$ 个地址比特要等第 $\ell$ 个在树里到位才出发,装载总深度是三角和

${\sum }_{\ell =1}^m\ell =\frac{m(m+1)}{2}=\Theta (m^2).$

流水线调度让第 $\ell +1$ 个比特在第 $\ell$ 个刚下移一层时立即进树:关键路径变为”首比特走完全部 $m$ 层”加上固定的错拍间隔,深度降为 $\Theta (m)$。直觉:这是把”串行发车”改成”间隔发车”,树是 $m$ 级移位结构,天然吃这一套。论文的流水线调度与 Hann 等、Di Matteo 等的并行调度等价,但把并行的来源点名为流水线 Xu et al. 2023;电路级再往下压要换分解方案(见 电路级优化 与 Paler 2020)。

每页成本与总深度

检索段每页的深度构成:类控双轨写入 $O(1)$ 层,CX 压缩阵列 $m$ 层,根部 MCX 记 1 层(未分解到 Clifford+T 的口径),卸载与换页写入并行——合计 $m+1$ 层的口径(论文表 1)。乘上 $2^k$ 页、加上装载:

$\Delta (k)=m+(m+1)\cdot 2^k=\Theta (m\cdot 2^k).$

渐近读法:总深度 = 页数 × 每页深度。每把一个地址比特从 QRAM 宽度挪到 SQC 宽度($m\to m-1$,$k\to k+1$),物理宽度近似减半,深度翻倍——虚拟化的本质是用时间的指数换空间的指数。

Clifford+T 记账:load-once 的指数收益

把门集分解到 Clifford+T,T 账只有两个来源:

• 装载段:SWAP/CSWAP/CX 全是 Clifford,但 CSWAP 分解到 Clifford+T 需深度 12、T-depth 3、零辅助比特(论文引 Amy et al. 2014)。装载网络含 $O(2^m)$ 个树内 CSWAP,合计 T-count $O(2^m)$、T-depth $O(m)$(关键路径 $m$ 层)。
• 检索段:每页一个 $k+1$ 控制的 MCX,T 成本 $O(k)$;$2^k$ 页合计 T-count 与 T-depth 均 $O(k\cdot 2^k)$。
• 类控门不计入 T 账:控制端是经典信号,不产生相干分解开销。

汇总即论文表 2(Big-O),与两个基线对照:

架构	比特数	电路深度	T-count	T-depth	Clifford 深度
SQC+BB(每页重装)	$2^m+k$	$m\cdot 2^k$	$(2^m+k)\cdot 2^k$	$(m+k)\cdot 2^k$	$(m+k)\cdot 2^k$
SQC+SS(load-once,换网)	$2^m+k$	$m^2\cdot 2^k$	$2^m+k\cdot 2^k$	$m+k\cdot 2^k$	$(m^2+k)\cdot 2^k$
虚拟 QRAM(load-once,树)	$2^m+k$	$m\cdot 2^k$	$2^m+k\cdot 2^k$	$m+k\cdot 2^k$	$(m+k)\cdot 2^k$

三行对照把两个设计自由度分开了。load-once 贡献 T 账的指数改进:每页重装的设计要把地址比特铺到 $O(2^m)$ 个路由器控制端(每层 $2^{\ell -1}$ 个控制,${\sum }_{\ell }{2}^{\ell -1}=2^m-1$),这份 $O(2^m)$ 的 T 账乘上 $2^k$ 页得 $(2^m+k)\cdot 2^k$;load-once 把它变成一次性的装载网络,$2^m$ 因子从流量栏搬进存量栏,T-count 降到 $2^m+k\cdot 2^k$——省掉的正是每页重装乘出的 $2^m\cdot 2^k$ 项 Xu et al. 2023。路由树贡献深度的平方改进:SQC+SS 同样 load-once,但第二段靠 CSWAP 换网而非树状路由,每页深度 $O(m^2)$,Clifford 深度涨到 $(m^2+k)\cdot 2^k$;T 账与虚拟 QRAM 同阶。可见深度优势来自”$m$ 层树 + 地址流水线”的组合,而非 load-once 本身。

小对照($n=16$,$k=4$,$m=12$):深度 $12+13\cdot 16=220$ 层,T-count $O(2^{12}+4\cdot 2^4)=O(4,160)$;纯 SQC($k=16$,$m=0$)深度 $2^{16}=65,536$ 层、T-count $O(16\cdot 2^{16})\approx 1.0\times 10^6$;纯 BB($k=0$)深度约 $2m+1=41$ 层但要 $2^{16}$ 个物理路由比特。虚拟化的位置一目了然:深度居中、宽度居中。

推导三:k 的最优化:深度–宽度–噪声三元权衡

单调性与平衡点

固定 $n$,令 $m=n-k$。宽度账(逻辑计数,论文表 2;比特编码的物理计数再乘 4)与深度账分别为

$w(k)=2^{n-k}+k,d(k)=m+(m+1)2^k=(n-k)+(n-k+1)2^k.$

两者单调性的代数很短:

$w(k+1)-w(k)=2^{m-1}+1-2^m-k=1-k-2^{m-1}\le 0,$

$d(k+1)-d(k)=-1+(m-1)2^k\ge 0(m\ge 2),$

即 $m\ge 2$ 时宽度严格递减、深度(弱)递增且被 $2^k$ 主导——实质指数上升。平衡点解 $d(k)\approx w(k)$,即 $(m+1)2^{n-m}\approx 2^m$;取对数得 $2m-n\approx {\log }_2(m+1)$,故

$m_{\text{*}}\approx \frac{n+{\log }_2{m}_{\text{*}}}{2}(\text{迭代求解,如 }n=20:m=12\to 11.85\to m_{\text{*}}\approx 11.8,k_{\text{*}}\approx 8).$

数值表($n=20$;$d$、$t$、$w$ 分别为深度、T-depth $=m+k\cdot 2^k$、逻辑宽度):

$k$	$m$	$d(k)$	$t(k)$	$w(k)$
0	20	41	20	1,048,576
2	18	94	26	262,146
4	16	288	80	65,540
6	14	974	398	16,390
8	12	3,340	2,060	4,104
9	11	6,155	4,619	2,057
10	10	11,274	10,250	1,034
12	8	36,872	49,160	268
14	6	114,694	229,382	78
16	4	327,684	1,048,580	32
20	0	1,048,576	$\approx 2.1\times 10^7$	20

$d$ 与 $w$ 的交点落在 $k=8$($d<w$)与 $k=9$($d>w$)之间,与解析估计一致。表的另一读法:T-depth 对大 $k$ 的惩罚比深度更狠($t(20)/d(20)\approx 20$:每页 MCX 的 $k$ 层 T 链在纯 SQC 端完全主导),所以”深度可接受”不等于”T 账可接受”。

噪声约束:k 应取宽度预算允许的最小值

推导四将给出整体不保真度的最坏情形包络 $I(k)=8\epsilon (m+1)\cdot 2^k(k+m)$(式 (5))。相邻比

$\frac{I(k+1)}{I(k)}=\frac{m}{m+1}\cdot 2\cdot \frac{k+m+1}{k+m}\stackrel{m,k\gg 1}{\to }2,$

每加一比特 SQC,最坏情形不保真度近乎翻倍;而加一比特 QRAM 宽度只添 $O(\epsilon m)$ 一项。机制层面更直白:SQC 段对任意 Pauli 错误毫无内在韧性($1-F\approx \epsilon k\cdot 2^k$),QRAM 段却有 $4\epsilon m^2$ 的局域化保护——把地址比特放进 SQC,等于把它从”有保护的账本”挪进”无保护的账本”。论文图 11 “增大 $k$ 比增大 $m$ 使保真度衰减快得多”的结论即由此而来 Xu et al. 2023。

于是设计法则是:在宽度预算内取最小 $k$。给定预算 $W$,约束 $2^{n-k}+k\le W$ 的近似解为 $k\approx n-\lfloor {\log }_{2}W\rfloor$。数值例:$n=20$、$W=2^{13}=8,192$——$k=7$ 时 $w=2^{13}+7=8,199$ 恰好超限,$k=8$ 时 $w=4,104$ 入围,故取 $k=8$、$m=12$(物理比特编码计数 $4\cdot 2^{12}+8=16,392$,是否可行取决于表面码占地)。

推导四:噪声账:Z 局域化与 X 全局失效

虚拟化没有破坏桶队最珍贵的性质——相位错误局域化——但把它折算成了对 $k$ 的硬约束。以下推导忠实复现论文 §5 的链条 Xu et al. 2023;一般噪声版本与有限纠缠根源见 一般噪声下的韧性 与 误差局域化。

好分支分解

取相位翻转信道 $\rho \mapsto (1-\epsilon )\rho +\epsilon Z\rho Z$(每个物理比特独立,错误率 $\epsilon$)。查询保真度定义为 $F=|⟨{\psi }_{\mathrm{out}}|{\psi }_{\mathrm{out}}^{\prime }⟩{|}^2$。关键观察是 Z 错误不沿树向上传播:CX 型门的共轭关系 $Z_c\to Z_c{Z}_t$、$Z_t\to Z_t$、$X_c\to X_c$、$X_t\to X_c{X}_t$ 表明相位错误只顺着门作用方向扩散进子树,不会污染兄弟分支;论文图 7 用交换子关系逐门演示了这一点。于是对每个计算基分支 $i$,存在”理想运行”条件:该分支路径上的路由器在整个查询中无 Z 错误。把理想分支集合记为 $Q_{\mathrm{good}}\subseteq \{0,\dots ,2^{m+k}-1\}$,输出分解为

$|{\psi }_{\mathrm{out}}^{\prime }⟩=\underset{\text{与理想输出重合的部分}}{\underbrace{\sum _{i\in Q_{\mathrm{good}}}{\alpha }_i|i{⟩}_A|x_i{⟩}_B}}+|{\psi }_{\mathrm{bad}}⟩.$

好分支与理想输出完全重合、坏分支携带权重 $1-P_{\mathrm{good}}$(这里 $P_{\mathrm{good}}={\sum }_{i\in Q_{\mathrm{good}}}|{\alpha }_i{|}^2$)。论文以 $|{\psi }_{\mathrm{out}}⟩$ 归一化为条件,把坏分支的内积用总权重封顶,得

$F=|⟨{\psi }_{\mathrm{out}}|{\psi }_{\mathrm{out}}^{\prime }⟩{|}^2\ge (2P_{\mathrm{good}}-1{)}^2.$

Z 界的完整推导

错误模型与分支无关,故理想分支的期望占比由单分支理想概率决定。每条分支的数据要沿 $m$ 层压缩阵列逐级上行,论文把单分支的错误暴露计为 $m^2$ 份($m$ 个路径路由器 × $m$ 层),于是单分支理想概率为 $(1-\epsilon {)}^{m^2}$,期望理想分支数为 $\mathbb{E}[c]=2^m(1-\epsilon {)}^{m^2}$,而

$\mathbb{E}[{\sum }_{i\in Q_{\mathrm{good}}}|{\alpha }_i{|}^2]=\frac{\mathbb{E}[c]}{2^m}=(1-\epsilon {)}^{m^2}.$

代回好分支不等式,再用两个初等不等式:Bernoulli 型下界 $(1-\epsilon {)}^{m^2}\ge 1-\epsilon m^2$,以及平凡展开 $(1-2\epsilon m^2{)}^2=1-4\epsilon m^2+4{\epsilon }^2{m}^4\ge 1-4\epsilon m^2$:

$\mathbb{E}[F]\ge (2(1-\epsilon {)}^{m^2}-1{)}^2\ge (1-2\epsilon m^2{)}^2\ge 1-4\epsilon m^2=1-4\epsilon {\log }^{2}M.$

这就是论文式 (3):QRAM 段(不含 SQC)的查询保真度下界随地址宽度 $m$ 多项式衰减,而非随树尺寸 $2^m$ 指数衰减。若采用双轨编码,路由器与数据比特翻倍、每路由器错误机会翻倍,同一推导逐字成立,只差常数因子:

$F_{\mathrm{dual}\text{-}\mathrm{rail}}\ge 1-8\epsilon m^2.$

直觉:每个分支只有 $m$ 个路由器”看门”,一颗 Z 错误只毁掉指数少分支中自己所在的那一支;树的其他部分哪怕全错,也好分支照常。这是有限纠缠局域化(见 误差局域化)在分页架构上的重现;Hann 等对一般 CPTP 信道的严格版本是 $1-F\le 4\epsilon T\log N$ Hann 2021。

X 界与 SQC 段:两条指数坏账

X(比特翻转)走的是共轭关系的另一支:$X_t\to X_c{X}_t$,错误沿阵列逆向爬向根。论文指出:任何一个 X 错误都会传播到根数据比特,毁掉整个查询态——于是”理想分支”的条件从”我的 $m$ 个路由器没错”退化为”全部 $O(2^m)$ 个比特无一出错”,理想概率 $(1-\epsilon {)}^{\Theta (m\cdot 2^m)}$。论文给出的 QRAM 段 X 信道下界是 $F\ge 1-8\epsilon m\cdot 2^m$:指数项 $2^m$ 显式回场,多项式保护消失。SQC 段对任意 Pauli 错误同样脆弱:$k$ 个控制比特在 $2^k$ 次 MCX 里累计 $k\cdot 2^k$ 次致命暴露,union bound 给 $1-F_{\mathrm{SQC}}\approx \epsilon k\cdot 2^k$。把树错误按门级信道蒙特卡洛抽样,结论不变——每条分支至多与 $O(m)$ 个门相交,标度相同。

合并界

两段合并、放宽常数因子后,论文统一写成(Virtual、下标 Z/X 指主导错误信道):

$F_{\mathrm{virtual},Z}\ge 1-8\epsilon (m+1)\cdot 2^k(k+m)\text{(5)}$

$F_{\mathrm{virtual},X}\ge 1-8\epsilon (m+1)\cdot 2^k(k+2^m)\text{(6)}$

读法:式 (5) 的系数 $(m+1)(k+m)\ge m^2$,同时压住”QRAM 段 $4\epsilon m^2$ 乘页数因子”与”SQC 段 $\epsilon k\cdot 2^k$“两项贡献;式 (6) 的 $(k+2^m)$ 则把 X 的全局失效要求(树尺寸)显式写进账面。两个包络都是最坏情形口径,合并时把不同机制的最坏情形串乘,数值上偏保守(数值算例一节可见它与机制分项的差距)——但它们给出的设计判据是稳的:X 比 Z 脆、SQC 比 QRAM 脆、$k$ 比 $m$ 贵。

推导五:非对称纠错的码距差

包络 (5)(6) 的不对称直接兑换成纠错码形状的选择。设物理错误率 $p$ 对 X/Z 无偏置,矩形表面码(rectangular surface code)的逻辑错误率满足(论文引 Bonilla Ataides et al. 2021)

$\frac{p_x^l}{p_z^l}\approx (\frac{p}{p_{\mathrm{th}}}{)}^{d_x-d_z},$

其中 $p_{\mathrm{th}}$ 为阈值、$d_x,d_z$ 为两个方向的码距。要令整体查询对两类错误平衡,令式 (5)(6) 的系数相等:

$\frac{{\epsilon }_x}{{\epsilon }_z}=\frac{8\epsilon (m+1)2^k(k+m)}{8\epsilon (m+1)2^k(k+2^m)}=\frac{k+m}{k+2^m},$

即需要 $p_x^l/p_z^l=(k+m)/(k+2^m)$。对数换底后得设计公式

$d_x-d_z\approx \frac{\ln \frac{k+m}{k+2^m}}{\ln \frac{p}{p_{\mathrm{th}}}}.$

符号判据:由于 $2^m\gg m$ 几乎总是成立,比值 $(k+m)/(k+2^m)<1$;又因物理错误率低于阈值($p/p_{\mathrm{th}}<1$,对数为负),必须 $d_x-d_z>0$——X 方向码距要拉大。物理根源正是推导四:X 错误会爬到根毁掉全场查询,是两项包络中更脆的那一支,码要在 X 方向加厚来补。

数值例(假设 $p=10^{-3}$、$p_{\mathrm{th}}=10^{-2}$,即 $p/p_{\mathrm{th}}=0.1$;数值假设非论文数据):

• $k=8$,$m=12$:比值 $=20/4,104=4.87\times 10^{-3}$,$d_x-d_z\approx \ln (4.87\times 10^{-3})/\ln (0.1)=(-5.32)/(-2.30)\approx 2.3$。两码距均取奇数故差为偶数,最小取 2(如 $d_z=11$、$d_x=13$),保守取 4。
• $k=4$,$m=16$:比值 $=20/65,540=3.05\times 10^{-4}$,$d_x-d_z\approx (-8.09)/(-2.30)\approx 3.5$。树越宽,X 码距越要拉——因为 $k+2^m$ 由树尺寸主导。

SQC 的 $k$ 个地址比特没有任何偏置可利用,论文的处理是用标准方形码($d_x=d_z$)全保护。非对称编码因此是”按部位分工”的:树上的逻辑比特用矩形码放大对 X 的裕量,地址寄存器用方码兜底。

2D 布图:传送路由为何是必需品

路由树的层 $\ell$ 有 $2^{\ell }$ 个节点,让每个节点与父、子等距只在双曲几何里可能;嵌进 2D 欧氏网格必然要付布图代价。论文的构造分两步 Xu et al. 2023:

H-tree 递归嵌入把容量 $M=2^m$ 的树铺成边长 $\Theta (\sqrt{M})$ 的方格:容量 $M=2^{2n}$ 的树嵌入边长 $2^{n+1}-1\approx 2\sqrt{M}$ 的方格,面积 $4M=O(M)$——渐近零开销;以 $(2^n-1{)}^2:(2^{n+1}-1{)}^2\approx 1:4$ 计,空置比特约 25%,改进嵌入可再压低。

传送路由(teleportation routing)解决远程门:两个逻辑比特之间闲置的比特可充当路由比特,局域 EPR 对制备与 Bell 态测量(BSM)并行执行,经纠缠交换把任意远程门(如跨层的 CSWAP)压回 $O(1)$ 深度;总查询深度保持 $O(\log M)$。对照方案 SWAP 路由的失败模式在论文图 8 中量化:根到叶距离 $\sim \sqrt{M}$,靠相邻 SWAP 搬运一个远程门本身就要 $O(2^{m/2})$ 层——额外深度随 $m$ 指数增长,对数深度标度整个丧失。这一布图后来被因果律分析采纳为”传送型 2D 设计”的实例(见 因果律极限)。

验证与局限

验证侧的两件工具值得一提。Feynman 路径模拟器:QRAM 电路由经典可逆门构成,基态映到基态,于是含噪仿真可以按”每个地址一条路径”展开,存储不随电路深度指数涨;论文最大规模仿真仅用 1.5 MB 内存,且是首个支持任意输入(容量、地址态、噪声模型)的通用 QRAM 模拟器(ECS 类可模拟性的一般讨论见 QRAM 模拟器)。IBMQ 噪声模型仿真($m=1,2$):当前 $10^{-3}$ 错误率下性能受限;错误率若经近期小规模纠错降到 $10^{-5}$,查询保真度可超 0.98 Xu et al. 2023——与推导四的量级核算一致($m=2,k=1$ 时式 (6) 包络 $8\epsilon \cdot 3\cdot 2\cdot 5=240\epsilon$,$\epsilon =10^{-5}$ 给 $F\ge 0.9976$)。

局限同样要按账本记:(i) QRAM 内部比特间通信的信号延迟是论文自认的关键瓶颈,传送路由的解法依赖 EPR 对制备与 Bell 测量的硬件能力;(ii) SQC 段无噪声韧性,这是虚拟化把地址比特挪出树的直接代价;(iii) 偏置噪声假设依赖 cat/dual-rail 一类硬件编码,双轨的代价已计入常数因子($4\epsilon m^2\to 8\epsilon m^2$);(iv) 验证规模仍小($m\le 2$ 的硬件仿真),大 $k$ 区间的包络只能靠解析界。

讨论:适用边界

何时虚拟化占优。 三类情形,各自对应一条账目:

• 宽度是硬约束时。容错口径下每个逻辑比特背后是约 $10^3$ 物理比特,$2^{20}$ 逻辑比特的 QRAM 器件不是工程对象,$2^{12}$ 是。虚拟化把”造不出的内存”换成”跑得慢的查询”:每加一比特 SQC 用 $2\times$ 深度换 $2\times$ 宽度,这笔交换只在宽度栏已经爆表时才划算(宽度-深度曲线见推导三的表)。
• 查询数少时。全程时间 $\approx Q\cdot m{2}^k$。Grover 于 $N=2^{20}$ 需 $Q\approx (\pi /4)\sqrt{N}\approx 804$ 次查询(推导见 成本口径),虚拟化($k=8$)总深约 $804\times 3,340\approx 2.7\times 10^6$ 层:比纯 BB(约 $804\times 41\approx 3.3\times 10^4$ 层)深 81 倍,但仍远浅于纯 SQC(约 $8.4\times 10^8$ 层)。$Q$ 再涨两个量级,天平移向真 QRAM。
• 数据局部性好时。lazy data swapping 在均匀数据下把类控 SWAP 从 $2^{n-1}$ 砍半到 $2^{n-2}$;查表类负载中相邻页大量重复时收益更大,页间完全独立则退化回原计数。

何时不如真 QRAM。 吞吐与多查询场景(流水线共享见 Fat-Tree 共享 QRAM,摊销时延与 $N$ 无关);查询数超多项式的算法——此时按 Regev–Schiff 谱系的论证纠错不可回避,而 SQC 段必须整个套上无偏置的方码,虚拟化的容错优势被削平 Arunachalam et al. 2015 Hann 2021;以及硬件宽度本来够用的场合——$k=0$ 严格最优(深度、韧性同时最好),虚拟化是有限预算下的工程最优解,不是渐近改进;它的渐近主张只相对此前混合设计(SQC+BB、SQC+SS)成立,见推导二的表。

与通用语义的关系。 虚拟 QRAM 在 分类学:四分类与主动/被动 里仍是通用 QRACM(叠加地址、经典数据);在 评价指标:六维打分卡 的口径下,它牺牲深度与并行两维,换取物理资源与容错接口两维——这正是”六维同时报告”的教科书案例。电路路线的 T 账参照系见 边界:qROM 电路与 QROM 模型(Babbush 等的 unary iteration T-count $4L-4$ 与”对数深度 ≠ 对数成本”的警告 Babbush 2018)。

延伸阅读

• Fat-Tree 共享 QRAM
• 因果律极限
• 噪声韧性
• 桶队架构
• 两能级路由器
• 误差局域化
• 成本口径
• 边界:qROM 电路与 QROM 模型