边界:qROM 电路与 QROM 模型

"QROM"一词指向两个完全不同的对象:容错成本模型下的只读查表电路,与密码学中分析量子敌手的随机预言机模型;两者都不是 QRAM 存储器件。

一词三义:先分清三种语境

“QROM”在 QRAM 文献里至少指向三个对象,共享”按量子寄存器索引、读取经典数据”的表层语义,深层契约完全不同:其一,容错成本模型下的只读查表电路(quantum read-only memory,常小写作 qROM);其二,密码学中分析量子敌手的量子随机预言机模型(Quantum Random Oracle Model);其三,被前两者共同排除在外的 QRAM 存储器件。本词条先厘清三种语境,再以四组推导把边界算清楚:计数下界、$O(N)$ 基线账目、亚线性 T-count 的科目转换、查询次数的摊销账。

电路式 qROM:把查表编进 Clifford+T

qROM 电路把映射

$Q_D:{\sum }_{\ell }{\alpha }_{\ell }|\ell ⟩|0⟩⟼{\sum }_{\ell }{\alpha }_{\ell }|\ell ⟩|d_{\ell }⟩$

编译为 Clifford+T 电路,以 T-count、T-depth 等容错成本核算,而非以抽象查询数核算。三条代表性账目:Babbush 等的 unary iteration(一元迭代)以 T-count $4L-4$ 实现任意 $L$ 项查表,且与输出字长无关 Babbush 2018;Phalak 等以预译码逻辑(pre-decoding)把 NISQ 上 8 位地址查表的深度/门数最多降 $75\times$ Phalak 2022;Zhu–Sundaram–Low 的统一查找表架构把比特数、非 Clifford 门数与噪声韧性之间的已知折中收进一个参数化连续统 Zhu 2024。作者对语义的界定毫不含糊:qROM 读经典数据、以量子寄存器为索引、只读不可写入,“与 QRAM 截然不同” Babbush 2018。

它被排除在 QRAM 器件之外的理由有二,后文逐一推导:其一,门数受 Jaques–Rattew 定理 5.2 的 $\tilde{\Omega }(N)$ 计数下界约束 Jaques-Rattew,“专用硬件换对数深度”的物理赌注在电路模型里无处安放;其二,Babbush 等指出 bucket-brigade 即便深度为 $O(\log L)$,在容错口径下 T 复杂度仍是 $O(L)$ Babbush 2018——对数深度 ≠ 对数成本是理解这条边界的关键。

密码学 QROM:安全证明的理想化函数

密码学的量子随机预言机模型把哈希函数 $H$ 理想化为一个随机函数,敌手可对其做叠加查询:$O_H|x,y⟩=|x,y\oplus H(x)⟩$。它与存储器件无关:没有表、没有路由树、没有任何实现承诺,“随机性”是证明用的数学对象而非被存储的数据。教科书级的两条查询账目决定其安全标定:找 $n$ 比特输出的原像需 $O(2^{n/2})$ 次查询(Grover 标度,匹配下界);在定义域规模 $N$ 的随机函数上找碰撞需 $O(N^{1/3})$ 量级查询(Brassard–Høyer–Tapp)。后量子密码把对称原语的安全级别从经典 $2^n$ 折半到量子抗性 $2^{n/2}$,账目正源于此。

两条语境的交汇点只在术语混乱本身:QRAM 综述文献以 “QROM” 指电路式查表 Jaques-Rattew,密码学文献则指安全模型;文献中 “QROM” 有时还被用来指电路式 QRACM Jaques-Rattew。同词异义是 QRAM 术语混乱的典型样本——引用任何 “QROM” 结论前,先辨语境,再谈成本或安全。

语义边界的形式化:缺的不是叠加寻址

三条判据

qROM 与 QRAM 的边界可操作地化为三条判据,每条对应一类被排除的能力:

1. 数据经典性。qROM 的输出是编译进电路的经典常数 $d_{\ell }$:经典比特可无条件复制,读出由 CNOT 或按数据位翻转相位的受控相位实现;量子数据受不可克隆定理限制,读出必须是 SWAP 型”取出并搬走”(见 查询语义:路由与读出)。qROM 只服务前者,QRAQM(量子地址、量子数据)被整体排除。
2. 路由相干性。QRAM 器件的核心难题是路由:叠加地址的信息要沿 $N-1$ 个节点的树相干传递——bucket-brigade(桶队)的 qutrit 节点逐级接力,路由器的指向自由度本身进入量子态 GLM 2008 (PRL)。qROM 没有路由树:电路里的”寻址”就是普通的可逆逻辑综合,中间比特当然也须保持相干,但那是标准电路相干性,不引入任何新的物理对象。
3. 持久性与可写性。QRAM 是存储器:数据驻留、写入与读出分离、换数据不改硬件。qROM 是编译产物:表一旦改变,电路必须重编译。这是”电路 vs 器件”的差别,不是”快 vs 慢”的差别。

叠加寻址是线性性的平凡推论

常见误读是”qROM 不支持叠加查询”。形式化地看,$U_D$ 是酉(异或式实现)或等距算子(干净目标寄存器实现),它对计算基的作用 $|\ell ⟩|0⟩\mapsto |\ell ⟩|D_{\ell }⟩$ 经线性延拓自动给出

$U_D\left({\sum }_{\ell }{\alpha }_{\ell }|\ell ⟩|0⟩\right)={\sum }_{\ell }{\alpha }_{\ell }|\ell ⟩|D_{\ell }⟩,$

即任何实现经典映射的可逆电路都免费支持叠加查询:线性性不需要额外代价,也不构成额外能力。QRAM 器件被单独研究的真正原因因此不是”能否叠加”,而是时间承诺:器件以 $N-1$ 个专用节点的并行路由把单次查询压到 $O(\mathrm{polylog}N)$ 时间——GLM 的原始卖点正是每次存储调用只需扳动 $O(\log N)$ 个开关、只激活 $O(n)$ 个二体相互作用 GLM 2008 (PRL)GLM 2008 (PRA)——而电路的单次查询规模被 $\tilde{\Omega }(N)$ 锁死(推导一)。一句话:QROM 把叠加查询当作线性性的赠品,QRAM 把它当作待实现的物理。

推导一:计数下界——任意查表逃不脱 $\tilde{\Omega }(N)$

论证(计数论证,counting argument)

设表 $D\in \{0,1{\}}^N$($n={\log }_{2}N$ 位地址,先取单比特字;多比特字逐位同理)。查询酉取异或式可逆实现

$U_D:|\ell ⟩|b⟩⟼|\ell ⟩|b\oplus D_{\ell }⟩,$

它置换计算基、线性延拓后为酉。

第一步:不同的表给出可分辨的酉。若 $D\ne D^{\prime }$,存在 ${\ell }^{\ast }$ 使 $D_{{\ell }^{\ast }}\ne D_{{\ell }^{\ast }}^{\prime }$,于是

$\Vert (U_D-U_{D^{\prime }})|{\ell }^{\ast }⟩|0⟩\Vert =\Vert |{\ell }^{\ast }⟩|1⟩-|{\ell }^{\ast }⟩|0⟩\Vert =\sqrt{2},$

由算子范数定义($\Vert A\Vert \ge \Vert Av\Vert /\Vert v\Vert$)得 $\Vert U_D-U_{D^{\prime }}\Vert \ge \sqrt{2}$。

第二步:近似不合并账。设门库共有 $M$ 种门。用 $G$ 个门、以算子范数误差 $\eta =1/4$ 近似实现各表,得电路 ${\tilde{U}}_D$。反设同一电路近似两个不同的表,则由三角不等式

$\Vert U_D-U_{D^{\prime }}\Vert \le \Vert {\tilde{U}}_D-U_D\Vert +\Vert {\tilde{U}}_{D^{\prime }}-U_{D^{\prime }}\Vert \le \frac{1}{2}<\sqrt{2},$

与第一步矛盾。故一个电路至多服务一个表——“电路数 ≥ 表数”是硬约束。

第三步:计数。$G$ 个门、每个 $M$ 种选择,至多构造 $M^G$ 个不同电路。要覆盖全部 $2^N$ 个表中至少分数 $\tau \in (0,1]$,必须

$M^G\ge \tau 2^N⟹G\ge \frac{N+{\log }_2\tau }{{\log }_{2}M}=\Omega \left(N+\log \frac{1}{\tau }\right).$

对门库细节与常数取对数因子,即 Jaques–Rattew 定理 5.2 的口径 $G\in \tilde{\Omega }(N+\log \tau )$(原文以误差 $\le 1/\sqrt{2}$ 陈述 Jaques-Rattew;上面的 $\eta =1/4$ 是同一论证的自洽常数选取)。

第四步:连续参数化不豁免。若门族携带 $p$ 个实参数,以精度 $\delta$ 离散后每个参数至多分辨 $O({\delta }^{-1})$ 档;重复第三步的计数得 $p\log (c/\delta )\ge \Omega (N)$——参数个数本身必须线性。变分电路、可训练参数化不提供逃逸通道,这与 边界:NISQ 可训练近似 QRAM 记录的现象互为表里。

数值算例

取 $N=2^{20}$(1 Mbit 表)、门库 $M=20$(即 ${\log }_{2}M\approx 4.32$):要求实现一半的表($\tau =1/2$)时,

$G\ge \frac{2^{20}-1}{4.32}\approx 2.4\times 10^5\text{个门};$

把要求放宽到只实现 $2^{-10}$ 比例的表($\tau =2^{-10}$),

$G\ge \frac{2^{20}-10}{4.32}\approx 2.4\times 10^5,$

分毫不差。分数 $\tau$ 只以 $\log \tau$ 进入下界:实现”几乎所有的表”与实现”所有的表”成本几乎相同,下界的重量全部压在 $N$ 上。

直觉

表有 $2^N$ 种可能,而每个门的描述复杂度是常数:电路必须携带 $\Theta (N)$ 比特的”表信息”,这些信息只能编码在门的种类、位置与参数里,故门数必为线性。这与香农计数论证(“绝大多数布尔函数需要指数规模电路”)同源——区别只在查询酉被限制为查表这一特殊形式,指数代价降为线性。由此也看得出下界的适用范围:它对稠密任意表最致命;数据本身有结构(稀疏、低秩、可分解)时,描述表所需的比特数远少于 $N$,计数论证随之松动(推导三的稀疏交叉点)。最后注意上下界的距离:unary iteration 给出 $4L-4$ 的上界,计数给出 $\Omega (N/\log M)$ 型下界,两者之间恰是后续工作用辅助比特与 Clifford 层争夺的对数因子空间。

推导二:$O(N)$ 基线的精确账目——unary iteration

电路结构

目标仍是 $Q_D$,$L=2^n$。Babbush 等的构造分三步 Babbush 2018:

第一步:准备迭代器。在 $L$ 比特的 unary 寄存器上制备均匀”单激子”叠加

$|W⟩=\frac{1}{\sqrt{L}}{\sum }_{\ell =0}^{L-1}|0\cdots \underset{\text{位置 }\ell }{\underbrace{1}}\cdots 0⟩,$

做法是从 $|10\cdots 0⟩$ 出发,依次施加 $L-1$ 个分叉门 $A_j$:第 $j$ 个门按确定角度把”1”的振幅分裂到下一个位置,角度序列由均匀叠加的目标比例唯一给定;每个 $A_j$ 的 T 复杂度为 $2$(文献口径 Babbush 2018)。这些角度是编译期常数,不需要运行时合成任意旋转——这是整个账目能压到常数的先决条件。

第二步:扫掠读出。用一个 CNOT 链把”1”从左推到右;泡经过位置 $\ell$ 时,以该比特为控制,按表项 $D_{\ell }$ 的第 $j$ 位对数据寄存器执行 $X^{d_{\ell ,j}}$——全部是 CNOT,属 Clifford 层。

第三步:复位。逆序施加 $L-1$ 个 $A_j$ 反算,清空迭代器,恢复 $|10\cdots 0⟩$。

总账

$\text{T-count}=\underset{\text{制备}+\text{复位}}{\underbrace{2(L-1)}}\text{个 }A\text{ 门}\times 2\text{T}=4(L-1)=4L-4.$

字长 $m$ 只出现在 Clifford 层(约 $mL$ 个 CNOT),不进 T 账——这就是”T-count 与字长无关”的机制:查表的 T 成本全部住在地址逻辑(迭代器的制备与扫掠)里,数据层是免费的 Clifford。这一分离并非 unary iteration 独有的技巧,而是一切 QROM 电路的普遍形状:T 账跟踪地址结构的处理,Clifford 账跟踪数据常数的搬运;下一节将看到,凡把 T 压亚线性的构造,都在 Clifford 层把账补回来。

对照暴力基线以确认这已接近结构最优:逐项译码对每个 $\ell$ 放置一个 $n$-控制非门,即使带辅助比特也需要 $\Theta (n)$ 个 Toffoli(可逆电路综合的标准事实);按每个 Toffoli 7 T 的表面码口径 Di Matteo 2020,$n=10$ 时总计 $\gtrsim 2^{10}\times 8\times 7\approx 5.7\times 10^4$ 个 T。unary iteration 的 $4092$ 个 T 省掉一个数量级——它把译码信息摊进迭代器的梯度制备,而不是在每个表项上重复解码。定理 5.2 则保证这条账没有下半场:无人能把总门数压到 $o(N/\mathrm{polylog}N)$。

数值算例

$L=2^{10}=1024$、$m=8$(1 KB 表):T-count $=4\times 1024-4=4092$,Clifford 层约 $8\times 10^3$ 个 CNOT;把表换成 $m=64$ 的长字:T-count 仍是 $4092$,CNOT 涨到约 $6.6\times 10^4$。T 账纹丝不动、Clifford 账线性上浮——两种科目分离,正是容错核算喜欢看到的形状,也是化学模拟敢把查表原语嵌进 $\lambda /ϵ$ 次查询循环的原因:字长增长不再放大最贵的资源。

NISQ 侧写

同一映射在 NISQ 上的瓶颈是深度而非 T-count:naive 编译的深度随地址比特数指数增长,4 位以上即不现实 Phalak 2022。Phalak 等以预译码逻辑(把部分译码挪到浅层/经典预处理)与量子比特复位,把 8 位地址的深度/门数最多降 $75\times$、编译时间降 $85\times$,代价最多 $2.28\times$ 比特(仅 $36\%$ 比特开销即可换至少 $2\times$ 改善);真机对照实验中保真度从 $40.8\%$ 升到 $73\%$ Phalak 2022。注意这类优化改变的是常数与深度,渐近形状仍由推导一锁死——qROM 工程的全部自由度都在 $\tilde{\Theta }(N)$ 的常数因子之内。

推导三:亚线性 T-count 为何不违反下界——成本换了科目

折中连续统

unary iteration 是”零辅助冗余、线性 T”的极端,两个方向的折中都存在。Babbush 等在同一工作中给出以辅助比特换深度的 swap 网络变体 Babbush 2018;Zhu–Sundaram–Low 把已知构造全部收进一个参数化架构:比特数、非 Clifford 门数与错误韧性之间的连续折中在对数因子内最优,只需局域 2D 连通性,合适参数下恢复 polylog 噪声标度,并识别出所有参数同时亚线性的新区域 Zhu 2024。Mukhopadhyay 的 qLUT_poly(两个 $\sqrt{N}$ 规模的 QRAM_poly 拼接,地址拆成两段)给出具体数据点:T-count $O(\sqrt{N})$、T-depth $O(\log \log N)$、量子比特 $O(\sqrt{N})$;前代 CSWAP 架构的 T-depth 为 $O(\sqrt{N})$ Mukhopadhyay 2025。

与定理 5.2 对账

$O(\sqrt{N})$ 的 T-count 看似击穿 $\tilde{\Omega }(N)$,其实没有:定理计数的是全部门。逐项核对账本:T-count 只计非 Clifford 门;qLUT_poly 复用的多项式求值层以 CNOT 为主(T-count 口径不计);而表中 $N$ 个经典常数每一个都必须由某个 Clifford 门写入电路——这一层 Clifford 底账正是下界锁定的 $\tilde{\Omega }(N)$ 缺额。同族 QRAM_poly 主体直接给出台面数字:CNOT 数 $O(3^n-2^n)\approx O(N^{1.585})$ Mukhopadhyay 2025,总门数稳稳高于下界。于是

$\text{亚线性 T-count}+\text{超线性 Clifford 层}=\text{换科目,不换总量}.$

这既是下界强度的体现(它约束任何门种类的组合,推导一第四步对连续参数同样成立),也是阅读 QROM 文献的第一守则:先问账计在哪一科目(T、Clifford、还是激活门),再比较数字。以 $N=2^{20}$ 为例:qLUT_poly 的 T-count 压到 $2^{10}=1024$ 量级,但按 QRAM_poly 的 CNOT 标度折算,Clifford 层约有 $2^{20\times 1.585}\approx 2^{31.7}\approx 3.5\times 10^9$ 个 CNOT——T 账上省下的三个数量级,原封不动躺在 Clifford 账上。

结构性豁免:稀疏交叉点

计数下界只对稠密任意表成立,表本身有结构时账目不同。设表中恰有 $K=2^q$ 个 1:隐式电路为每个 1 放置一个 $n$-控制非门(每个 $\Theta (n)$ 个 Toffoli),总计约 $c_{1}Kn$;显式电路(unary/BB 型)总计约 $c_{2}N=c_2{2}^n$。令两式相等:

$c_1{2}^{q}n=c_2{2}^n⟹2^q=\frac{c_2}{c_1}\cdot \frac{2^n}{n}⟹q_{\max }\approx n-{\log }_{2}n(+O(1)),$

即 Di Matteo 等给出的隐式/显式交叉点:比这更空的存储器用隐式电路更省 Di Matteo 2020。数值代入 $n=36$(8 GB):$q_{\max }\approx 36-{\log }_{2}36\approx 30.8$,即 1 的个数少于约 $2^{30.8}\approx 1.9\times 10^9$(密度 $\lesssim 1/n\approx 2.8\%$)时隐式编译胜出;对 $n=15$(4 KB),交叉点在 $q_{\max }\approx 11.1$、密度约 $6.7\%$。代价是固有的:数据库一变,隐式电路必须重编译 Di Matteo 2020——结构豁免与可写性不可兼得,这一张力在 多项式编码 QRAM 中还会出现。

推导四:对数深度为何仍是对数成本——BB 电路化殊途同归

把 bucket-brigade 的路由逻辑原样搬进电路(每个 qutrit 节点实现一次受地址控制的受控交换门,Fredkin),会得到深度 $O(n)$ 的并行电路——深度是对数的,看起来”深度即成本”的直觉成立。容错口径拆穿它:每个路由节点一次 Fredkin,标准分解为常数个 Toffoli(视辅助比特为 3–5 个),每个 Toffoli 在表面码口径记 7 个 T(T-depth 为 1 的最优分解 Di Matteo 2020),于是

$\text{T-count}\approx (N-1)\times (3\sim 5)\times 7=\Theta (N).$

数值:$n=36$ 时约 $(2^{36})\times 21\sim 2^{36}\times 35\approx 1.4\sim 2.4\times 10^{12}$ 个 T,与 QRAM_poly 实测口径的 $5.5\times 10^{11}$ 同量级(常数因子以内)Mukhopadhyay 2025。这就是 Babbush 等那句判词的电路版证明:bucket-brigade 即便深度 $O(\log L)$,容错 T 复杂度仍是 $O(L)$ Babbush 2018。深度省下的是 Clifford 层的并行时间,省不掉的是每个节点一次的非 Clifford 操作——$N-1$ 个节点就是 $N-1$ 份 T 账,定理 5.2 保证无人能替它们付账。对数深度 ≠ 对数成本,在 QROM 与 BB 电路两条路线上以同一形式兑现。

推导五:何时 QROM 替代 QRAM 足够——查询次数的摊销账

两侧的账单

设算法共需 $Q$ 次查询,表长 $N$。

QROM 侧:零专用硬件;总 T-count $Q(4N-4)$(unary 口径),辅助比特 $O(N)$;错误走标准容错流水线,不需要任何专门的器件级噪声分析。这是电路路线的结构性优点:Babbush 等在表面码、每门错误率 $10^{-3}$ 的假设下核算出”约一百万超导物理比特、数小时”完成有意思规模的化学相位估计 Babbush 2018;Jaques–Rattew 同样明确建议算法设计者把电路式查表当作编译工具直接使用(化学、密码、算术)Jaques-Rattew。

器件侧:硬件是 $N-1$ 个路由节点加存储阵列;收益是单查询 $O(\mathrm{polylog}N)$ 时间(GLM:每次调用只激活 $O(n)$ 个二体相互作用 GLM 2008 (PRA));代价是噪声预算与查询次数耦合。Hann 等在完全一般噪声模型下证明单查询不保真度 $1-F\le 4\epsilon T\log N$($\epsilon$ 为单门错误率,$T$ 为整个电路的门数)Hann 2021;要 $Q$ 次查询的累计失败概率仍 $\le \delta$,需

$\epsilon \lesssim \frac{\delta }{4Qg(n){\log }_{2}N},$

其中 $g(n)$ 为单查询激活门数(GLM 相干检索口径为 $O(n^2)$)。数值代入 $n=36$、$Q=100$、$g=2n^2=2592$、$\delta =1$:

$\epsilon \lesssim \frac{1}{4\times 100\times 2592\times 36}\approx 2.7\times 10^{-8}.$

更苛刻的用法是 Grover:Regev–Schiff 型结果表明 bucket-brigade 用作搜索预言机时单门错误须 $o(2^{-n/2})$ Arunachalam 2015;反过来,多项式查询次数的算法(HHL、qML 一类)只要求错误率多项式小,或可免于纠错 Arunachalam 2015。错误预算随 $Q$ 线性收紧,是器件路线的摊销逆项:查询越多,每个节点必须越干净——收益按 $Q$ 摊薄,代价按 $Q$ 加码。

交叉点推导

把两类成本折到同一单位(逻辑 T 门当量),设一个相干路由节点的全周期工程成本(置态、路由、复位与噪声控制)为 $h$ 个 T 当量。这是纯为量纲化而设的保守口径——真实的 $h$ 无人知晓,因为它取决于尚未建成的硬件。两侧总账:

$\text{QROM}:Q\cdot (4N-4)\approx 4QN;\text{器件}:hN+Q\cdot c{\log }^{2}N.$

令其相等,解出交叉查询次数

$Q^{\ast }=\frac{hN}{4N-c{\log }^{2}N}\approx \frac{h}{4}(N\gg {\log }^{2}N).$

两个推论:

• $Q<Q^{\ast }$ 时 QROM 便宜:查询次数少于”节点单价的四分之一”时,电路路线胜出;由于 $h$ 的分子上是尚未兑现的硬件,$Q^{\ast }$ 目前纯属纸面数字。
• $h$ 是全部赌注:QRAM 器件研究的实质就是把 $h$ 做小、同时让 $\epsilon$ 过推导五第一段的预算关。Hann 等证明”无需纠错的高保真查询”在一般噪声下原则可行 Hann 2021,Jaques–Rattew 的判词则是”廉价 QRAM 应视为不可行,除非被证明否则” Jaques-Rattew;$2^{30}$ 比特以内的小规模两边都不受渐近影响 Jaques-Rattew。

现状判断

对静态经典数据 + 可控查询次数的算法,QROM 不是妥协,而是当前唯一已交付的路线:化学模拟的整个 qubitization 程序就跑在 qROM/oracle 电路上 Babbush 2018。QRAM 器件留给四类尚未被电路覆盖的需求:查询次数巨大且时间预算紧、数据动态可写、量子数据(QRAQM),以及把访问压进 NISQ 深度预算。

数值算例:三个规模的总账

规模	表长 $N$	unary T-count/查询($=4N-4$)	qLUT_poly T-count(渐近)	BB 电路表面码嵌入	器件节点数
4 KB	$2^{15}=3.3\times 10^4$	$1.3\times 10^5$	$O(2^{7.5})\approx 180\times c$	$2.89\times 10^8$ 物理比特 / 0.348 ms [[sources/QR009	Di Matteo 2020]]
1 Mbit	$2^{20}=1.05\times 10^6$	$4.2\times 10^6$	$O(2^{10})=1024\times c$	—(文献未核算)	$1.0\times 10^6$
8 GB	$2^{36}=6.9\times 10^{10}$	$2.7\times 10^{11}$	$O(2^{18})\approx 2.6\times 10^5\times c$	$1.50\times 10^{15}$ 物理比特 / 2.13 ms [[sources/QR009	Di Matteo 2020]];QRAM_poly 变体 $4.18\times 10^{14}$ / $4.2\times 10^{-4}$ s [[sources/QR028

其中 $c$ 是文献未发表的乘性常数,渐近口径取自 Mukhopadhyay 2025($\sqrt{N}$ 标度)。三行算例的读法:

• 4 KB、$Q=10^4$ 次:QROM 总 T 账 $10^4\times 1.31\times 10^5\approx 1.3\times 10^9$ 个 T;BB 电路路线则是 $2.89\times 10^8$ 物理比特的固定成本换每查询 0.348 ms。两条账都能在标准成本模型里闭环到物理比特与秒——确定性是电路族对器件提案的根本优势。
• 8 GB 单查询:unary 口径 $2.7\times 10^{11}$ 个 T 与 QRAM_poly 实测口径 $\le 5.5\times 10^{11}$ 同量级 Mukhopadhyay 2025;qLUT_poly 把 T-count 渐近压到 $2^{18}\approx 2.6\times 10^5$ 量级,但按推导三,缺额记回 Clifford 层。器件路线需要 $6.9\times 10^{10}$ 个相干 qutrit 节点——对照当前实验规模(见 桶队架构),相差十余个数量级。
• 1 Mbit 的下界视角:计数下界($M=20$)要求任何”通用查表器”至少 $2.4\times 10^5$ 个门,unary 上界 $4.2\times 10^6$ 个 T,二者相距一个 $\log$ 因子略多——上下界夹逼出的改进空间是真实的,但只会以对数因子的形式兑现 Zhu 2024。

三行合读:没有任何一格逃出”$\tilde{\Theta }(N)$ 总门数,或 $N$ 个相干节点”的二选一——这是 Jaques–Rattew 定理 5.2 与 GLM 资源账在三个数量级上的重合 Jaques-Rattew。

讨论:边界上的灰区

量子数据不在此边界内。qROM 的读出是 CNOT 型复制,只对经典常数成立;量子数据的读出必须 SWAP 型”取出并搬走”,需要真实存储单元与相干路由(见 查询语义:路由与读出 与 分类学:四分类与主动/被动)。QRAQM 无法靠编译绕过。

可写性是隐形判据。“查表”预设表不变;数据频繁变动时,重编译成本必须计入总账(稀疏隐式电路尤其如此 Di Matteo 2020)。QRAM_poly 的立身之本正是读写兼备、免重编译 Mukhopadhyay 2025——它因此留在架构词条而非本边界词条(见 多项式编码 QRAM)。

机制可以进电路,器件语义进不去。Casares 把 bucket-brigade 逐位编译成 qutrit 门电路:单次查询路由操作 $n(n-1)/2$ 次、仅纠缠 $n$ 个 qutrit Casares 2020。“BB 机制 ≠ BB 器件”:同一路由逻辑搬进电路模型后,成本口径完全改变(见 成本口径:激活门、干预与能量)——与 qROM 的处境互为镜像:一个把器件逻辑电路化,一个把电路逻辑器件化(图灵完备的门集里”存”一张表),都不构成对方。

清单式结论。遇到自称 QROM 或 QRAM 的工作,依次问四个问题:数据是经典常数还是量子态?表是否需要免编译更换?单查询的渐近账计在哪一科目(T、Clifford、激活门)?错误分析走标准 QEC 流水线还是专门的器件韧性论证 Hann 2021Arunachalam 2015?四个答案合起来,就定位了它在 QRAM 总览 谱系中的坐标;电路级再优化的天花板见 电路级优化 与 评价指标:六维打分卡。

延伸阅读

• 边界:态制备电路不是 QRAM
• 机会成本定理
• 容错资源红线
• Oracle 假设谱系
• 桶队架构
• 多项式编码 QRAM
• 电路级优化
• 查询语义:路由与读出