算法的输入模型谱系

任何声称指数加速的量子算法都隐含一个输入模型——数据如何变成量子态;算法文献的假设从"行可计算的稀疏 oracle"一路升级为对 QRAM 器件的点名要求,这条谱系正是 QRAM 全部争论的起点。

起点:HHL 的抽象 oracle

HHL Harrow, Hassidim & Lloyd 2009 求解线性方程组 $Ax=b$,运行时间 $\tilde{O}(\log N\cdot s^2{\kappa }^2/ϵ)$。其对数据的假设完全是抽象的:$A$ 需为 $s$-稀疏且行可计算(efficiently row computable)——给定行标号,能在 $O(s)$ 时间内算出该行全部非零元;右端向量 $|b⟩$ 假设存在高效酉算子制备(例如 $b_i$ 及其前缀和均可高效计算时)。值得注意的是,原文通篇未出现”QRAM”一词;输出也只是 $|x⟩$ 上的观测量期望与样本,而非 $x$ 本身。这一输入模型对应结构化问题:模拟类问题的矩阵可以在线生成,不依赖外部存储。

机制回顾:oracle 的形式化与三种记账口径

行可计算的合同:一对 oracle

“$s$-稀疏且行可计算”在算法论文里落实为一对黑盒酉算子(本词条按 HHL 附录的访问模型整理):

$$O_{\mathrm{pos}}:|i⟩|\ell ⟩⟼|i⟩|\nu (i,\ell )⟩,O_{\mathrm{val}}:|i⟩|\ell ⟩|z⟩⟼|i⟩|\ell ⟩|z\oplus a_{i,\nu (i,\ell )}⟩,$$

其中承诺 $\nu (i,1),\dots ,\nu (i,s)$ 是第 $i$ 行至多 $s$ 个非零元的列标(不足处按自环补齐)。查询复杂度(query complexity)口径只数对这对 oracle 的调用次数,每次调用记 1,其余全部量子门免费。行可计算的实质是:这对 oracle 有 polylog $N$ 规模的一致电路族——例如离散化偏微分方程与局域哈密顿量的矩阵,其非零元位置与值由行标号的算术表达式直接生成。矩阵从不进存储器:数据是被计算的,不是被读取的。这一句区分是全词条的枢纽。

稀疏模拟由此把 $N$ 压进对数。以线性组合酉算子(linear combination of unitaries, LCU)框架为例(本词条整理):把 $A$ 拆成 $s$ 个”每行恰取一个非零元”的切片 $A={\sum }_{\ell =1}^s{A}_{\ell }$,每个切片由一对 $(O_{\mathrm{pos}},O_{\mathrm{val}})$ 查询按选择算子(select)方式实现;于是模拟时长 $t$ 的 $e^{-iAt}$ 只花 $O(s\cdot t)$ 次 oracle 查询、与 $N$ 无关。HHL 的相位估计(phase estimation)把精度折算成模拟时长,逐因子拼出 $\tilde{O}(\log N\cdot s^2{\kappa }^2/ϵ)$($s$ 的幂次视实现为 1–2,不影响下文):$\log N$ 因子全部来自稀疏模拟的地址宽度,指数加速在查询口径内是自洽的。

口径 Q:查询复杂度——“逻辑门免费”

形式化:算法是固定门与 oracle 调用的交替序列 $U_T\mathcal{O}{U}_{T-1}\cdots U_1\mathcal{O}{U}_0$,成本函数就是 $T$。HHL 摘要声明的”对最好经典算法 $\tilde{O}(N\sqrt{\kappa })$ 的指数改进”正是口径 Q 陈述——但要注意这是跨口径比较:经典一侧按时间记账,量子一侧按查询记账。这个比较合法,仅因为对行可计算的 $A$,量子算法每步的电路成本也确是 polylog $N$:数据可计算,三种口径在结构化输入上自动重合。口径 Q 里的”指数加速”是一份有隐含前提的合同,前提写进输入模型,不写在结论里。

口径 G:单位成本——“每查询一门”

单位成本口径把 oracle 当作电路模型里的一个初等门:成本 $=T+\Theta (1)\cdot T$。它与口径 Q 至多差常数——当且仅当 oracle 电路本身就是小的。数据是存储的表格时,这个前提不成立:查表 oracle 是经典查找表的 reversible 布尔电路,其成本就是电路口径的 QROM 账——unary iteration 遍历长度 $N$ 的表需 $4N-4$ 个 T 门 Babbush et al. 2018;Zhu–Sundaram–Low 把量子比特数、非 Clifford 门数与误差韧性之间的折中统一成参数化架构,至对数因子最优、只假设二维局域连通 Zhu, Sundaram & Low 2024;而下界一侧,一般态制备需 $2N-3$ 个门(递推构造与参数计数下界见 边界:态制备电路不是 QRAM)。于是单次查询的电路成本被钉死在

$$C_q^{(G)}=\Theta \left(\frac{N}{\mathrm{polylog}N}\right)⟹T_{\mathrm{tot}}^{(G)}=\Theta (N)+T\cdot C_q^{(G)}=\Theta (TN/\mathrm{polylog}),$$

任何 $T=\mathrm{polylog}$ 的算法总账被逐查询重付的装载项拉回线性;只有 $T=O(1)$ 的算法(周期查找一类)能摊薄。同一句”polylog 算法”,口径 Q 下是指数加速,口径 G 下是”与经典读一遍数据同阶”的常数竞速——结论漂移的第一个台阶。

口径 H:物理 QRAM——“查询即器件调用”

口径 H 把单次查询记为一次器件调用:GLM 的理想账目里,访问 $N$ 项的 QRAM 由 $2N$ 个量子开关的分支阵列构成,一次访存 $O({\log }_{2}N)$ 层、全部开关相干工作 GLM 2008 (PRL) GLM 2008 (PRA);单次调用的成本因而是深度 $C_q^{(H)}=O(\log N)$ 加上一份错误预算(每调用 $m=\Theta (n^2)$ 个可能出错的操作、$n={\log }_{2}N$,见 成本口径:激活门、干预与能量)。对同一张表查询 $Q$ 次,建造项只付一次:

$$T_{\mathrm{tot}}^{(H)}=\Theta (N)+Q\cdot O(\log N),Q^{\ast }\approx \frac{N}{\mathrm{polylog}N}$$

(临界查询数 $Q^{\ast }$ 的推导见 边界:态制备电路;摊销逻辑同源)。口径 H 恢复了 polylog 叙事——但复杂度结论现在自带硬件前提:$O(N)$ 个开关在一次访存内相干工作、错误率过判据、器件是 passive 的(passive 论证:每数一单元的主动 QRAM 本身就是能以 $O({\log }^{2}n)$ 步解 $Ax=b$ 的并行经典机,机会成本见 机会成本批判)。

三种口径,同一句话

把三口径并排,同一条”HHL 型算法 polylog”的漂移一目了然(本词条归纳):

口径	单查询成本	”polylog 算法”的总账	结论
Q 查询复杂度	免费(只数次数)	$O(\mathrm{polylog}N)$	指数加速(隐含”数据可计算”)
G 单位成本电路	$\Theta (N/\mathrm{polylog})$ 门	$\Theta (TN/\mathrm{polylog})$	装载主导,退化常数竞速
H 物理 QRAM	深度 $O(\log N)$+错误预算	$\Theta (N)+QO(\log N)$	polylog 成立,前提是器件存在且过噪声判据

漂移不是语义游戏:$N$ 在口径 Q 里只出现在 $\log N$,在口径 G 里以乘法身份回到分子,在口径 H 里以 $\Theta (N)$ 个物理开关的身份回到前提。算法文献的谱系——HHL 的抽象 oracle、qPCA 的器件点名、QML 综述的依赖表——正是逐级显性化这三个口径的过程。

升级:qPCA 把假设写成器件

qPCA Lloyd, Mohseni & Rebentrost 2014 第一次把输入假设落成器件形式,原文写道:“we have a quantum computer or quantum random access memory (qRAM) that takes $|i⟩|0⟩|0⟩\to |i⟩|a_i⟩|\Vert a_i\Vert ⟩$“——要求按列量子访问矩阵,直接返回列向量量子态及其范数;由此构造 ${\sum }_i\Vert a_i\Vert |e_i⟩|a_i⟩$,其第一个寄存器的约化密度矩阵恰为 $X=A^{†}A$。这已超出算法最常假设的 QRACM(量子地址-经典数据)形态,达到 QRAQM 级别(四分类见 分类学:四分类与主动/被动)。技术内核是密度矩阵指数化:$n$ 份 $\rho$ 经无穷小交换门实现 $e^{-i\rho t}$,对非稀疏低秩矩阵做相位估计;精度 $ϵ$ 需 $n=O(t^2/ϵ)$ 份拷贝,相位估计取 $t=O(1/ϵ)$ 时拷贝数升至 $O({ϵ}^{-3})$。

用三口径读 qPCA,器件点名的原因就清楚了:非稀疏特征矩阵没有行可计算的合同,口径 G 下每份 $\rho$ 拷贝都是一次 $\Theta (d)$ 门的态制备、$O({ϵ}^{-3})$ 份拷贝即 $\Theta ({ϵ}^{-3}d)$ 装载;要把装载项压回 polylog,只剩器件 QRAM 一条路——而且按列返回叠加态及范数的要求落在 QRAQM 档。qPCA 的”指数加速”因此不是口径 Q 的定理,而是口径 H 的有条件报价(总账的三模型拆解见 量子机器学习的 QRAM 依赖)。

Regev–Schiff 判据:错误 oracle 下哪些算法失效

三口径的差异在无错 oracle下只是记账习惯;一旦 oracle 带错误,查询次数本身变成器件指标——这是谱系上最硬的一步。

故障预言机模型与器件接口

Regev–Schiff(ICALP 2008;本站文献库未单列,按 Arunachalam et al. 2015 的转述口径)考虑故障预言机(faulty oracle):每次调用以概率 $1-p$ 正确执行相位翻转 $\hat{O}$,以概率 $p$ 什么都不做,

$$O_p(\rho )=(1-p)\hat{O}\rho {\hat{O}}^{†}+p\rho .$$

定理(Regev–Schiff):任何在 $p$-故障预言机上以 $9/10$ 成功率解决无结构搜索的算法,查询数满足 $T>\frac{p}{10(1-p)}N$——$p$ 为常数时下界 $\Omega (N)$,二次加速消失(三步证明骨架见 十八年时间线;本节不再重复,只推导判据侧的推论)。

器件侧到这个模型的接口是一行概率换算。设每次调用涉及 $m$ 个可能出错的器件操作、单门错误率 $\epsilon$,则调用级故障率

$$p=1-(1-\epsilon {)}^m\ge 1-e^{-m\epsilon }\ge \frac{m\epsilon }{2}(m\epsilon \le 1),$$

第一步用 $\ln (1-x)\le -x$($x\in [0,1]$),第二步:对 $x\in [0,1]$,交错级数 $e^{-x}=1-x+\frac{x^2}{2}-\frac{x^3}{6}+\cdots$ 各项模长递减,故截断于正项处得上界 $e^{-x}\le 1-x+\frac{x^2}{2}$,而 $x\le 1$ 给出 $\frac{x^2}{2}\le \frac{x}{2}$,即 $e^{-x}\le 1-\frac{x}{2}$。bucket-brigade 的 $m=\Theta (n^2)$(与 Hong 统计的 $n(n+5)/2$ 同量级),故 $p=\Omega (n^2\epsilon )$;通用噪声下 Hann 的严格界给单次查询不保真度 $1-F\le 4\epsilon D\log N$($D$ 为单次调用深度;推导见 噪声韧性),与 $p$ 扮演同一接口角色。

判据的两侧:下界与预算

必要侧(RS 下界的反解)。 定理说任何成功算法都有 $T>\frac{p}{10(1-p)}N$;反解 $p$,一个 $T$ 次查询的成功算法存在的必要条件是

$$\frac{p}{10(1-p)}N<T⟺p<\frac{10T}{N+10T}\approx \frac{10T}{N}(T\ll N).$$

充分侧(误差预算)。 对任意算法,若每次调用独立以概率 $p$ 故障,则 $Q$ 次调用中至少一次故障的概率按 union bound 不超过 $Qp$;要求算法成功率仍为 $1-\delta$,充分条件是

$$Qp\le \delta ⟺p\le \frac{\delta }{Q}.$$

Grover 专用版可做得更细(本词条推导,振幅涨落版):$T$ 次迭代中故障数 $K\sim \mathrm{Bin}(T,p)$,每次故障使总转角少转 $2\theta$($\sin \theta =1/\sqrt{N}$);末态转角偏离目标 $\pi /2$ 的标准差为 $2\theta \sqrt{Tp(1-p)}$,而成功要求偏离 $\lesssim \theta$,代入 $\theta \approx 2^{-n/2}$ 得 $Tp\lesssim O(1)$——与朴素 union bound 同标度、常数更松。

两侧对拼。 故障率必须同时落在两条线以下:

$$p^{\ast }(T)\sim \min \{\frac{\delta }{T},\frac{10T}{N}\},$$

预算线管”这趟算法还能不能跑成”,存在线管”这么快的算法压根有没有”。两线相交于 $T\sim \sqrt{\delta N/10}$:对无结构搜索,噪声分析独立复现了 $\Theta (\sqrt{N})$ 的查询最优性(与 BBBV 下界一致)——故障率判据与算法下界在阈值上互相咬合,这不是巧合,而是同一杠杆臂 $2^{-n/2}$ 从器件侧与算法侧各算了一遍。

两档算法的分流:多项式查询为何安然无恙

把 $m=\Theta (n^2)$ 与判据合并,单门错误率需求按查询次数分档(推导承上节;结论与 Arunachalam et al. 2015 一致):

• 多项式查询档($Q=n^c$:HHL 型矩阵求逆、qPCA 型 QML):$p\le \delta /Q$ 给 $\epsilon \lesssim \delta /(Qm)=\delta /n^{c+2}$——多项式衰减,GLM 的 $\epsilon \sim 1/n^2$ 口径在 $c\le$ 常数时兼容,纠错可能不需要 Arunachalam 2015。
• 平方根档($Q=\Theta (2^{n/2})$:Grover):存在线给出 $p\lesssim 2^{-n/2}$,合并 $m$ 得

$$\epsilon \lesssim \frac{2^{-n/2}}{n^2}\in o\left(2^{-n/2}\right);$$

数值:$n=30$ 得 $\epsilon \lesssim 2^{-15}/900\approx 3.4\times 10^{-8}$,$n=100$ 得 $2^{-50}/10^4\approx 8.9\times 10^{-20}$——对照 GLM 口径的 $10^{-3}$,差 11–16 个数量级。

• 超多项式档($Q$ 超多项式):Arunachalam 等猜想错误率须超多项式地小、纠错不可回避 Arunachalam 2015;一般噪声下的无条件账目由 Hann 界接管:$Q\cdot 4\epsilon D\log N\le \delta$。

判据的物理归属值得点明:分档变量是查询次数 $Q$,与路由架构无关——这正是它出现在本词条(算法假设)而非器件词条的原因;器件侧的模型细化(right/wrong/no-path)与纠错悖论见 噪声韧性之争。

oracle 假设审查清单

把前两节的推导折成四条可执行的审查项。任何”以量子访问为前提”的加速宣称,四条全过才算账目完整(清单结构为本词条归纳,各条推导见上文与所链词条)。

清单一:查询次数——多项式还是 $\sqrt{N}$

查询次数决定器件噪声档位:${\epsilon }^{\ast }(Q)=\delta /(Qm)$。$Q=O(1)$(周期查找)给 $\epsilon \sim 1/n^2$ 的 GLM 档;$Q=\mathrm{poly}(n)$ 给 $1/n^{c+2}$;$Q=\Theta (2^{n/2})$ 给 $2^{-n/2}/n^2$ 的纠错档。审查动作:从算法伪代码里数出对数据 oracle 的相干查询次数——注意每次重复统计(repetition)都把 $Q$ 乘一遍,交换测试类 subroutine 的 $O({ϵ}^{-2})$ 次重复由此翻倍入账(量子机器学习的 QRAM 依赖 的乘法结构一节)。

清单二:错误模型——随机故障还是相干转角

Regev–Schiff 模型与 union bound 预算都假设随机故障(混合酉型):故障是”oracle 缺席”,无偏置、可概率摊销。相干错误不适用这条账: systematic 转角误差按 $Q$ 线性相干累积、不按 $\sqrt{Q}$ 抵消,且 Hann 的一般 CPTP 界只保单次查询的多对数不保真度,跨查询累积仍按 union bound 走 Hann 2021。审查动作:确认噪声通道类型,把清单二的账写成 $Q\cdot (1-F_{\mathrm{call}})\le \delta$,$1-F_{\mathrm{call}}$ 取 $4\epsilon D\log N$(通用)或 $m\epsilon$(事件口径)。

清单三:数据可分性——可计算还是存储

这是三口径漂移的总开关。可计算数据(稀疏行可计算矩阵、log-concave 分布、可学习的生成分布):oracle 电路 polylog,三口径重合,QRAM 不被点名——期权定价流水线是正面样本:对数正态等 log-concave 分布闭式可积、任意分布用 qGAN 以多项式门数学习加载,IBM/JPMorgan 研究 Stamatopoulos et al. 2020 全文 0 次提及 QRAM。存储数据(特征表、预计算表):口径 G 装载主导,只剩器件 QRAM(口径 H)或经典采样数据结构两条路——后者是 Aaronson 2015 双向规则的下半句:可信的指数加速需要”存在极快制备某种叠加的方法”且”不存在用经典计算机快速制备类似分布的方法”;KP-tree 数据结构与 Tang 的量子启发经典算法把这条规则的判例钉死(Kerenidis & Prakash 2016 Tang 2019;机制见 去量子化)。审查动作:先问数据有没有小电路;再问同样访问能否由经典数据结构 polylog 提供——两问都过不了,加速宣称退回多项式档。

清单四:输出维度——$|x⟩$ 还是 $x$

HHL 的第四条 fine print:输出是 $|x⟩$ 上的观测量而非解向量本身;读出全解需 $O(N)$ 次重复,每次重复重跑整条算法栈(含全部装载),读出项 $k_{\mathrm{out}}\cdot T_{\mathrm{tot}}$ 直接把总账拉回线性 HHL Aaronson 2015。审查动作:写出输出量的维度 $d_{\mathrm{out}}$,总重复次数 $O(d_{\mathrm{out}}/{\delta }^2)$ 入账;指数宣称只有 $d_{\mathrm{out}}=O(1)$(或 polylog)时才完整。QML 表里恰有两行(最小二乘、量子 SVM)以小输出躲过此条,是”装载项与读出项两头都要小”的非巧合(量子机器学习的 QRAM 依赖)。

数值算例:三种口径下的总成本

取统一的对照场景:$N=2^{30}$ 的存储表($n=30$),单门错误率与器件参数取当前文献讨论的量级;全部数字为本词条按上文公式换算的示意估算。

算例 1:Grover 对存储表

查询次数一行几何给出:初始态与均匀叠加态在目标态平面内的夹角 $\theta$ 满足 $\sin \theta =2^{-15}=3.05\times 10^{-5}$,每次迭代转 $2\theta$,推到 $\pi /2$ 需

$$T\approx \frac{\pi /2-\theta }{2\theta }\approx \frac{\pi }{4}\sqrt{N}\approx 2.57\times 10^4$$

次 oracle 调用(经典逐项扫描 $N=1.07\times 10^9$ 次,口径 Q 的二次加速 $\approx 4\times 10^4$ 倍)。三口径入账:

• 口径 Q: oracle 免费,总成本 $\approx 2.6\times 10^4$ 步——二次加速成立。
• 口径 G: 每次查询按 unary iteration 付 $4N-4\approx 4.3\times 10^9$ 个 T 门 Babbush 2018,总账 $2.57\times 10^4\times 4.3\times 10^9\approx 1.1\times 10^{14}$ T 门——比经典逐项扫描多付约 $10^5$ 倍(恰好 $\approx 4\sqrt{N}$):逐查询重付的线性装载把二次加速打成二次倒退。
• 口径 H: 单次调用深度 $O(n)=30$,总深度 $\approx 7.7\times 10^5$ 层(扩散算子另加同阶),对经典 $1.07\times 10^9$ 次串行读出保持 $\sim 10^3$ 倍深度优势;硬件前提是 $2N\approx 2.1\times 10^9$ 个相干开关,错误预算按判据:预算线 $p\le \delta /T=0.1/2.57\times 10^4\approx 3.9\times 10^{-6}$,折单门 $\epsilon \lesssim p/n^2\approx 4.3\times 10^{-9}$;与存在线 $p\lesssim 2^{-15}$ 量级同域(常数差来自成功率参数)——正是 Arunachalam 2015 判据的 $10^{-8}$ 档。

算例 2:周期查找对存储表

函数 $f:\{0,\dots ,N-1\}\to \{0,\dots ,N-1\}$ 承诺有周期 $r\mid N$、各剩余类取值互异;取 $r=2^{29}$。量子周期查找教科书流程:制备 $\frac{1}{\sqrt{N}}{\sum }_x|x⟩|0⟩$,一次 oracle 调用得 $\frac{1}{\sqrt{N}}{\sum }_x|x⟩|f(x)⟩$,对第一寄存器做 QFT 读周期;单次成功概率 $\ge 4/{\pi }^2\approx 0.405$,常数次重复即可——查询次数 $Q=1$,oracle 后的 QFT 花 $O(n^2)\approx 10^3$ 个双比特门。经典侧按生日悖论(birthday paradox)找碰撞,需 $\Theta (\sqrt{r})=\Theta (\sqrt{N/2})\approx 2.3\times 10^4$ 次取值。三口径:

• 口径 Q: 1 次查询对 $2.3\times 10^4$ 次——“常数查询解周期”的教科书宣称。
• 口径 G: 一次付清的查表电路 $4N-4\approx 4.3\times 10^9$ T 门 + $10^3$ QFT,对经典 $2.3\times 10^4$ 次表读落后约 $2\times 10^5$ 倍——$Q=O(1)$ 摊不平一次性的 $\Theta (N)$ 电路。
• 口径 H: 调用深度 $30$ + QFT $10^3\approx 10^3$ 层,对经典约 $20$ 倍深度优势(渐近是 polylog 对 $2^{n/2}$ 的指数差距,但 $n=30$ 时 QFT 的 $n^2$ 常数把比分压薄——常数意识不可省);错误档位由判据给 $\epsilon \lesssim \delta /m\approx 10^{-4}$,$Q=1$ 不放大,GLM 档、免纠错可能。

算例 2 的对照面同样是教科书事实:Shor 分解里的周期查找作用在 $f(x)=a^x\mathrm{mod}M$ 上——模幂是可计算函数,oracle 电路 poly $(n)$,三口径结论一致,全程无需 QRAM。同一个”周期查找”原语,喂可计算数据则三口径稳如磐石,喂存储表则漂移全部重现:决定 QRAM 是否被点名的不是算法,是数据可分性(清单三)。

三口径总账表

算法(输入形态)	口径 Q	口径 G	口径 H	漂移判读
Grover(存储表)	$\frac{\pi }{4}\sqrt{N}$ 查询,二次加速	$\Theta (N^{3/2})$ T 门,倒退 $\sim 4\sqrt{N}$	深度 $\Theta (\sqrt{N}n)$,须 $\epsilon \sim 2^{-n/2}/n^2$	加速只在 H 成立且带噪声判据
周期查找(存储表)	1 次查询	$\Theta (N)$ T 门一次付清,输给 $\sqrt{r}$	深度 $\Theta (n^2)$,$\epsilon \sim 1/n^2$ 免纠错	$Q=O(1)$ 也救不了 G,但 H 代价温和
HHL(可计算稀疏 $A$)	polylog 查询,“指数”	oracle 电路 polylog,结论稳	无需 QRAM	三口径重合,宣称自洽
qPCA(存储特征表)	$(\log d{)}^2$ 查询	$\Theta ({ϵ}^{-3}d)$ 装载主导	需 QRAQM 级器件 + 拷贝账	从 Q 到 H 逐级加码
期权定价(可计算分布)	poly 查询	电路显式构造,结论稳	无需 QRAM	可计算数据免点名

四行的共同读法:漂移钉在输入形态上,不在算法名字上;HHL 与期权定价两行证明”量子算法无需 QRAM”与”量子算法点名 QRAM”可以同为真——取决于输入合同签在哪一栏。

讨论:口径各答一个问题

三种记账口径并不互相推翻,它们回答三个不同的问题:口径 Q 回答”量子控制流比经典强多少”(下界与算法论的母语,查询复杂度定理只能在此口径陈述);口径 G 回答”真电路多少钱”(诚实的会计口径,容错资源估算全在此入账);口径 H 回答”器件要付出什么”(硬件报价口径,噪声判据与机会成本在此结算)。指数加速宣称的失效,几乎总是跨口径走私:在 Q 里陈述定理、默认 G 或 H 的成本会自己消失。

谱系的走向因此可以一句话概括:HHL(2009)在口径 Q 里签了抽象合同;qPCA(2014)把合同条款写成器件规格;QML 综述(2017)用依赖表把全领域的签单状态公示,并附上四项基本问题的 fine print Biamonte et al. 2017;Regev–Schiff 与 Arunachalam 把合同里的”查询次数”一栏换算成器件错误率指标 Arunachalam 2015;Aaronson 立下”fine print 必须计价”的方法论判词 Aaronson 2015;Tang 则证明有些签单可以由经典数据结构以多项式差价履约 Tang 2019。正反论证的系统化清单见 Jaques–Rattew 综述 Jaques & Rattew;器件侧的工程答案(把装载算法绑定桶队硬件压进 $O({\log }^2(MN))$)见 架构感知数据加载,批判接力见 passive 论证 与 机会成本批判。

本词条的使用守则:读任何一条”指数加速”宣称,先问三件事——oracle 在哪个口径下免费、查询次数落在哪一档、数据是可计算还是存储;再过四条审查清单。三问四查之后,“需要 QRAM”与”不需要 QRAM”就不再是立场,而是可以逐项核算的账目。

延伸阅读

• 量子机器学习的 QRAM 依赖
• passive 论证
• QRAM 总览
• 分类学:四分类与主动/被动
• 去量子化
• 十八年时间线
• 噪声韧性之争
• 边界:态制备电路不是 QRAM