QRAM 总览:定义、三要素与存在理由

量子随机存取存储器(QRAM)是设想中能以量子叠加态寻址、把经典或量子数据相干地装载进量子处理器的专用器件:一次查询,全部被寻址单元同时响应。

定义与总览公式

经典 RAM 用 $n={\log }_{2}N$ 位地址随机访问 $N=2^n$ 个存储单元;QRAM 允许地址寄存器处于叠加态,执行

$$U_{\mathrm{QRAM}}:\sum _{\mathbf{x}}{\psi }_{\mathbf{x}}|\mathbf{x}⟩|0⟩⟼\sum _{\mathbf{x}}{\psi }_{\mathbf{x}}|\mathbf{x}⟩|D_{\mathbf{x}}⟩,$$

即对全部被寻址单元的数据做一次相干读取——输出仍是叠加态,而非逐个读出的经典结果。这一概念由 Giovannetti、Lloyd 与 Maccone(GLM)在 2008 年的两篇论文中奠定 GLM PRL 2008 GLM PRA 2008,其 bucket-brigade(桶队)架构把量子寻址所需的纠缠两体相互作用门从 $O(N)$ 降至 $O({\log }^{2}N)$。

公式的三个关键词各自排除一种”伪 QRAM”:叠加寻址(${\psi }_{\mathbf{x}}$ 是概率幅而非概率,携带相对相位,地址全程不被测量)、并行响应($N$ 个分支在一次查询内同时读出)、相干输出(输出仍是纠缠叠加态,保留分支干涉的可能)。

三要素

• 地址寄存器:持有叠加态地址 $\mathbf{x}$ 的量子寄存器;
• 路由树:$N-1$ 个节点(量子开关或路由器)组成的二叉树,把地址信息从根相干地传到叶子(见 查询语义);
• 存储单元阵列:$N$ 个被读取的单元,内容可为经典比特或量子态。

节点数 $N-1$ 是一条可验算的几何账目:第 $\ell$ 层($\ell =0,\dots ,n-1$)恰有 $2^{\ell }$ 个节点,总数为 ${\sum }_{\ell =0}^{n-1}{2}^{\ell }=2^n-1=N-1$。总览公式的第二个寄存器是总线寄存器(bus),读出经它落地;幺正延拓与不可克隆约束都挂在它身上。

寻址映射的形式化

地址编码与指标函数

设地址为 $n$ 位比特串 $\mathbf{x}\in \{0,1{\}}^n$,指标函数

$$\mathrm{idx}(\mathbf{x})=\sum _{j=1}^n{x}_j{2}^{n-j}\in \{0,1,\dots ,N-1\}$$

把比特串按大端序读作整数;“寻址 $\mathbf{x}$“即访问数据表 $D$ 的第 $\mathrm{idx}(\mathbf{x})$ 项。算例:$N=8$($n=3$)时 $\mathbf{x}=101$ 给出 $\mathrm{idx}=4+1=5$。QRAM 的全部非平凡性,来自把这个平凡映射线性延拓到叠加态上而不引入任何经典路径记录。

查询算符是等距映射

在计算基上定义

$$V:|\mathbf{x}⟩|0⟩⟼|\mathbf{x}⟩|D_{\mathbf{x}}⟩,D_{\mathbf{x}}:=D[\mathrm{idx}(\mathbf{x})],$$

并验证内积保持:

$$⟨V(\mathbf{x},0)|V({\mathbf{x}}^{\prime },0)⟩=⟨\mathbf{x}|{\mathbf{x}}^{\prime }⟩⟨D_{\mathbf{x}}|D_{{\mathbf{x}}^{\prime }}⟩={\delta }_{\mathbf{x}{\mathbf{x}}^{\prime }}\cdot ⟨D_{\mathbf{x}}|D_{{\mathbf{x}}^{\prime }}⟩={\delta }_{\mathbf{x}{\mathbf{x}}^{\prime }}=⟨(\mathbf{x},0)|({\mathbf{x}}^{\prime },0)⟩,$$

其中 $\mathbf{x}\ne {\mathbf{x}}^{\prime }$ 时第一因子已使乘积为零,$\mathbf{x}={\mathbf{x}}^{\prime }$ 时只要求数据态归一化,不要求彼此正交。故 $V$ 是从 ${\mathcal{H}}_A\otimes \mathrm{span}\{|0{⟩}_B\}$ 到 ${\mathcal{H}}_A\otimes {\mathcal{H}}_B$ 的等距映射(isometry),由线性性,它在叠加态上的作用被唯一确定:

$$V(\sum _{\mathbf{x}}{\psi }_{\mathbf{x}}|\mathbf{x}⟩|0⟩)=\sum _{\mathbf{x}}{\psi }_{\mathbf{x}}|\mathbf{x}⟩|D_{\mathbf{x}}⟩,$$

范数守恒自动成立。两条推论:其一,语义唯一性——任何两台 QRAM 只要在全部计算基上给出同样的 $|\mathbf{x}⟩|D_{\mathbf{x}}⟩$,在输入子空间上就是同一算符,算法侧的”QRAM 假设”因此无歧义;其二,即使不同单元的数据态不正交(量子数据情形),输出基矢也因地址寄存器而两两正交。

两种标准幺正延拓:XOR 型与 SWAP 型

等距映射延拓成完整 Hilbert 空间上的幺正算符在数学上是免费的(把剩余基矢任意补全),物理内容全在延拓的形态与代价上。按数据类型分两种(与 分类学 的 QRACM/QRAQM 之 分对应)。

XOR 型(经典数据):把查询定义在整个总线空间上

$$U_D:|\mathbf{x}⟩|y⟩⟼|\mathbf{x}⟩|y\oplus D_{\mathbf{x}}⟩,\text{即}{U}_D=\sum _{\mathbf{x}}|\mathbf{x}⟩⟨\mathbf{x}|\otimes P_{\mathbf{x}},$$

其中 $P_{\mathbf{x}}={⨂}_{j=1}^b{X}^{D_{\mathbf{x}}^{(j)}}$ 是按数据第 $j$ 位逐位翻转的泡利串($b$ 为位宽)。验证:$P_{\mathbf{x}}|y⟩=|y\oplus D_{\mathbf{x}}⟩$;又 $(y\oplus D_{\mathbf{x}})\oplus D_{\mathbf{x}}=y$ 给出 $U_D^2=1$,查询自逆——uncompute 只需再跑一遍。把总线置于 $|-⟩$ 还有零开销的条件相位读出:

$$U_D|\mathbf{x}⟩|-⟩=|\mathbf{x}⟩X^{D_{\mathbf{x}}}|-⟩=(-1{)}^{D_{\mathbf{x}}}|\mathbf{x}⟩|-⟩,$$

末步用了 $X|-⟩=-|-⟩$:数据不离开总线,而以相位回踢(phase kickback)刻在地址分支上——这就是 查询语义 的 $Z^{D_{\mathbf{x}}}$ 条件相位读出。

SWAP 型(量子数据):单元内是量子态 $|{\phi }_{\mathbf{x}}⟩$,不可克隆定理禁止复制,唯一相干读出是把总线的旧内容与单元态交换:

$$|\mathbf{x}⟩|\varphi {⟩}_B\otimes |{\phi }_k{⟩}_{C_k}⟼|\mathbf{x}⟩|{\phi }_k{⟩}_B\otimes |\varphi {⟩}_{C_k},k=\mathrm{idx}(\mathbf{x}),$$

查询消耗单元内容,且幺正性要求每个单元能接住总线送来的任意态——这是 查询语义 中”经典数据可条件复制、量子数据只能 SWAP 取出”之分的算符级根源。

相干条件:为何”测量后经典反馈”失败

查询的三个相干条件

把路由显式写进状态:设查询结束时树的构型为 $r(\mathbf{x})$(根到单元 $\mathrm{idx}(\mathbf{x})$ 的路径),干净查询的输出为

$$|\Psi ⟩=\sum _{\mathbf{x}}{\psi }_{\mathbf{x}}|\mathbf{x}{⟩}_A|r(\mathbf{x}){⟩}_R|D_{\mathbf{x}}{⟩}_B.$$

要对数据做后续干涉运算,三条缺一不可:

1. 地址全程相干:不对 $A$ 做任何测量或不可逆投影;
2. 路由自由度只携带地址的确定函数:对 $R$ 求迹后,干涉块系数为 ${\psi }_{\mathbf{x}}{\psi }_{{\mathbf{x}}^{\prime }}^{\ast }⟨r({\mathbf{x}}^{\prime })|r(\mathbf{x})⟩$——$r$ 确定时求迹只是暂时的,路径信息可在 uncompute 时完整收回;若噪声使构型随机化为 $\tilde{r}$,系数退化为 $⟨{\tilde{r}}_{{\mathbf{x}}^{\prime }}|{\tilde{r}}_{\mathbf{x}}⟩<1$,相干性按此因子衰减(Hann 2021 的错误透明性图像);
3. 环境无路径记录:控制硬件、未激活开关、驱动场不得”看见”走了哪条路;任何一路有测量型耦合,条件 1 即在环境维度被破坏。

测量破坏的账目:Lüders 规则

对 $|\Psi ⟩$ 做地址投影测量,投影元 ${\Pi }_{\mathbf{x}}=|\mathbf{x}⟩⟨\mathbf{x}|\otimes 1$。按 Lüders 规则:得到 $\mathbf{x}$ 的概率 $p_{\mathbf{x}}=|{\psi }_{\mathbf{x}}{|}^2$,条件态为 ${\Pi }_{\mathbf{x}}|\Psi ⟩/\sqrt{p_{\mathbf{x}}}=|\mathbf{x}⟩|D_{\mathbf{x}}⟩$,混合后

$${\rho }_{\mathrm{meas}}=\sum _{\mathbf{x}}|{\psi }_{\mathbf{x}}{|}^2|\mathbf{x}⟩⟨\mathbf{x}|\otimes |D_{\mathbf{x}}⟩⟨D_{\mathbf{x}}|.$$

对比原始 $\rho =|\Psi ⟩⟨\Psi |={\sum }_{\mathbf{x},{\mathbf{x}}^{\prime }}{\psi }_{\mathbf{x}}{\psi }_{{\mathbf{x}}^{\prime }}^{\ast }|\mathbf{x}⟩⟨{\mathbf{x}}^{\prime }|\otimes |D_{\mathbf{x}}⟩⟨D_{{\mathbf{x}}^{\prime }}|$:测量恰好杀掉全部非对角块。均匀振幅下,$N^2-N$ 个干涉块归零,只剩 $N$ 个对角块——这就是相干查询与”测地址、查表、按概率制备”的全部差别。

数值算例:一个比特的 Bell 态与经典混合

取 $n=1$、$N=2$、单位数据 $D_0=0,D_1=1$、均匀地址 $|+⟩$。相干查询输出

$$|\Phi ⟩=\frac{1}{\sqrt{2}}(|0⟩|0⟩+|1⟩|1⟩),{\rho }_{\mathrm{meas}}=\frac{1}{2}\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 1\end{array}\right)(|00⟩,|01⟩,|10⟩,|11⟩\text{基}).$$

三笔账把差距算成数字:保真度 $F=⟨\Phi |{\rho }_{\mathrm{meas}}|\Phi ⟩=\frac{1}{4}+\frac{1}{4}=\frac{1}{2}$;迹距离(trace distance,纯态对混合态的公式 $D=\sqrt{1-F}$)为 $1/\sqrt{2}\approx 0.707$,绝非微扰;干涉观测量 ${\sigma }_x\otimes {\sigma }_x$:由 $(X\otimes X)|\Phi ⟩=|\Phi ⟩$ 得期望 $+1$,而 $\mathrm{Tr}[(X\otimes X){\rho }_{\mathrm{meas}}]=\frac{1}{2}⟨00|X\otimes X|00⟩+\frac{1}{2}⟨11|X\otimes X|11⟩=0$——关联从 1 掉到 0,因为 $⟨D_0|{\sigma }_x|D_1⟩$ 型交叉项全部来自被杀掉的非对角块。

经典反馈为何无法事后补救

“测量地址 → 查表 → 按 $|{\psi }_{\mathbf{x}}{|}^2$ 制备 $|D_{\mathbf{x}}⟩$“得到的正是 ${\rho }_{\mathrm{meas}}$:测量丢弃相位,反馈无法重建。重新合成纯态需知道 $2N-2$ 个实参数(归一化与全局相位各去掉一个;参数计数论证),而每次测量至多提供常数比特信息,故重建需 $\Omega (N/\mathrm{polylog}N)$ 个拷贝——按查询重建的代价 $\Omega (N)$,恰是 QRAM 要省掉的那一笔。边界要说清:若最终观测量在地址基下是对角的(经典期望 ${\sum }_{\mathbf{x}}|{\psi }_{\mathbf{x}}{|}^{2}f(D_{\mathbf{x}})$),采样加经典平均即可;相干性的必要性专属于需要分支干涉的场景,下文装载瓶颈一节把它变成指数差距。

朴素 fanout:为何需要 O(N) 个纠缠两体门

逐层门计数

fanout(扇出)架构把经典解码器原样量子化:第 $k$ 个地址比特经 CNOT 级联扇出,控制第 $k$ 层的 $2^k$ 个开关;总线与被寻址单元交换数据 GLM PRA 2008。纠缠两体门按层累加:

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

具体数字:$N=2^{10}$ 时 $G=2046$;$N=2^{30}$ 时 $\approx 2.1\times 10^9$;$N=2^{50}$ 时 $\approx 2.25\times 10^{15}$。GLM 更进一步指出任何 RAM/qRAM 设计都需要 $O(2^n)$ 个两比特逻辑门 GLM PRA 2008:直觉计数是,$N$ 个单元各自至少要有一条通往解码网络的两体耦合,而一个两体门至多把常数个单元接进网络,下限即 $\Omega (N)$。

union bound 与误差要求

设每门错误率 $\epsilon$ 且各门独立。fanout 中每个开关都携带地址信息,没有旁观者,任何一门出错都可能污染输出,由 union bound(联合界):

$$p_{\mathrm{fail}}\le (2N-2)\epsilon \le \delta ⟹\epsilon \le \frac{\delta }{2N-2}\approx \delta \cdot 2^{-n-1}.$$

误差要求随规模指数收紧:$N=2^{50}$、目标 $\delta =0.1$ 时 $\epsilon \le 0.1/2^{51}\approx 4.4\times 10^{-17}$;而现有超导确定性路由器的平均路由保真度为 95.3%,即 $\epsilon \approx 5\times 10^{-2}$ Miao 2025——差约 15 个数量级,期望错误门数 $\sim 10^{14}$,宏观上必然失败。

宏观叠加与保真度衰减

误差要求指数小的物理根源是宏观叠加:地址处于叠加态时,全部 $\Theta (N)$ 个开关必须同时处于不同设置基矢的叠加并保持相干——每个分支里整棵解码树都是”活的”。GLM 给出过直接的衰减律:若每条线上各有一个门被降质,保真度随层数按 $2^{-k}$ 衰减 GLM PRL 2008。这正是 GLM 自陈大规模下 fanout”必然屈服于噪声与退相干”的含义,也是 bucket-brigade 的反面动因 GLM PRA 2008。

fanout 并未退场:当硬件提供全局多目标门(离子阱 GMS 门、超导和频驱动),单控制多目标 CNOT 可一步完成,fanout 型显式存储可达 $O(n)$ 深度、零辅助比特 Gokhale 2020。但全局门只是把 $2N-2$ 个物理耦合并行化,每查询激活的耦合总数仍为 $\Theta (N)$,一般噪声下 $\sim N\log N$ 的不保真度标度不变 Hann 2021——速度账改善,噪声账照旧,细节见 fanout 架构。

bucket-brigade 的账目:O(N) → O(log² N)

接力机制的形式化与 $n=2$ 算例

bucket-brigade 把”每层全部扳动”改为”逐级接力”:树节点为三能级 qutrit(等待态 $|w⟩$、指向态 $|L⟩/|R⟩$),地址比特依次进树,第 $i$ 个比特与当前前沿激活节点相互作用,节点按该比特取值置向,被指向的子节点成为新前沿。用 $n=2$、$N=4$(根 $g_1$,子 $g_2,g_3$)写出全过程。初始

$$|{\Psi }_0⟩=\sum _{x_1,x_2}{\psi }_{x_1{x}_2}|x_1{x}_2{⟩}_A|www{⟩}_R;$$

第一步 $x_1$ 与根相互作用,根指向 $\mathrm{dir}(x_1)\in \{L,R\}$:

$$|{\Psi }_1⟩=\sum _{x_1,x_2}{\psi }_{x_1{x}_2}|x_1{x}_2{⟩}_A|\mathrm{dir}(x_1)ww{⟩}_R;$$

第二步 $x_2$ 被指向的子节点接力吸收:

$$|{\Psi }_2⟩=\sum _{x_1,x_2}{\psi }_{x_1{x}_2}|x_1{x}_2{⟩}_A|\mathrm{dir}(x_1)\mathrm{dir}(x_2)\cdot {⟩}_R,$$

第三个槽位(未被指向的子节点)保持在 $|w⟩$;读出后逆序 uncompute 复位。两个结构不变量:激活节点恰为路径上的 $n$ 个,其余 $2^n-n-1$ 个始终等待;路由构型 $r(\mathbf{x})$ 是地址的确定函数——中途测量路由节点会把叠加投影到单一 $r({\mathbf{x}}_0)$、地址随之坍缩,故路径信息必须 uncompute 而不能丢弃。

相互作用门计数

接力账目按比特累计:第 $j$ 个地址比特要穿过 $j-1$ 个已激活节点才在第 $j$ 层被吸收,每穿一层是一次两体相互作用,加最后的吸收共 $j$ 次,合计

$$G_{\mathrm{BB}}=\sum _{j=1}^{n}j=\frac{n(n+1)}{2}=\Theta ({\log }^{2}N),$$

uncompute 再加同量级。这就是 GLM 的纠缠两体门 $O(N)\to O({\log }^{2}N)$ 计数 GLM PRL 2008;相应地,每次查询只需”扳动”路径上的 $O(\log N)$ 个开关 GLM PRL 2008。数字对比:$n=100$($N=2^{100}$)时,fanout 需 $2N-2\approx 2.5\times 10^{30}$ 个纠缠两体门,bucket-brigade 只需 $100\times 101/2=5050$ 个——27 个数量级。

误差账目的两层:GLM 局域化与 Hann 定理

第一层(GLM,启发式)。误差只对激活组件计数:路径上 $O(\log N)$ 个节点加读出,每处贡献 $\le \epsilon$,union bound 给每查询错误率

$$p_{\mathrm{err}}\approx \epsilon {\log }_{2}N.$$

GLM 的标志性数字由此而来 GLM PRA 2008:$\epsilon =0.1\%$、${\log }_{2}N=100$ 时 $p=0.001\times 100=10\%$——可对 $2^{100}$ 个地址做叠加寻址;$\epsilon =1\%$ 时 $n=10,20,30$ 对应 $p=10\%,20\%,30\%$。关键前提是那条噪声约束:指数多个等待态节点不得被意外激发,否则旁观者重新变回参与者。

第二层(Hann,定理)。GLM 的账默认非激活节点绝对安全,这需要论证。Hann、Lee、Girvin 与 Jiang 在最不利设定下——全部 $N-1$ 个路由器(含等待态)承受任意 CPTP 噪声信道——证明了同样的多对数标度:

$$1-F\le 4\epsilon T\log N,T=O(\log N),$$

要求 $\epsilon T\log N\le 1/4$ Hann 2021。韧性的来源不是”激活门少”,而是有限纠缠:第 $\ell$ 层节点只在全部分支的 $2^{-\ell }$ 中被激活,单个错误至多毁掉 $2^{\ell }$ 个分支,逐层求和

$$1-F\sim \sum _{\ell =1}^n{2}^{-\ell }\cdot \epsilon T\cdot 2^{\ell }=\epsilon T\log N,$$

坏分支的权重被好分支的指数多数抵消。数值算例:$N=2^{50}$($n=50$)、$T=2n=100$,要把 $1-F$ 压到 $0.1$,需 $\epsilon \le 0.1/(4\times 100\times 50)=5\times 10^{-6}$(验证前提 $5\times 10^{-6}\times 100\times 50=0.025\le 1/4$);对照 fanout 同规模要求的 $4.4\times 10^{-17}$,两本账差约 12 个数量级。再对照硬件:路由保真度 95.3%($\epsilon \approx 5\times 10^{-2}$)距 $5\times 10^{-6}$ 尚有约四个数量级 Miao 2025——这正是错误缓解与纠错路线的用武之地(见 错误局域化 与 噪声韧性)。

把 QRAM 当 Grover 预言机:Regev–Schiff 约束

多对数错误率并非所有用法都够用。Grover 搜索迭代 $Q\approx (\pi /4)\sqrt{N/M}$ 次($M$ 为解数),错误按查询次数线性累积,union bound 要求 $Q\cdot {\epsilon }_{\mathrm{q}}\lesssim 1$,即每查询错误 $O(2^{-n/2})$;Arunachalam 等援引 Regev–Schiff 把约束收紧到每门错误率 $o(2^{-n/2})$(一类误差模型、bucket-brigade 用作搜索预言机),远比 GLM 的 $O(1/n^2)$ 口径严苛 Arunachalam 2015。代入 $n=100$:$2^{-50}\approx 8.9\times 10^{-16}$ 对 $1/n^2=10^{-4}$,差 11 个数量级。分界线在查询次数:$O(2^{n/2})$ 次(搜索)要求指数小误差;多项式次(如矩阵求逆所引 HHL、qPCA Lloyd 2014)只要求多项式小误差,纠错可能不需要。纠错另有代价:整体施加传统 CSS 码会把全部 $N-1$ 个节点纳入主动纠错,优势瓦解、退化为 fanout 式 Arunachalam 2015;Hann 等则证明桶队韧性在纠错框架下依然成立 Hann 2021。编年见 十八年时间线 与 噪声韧性之争。

时间账目

顺序接力使单次相干检索耗时 $O(n^2)$,并要求错误率显著小于 $1/O(n^2)$;这是该架构最常被诟病的一笔 GLM PRA 2008。缓解有二:门级并行化与地址流水线把摊销深度压回 $O(n)$ 层(见 电路级优化);综述汇总表给出查询深度 $O(n)$(流水线后)、比特 $O(N)$、总门数 $O(N\log N)$、不保真度 $\epsilon \log N$ 至 $\epsilon {\log }^{3}N$ Phalak 2023。总门数与每查询激活门两笔账不矛盾:器件的 $N-1$ 个节点都要造出来(硬件开销),每次查询只在多对数个组件上消耗相干操作(运行开销)。

数据装载瓶颈:叠加查询为何是 QML 指数加速的前提

当算法需要对大规模外部数据集做叠加查询——机器学习中的特征矩阵与训练样本、金融中的历史路径、密码分析中的预计算表——装载成本就是独立的一项,必须单独记账;对结构化问题(整数分解、量子模拟)输入可在线生成,不存在此项。

装载侧下界:参数计数论证

把任意 $N$ 维经典数据 $D$ 装成振幅态 $\frac{1}{\Vert D\Vert }{\sum }_k{D}_k|k⟩$(amplitude encoding,振幅编码),电路规模有参数计数下界:归一化并去除全局相位后,该态由 $2N-2$ 个独立实参数刻画;而 $G$ 个门的电路即便每个门都带连续可调参数,所能覆盖的态流形维数至多是 $G$ 的常数倍,故

$$G=\Omega (N).$$

这是维数账而非技术障碍:数据有 $N$ 个数,电路至少要”写” $N$ 次。代入 $N=2^{30}\approx 1.07\times 10^9$:每次装载 $\gtrsim 10^9$ 个门,且装载出的态用一次即耗散,数据集每变更一次就重付 $\Omega (N)$。若数据有可高效计算的稀疏或代数结构,可用专用电路绕开(见下文空档);一般 dense 数据不存在普遍的多项式装载电路。

查询侧摊销:把 O(N) 一次性移交给硬件

QRAM 换了一个支付时点:数据以经典方式离线写入 $N$ 个单元(一次性 $O(N)$,可并行),此后每次相干查询只花 $\Theta ({\log }^{2}N)$ 个激活两体门、$O(\log N)$ 层深度。$K$ 次查询的总账为 $O(N)+O(K{\log }^{2}N)$,对比逐次重装载的 $O(KN)$:$N=2^{30}$、$K=10^4$ 时,前者约 $10^9+9.3\times 10^6$,后者约 $10^{13}$——差三个数量级,且 $K$ 越大差距越大。更重要的是能力差异:振幅编码只能制备算法设计时已知的特定叠加,QRAM 回答运行中自适应选择的任意地址叠加——查询原语与状态制备器的本质区别。qPCA 是最早把该假设写成器件形式的算法 Lloyd 2014;Biamonte 综述对装载写出明确口径——“用 qRAM 把向量映射为量子态……需要 $O(d)$ 次运算,分摊到可并行执行的 $O(\log d)$ 步”,qPCA 整体复杂度 $O((\log d{)}^2)$ Biamonte 2017:$O(d)$ 的一次性成本摊销进硬件,$O((\log d{)}^2)$ 的指数加速是在线复杂度。其依赖表显示,几乎所有指数级 QML 加速都标注 QRAM=Y 并附 fine print(明细见 量子机器学习的 QRAM 依赖)。

为何”测量后多次采样”不能替代

测量式访问每次产出 ${\rho }_{\mathrm{meas}}$ 型混合态,而 HHL 类算法的核心步骤(相位估计中分支相位的相干演化、QFT 分支重组、振幅放大)消费的恰是非对角块。用经典采样凑相干性,按参数计数需 $\Omega (N/\mathrm{polylog}N)$ 次拷贝,每次拷贝又是一次 $\Omega (N)$ 装载:总账 $\Omega (N^2/\mathrm{polylog})$,指数加速荡然无存。换言之,指数加速的多对数运行时间,逻辑上必须由”一次查询内全部分支同时相干响应”支付。反例同时划清边界:期权定价一类结构化分布可用参数化电路与生成模型高效装载,全文无需 QRAM,振幅估计仍拿到对经典蒙特卡洛的二次加速 Stamatopoulos 2020。假设谱系(稀疏 oracle 与量子访问)见 算法的输入模型谱系,经典启发式替代路线见 去量子化。

讨论:边界与常见误读

“QRAM 就是量子存储器”。不是。随机存取量子存储器(RAQM,经典地址、量子数据)不提供叠加寻址,不在本站定义之内(见 边界:RAQM 与量子存储);qROM 式查表电路在计算基上直接计算 $D(x)$,语义相同却是 $O(\mathrm{poly}(N))$ 门的有源电路、无内在噪声韧性 Hann 2021(见 边界:qROM 电路与 QROM 模型);一般性态制备电路同样不在此列(见 边界辨析 系列)。本站立场:QRAM 是实现总览公式所述幺正变换的专用器件。

”$O({\log }^{2}N)$ 意味着硬件便宜”。不是。多对数的是每查询激活门;器件本身仍需 $N-1$ 个节点、$O(N)$ 量子比特与 $O(N\log N)$ 总门数 Hann 2021。Jaques–Rattew 进一步质疑成本方向:若每次查询需 $\Omega (N)$ 次外部干预(active),控制硬件可被重编程为大规模并行经典机,量子优势大半消失;passive(单一不含时哈密顿量自主演化)才保住优势,“被动到什么程度”仍是开放问题 Jaques-Rattew(源头是 Aaronson 的 fine print 批评 Aaronson 2015)。能量口径下,若每比特每次访问耗散一个可见光子的能量,访问 $2^{80}$ bit 达约 1 GJ Jaques-Rattew;容错化路线的资源估计同样触及天文数字 Di Matteo 2020。口径之别见 成本口径。

“噪声韧性已被证明,QRAM 已解决”。也没有。Hann 定理给出的是不保真度多对数上界 Hann 2021,而 $O(N)$ 比特、主动/被动之争、超多项式查询仍需纠错三笔账都还在;理论侧最坏结论(一般噪声下不可扩展)已被排除,工程侧刚开始交付器件级证据。

账目速查

账目	fanout	bucket-brigade
每查询激活开关	$\Theta (N)$	$\Theta (\log N)$
每查询纠缠两体门	$2N-2$	$n(n+1)/2$
同时处于叠加的组件	$\Theta (N)$	$\Theta (\log N)$
不保真度标度	$\sim N\epsilon$;一般噪声 $\sim N\log N$	$\epsilon {\log }_{2}N$;$\le 4\epsilon T\log N$
单门误差要求	$O(2^{-n})$	$O(1/n^2)$(串行检索);$o(2^{-n/2})$(Grover 预言机)
器件总门数	$O(N)$	$O(N\log N)$

从假设到器件

此后十余年,QRAM 更多以”假设”而非”器件”的形态存在:2015 年的鲁棒性分析 Arunachalam 2015 与 2020 年的容错资源估计 Di Matteo 2020 一度把前景推向悲观,2021 年的严格韧性证明 Hann 2021 扭转叙事,2023 年的批判综述 Jaques-Rattew 要求社区对”廉价 QRAM”保持克制。2024–2026 年,器件化沿实验阶梯上行:超导确定性路由器 Wang 2021、地址可寻址的 Q²-router(平均路由保真度 95.3%)Miao 2025、首个完整 bucket-brigade 全循环实验(两层/三层查询保真度 $0.800\pm 0.026$ 与 $0.604\pm 0.005$;错误注入证实误差局域化:被查询路径保真度斜率 $-0.255$,最远分支 $-0.005$)Shen 2026,以及把查询整体化为离线资源态制备的 QRAM 工厂路线 Cesa 2026。上述五组推导是评估这些器件声明时的核对底账。

延伸阅读

• 查询语义:路由与读出
• 分类学:四分类与主动/被动
• 桶队架构
• 十八年时间线
• fanout 架构
• 一般噪声下的韧性
• 量子机器学习的 QRAM 依赖
• 成本口径:激活门、干预与能量