蒸馏–传态协议

AWS 量子中心 2025 年的协议:只要存在保真度低至 1/poly(n) 的专用噪声 QRAM 器件,就能用 poly(n) 容错量子资源实现任意高保真的逻辑 QRAM——代价是把指数级开销转移给经典计算。

定位:三方分工的容错方案

电路式容错 QRAM 的死结:查询电路含 $\Omega (2^n)$ 个门,纠错即意味着对全部组件主动纠错,“激活门少”的红利被清零 Arunachalam 2015;表面码核算给出 8 GB 毫秒级查询需 $10^{15}$ 物理比特的红线 Di Matteo 2020(见容错资源红线)。蒸馏–传态协议(distillation–teleportation,Dalzell 等)Dalzell 2025改为三方分工:指数大而噪的专用 QRAM 器件(只查询、不纠错)、poly(n) 大而净的容错处理器(承担全部纠错)、指数大的经典计算(自适应更新数据表)——首个严格论证”专用噪声 QRAM 器件对容错量子计算有用”的方案:器件保真度可低至 $1/\mathrm{poly}(n)$,蒸馏把它升到任意高。

协议由至多 $n$ 轮循环构成:物理制备 → 容错编码 → 蒸馏 → 传态 → 经典更新,终态保证是钻石范数意义下的 $\frac{1}{2}\Vert {\mathcal{P}}_{\mathrm{DT}}-\overline{V}(f)[\cdot ]\overline{V}(f{)}^{†}{\Vert }_{\diamond }\le \epsilon$,代价为 $Q=O(n(1-F)/F^2\cdot (n/\epsilon +1/F))$ 次器件查询与 $Q^{\prime }=O(n^{2}Q)$ 个容错门 Dalzell 2025。

相位形式与 QRAM 资源态

相位态与代数正规型

Dalzell 等把 QRAM 取相位形式:$V(f):|x⟩\to (-1{)}^{f(x)}|x⟩$,$f:\{0,1{\}}^n\to \{0,1\}$ 为数据表。读出形式 $U(f):|x⟩|u⟩\to |x⟩|u\oplus f(x)⟩$ 经 Hadamard 共轭化为对角酉:对角元 $(-1{)}^{\hat{f}(x,u)}$、$\hat{f}(x,u)={⨁}_j{u}_j{f}_j(x)$,代数次数至多 $n+1$、与总线宽度 $b$ 无关——故只需实现相位形式,资源态涨到 $n+b$ 比特、轮数上界变 $n+1$(论文附录 A)。

QRAM 资源态定义为

$$|\Psi (f)⟩=V(f)|+{⟩}^{\otimes n}=\frac{1}{\sqrt{2^n}}\sum _{x\in \{0,1{\}}^n}(-1{)}^{f(x)}|x⟩,$$

即相位态(phase state):全部基态等幅叠加、相位由数据表逐点编码,首次被用作 QRAM 资源 Dalzell 2025。

关键代数恒等式是合成律 $V(h)V(h^{\prime })=V(h\oplus h^{\prime })$(相位相加),以及 $f$ 的代数正规型(algebraic normal form,ANF):$f(x)={⨁}_{e\in \{0,1{\}}^n}{c}_e{x}^e$($c_e\in \{0,1\}$,$x^e={\prod }_i{x}_i^{e_i}$),次数 $\mathrm{deg}f=\max \{|e|:c_e=1\}$。整个协议的”量子侧只需 poly(n)“都挂在 $\mathrm{deg}f$ 上。

数据集无关噪声

蒸馏要求谱结构对所有数据表一致,故论文假设(Definition 1)噪声与数据集无关:

$$\tilde{V}(g)={\mathcal{N}}_2\circ V(g)\circ {\mathcal{N}}_1,$$

即器件 = 前置噪声 ${\mathcal{N}}_1$ + 理想查询 $V(g)$ + 后置噪声 ${\mathcal{N}}_2$,两个信道不依赖 $g$。这个假设比直觉宽松,反例是”死路由器”(dead router):树中某路由器永久失效,凡查询路径经过它,器件就整体输出最大混合态 $\mathbb{I}/2^n$。设坏地址集 $\mathcal{X}\subset \{0,1{\}}^n$、投影 ${\Pi }_{\mathcal{X}}={\sum }_{x\in \mathcal{X}}|x⟩⟨x|$,器件信道

$$\tilde{V}(g)[\rho ]=(\mathbb{I}-{\Pi }_{\mathcal{X}})V(g)\rho V(g{)}^{†}(\mathbb{I}-{\Pi }_{\mathcal{X}})+\mathrm{tr}({\Pi }_{\mathcal{X}}\rho )\mathbb{I}/2^n$$

正是 ${\mathcal{N}}_2\circ V(g)\circ {\mathcal{N}}_1$(${\mathcal{N}}_1=\mathcal{I}$)——“灾难性”失败被吸收进与数据表无关的信道。器件保真度(以 $|+{⟩}^{\otimes n}$ 为输入)满足 Dalzell 2025

$$F_{\mathrm{phys}}\ge 1-\frac{2|\mathcal{X}|}{2^n}.$$

坏路由器埋得越深($|\mathcal{X}|/2^n$ 越小)器件越好——坏事件占比可压,正是蒸馏吃得下的误差类型。

推导一:代数次数与 Clifford 层级

引理(论文附录 D,复述并补关键步骤): 若 $\mathrm{deg}h=d$,则 $V(h)$ 属于 Clifford 层级(Clifford hierarchy)第 $d$ 层 ${\mathcal{C}}_d$,其中 ${\mathcal{C}}_1$ 为 Pauli 门集、${\mathcal{C}}_k=\{U:UP{U}^{†}\in {\mathcal{C}}_{k-1},\forall \text{Pauli }P\}$。

对 $d$ 归纳。$d=0$:$h$ 为常数,$V(h)=\pm \mathbb{I}\in {\mathcal{C}}_1$。设结论对 $d-1$ 成立,考虑 $\mathrm{deg}h=d$ 的 $h$。$V(h)$ 对角,与 $Z^b$ 对易:$V(h)Z^{b}V(h{)}^{†}=Z^b$。对 $X^a$,逐基态计算共轭:

$$V(h)X^{a}V(h{)}^{†}|x⟩=(-1{)}^{h(x)}{X}^a(-1{)}^{h(x)}|x⟩=(-1{)}^{h(x)}(-1{)}^{h(x\oplus a)}|x\oplus a⟩,$$

两份相位因子相乘,换元 $y=x\oplus a$ 后重排为 $V(h^{\prime })X^a$ 的作用形式,其中

$$h^{\prime }(x)=h(x)\oplus h(x\oplus a).$$

由归纳假设只需证 $\mathrm{deg}{h}^{\prime }\le d-1$。在 ANF 里,把 $x\to x\oplus a$ 代入单项式 $x^e$:替换后多项式的最高次项仍是 $x^e$ 本身($x_i\to x_i\oplus m_i$ 不消去 $x_i$ 的一次项),故 $h(x)$ 与 $h(x\oplus a)$ 的所有 $d$ 次单项系数逐项相同,在 $\oplus$ 下全部相消,$h^{\prime }$ 的剩余项次数至多 $d-1$。单变量演示:$x\oplus (x\oplus 1)=1$,次数从 1 降到 0。于是 $V(h)X^a{Z}^{b}V(h{)}^{†}=V(h^{\prime })X^a{Z}^b\in {\mathcal{C}}_{d-1}$,即 $V(h)\in {\mathcal{C}}_d$。$\square$

任意 $n$ 比特函数 $\mathrm{deg}f\le n$,故 $V(f)\in {\mathcal{C}}_n$。直觉:门电路规模由真值表长度 $2^n$ 决定,传态校正层级由 ANF 次数决定——前者指数、后者线性,协议的杠杆正压在这条裂缝上。

推导二:门传态与校正链

传态电路与测量结果分析

对逻辑数据寄存器实施 $V(\bar{f})$ 的门传态(gate teleportation):制备逻辑资源态 $|\overline{\Psi (f)}⟩$,$n$ 个逻辑 CNOT 把数据逐位拷入资源态,再对资源态逐位做 $X$ 基测量得 $n$ 比特结果 $m$ Dalzell 2025。逐基态追踪相位:$m$ 均匀分布于 $\{0,1{\}}^n$,实际施加的是

$$\sum _x{\alpha }_x(-1{)}^{f(x\oplus m)}|x⟩=V(f^{\oplus m})[\sum _x{\alpha }_x|x⟩],f^{\oplus m}(x):=f(x\oplus m),$$

即地址被 $X^m$ 平移后再取相位。$m=0^n$(概率 $2^{-n}$)时歪打正着;一般情形需校正 $V(f^{\oplus m})\to V(f)$,由合成律,校正门恰为

$$V(f^{\prime })\text{其中}{f}^{\prime }(x)=f(x)\oplus f(x\oplus m)$$

($f^{\prime }$ 依赖 $m$,只能在传态之后由经典机算出;单比特对应式为经典结果 $GX{G}^{†}X$)。

次数下降与终止

校正门 $V(f^{\prime })$ 本身还是一族 QRAM 门——这是协议能循环的原因。推导一的引理给出 $\mathrm{deg}{f}^{\prime }=\mathrm{deg}(\mathrm{UR}(f,m))\le \mathrm{deg}f-1$(UR 即 update rule,见推导六),故第 $j$ 轮的校正函数 $g^{(j)}$ 满足

$$\mathrm{deg}{g}^{(1)}\le n,\mathrm{deg}{g}^{(j+1)}\le \mathrm{deg}{g}^{(j)}-1⟹\mathrm{deg}{g}^{(j)}\le n-j+1.$$

$n$ 轮后次数降到 0,$g\in \{0,1\}$,校正门为 $\pm \mathbb{I}$,链必然终止;中途得零函数可提前停机。直觉:随机平移把数据表与自己的平移副本”做差”,削掉 ANF 最高层——如对多项式做差分,$n$ 次后任何 $n$ 变量函数变为常数。每轮量子侧成本恒定($n$ CNOT + $n$ 测量),变的只是经典数据表。

推导三:部分 Clifford twirling 与本征值隙

为何蒸馏需要一个已知的主本征向量

蒸馏是态不可知(state-agnostic)纯度放大(purity amplification):输入多份混合态 ${\rho }_{\mathrm{in}}$,输出其主本征向量(principal eigenvector)的高纯版本,全程不学习、不利用该向量的任何内容 Dalzell 2025。它能工作当且仅当主本征向量恰是 $|\overline{\Psi (g)}⟩$(否则蒸馏忠实放大错态);其速度由谱隙控制(推导四给出定量)。谱整形由部分 Clifford twirling 完成:每次查询前经典地把数据表随机变换 $g\mapsto g_C$($C$ 取自部分 Clifford 集合 $\mathbb{T}$),查询后做可逆修正。结论(论文 Proposition 5):

$${\overline{\varphi (g)}}_{\mathrm{twirl}}|\overline{\Psi (g)}⟩={\lambda }_{\mathrm{twirl}}|\overline{\Psi (g)}⟩,{\lambda }_{\mathrm{twirl}}\ge F_{\min },{\lambda }_{\mathrm{other}}\le 2^{-n+1}.$$

主本征向量被”钉”在目标态上,其余本征值一致压到 $2^{-n+1}$(完整 Clifford 群可得 $2^{-n}$,部分集合的代价是 2 倍)。直觉:twirling 把可能集中在错误方向上的谱重量打散成近最大混合,唯一保住的对称方向是相位态自身;谱隙 ${\lambda }_1-{\lambda }_2\gtrsim F_{\min }$——哪怕 $F_{\min }=1/\mathrm{poly}(n)$ 也是多项式级的隙。

twirling 如何驯服死路由器

twirling 的第二重作用:信息 $g(x)$ 的位置被随机化,等概率藏在某个 $g_C(y)$ 里,$y\in \mathcal{X}$ 的概率为 $|\mathcal{X}|/2^n$——每个 $x$ 的信息都只以这个小概率被坏投影吃掉,与 $x$ 是否本属坏地址无关,查询坏地址不再必死。若器件与编码无噪 twirling 可免,更新规则则免不了 Dalzell 2025。

推导四:蒸馏的保真度–产率公式

swap test 的基本代数

迭代 swap test 是纯度放大的最简实现(容错实现 = 受控 SWAP + Hadamard + 测量)。对两份 ${\rho }_{\mathrm{in}}$,辅助比特读 $|0⟩$ 记”通过”。在基底 ${\rho }_{\mathrm{in}}={\sum }_i{p}_i|i⟩⟨i|$ 下展开:通过分支的拷贝对处于 $(|ij⟩+|ji⟩)/2$,$i=j$ 项模方为 1、$i\ne j$ 项为 1/2,求和得通过概率

$$\mathrm{Pr}[\text{pass}]=\frac{1+\mathrm{Tr}({\rho }_{\mathrm{in}}^2)}{2},$$

条件输出态(投影 $P_{+}=(\mathbb{I}+S)/2$ 作用于拷贝对、舍去一份;因 $S$ 与 ${\rho }^{\otimes 2}$ 对易,$P_{+}$ 保对角、砍反对称):

$${\rho }_{\mathrm{out}}=\frac{{\rho }_{\mathrm{in}}+{\rho }_{\mathrm{in}}^2}{1+\mathrm{Tr}({\rho }_{\mathrm{in}}^2)}.$$

输出是输入的多项式函数,故与输入同本征基,本征值逐点映射 $\lambda \mapsto (\lambda +{\lambda }^2)/(1+\mathrm{Tr}{\rho }_{\mathrm{in}}^2)$。设主本征值 $1-{\eta }_{\mathrm{in}}$,用 $\mathrm{Tr}{\rho }^2\le (1-{\eta }_{\mathrm{in}}{)}^2+{\eta }_{\mathrm{in}}^2$(其余谱最坏挤在一个本征值上),不保真度迭代式

$${\eta }_{\mathrm{out}}\le 1-\frac{(1-{\eta }_{\mathrm{in}})+(1-{\eta }_{\mathrm{in}}{)}^2}{1+(1-{\eta }_{\mathrm{in}}{)}^2+{\eta }_{\mathrm{in}}^2}=\frac{{\eta }_{\mathrm{in}}}{2}\cdot \frac{1+{\eta }_{\mathrm{in}}}{1-{\eta }_{\mathrm{in}}+{\eta }_{\mathrm{in}}^2}\stackrel{{\eta }_{\mathrm{in}}\ll 1}{\to }\frac{{\eta }_{\mathrm{in}}}{2}.$$

直觉:一次成功的 swap test 把不保真度砍半——产率分析的种子。

迭代收敛:不保真度逐层减半

把通过测试的输出回灌为输入,迭代 $k$ 层。上式可放缩为 ${\eta }_{i+1}\le {\eta }_i/(2-4{\eta }_i)$(用 $(1+\eta )(1-2\eta )\le 1-\eta +{\eta }^2$),对它归纳(论文 Eq. 55):若 ${\eta }_0<1/4$,则

$${\eta }_k\le \frac{2^{-k}{\eta }_0}{1-4{\eta }_0}:$$

归纳一步为 ${\eta }_{i+1}\le 2^{-1-i}{\eta }_0/(1-4{\eta }_0+2^{1-i}{\eta }_0)$。达到目标 ${\epsilon }_{\mathrm{dist}}$ 只需

$$k={\log }_2\frac{{\eta }_0}{(1-4{\eta }_0){\epsilon }_{\mathrm{dist}}}\approx {\log }_2\frac{1-F_{\min }}{{\epsilon }_{\mathrm{dist}}}\text{层}.$$

直觉:减半律是指数收敛,$k$ 只是对数;真正的代价藏在”每层要两份上一层副本”的二叉树结构里,下一步算清。

产率:副本数与 swap test 数

第 $i$ 层每个成功测试消耗 2 份 ${\rho }_{i-1}$、期望重复 $1/p_i^{\mathrm{succ}}$ 次($p_i^{\mathrm{succ}}\ge 1-{\eta }_{i-1}$),归纳得副本数 $c_i=2^i{\prod }_{j\le i}1/p_j^{\mathrm{succ}}$。论文给出 telescoping 型下界 ${\prod }_{j=1}^i{p}_j^{\mathrm{succ}}\ge \sqrt{1-4{\eta }_0}$(把成功概率下界平方、代入 ${\eta }_j$ 的归纳式后逐项相消),于是 Proposition 7:

$$c_k\le \frac{2^k}{\sqrt{1-4{\eta }_0}}=O\left(\frac{1-F_{\min }}{{\epsilon }_{\mathrm{dist}}}\right),s_k\le \frac{2^k-1}{\sqrt{1-4{\eta }_0}}\text{次 swap test},$$

存储只需 1 个比特 + $k+1$ 个 qudit(每 qudit 为 $n$ 个逻辑比特;流式实现空间 $O(n\log \frac{n}{\epsilon })$)。$F_{\min }\to 1$ 时样本数 $\approx (1-F_{\min })/{\epsilon }_{\mathrm{dist}}$ 接近最优——态不可知纯度放大的普适下界是 $\Theta (1/{\epsilon }_{\mathrm{dist}})$ Dalzell 2025。每次 swap test 的非 Clifford 代价是 $n$ 个逻辑 Toffoli 级 CSWAP——全协议非 Clifford 门的唯一来源。

低保真区:逐层增益衰竭与谱隙的救赎

${\eta }_0\ge 1/4$(即 $F\le 3/4$)时 Proposition 7 失效,且恶化是指数的。机制(本词条按论文引述的结果整理):记 ${\gamma }_i=1-{\eta }_i$,一次 swap test 给

$${\gamma }_{i+1}=\frac{{\gamma }_i+{\gamma }_i^2}{1+\mathrm{Tr}{\rho }_i^2}\le {\gamma }_i+{\gamma }_i^2\cdot \frac{1-{\gamma }_i}{1+{\gamma }_i^2}(\text{次本征谱摊开时}),$$

增益从 $O(\gamma )$(高保真区的减半律)退化为 $O({\gamma }^2)$,而每层成功概率 $p_i\approx \frac{1}{2}$:爬到 $O(1)$ 需 $\Theta (1/{\gamma }_{\mathrm{in}})$ 层,二叉树叶子数逐层翻倍,副本数 $2^{\Theta (1/{\gamma }_{\mathrm{in}})}$——对 $1/F_{\min }$ 指数 Dalzell 2025。

救赎恰是推导三的谱隙。设次大本征值 ${\lambda }_2\le \alpha {\lambda }_1$($\alpha <1$),本征值映射给出(论文 Eq. 56)

$${\gamma }_{\mathrm{out}}\ge p({\gamma }_{\mathrm{in}}):=\frac{{\gamma }_{\mathrm{in}}}{1-(1-\alpha )\frac{{\gamma }_{\mathrm{in}}(1-{\gamma }_{\mathrm{in}})}{1+{\gamma }_{\mathrm{in}}}}>{\gamma }_{\mathrm{in}},$$

且本征值比 ${\lambda }_2/{\lambda }_1$ 每层改乘 $(1+{\lambda }_2)/(1+\gamma )\approx 1/(1+\gamma )$、几何式缩小——主本征值按比例抬升、次本征值原地踏步。twirling 给 $\alpha \le 2^{-n+1}/F_{\min }$(指数小),分母修正项 $(1-\alpha )\approx 1$,迭代 $\gamma \to \gamma (1+\gamma )/(1+{\gamma }^2)$ 常数层内达 $\gamma \ge 5/6$,再接 Proposition 7。论文的保守账:$\alpha \le 10^{-3}$、${\gamma }_{\mathrm{in}}\ge 0.2$ 时 9 层内达 $5/6$,副本上界约 $1.2\times 10^4$;低到 $F_{\min }=1/\mathrm{poly}(n)$ 也只是多项式开销——“保真度低至 $1/\mathrm{poly}(n)$“的宣称就落在这条谱隙上。直觉:没有谱隙,低保真蒸馏指数慢;twirling 用一次经典随机化买来指数谱隙,抹平指数账。

最优样本复杂度与 qPCA 流式协议

${\gamma }_{\mathrm{in}}\ll 1$ 区,基于 Schur 变换的并行最优协议样本数 $\sim \frac{1}{{\epsilon }_{\mathrm{dist}}}\cdot \frac{1-{\gamma }_{\mathrm{in}}}{(1-\alpha {)}^2{\gamma }_{\mathrm{in}}^2}$,比迭代 swap test 指数好,但要并行存储全部副本、空间爆炸。论文为此提出基于 qPCA(quantum principal component analysis)的流式纯度放大:逐副本处理、只用两个 qudit 存储,在低保真区匹配上述渐近最优样本复杂度 Dalzell 2025。作为对照,普通魔态 $|\bar{T}⟩$ 蒸馏利用 $T$ 横穿的码,开销仅 $\mathrm{polylog}(1/{\epsilon }_{\mathrm{dist}})$、高码率码下可到 $O(1)$;$V(g)$ 没有已知的此类码,只能用态不可知纯度放大的 $\Theta (1/{\epsilon }_{\mathrm{dist}})$——这是”QRAM 资源态比魔态贵”的准确表述。

推导五:传态换深度

一般机制:传输指数账

传态的第一性作用是把”信息走完全程”换成”每层消费一份预共享纠缠”。$n$ 层二叉路由树装载地址:直接传输时第 $j$ 位要穿过前 $j-1$ 层已配置节点,单次穿越存活率 ${\eta }_r$,总存活指数

$$\sum _{j=1}^n(j-1)=\frac{n(n-1)}{2}⟹P_{\mathrm{surv}}={\eta }_r^{n(n-1)/2};$$

传态变体逐层预制备纠缠、以局域 Bell 测量把地址并行注入各层,每位只需 $O(1)$ 次穿越,$P_{\mathrm{surv}}^{\prime }={\eta }_r^n$——指数从 $O(n^2)$ 压到 $O(n)$(数值表见 硬件共识设计策略 算例 3 与 光子–自旋 QRAM 推导三)。直觉:传输坏账按”路径长度”复合;传态把路径长度摊给离线纠缠制备,在线穿越从平方变线性。

本协议的两处传态

1. 跨物理/逻辑边界: 逻辑 QRAM 门 $V(\bar{f})$ 不以电路形式运行,而是消耗一份蒸馏好的资源态:门传态只需 $n$ 个逻辑 CNOT + $n$ 个单比特测量,在线深度 $O(n)$、全 Clifford(非 Clifford 门全部留在蒸馏的 swap test 里)。对照电路式实现:$\Omega (2^n)$ 个门与逻辑比特、至少 $\Omega (\sqrt{2^n})$ 个并行魔态工厂、外加 $\Omega (2^n)$ 个实时纠错协处理器(论文举例:$2^{20}$ 逻辑比特在 1 MHz 码周期下每秒产生超 15 TB 综合征数据)Dalzell 2025。买到的是相干深度:$O(2^n)\to O(n)$,账单转给经典侧。
2. 校正链的接力: 每轮传态把”下一个指数级门 $V(g^{(j)})$“的实施权交还器件(重载新数据表再查询),量子侧每轮恒定 $O(n)$;无传态则校正门须以电路形式内嵌进相干计算,指数深度无法隔离。

合并读法:器件的指数规模只出现在非相干的资源制备里,进入相干计算后一切被压到 poly(n)——与 Clifford 化路线(Clifford 化容错接口)把非 Clifford 成本推给离线资源态同一哲学,只是本协议把离线制备进一步外包给了噪声器件。

推导六:时空开销总账

量子侧:查询数与容错门数

账目自下而上(论文 Theorem 2 的推导链):$n$ 轮误差线性累加,故单轮传态误差 $\le \epsilon /n$,即蒸馏须达 ${\epsilon }_{\mathrm{dist}}=\epsilon /n$;Proposition 6 给每轮副本数 $O\left(\frac{1-F_{\min }}{F_{\min }^2}\right(\frac{1}{{\epsilon }_{\mathrm{dist}}}+\frac{1}{F_{\min }}\left)\right)$;乘 $n$ 轮、代入 $F_{\min }=\Theta (F)$(见下小节):

$$Q=O\left(\frac{n(1-F)}{F^2}(\frac{n}{\epsilon }+\frac{1}{F})\right),Q^{\prime }=O(n^{2}Q);$$

$Q^{\prime }$ 的支配项是 twirling(每份副本 $O(n^2)$ 个容错 Clifford 门),蒸馏贡献 $O(nQ)$(每副本 $O(n)$ 门),传态贡献 $n^2$ 个 CNOT。量子侧确实 $\mathrm{poly}(n)/\epsilon$:逻辑比特、逻辑门、QEC 周期全是多项式,没有任何 $\Omega (2^n)$ 量子组件被主动纠错。

器件侧:错误率门槛

$F_{\min }$ 由两级误差串联:器件物理保真度 $F_{\mathrm{phys}}$ 与编码误差。编码 $n$ 个物理比特进逻辑比特的误差为 ${\epsilon }_{\mathrm{enc}}\le \Gamma (\mathcal{E})+2\sqrt{cp}n+2|\mathcal{E}|(cp{)}^k$(一般码,论文 Corollary 1;$\Gamma (\mathcal{E})$ 随码距消失,拓扑码每比特 $O(p)$、总计 $O(np)$),于是

$$F_{\min }\ge (1-np-6n\sqrt{cp})\cdot \underset{g}{\min }{F}_{\mathrm{phys}}(g)=\Omega (F)\text{当 }p{n}^2\text{低于常数阈值}.$$

器件端,bucket-brigade 韧性给出总不保真度 $O(q{n}^2)$(Hann 界 $4\epsilon T\log N$ 以 $T=O(\log N)$ 代入,见一般噪声下的韧性与桶队架构)Hann 2021,故组件错误率需 $q=O(1/n^2)$;编码端需 $p=O(1/n)$(拓扑码)或 $O(1/n^2)$(一般码)。$q=p=10^{-4}$ 时 $n=36$(约 10 GB)即可、$n=43$ 对应 1 TB——门槛只按 $1/n^2$ 收紧。

经典侧:更新规则的 $\Omega (2^n)$

更新规则 $\mathrm{UR}(g,m)(x)=g(x)\oplus g(x\oplus m)$ 是协议的阿喀琉斯之踵,论文给它三本账:

1. RAM 模型下界: 输出 $2^n$ 比特、每个输出位 $h(x)$ 依赖 $g(x)$ 与 $g(x\oplus m)$、每次 RAM 查询只能读 1 比特,故至少 $\Omega (2^n)$ 次查询;电路模型下输出规模即给 $\Omega (2^n)$ 门。
2. 并行化与布线: 全连接布线下存在 $O(n)$ 深度电路(宽 $O(n{2}^n)$);嵌入 $d\le 3$ 维空间时,$n$ 维超立方体的连线塞进 $d$ 维网格,总线长 $\Omega (2^{n(1+1/d)})$、线密度(wire density)$\Omega (2^{n/d}/\mathrm{poly}(n))$——与经典 RAM 的常数线密度有本质差距。论证骨架是分割(bisection):$d$ 维网格切半只切开 $O(L^{d-1})$ 条线($L$ 为边长),超立方体的分割面却有 $2^{n-1}$ 条跨边,逼出 $L\ge 2^{n/d}$。
3. WH 变换等价: 在 $2^n$ 协处理器并行模型下,更新规则与 Walsh–Hadamard 变换互相约化到 $\mathrm{poly}(n)$ 因子内。正方向一行算完:$h(x)=g(x)+g(x\oplus m)$(普通加法)时

$$(Hh{)}_x=(Hg{)}_x+(-1{)}^{x\cdot m}(Hg{)}_x=(1+(-1{)}^{x\cdot m})(Hg{)}_x,$$

即 WH 加一次逐点屏蔽;反方向按位切片、每比特面调一次 UR 即实现快 WH 的一步。基准由此锚定:UR 的能力 $\approx$ 对 $2^n$ 维向量做稀疏矩阵–向量乘。

作者自陈这笔指数经典账”暴露了实现真正 poly(n) 成本容错 QRAM 的潜在根本限制”,并把协议概括为”用 $O(2^n)$ 量子资源换 $O(2^n)$ 经典资源” Dalzell 2025。它同时是机会成本论证的活靶:同样的 $\Omega (2^n)$ 协处理器本身就能做稀疏矩阵–向量乘,吃掉一大部分设想的量子优势(见机会成本定理)。

数值算例

算例 1:$n=36$、$F\approx \frac{1}{2}$ 的完整账(本词条按论文公式与参数复算)

取论文设定:10 GB 存储($n=36$)、$q=p=10^{-4}$、总误差预算 ${\epsilon }_{\mathrm{tot}}=0.1$。逐项:

1. 器件保真度: Hann 韧性给 $1-F\lesssim 4q{n}^2=4\times 10^{-4}\times 1296\approx 0.52$,即 $F\approx 0.48$——论文取 "$F=50\%$" 做工作例子的原因即此;
2. 每轮蒸馏目标: ${\epsilon }_{\mathrm{dist}}={\epsilon }_{\mathrm{tot}}/n=0.1/36\approx 2.8\times 10^{-3}$;
3. 每轮副本数(Prop 6 上界): $\frac{1-F}{F^2}(\frac{1}{{\epsilon }_{\mathrm{dist}}}+\frac{1}{F})=\frac{0.5}{0.25}\times (360+2)\approx 724$;
4. 总量: $Q=n\times 724\approx 2.6\times 10^4$ 次器件查询与编码;$Q^{\prime }=n^{2}Q\approx 3.4\times 10^7$ 个容错门;非 Clifford(Toffoli)$\approx nQ\approx 9.4\times 10^5$;
5. 经典: $Q$ 次 twirl + $n$ 次 UR,每次扫一张 $2^{36}$ bit(8 GB)表:$Q\cdot 2^{36}\approx 1.8\times 10^{15}$ 比特操作,等效搬运约 $2\times 10^5$ GB $\approx 200$ TB 数据。

对照读法:量子侧 $3.4\times 10^7$ 容错门”大而可行”,同任务的电路式 QRAM 是 $10^{15}$ 物理比特 Di Matteo 2020;省下的指数全记在经典侧 200 TB 的数据搬运上。

算例 2:蒸馏链逐步复算(本词条按论文公式推演)

接算例 1:${\gamma }_0=F_{\min }\approx 0.5$ 在 Proposition 7 适用区(${\eta }_0>1/4$)之外,先走 boost 段。twirling 给 $\alpha \le 2^{-n+1}/F_{\min }\approx 2^{-36}$,取 $\alpha \approx 0$,映射 $\gamma \to \gamma (1+\gamma )/(1+{\gamma }^2)$:

$$0.500\to 0.600\to 0.706\to 0.804\to 0.881(>\frac{5}{6}).$$

4 层 boost,每层成功概率 $\ge (1+{\gamma }^2)/2\in [0.61,0.82]$,期望副本 $2^4/0.26\approx 61$。随后 $\eta =1-0.881=0.119<1/4$,解 $2^{-k}\eta /(1-4\eta )\le 2.8\times 10^{-3}$ 得 $k=7$;副本 $2^7/\sqrt{1-4\eta }\approx 177$、swap test $\approx 176$。合计约 240 副本/轮——与 Prop 6 的保守上界 724 同量级(界松约 3 倍)。保真度从 48% 到 $1-2.8\times 10^{-3}$,代价是每轮数百次器件查询 + 容错 swap test——“蒸馏把 $1/\mathrm{poly}(n)$ 变成 $1-O(\epsilon /n)$“的价格标签。

算例 3:经典侧的墙钟时间(本词条估算,假设已列明)

以 $Q+n\approx 2.6\times 10^4$ 次全表操作、每张 8 GB 表计:单核 $10^9$ 比特操作/秒需 $1.8\times 10^6$ s(约 20 天);$O(n)$ 深度并行电路(宽 $O(n{2}^n)$)或 $10^5$ 核集群压到 $O(10)$ s/逻辑查询。对比:器件以 10 kHz 供 $2.6\times 10^4$ 次查询约 2.6 s、$\sim 10^4$ 级容错 swap test 在毫秒–秒级——墙钟与成本瓶颈都在经典侧。流水线上相邻查询可重叠(器件与处理器是两台机器),吞吐由 max(器件速率, 蒸馏门速, 经典更新速率) 决定;单条查询延迟被 $n$ 轮串行(每轮等上一轮测量结果)钉死。

讨论:边界、绕过与开放问题

绕过 no-go 定理。 Jaques–Rattew 综述曾证明:$d$ 次物理 QRACM 调用的非自适应蒸馏–传态过程,最小保真度不超过 $3/4+d\sqrt{2/N}$ Jaques-Rattew 2025(该定理假设蒸馏过程与数据表无关,见机会成本定理)。本协议靠自适应性绕开:第 $j$ 轮的数据表 $g^{(j)}$ 依赖 $f$ 与前 $j-1$ 轮测量结果,逐轮不同,“表无关”假设从根上不成立。

应用粗估不乐观。 ECC 密码分析($b=512$、$F=50\%$、${\epsilon }_{\mathrm{tot}}=0.1$):QRAM 方案的 Toffoli 最优点在 $2^{64}$ 规模分组(经典更新已不可行),现实的 $2^{32}$ 分组也比 QROM 方案最低 Toffoli 成本差约 1.8 倍(active volume 1.6 倍),未计器件成本;FeMoCo 化学($\lambda =7614$、$L\approx 1.8\times 10^5$、$b=84$)每次块编码需 $\ge 2.5\times 10^{11}$ 个 Toffoli,对比 QROM 查找表约 $10^4$——当前形式均无实际优势 Dalzell 2025。症结:成本压在 $n/\epsilon$ 与 $b$ 的乘积上。

结构性出路。 若数据表自由度少于 $2^n$(如稀疏矩阵只有 $\sqrt{2^n}$ 个独立参数),UR 只需在有效规模上运行,经典账按自由度收费,端到端可能出现”经典二次 + 量子指数”的组合加速 Dalzell 2025;反向边界是:经典稀疏代数已能 $\mathrm{poly}(n)$ 解决的问题,本协议无净优势。

与其他容错路线的位置。 四维对照(查询时间/量子比特/不保真度/物理错误率)中本协议占 $O(n)$、$O(n)$、$O(1)$、$O(n^{-2})$——逻辑资源最省、器件要求随规模收紧 Singal 2025(对照表见异构纠错 QRAM)。三条路线共同回答”QRAM 能否纠错”,唯本协议容许 $1/\mathrm{poly}(n)$ 器件保真度,也唯它把指数复杂性显式留在账面。开放问题(论文自列):指数经典更新是否必然;微观噪声到数据集无关噪声的严格归约;$b$ 比特推广版的门数优化。对照方案见资源态 QRAM与QRAM 工厂。

延伸阅读

• 容错资源红线
• 异构纠错 QRAM
• Clifford 化容错接口
• 机会成本定理
• 资源态 QRAM
• 评价指标