多项式编码 QRAM

QRAM_poly(Mukhopadhyay,2025)用 GF(2) 上的多变元多项式编码地址,使 N 个辅助比特中恰有被寻址者翻转,实现 T 深度的指数级改进——属于"电路即架构"(circuits-as-architecture)路线的代表。

机制回顾:一元选择子与四个步骤

QRAM_poly 把一次存储调用整体编译为 Clifford+T 电路:不设路由树,先在 $N=2^n$ 个辅助比特上算出一组一元选择子(one-hot selector)——任意计算基址下恰有被寻址者为 1——再用它完成读、写或相位标记,实现标准查询映射 ${\sum }_{\vec{b}}{\alpha }_{\vec{b}}|\vec{b}⟩|0⟩\mapsto {\sum }_{\vec{b}}{\alpha }_{\vec{b}}|\vec{b}⟩|D_{\vec{b}}⟩$(记号与语义见 查询语义:路由与读出 与 成本口径:激活门、干预与能量),电路分四步 Mukhopadhyay 2025:

1. 算单项式(monomial):用 Toffoli 做乘法、CNOT 做复制,在专用辅助比特上算出全部 $2^n$ 个单项式 $m_{\mathcal{I}}={\prod }_{i\in \mathcal{I}}{x}_i$($x_i$ 是地址比特 $q_i$ 携带的变量);权重 0 的常数用 $X$ 门,权重 1 的就是地址变量本身。
2. 算编码多项式:用 CNOT 把单项式按求和恒等式(推导一)异或累加,使辅助比特 $a_{\vec{b}}$ 恰好存下地址 $\vec{b}$ 的编码多项式 $p_{\vec{b}}$。
3. 选择与读出:以 $a_{\vec{b}}$ 与存储单元 $M_{\vec{b}}$ 控制、输出总线为靶的 Toffoli 完成读取;写操作把两者的控制/靶角色对调;字长 $\ell$ 时该层是 $N\ell$ 个 Toffoli。
4. 逆序清场(uncompute):把步骤 1–2 逆放,辅助比特复位到 $|0⟩$,保证整体可逆。

读出层与一切架构同价(数据总要搬一次),论文的资源比较把它单列;区分架构的是步骤 1–2 的地址译码层——本词条的全部推导都在这一层。相位标记 oracle 连步骤 3 也不需要:步骤 2 之后对每个存储单元施加以 $a_{\vec{b}}$ 为控制的 CZ 即可(见末节)Mukhopadhyay 2025。

推导一:编码代数——指示多项式的四条性质

性质一:指示性质

对地址串 $\vec{b}=(b_1,\dots ,b_n)\in \{0,1{\}}^n$ 与取值于 GF(2) 的变量 $x_1,\dots ,x_n$,定义编码多项式

$p_{\vec{b}}(x_1,\dots ,x_n)={\prod }_{i=1}^n\left[\frac{1+(-1{)}^{b_i}}{2}+x_i\right],$

按 $b_i$ 取值展开因子:$b_i=0$ 时因子为 $1+x_i$,$b_i=1$ 时因子为 $x_i$。

引理 1(指示性质)。 $p_{\vec{b}}(b_1^{\prime },\dots ,b_n^{\prime })\equiv {\delta }_{\vec{b},{\vec{b}}^{\prime }}(\mathrm{mod}2)$:在 ${\vec{b}}^{\prime }=\vec{b}$ 处取 1,其余处取 0。

证明。 先看单因子 $p_{b_i}(x_i)$ 对任意比特值的响应。若 $x_i=b_i$:当 $b_i=0$ 时给出 $1+0=1$,当 $b_i=1$ 时给出 $1$——恒为 1。若 $x_i\ne b_i$:当 $b_i=0$ 时给出 $1+1=0(\mathrm{mod}2)$,当 $b_i=1$ 时给出 $0$——恒为 0。所以每个因子是第 $i$ 位的”相等指示子”;乘积取 1 当且仅当所有因子取 1,当且仅当每一位都相等,即 ${\vec{b}}^{\prime }=\vec{b}$。(若先在整数上求值再模 2,失配位给出 0 或 2,均为偶数,结论相同。)∎

三比特算例($\vec{b}=011$,$p=x_2{x}_3(1+x_1)=x_2{x}_3+x_1{x}_2{x}_3$):在 $011$ 处 $=1+0=1$;在 $111$ 处 $=1+1=0$;在 $010$ 处 $=0+0=0$。一个多项式恰好”点亮”一个地址——这就是 $N$ 个辅助比特中恰有被寻址者翻转的代数来源。

性质二:单项式展开与两个计数

引理 2(展开)。 设 $\vec{b}$ 中恰有 $w$ 个 1,其下标集为 ${\mathcal{I}}_1$($|{\mathcal{I}}_1|=w$),则

$p_{\vec{b}}=\left({\prod }_{j\in {\mathcal{I}}_1}{x}_j\right)({\prod }_{\ell \notin {\mathcal{I}}_1}(1+x_{\ell }))={\sum }_{{\mathcal{I}}^{\prime }\supseteq {\mathcal{I}}_1}{m}_{{\mathcal{I}}^{\prime }},$

即 $p_{\vec{b}}$ 等于所有”下标集包含 ${\mathcal{I}}_1$“的单项式之和,共 $2^{n-w}$ 项。证明只需对第二个括号二项式展开 ${\prod }_{\ell }(1+x_{\ell })={\sum }_{\mathcal{J}}{m}_{\mathcal{J}}$($\mathcal{J}$ 取遍全部子集),再乘上前一括号:留下的项恰是 ${\mathcal{I}}^{\prime }\supseteq {\mathcal{I}}_1$。

两个直接推论决定全篇资源账。

单项式出现次数求和是 $3^n$。 全部 $N$ 个多项式的单项式合计

${\sum }_{\vec{b}}{2}^{n-|\vec{b}|}={\sum }_{w=0}^n\left(\genfrac{}{}{0ex}{}{n}{w}\right)2^{n-w}=(1+2{)}^n=3^n,$

最后一步是二项式定理。这个 $3^n$ 将在推导二的 CNOT 账里原样再现。

全零地址最贵,而且谁都躲不开。 $\vec{b}=0\cdots 0$ 的多项式是 ${\prod }_i(1+x_i)$,包含全部 $2^n$ 个单项式;电路必须服务最坏地址,“每个单项式都要算出来、有地方存”于是不是实现选择,而是内在要求——译码层宽度 $\Theta (N)$ 由此锁定。

性质三:最小权单项式与辅助比特标记

推论(唯一最小权单项式)。 每个 $p_{\vec{b}}$ 的单项式中有唯一权重最小者 $m_{{\mathcal{I}}_1}={\prod }_{j\in {\mathcal{I}}_1}{x}_j$:由引理 2,权重更小的 ${\mathcal{I}}^{\prime }⊉{\mathcal{I}}_1$ 都不出现,而 $m_{{\mathcal{I}}_1}$ 本身总在。反过来,每个单项式 $m_{\mathcal{I}}$ 恰是一个多项式(${\mathcal{I}}_1=\mathcal{I}$ 那个)的最小权单项式。

于是单项式、地址串、辅助比特一一对应:$m_{\mathcal{I}}$ 存进 $a_{\mathcal{I}}$。这个”标记”是电路骨架:步骤 1 按它放置单项式,步骤 2 按它决定每条 CNOT 的方向与靶。

性质四:求和恒等式——多项式之间的递推

定理(求和恒等式)。 以最小权单项式为标记,$p_{\vec{b}}=p_{m_{{\mathcal{I}}_1}}$ 满足

$p_{m_{{\mathcal{I}}_1}}=m_{{\mathcal{I}}_1}\oplus {⨁}_{{\mathcal{I}}^{\prime }⊋{\mathcal{I}}_1}{p}_{m_{{\mathcal{I}}^{\prime }}},$

其中 $\oplus$ 表示同单项式系数模 2 相加。

证明。 由引理 2,$m_{{\mathcal{I}}_1}$ 在左端出现一次。考察权重 $w^{\prime }>w$ 的单项式 $m_{{\mathcal{I}}_{w^{\prime }}}$(${\mathcal{I}}_{w^{\prime }}={\mathcal{I}}_1\cup {\mathcal{I}}_2$,$|{\mathcal{I}}_2|=w^{\prime }-w$):它出现在每个满足 ${\mathcal{I}}_1\subseteq {\mathcal{I}}^{\prime \prime }\subseteq {\mathcal{I}}_{w^{\prime }}$ 的 $p_{m_{{\mathcal{I}}^{\prime \prime }}}$ 中,这样的 ${\mathcal{I}}^{\prime \prime }$ 共 ${\sum }_{\ell =0}^{w^{\prime }-w}\left(\genfrac{}{}{0ex}{}{w^{\prime }-w}{\ell }\right)=2^{w^{\prime }-w}$ 个;除去 ${\mathcal{I}}^{\prime \prime }={\mathcal{I}}_{w^{\prime }}$ 自身(其最小权单项式即 $m_{{\mathcal{I}}_{w^{\prime }}}$,单独计入左端)后,它在右端出现 $2^{w^{\prime }-w}-1$ 次——奇数次,模 2 下恰贡献一次。∎

这条恒等式把步骤 2 的连线完全确定:从权重最高的单项式开始,把 $a_{\mathcal{I}}$ 异或进每个 $a_{{\mathcal{I}}^{\prime }}$(${\mathcal{I}}^{\prime }⊊\mathcal{I}$),按权重从高到低扫一遍,全部 $N$ 个多项式同时就位。三比特算例(${\mathcal{I}}_1=\{1\}$,即 $\vec{b}=100$):

$p_{100}=x_1(1+x_2)(1+x_3)=x_1+x_1{x}_2+x_1{x}_3+x_1{x}_2{x}_3,$

$m_1\oplus p_{110}\oplus p_{101}\oplus p_{111}=x_1\oplus (x_1{x}_2+x_1{x}_2{x}_3)\oplus (x_1{x}_3+x_1{x}_2{x}_3)\oplus x_1{x}_2{x}_3,$

右端 $x_1{x}_2{x}_3$ 出现三次、模 2 剩一次,逐项与左端一致。

推导二:资源账——T、比特、CNOT 的精确计数

Toffoli 账:$2^n-n-1$ 对

权重 0、1 的单项式不花 Toffoli:常数由 $X$ 门生成,字面量是地址变量本身。每个权重 $k\ge 2$ 的单项式由两个已算出的低权单项式($k_1+k_2=k$)经一个 Toffoli 相乘,权重 $k$ 的单项式共 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 个,故

${\mathcal{T}}_c^{of}={\sum }_{k=2}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)={\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)-n-1=2^n-n-1=N-{\log }_{2}N-1,$

这是 compute 半边;uncompute 逆放再花同样多。读出层另计 $N\ell$ 个 Toffoli(每单元每位一个)。账的科目也须注明:Toffoli 到 Clifford+T 有两条标准路线——逻辑 AND 门件(logical AND gadget,4 T、T-depth 2,成对使用时 uncompute 半边以测量完成、不花 T)与 7 T、T-depth 1、耗 4 辅助比特的分解——比较架构应以 Toffoli 计数为准、按所选实现换算 Mukhopadhyay 2025。

比特账:$N+\log N$ 起、至多 $2N+\log N$

$n$ 个地址比特加 $N$ 个选择子辅助比特,合计 $\mathcal{Q}=N+{\log }_{2}N$(存储阵列 $N\ell$ 另计);推导三的并行化另需辅助比特,上界 ${\max }_k{A}_k\le 2^n=N$,总计

${\mathcal{Q}}_{par}\le 2N+\log N.$

CNOT 账:$3^n-2^n$ 对——“以 Clifford 换非 Clifford”的价签

按标记,存在 $a_{\mathcal{I}}$ 里的单项式 $m_{\mathcal{I}}$(权重 $k=|\mathcal{I}|$)要异或进每个真子集辅助比特 $a_{{\mathcal{I}}^{\prime }}$(${\mathcal{I}}^{\prime }⊊\mathcal{I}$,由引理 2 与求和恒等式),共 $2^k-1$ 个靶;权重 $k$ 的单项式有 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 个;外加开局把 $n$ 个字面量复制进 $a_{\{i\}}$ 的 $n$ 条 CNOT:

$\mathcal{C}=n+{\sum }_{k=1}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)(2^k-1)=n+(3^n-1)-(2^n-1)=n+3^n-2^n,$

两个求和分别用 ${\sum }_k\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^k=(1+2{)}^n=3^n$ 与 ${\sum }_k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$。换个数法:单项式×多项式的出现次数合计 $3^n$(推导一),其中 $2^n$ 次”单项式已在自己家”无需连线,其余各连一条 CNOT——两种数法严格相等。

量级上 $\mathcal{C}\approx N^{{\log }_{2}3}=N^{1.585}\approx N^{1.6}$,是 Toffoli 账的 $(3/2{)}^n$ 倍:$n=10$ 时 $\mathcal{C}=58035$ 对 1013 对,比值约 57;$n=36$ 时 $\mathcal{C}\approx 1.50\times 10^{17}$ 对 $6.87\times 10^{10}$ 对,比值约 $2.2\times 10^6$。这就是该架构的核心交换:T 科目省下的深度,原样记进 Clifford 科目。轻重取决于口径:表面码里一控多靶 CNOT(multi-target CNOT)与单靶同价同时,执行时间口径下这笔账还会坍缩(推导五);NISQ 连通受限架构上多比特门却要先拆成 SWAP 链,CNOT 价签反而最先爆炸——论文自陈这是未解决的短板 Mukhopadhyay 2025。

顺序版(不引入额外辅助比特)的 Toffoli 深度按论文粗估为 $O((2^n-n-1)/{\log }_{2}N)$(式 12,每轮至多并行算出 $O(n)$ 个新单项式);下面的并行化把深度从指数级压到 $\log \log N$。

推导三:并行化——Toffoli 深度为何是 $\log \log N$

阶段倍增引理

引理(阶段倍增)。 若某阶段开始时权重 $\le 2^{s-1}$ 的单项式全部就位,则该阶段以 Toffoli 深度 1 算出全部权重 $\le 2^s$ 的单项式。

证明。 任取权重 $k\le 2^s$ 的目标:取 $k_1=\lfloor k/2\rfloor$、$k_2=\lceil k/2\rceil$,则 $k_1+k_2=k$、$k_1,k_2\le 2^{s-1}$,两因子已就位,一个 Toffoli 完成计算;不同目标的 Toffoli 靶不同,可全部并行。∎

从权重 1 起步,权重上限每阶段翻倍、$\lceil {\log }_{2}n\rceil$ 个阶段覆盖到 $n$,故

${\mathcal{T}}_{d,par}^{of}={\log }_{2}n={\log }_2{\log }_{2}N.$

注意 T-count 一个不省:每个权重 $\ge 2$ 的单项式仍只算一次,总账仍是 $2^n-n-1$;买深度的货币是辅助比特与 CNOT。

为什么要复制:层内源冲突

并行化的隐藏成本来自”每层每量子比特至多参与一个门”:同一源单项式在同一阶段要充当多个乘法的因子——$x_1{x}_2$ 同时是 $x_1{x}_2{x}_3$ 和 $x_1{x}_2{x}_4$ 的因子——控制端不能复用,必须先 CNOT 复制到空闲辅助比特再上 Toffoli。论文的逐阶段核算:权重至多 $k$ 的新单项式需要

$A_k=2\left(\right(\genfrac{}{}{0ex}{}{n}{k})+\cdots +(\genfrac{}{}{0ex}{}{n}{k/2+1}\left)\right)-\left(\right(\genfrac{}{}{0ex}{}{n}{k/2})+\cdots +(\genfrac{}{}{0ex}{}{n}{2})+2n)$

个额外辅助比特(一半存因子副本,差额补新目标),放缩得 ${\max }_k{A}_k\le 2^n=N$;复制 CNOT 每阶段至多 ${\max }_k{A}_k$ 对、全程至多 $2^n{\log }_{2}n=N\log \log N$ 对,

${\mathcal{C}}_{par}\in O(3^n-2^n+2^n{\log }_{2}n)\in O(N^{1.6}+N{\log }_2{\log }_{2}N).$

叠加 Toffoli 实现本身的深度(AND 门件每 Toffoli 占 T-depth 2,两半都计),整电路 T-depth 至多 $2{\log }_2{\log }_{2}N$(读出层另计,可再加 $N\ell$ 个辅助比特并行到 Toffoli 深度 1)。

直觉:乘法可重结合,路由树不可

并行 bucket-brigade 电路的 Toffoli 深度 ${\log }_{2}N$ 来源是刚性的:第 $k$ 层路由门的控制端是第 $k-1$ 层路由器的输出,依赖链长度就是树高 $n$——门级并行化只能把同一层的门横向排开,压不短链条。多项式编码绕开的正是这一点:选择函数被改写成单项式之和,而乘法满足结合律,$k$ 个字面量的连乘可任意重组为平衡乘法树,树高 ${\log }_{2}k$;全部单项式的乘法 DAG 深度因此是 ${\log }_{2}n$ 而非 $n$。代价是重组后的展开项数为 $3^n$ 量级(推导一),求和(CNOT)与存储(比特)都按此记账。一句话:$\log \log N$ 的 T 深度,是用 $N^{1.6}$ 的 Clifford 账与至多 $2N$ 的宽度买来的。

推导四:对比账——bucket-brigade 电路与 qLUT

与并行 BB 电路的三项比值

Di Matteo 等在同一表面码框架下核算的并行 bucket-brigade 电路族需 $N-2$ 对 compute–uncompute Toffoli、$2N+{\log }_{2}N$ 个逻辑比特、Toffoli 深度 ${\log }_{2}N$ Di Matteo 2020Mukhopadhyay 2025。三项比值(论文式 17–19):

${\mathcal{R}}_{T\text{-depth}}=\frac{{\log }_2{\log }_{2}N}{{\log }_{2}N},{\mathcal{R}}_{T\text{-count}}=\frac{N-{\log }_{2}N-1}{N}<1,{\mathcal{R}}_{\mathrm{qubits}}=\frac{2N}{2N}=1.$

以论文沿用的粗成本度量 ${\log }_2(\text{逻辑比特}\times \text{T-depth})$ 折算,改善量为

${\log }_2\frac{(2N+\log N)\cdot {\log }_{2}N}{(2N+\log N)\cdot {\log }_2{\log }_{2}N}={\log }_2\frac{{\log }_{2}N}{{\log }_2{\log }_{2}N},$

$n=36$ 时约 ${\log }_2(36/5.17)\approx 2.8$,即约 7 倍——推导五完整核算的实际改善(物理比特 3.6 倍、时间 5.1 倍)与此同量级。该比值随 $n$ 仅按 ${\log }_{2}n$ 增长:深度优势是真的,但增长缓慢。

qLUT_poly:把规模折半的拼接

把 $n=n_1+n_2$ 位地址对应的整数按位权拆开:

$N^{\prime }={\sum }_{j=0}^{n-1}{b}_j{2}^j=N_2^{\prime }+N_2{N}_1^{\prime },N_1=2^{n_1},N_2=2^{n_2}.$

qLUT_poly 用两个小 QRAM_poly 分两步选择:QRAM${}_{poly,n_1}$ 按高 $n_1$ 位选出一组 $N_2$ 个单元,内容复制进 $\ell N_2$ 个寄存器;QRAM${}_{poly,n_2}$ 按低 $n_2$ 位在副本中选出唯一者;最后 $\ell N_2$ 个 Toffoli 把奇偶性累加进输出总线。并行化后的账 Mukhopadhyay 2025:

$\text{Toffoli-count}=N_1+(\ell +1)N_2-n-2,\text{Toffoli-depth}=\max \{{\log }_2{n}_1,{\log }_2{n}_2\}+1,\text{辅助比特}=2(N_1+(\ell +1)N_2).$

拆分比 $n_1:n_2$ 本身可以优化:在约束 $N_1{N}_2=N$ 下极小化主项 $N_1+(\ell +1)N_2$,一阶条件给出 $N_1^{\ast }=\sqrt{(\ell +1)N}$、$N_2^{\ast }=\sqrt{N/(\ell +1)}$,最小值 $2\sqrt{(\ell +1)N}$——$\ell$ 为常数时即 $\Theta (\sqrt{N})$。对照前代 CSWAP 查表架构(T-count、T-depth、比特均 $O(\sqrt{N})$),T-depth 从 $O(2^{n/2})$ 层压到 $O(\log \log N)$ 层,论文称之为”双指数改进”:从 $N$ 到 $\log N$ 到 $\log \log N$,降两级指数。

但这条账要按 边界:qROM 电路 的守则读:T 账亚线性不代表总门数亚线性。复制步骤要 $\ell N_1{N}_2=\ell N$ 个 CNOT——线性底账原封不动躺在 Clifford 科目上,与 Jaques–Rattew 的 $\tilde{\Omega }(N)$ 总门数下界安然相容 Jaques & Rattew 2025。两个注脚:这 $\ell N$ 个 CNOT 可组织成 $N_1$ 个”一控 $N_2$ 靶”的多靶 CNOT,表面码执行时间只按 $N_1$ 个逻辑 CNOT 计,与 CSWAP 同价 Mukhopadhyay 2025;qLUT 属只读的 QROM 类构造,表一变就要重编译,而 QRAM_poly 主体读+写兼备、免重编译,对比时应分开对待。

推导五(表面码实例):$n=36$ 的完整核算

电路级方案的优势在容错成本算得清:论文以 $n=36$($N=2^{36}$ 个单元、$\ell =1$,恰 8 GB 经典数据)在表面码下走完全程 Mukhopadhyay 2025;参数取与 容错资源红线 相同的口径:态注入错误 $p_{in}=10^{-4}$、门错误 $p_g=10^{-5}$、码周期 $t_{sc}=200$ ns。

非 Clifford 层:计数与深度

按 AND 门件口径(每 Toffoli 4 T),compute–uncompute 成对计入:

$\mathcal{T}\le 4(2N-\log N-1)=5.4975\times 10^{11}(\text{恰为 }{2}^{39}\text{ 量级}),$

${\mathcal{T}}_d\le 2(\lceil {\log }_{2}n\rceil +1)=14(n=36:\lceil {\log }_{2}36\rceil =6).$

(AND 门件的 uncompute 半边本可用测量免 T,上式把两半都按 4 T 计,偏保守。)T-count 越大精度要求越高——由 union bound,单枚魔态(magic state)输出错误须

$p_{out}\le \frac{1}{\mathcal{T}}\approx 1.8\times 10^{-12}.$

精度如何变成宽度:蒸馏与工厂并行

$p_{out}$ 是指数小的,但由蒸馏(distillation)工厂确定性交付。按资源估计算法以 $p_{in}=10^{-4}$、$p_g=10^{-5}$ 定出两级蒸馏、码距 $d_1=10$、$d_2=5$:

第二层($d_2=5$)每逻辑比特 $2.5\times 1.25\times d_2^2\approx 79$ 物理比特,每枚魔态耗 $16\times 15=240$ 个逻辑比特,足迹 18750 物理比特、耗时 ${\sigma }_2=10d_2=50$ 个码周期;第一层($d_1=10$)每逻辑比特约 313 物理比特,16 个合计 5000、耗时 ${\sigma }_1=100$ 个码周期。两级串联共 $\sigma =150$ 个码周期;第一层足迹远小于第二层,可流水线化:

$\frac{150\times 18750}{100\times 5000+50\times 18750}\approx 2,$

即每 $\sigma \times t_{sc}=30\mu s$ 产出约 2 枚魔态。需求侧:每层 T 深度消耗 $\mathcal{T}/{\mathcal{T}}_d\approx 3.9\times 10^{10}$ 枚,须同层并行备齐——并行工厂数 $\frac{1}{2}\times 3.9\times 10^{10}$,蒸馏侧物理比特

$\frac{1}{2}\times 3.9\times 10^{10}\times 18750\approx 3.66\times 10^{14},$

每层 T 深度的耗时即一个工厂周期 30 μs,全程 $14\times 30\mu s=4.2\times 10^{-4}$ s。

Clifford 层与码距

表面码里一控多靶 CNOT 与单靶 CNOT 同价同时,记作一个逻辑 CNOT Mukhopadhyay 2025。于是推导二那笔 $3^n$ 量级的 CNOT 账在执行时间口径下坍缩:XOR 层每组同控 CNOT 合并为一个多靶 CNOT,只剩约 $2N$ 个;每个 Toffoli 按”2 CNOT + 2 多靶 CNOT + 1 H + 1 S”折算,论文对全电路逻辑 Clifford 总量给出上界

$7N=7\times 2^{36}=4.81\times 10^{11},$

从而每个逻辑 Clifford 的错误率须 $<1/(7N)\approx 2.08\times 10^{-12}$。码距取满足

$(\frac{p_{in}}{0.0125}{)}^{\frac{d+1}{2}}<2.08\times 10^{-12}$

的最小 $d$:代入 $p_{in}=10^{-4}$ 得比值 $0.008$,$d=9$ 时 $0.008^5\approx 3.3\times 10^{-11}$ 不达标,$d=11$ 时 $0.008^6\approx 2.6\times 10^{-13}$ 达标,故 $d=11$。数据与 Clifford 层的物理比特

$2\times 2^{36}\times 2.5\times 1.25\times 11^2\approx 5.20\times 10^{13}.$

总账与对照

$W_{phys}\approx 3.66\times 10^{14}+5.20\times 10^{13}\approx 4.18\times 10^{14},t\approx 4.2\times 10^{-4}\text{s/次读写}.$

同参数同法下,Di Matteo 等的 bucket-brigade 电路族为 $1.5\times 10^{15}$ 物理比特、$2.13\times 10^{-3}$ s Di Matteo 2020Mukhopadhyay 2025——QRAM_poly 把比特压到 $1/3.6$、时间压到 $1/5.1$。两案同属”天文数字”量级(对照 容错资源红线):红线没有被绕开,只是被推远三到四倍。

三元权衡的公式化

把上述核算收拢成”规模—精度—宽度”传递链(深度另有一条对价线):

$\underset{\text{规模}\to \text{T-count}}{\underbrace{\mathcal{T}(n)\approx 2^{n+3}}}⟹\underset{\text{T-count}\to \text{精度}}{\underbrace{p_{out}\le {\mathcal{T}}^{-1}\approx 2^{-n-3}}}⟹\underset{\text{精度}\to \text{宽度(工厂反馈)}}{\underbrace{W_{phys}\approx cd(n{)}^2\cdot 2N+\frac{1}{2}\frac{\mathcal{T}}{{\mathcal{T}}_d}{F}_{dist}}}.$

其中 $c=2.5\times 1.25$ 是每逻辑比特的表面码面积系数,$d(n)$ 随 $\mathcal{T}$ 对数增长,$F_{dist}=18750$ 是两级工厂足迹。三条读法:

• 精度要求仍是指数的($2^{-n-3}$),与器件路线并无二致,区别在兑现方式:器件路线要求物理门错误率本身随 $n$ 指数收紧(fanout 的 $\epsilon \le \delta /2N$、Grover 用法的 $\tilde{O}(2^{-n/2})$,见 成本口径:激活门、干预与能量;严格界见 Hann 2021 与 噪声韧性),电路路线把这份指数压力转交魔态工厂——确定性、可并行、成本可核算,代价是上式第二项:$n=36$ 时工厂占总宽度的 88%。
• 深度与宽度互为对价:并行化用至多 $N$ 个辅助比特、$N\log \log N$ 对 CNOT 把 Toffoli 深度从 $O(2^n/n)$ 压到 ${\log }_{2}n$;不付这笔钱,优势立即蒸发。
• 总门数无恙:Toffoli $\approx N$、CNOT $\approx N^{1.585}$,全程高于 $\tilde{\Omega }(N)$ 总门数下界 Jaques & Rattew 2025——T-depth 的指数改善不与下界冲突,因为下界数的是总量,不是深度。

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

把推导二、三的公式逐规模代入($\ell =1$;Toffoli 对 $=2^n-n-1$;CNOT 对 $=3^n-2^n+n$;并行 Toffoli 深度 $=\lceil {\log }_{2}n\rceil$;逻辑比特取并行上界 $2N+{\log }_{2}N$):

规模	$n$	$N=2^n$	Toffoli 对	CNOT 对	并行 Toffoli 深度	逻辑比特(上界)
1 Kbit	10	1024	1013	$5.80\times 10^4$	4	2058
1 Mbit	20	$1.05\times 10^6$	$1.05\times 10^6$	$3.49\times 10^9$	5	$2.10\times 10^6$
8 GB	36	$6.87\times 10^{10}$	$6.87\times 10^{10}$	$1.50\times 10^{17}$	6	$1.37\times 10^{11}$

• n=10:CNOT/Toffoli 比值已到 57——玩具规模上 Clifford 价签已清晰;而 Toffoli 深度只有 4 层,深度优势在小规模即兑现。
• n=20:比值约 3300;并行 Toffoli 深度 5 层对 BB 的 20 层,约 4 倍——与公式 ${\log }_{2}N/{\log }_2{\log }_{2}N=20/4.3\approx 4.6$ 一致。
• n=36:Clifford 账按门数是非 Clifford 账的 $2.2\times 10^6$ 倍,多靶 CNOT 折算后只剩 $7N\approx 4.8\times 10^{11}$ 个逻辑 Clifford(推导五)。
• qLUT_poly($n=36$、$\ell =1$、均分 $n_1=n_2=18$):Toffoli $=3\sqrt{N}-38=786394$、Toffoli 深度 $=\lceil {\log }_{2}18\rceil +1=6$、辅助比特 $=6\sqrt{N}\approx 1.57\times 10^6$;对照 CSWAP 的 $2^{18}$ 层,改善约 $4\times 10^4$ 倍。

三个规模合读:深度改善因子按 $\log N/\log \log N$ 缓慢爬升,Clifford 价签按 $(3/2{)}^n$ 指数膨胀——这项技术买的是容错深度,不是门数,能兑现多少取决于口径给 Clifford 打几折。

附带贡献:TOFFOLI-OPT-POLY 与相位标记 oracle

同一套编码可反哺电路综合:对”子集 $\mathcal{S}\subseteq \{0,1{\}}^n$ 内地址翻转目标比特”的一组多控制 NOT(MPMCT),TOFFOLI-OPT-POLY 的流程:写出每个 $\vec{b}\in \mathcal{S}$ 的编码多项式,取模 2 和

$p(x_1,\dots ,x_n)={⨁}_{\vec{b}\in \mathcal{S}}{p}_{\vec{b}}(x_1,\dots ,x_n),$

再把 $p$ 整理成线性因子乘积之和(ESOP,exclusive sum-of-products):每个线性因子用 CNOT 与 $X$ 门实现,每个乘积用一个 Toffoli Mukhopadhyay 2025。论文示例:$\mathcal{S}=\{000,001,011,111\}$,

$p=p_{000}\oplus p_{001}\oplus p_{011}\oplus p_{111}=1+x_1+x_2+x_1{x}_2+x_2{x}_3=1+x_1+x_2+x_2(x_1+x_3),$

逐项核对:常数只由 $p_{000}$ 贡献;$x_3$ 在 $p_{000},p_{001}$ 中各出现一次而抵消;$x_2{x}_3$ 出现三次剩一次;$x_1{x}_2{x}_3$ 出现四次全消。合成只需 1 个 CNOT(算 $x_1\oplus x_3$)加 1 个 Toffoli(乘 $x_2$)——对照 Di Matteo 等的 2 个 Toffoli、以及标准分解下每个 $C^{3}X$ 花 2 个 Toffoli(4 门共 8 个)的朴素做法。Grover 相位标记见机制回顾:编码多项式就位后以每个 $a_{\vec{b}}$ 控制对应存储单元的 CZ,即对被标记地址施加 $(-1{)}^{f(\vec{b})}$ 相位,读出层整个省去——QRAM 越快,容错 Grover 每次迭代越便宜 Mukhopadhyay 2025。

定位与边界

QRAM_poly 是门电路级的 QRAM 架构:把存储调用酉整体编译为 Clifford+T 电路。它与 qROM/qLUT 的区别在语义而非快慢:支持读+写、数据可更换而免重编译,在”可实现 $|x⟩|0⟩\to |x⟩|D_x⟩$ 且数据可动态更换”的意义上仍是 QRAM 架构而非伪 QRAM(三条判据见 边界:qROM 电路)。其渐近门数受 Jaques–Rattew 的 $\tilde{\Omega }(N)$ 下界约束 Jaques & Rattew 2025,本架构以 $N^{1.585}$ 的 CNOT 账安然满足;qLUT_poly 的 $O(\sqrt{N})$ T-count 则靠线性 Clifford 底账补齐(推导四)。

论文自陈的空白有三块,恰好都是器件路线的主战场 Mukhopadhyay 2025:其一,噪声韧性未分析——prefault-tolerant 区的 QRAM 噪声是活跃问题,电路路线把它推给 QEC 流水线,器件路线则有严格界与实验(见 噪声韧性);其二,2D 网格映射开销未研究——$3^n$ 量级的 CNOT 与至多 $2N$ 宽度如何在局域拓扑落布线是未解问题(布图与因果约束见 因果律极限);其三,NISQ 连通受限架构上多比特门更贵。对位而言,器件路线(见 桶队架构)押注相干器件把单查询压到 polylog 时间与 $O(\log N)$ 激活门,电路路线押注容错核算的确定性;同一谱系上的虚拟 QRAM(见 虚拟 QRAM 与系统架构)以 $O(M)$ 物理比特换更大虚拟地址空间并处理 2D 布图与非对称纠错——两者都未回答”无需纠错的高保真查询”这一器件级问题。

总之:QRAM_poly 把”电路式容错 QRAM”的账做到了当时最优——T-depth 指数改善、T-count 与比特不升、总账可精确核算——但 $4.18\times 10^{14}$ 物理比特换 $4.2\times 10^{-4}$ s 仍是天文数字;它改善的是红线的斜率,不是红线的存在(见 电路级优化 与 容错资源红线)。

延伸阅读

• 电路级优化
• 容错资源红线
• 边界:qROM 电路
• 桶队架构
• 虚拟 QRAM 与系统架构
• 成本口径:激活门、干预与能量
• 评价指标:六维打分卡
• 噪声韧性