量子机器学习的 QRAM 依赖

量子机器学习是 QRAM 假设最密集的应用领域:Biamonte 综述的方法依赖表显示指数级加速几乎全部标注 QRAM=Y,而同一篇综述也承认,对大数据问题 QRAM 的成本可能令人望而却步。

方法×技术依赖表

Biamonte et al. 2017 在 Nature 的 QML 综述中给出一张”方法×技术”表,逐方法标注其加速依赖哪些技术。原表 8 行,技术列 4 个:振幅放大(AA)、HHL 型线性代数、绝热、QRAM;Y 表示该方法的加速依赖此技术,N 表示不依赖,optional 表示可用可不用,斜杠(如 Y/N)按变体而异:

方法(原表所引文献)	加速	AA	HHL	绝热	QRAM
贝叶斯推断(Low–Yoder–Chuang 2014;Wiebe–Granade 2015)	$O(\sqrt{N})$	Y	Y	N	N
在线感知机(Wiebe et al. 2016)	$O(\sqrt{N})$	Y	N	N	optional
最小二乘拟合(Wiebe–Braun–Lloyd 2012)	$O(\log \sqrt{N}{)}^{\ast }$	Y	Y	N	Y
经典玻尔兹曼机(Wiebe–Kapoor–Svore 2014)	$O(\sqrt{N})$	Y/N	optional/N	N/Y	optional
量子玻尔兹曼机(Amin et al. 2016;Kieferová–Wiebe 2016)	$O(\log N{)}^{\ast }$	optional/N	N	N/Y	N
qPCA(Lloyd–Mohseni–Rebentrost 2014)	$O(\log N{)}^{\ast }$	N	Y	N	optional
量子 SVM(Rebentrost–Mohseni–Lloyd 2014)	$O(\log \sqrt{N}{)}^{\ast }$	N	Y	N	Y
量子强化学习(Dunjko–Taylor–Briegel 2016)	$O(\sqrt{N})$	Y	N	N	N

表注三项全部出自原文:加速列以经典对应算法为参照,$O(\sqrt{N})$ 为二次加速、$O(\log N)$ 为指数加速($\log \sqrt{N}=\frac{1}{2}\log N$,同级);星号表示”能限制方法适用性的重要附注”,原文引向 Aaronson 2015 的 fine print 评论;QRAM=Y 意味着该方法的指数加速声明以 qRAM 的存在为前提。

规律清晰:$O(\log N)$ 级的指数加速几乎全部出现在 QRAM=Y 或 optional 行,且所有指数级行都带星号;线性代数类 QML 中,持久同调(persistent homology)是综述在正文里承认的唯一不依赖大规模 qRAM 的孤例——原文措辞:除组合优化类方法外,“唯一已知不依赖大规模 qRAM 的线性代数型 QML 算法”是数据拓扑分析(Lloyd–Garnerone–Zanardi 2016)。下文依次推导各行标注的来由、“指数加速”的乘法结构、去量子化冲击下的修订,并换算成三种数据访问模型下的数字总账。

逐行推导:每个标注从哪里来

最小二乘拟合与量子 SVM:QRAM=Y 的成本账

两个 QRAM=Y 行建在同一条 subroutine 栈上:内积估计 + HHL 型矩阵求逆 Harrow, Hassidim & Lloyd 2009。算清最底层的内积估计装载账,上层的标注就自动落位。

内积估计的交换测试(swap test)。 给定两份特征态拷贝 $|\psi ⟩$、$|\varphi ⟩$(数据向量振幅编码而来),加辅助比特置 $|+⟩=\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$,执行受控 SWAP 后总态为

$$|\Psi ⟩=\frac{1}{\sqrt{2}}(|0⟩|\psi ⟩|\varphi ⟩+|1⟩|\varphi ⟩|\psi ⟩).$$

在计算基上测量辅助比特。投影到 $|0⟩$ 的概率逐项展开:

$$P(0)=\frac{1}{4}\Vert |\psi ⟩|\varphi ⟩+|\varphi ⟩|\psi ⟩{\Vert }^2=\frac{1}{4}(1+1+2|⟨\psi |\varphi ⟩{|}^2)=\frac{1}{2}(1+|⟨\psi |\varphi ⟩{|}^2),$$

对称地 $P(1)=\frac{1}{2}(1-|⟨\psi |\varphi ⟩{|}^2)$,两者相减得 $P(0)-P(1)=|⟨\psi |\varphi ⟩{|}^2$:内积模方被编码进辅助比特的读出统计。要把 $|⟨\psi |\varphi ⟩{|}^2$ 估到加性误差 $ϵ$,二项采样需 $O({ϵ}^{-2})$ 次重复(置信 $1-\delta$ 时乘 $\ln \frac{1}{\delta }$;振幅放大可把 ${ϵ}^{-2}$ 二次压低为 ${ϵ}^{-1}$——AA 列的含义之一)。关键在下一步:每次重复消耗一份新的 $|\psi ⟩$、$|\varphi ⟩$ 拷贝——测量毁掉输入态,拷贝不可复用。于是”估计一次内积”的完整成本是

$$C_{\mathrm{ip}}(ϵ)=O({ϵ}^{-2})\times C_{\mathrm{load}},$$

乘法结构从 subroutine 栈的最底层就出现了(以上为本词条推导;装载项 $C_{\mathrm{load}}$ 不因振幅放大而减小)。

装载项是 Y 与 N 的分水岭。 振幅编码 $\frac{1}{\Vert x\Vert }{\sum }_j{x}_j|j⟩$ 的制备,若走一般态制备电路,门数 $2N-3$ 且每份拷贝从头编译(递推构造与参数计数下界的完整推导见 边界:态制备电路不是 QRAM);若走器件 QRAM,单次查询深度 $O(\log N)$。综述对量子 SVM 的数据来源原文口径是:“既可来自 qRAM 访问经典数据,也可来自制备量子态的量子子程序”——两条路都通,但指数加速只在 qRAM 一条路上成立:$C_{\mathrm{load}}=O(\log N)$ 时,内积栈加 HHL 栈把总时间维持 polylog;$C_{\mathrm{load}}=\Theta (N)$ 时,装载项立刻主导,总时间 $\Theta (N)+\mathrm{polylog}$,与”经典把训练集读一遍”同阶(§乘法结构的形式化)。综述把最小二乘拟合与量子 SVM 标 Y 而不标 optional,按的正是这个口径:已发表版本的指数声明以 qRAM 为前提。两行又同时躲过输出问题——输出是低维量(超平面参数、单点预测),不付 $O(N)$ 重复(§读出项);但低维输出仍要 $O({ϵ}^{-2})$ 次重复压统计误差,每次重复重跑整个算法栈(含全部装载),这笔账在 §数值算例 入账。

qPCA:optional 的两面

综述对 qPCA Lloyd, Mohseni & Rebentrost 2014 数据加载写出明确的器件口径:“用 qRAM 把向量映射为量子态……该操作需要 $O(d)$ 次运算,分摊到可并行执行的 $O(\log d)$ 步”;qPCA 整体复杂度 $O((\log d{)}^2)$,“在计算复杂度与查询复杂度两个口径下”。optional 恰好对应两个不同的 $C_{\mathrm{load}}$:

量子数据面(不需要 QRAM)。 qPCA 的输入是密度矩阵 $\rho$ 的多份拷贝,技术内核是密度矩阵指数化:配 $n$ 份拷贝、以无穷小交换门串实现 $e^{-i\rho t}$,再做相位估计读出特征对。当数据本来就是量子系统(样品态、信号态、处理器输出态)时,$\rho$ 拷贝由物理系统直接供给,装载成本为零——综述正是在此语境里说”量子数据”应用”不需要 QRAM 且有潜力带来指数加速”,并把”用 QML 分析量子数据”列为近期最有希望的方向。经典协方差 $C={\sum }_j{\vec{v}}_j{\vec{v}}_j^T$ 与 $\rho$ 谱结构相同(差迹因子),共用同一套本征分析。

经典数据面(需要 QRAM)。 数据是经典表格时,$\rho$ 的每份拷贝都要装载。两笔账:其一,样本账——把经验密度矩阵 $\hat{\rho }$ 与真 $\rho$ 的偏差压到 $ϵ$,按矩阵浓度不等式需 $k=O(d\log d/{ϵ}^2)$ 份随机样本(本词条估算;综述的叙述是”反复采样数据”);其二,算法账——密度矩阵指数化与相位估计本身按精度 $ϵ$ 消耗 $O({ϵ}^{-3})$ 份拷贝($n=O(t^2/ϵ)$ 份、$t=O(1/ϵ)$,此账目承 Oracle 假设谱系 对 QR048 的读法)。每份样本等于一次 qRAM 装载、深度 $O(\log d)$。于是经典数据面 qPCA 的深度总账为

$$T_{\mathrm{qPCA}}^{\mathrm{cl}}\approx O({ϵ}^{-3})\cdot O(\log d)+O((\log d{)}^2/ϵ),$$

两项都是 $d$ 的多项式——polylog 叙事只在”拷贝免费”的量子数据面成立(本词条推导)。optional 的两面由此得到精确定义:量子数据面不需要 QRAM,经典数据面离了 QRAM 退回多项式;依赖表把 qPCA 标 optional 而非 Y,是因为该算法的复杂度声明(查询复杂度口径)并不内在地需要 qRAM——需要的是”拿到 $\rho$ 拷贝”这个能力,而这个能力有两个来源。

在线感知机与玻尔兹曼机:Grover 层的 optional 与 N

在线感知机(Wiebe et al. 2016)。 感知机每轮要在训练集中搜一个误分类点:经典线性扫描 $O(N)$ 一次,Grover 式振幅放大 $O(\sqrt{N})$ 一次;对训练集的叠加寻址正是 QRACM 语义。二次加速是否兑现,取决于装载货币(本词条推导):设训练共发生 $M$ 次搜索,每次搜索需要一份新鲜的训练集叠加(振幅放大在读出后摧毁叠加)。电路装载下每次搜索先付 $\Theta (N)$ 门制备叠加:

$$T_{\mathrm{perc}}^{(B)}=M(\Theta (N)+\sqrt{N})=\Theta (MN),$$

与经典 $M$ 轮全扫的 $\Theta (MN)$ 打平——二次加速被装载项精确吃掉。器件装载下:

$$T_{\mathrm{perc}}^{(A)}=M(\mathrm{polylog}N+\sqrt{N})=\Theta (M\sqrt{N}\cdot \mathrm{polylog}),$$

二次优势完整兑现。QRAM=optional 的准确含义因此是:不造器件,加速打平;造了器件(或训练集天然有黑盒制备),加速成立。

玻尔兹曼机两行。 经典玻尔兹曼机行(综述引 Wiebe–Kapoor–Svore 2014 “Quantum deep learning”)标 optional:原文的说法是”对训练数据的量子访问(qRAM 或量子黑盒子程序)使机器以平方级更少的训练数据访问完成训练”——注意原文同时给了两个来源,与感知机行同构。AA/HHL/绝热列的斜杠(Y/N、optional/N、N/Y)反映训练路线的分歧:门型采样路线走振幅放大或线性代数,D-Wave 型退火路线本身是绝热处理器。量子玻尔兹曼机行标 QRAM=N:它训练的对象是量子系统的热统计与动力学,输入是量子数据(装置自己产生 $\rho$),同 qPCA 的量子数据面,装载项不存在;量子相干能把学习性能所需的样本数平方压低,这是模型内部的增益,与外部存储无关。

贝叶斯推断、量子强化学习与持久同调:三个 N 的来由

贝叶斯推断(Low–Yoder–Chuang 2014;Wiebe–Granade 2015)。 输入不是大数据表,而是贝叶斯网络本身——紧凑的条件概率表,可直接编译为量子线路;加速(推断所需样本数的平方改进)来自振幅放大与网络上量子行走。QRAM=N 的语义是”该方法的加速声明不按 QRAM 下注”:没有存储瓶颈,因为要装载的对象是电路而非数据表。HHL=Y 一格指其加速路线借相位估计型子程序。

量子强化学习(Dunjko–Taylor–Briegel 2016)。 projective simulation 代理的记忆是内部情景记忆(episodic memory),存在量子器件自身之中;每次决策是在代理自己的记忆网络上做相干演化,平方加速出现在决策时间上。没有外部数据库可装载,QRAM=N 是结构性的。

持久同调(Lloyd–Garnerone–Zanardi 2016)。 综述正文承认的孤例。数据在线生成:从 $O(n^2)$ 个两两距离出发构造单纯复形,叠加制备在 $\sim 2^n$ 个单纯形上,指数大的复形从头到尾不进任何存储器。Aaronson 2015 把它与 Clader 等的电磁散射 HHL 并列为正面教材,并从中提炼出总规则:可信的指数加速需要”存在极快制备某种特定叠加的方法”,且”不存在用经典计算机快速制备类似概率分布的方法”——后半句在 2019 年被 去量子化 兑现成了具体算法(§修订)。

指数加速的乘法结构

三项分解

把一切”输入态 + 相干子程序”型 QML 算法的总时间写开:

$$T_{\mathrm{tot}}=\underset{\text{装载项}}{\underbrace{k_{\mathrm{in}}{T}_{\mathrm{load}}}}+\underset{\text{算法项}}{\underbrace{Q{T}_{\mathrm{query}}}}+\underset{\text{读出项}}{\underbrace{k_{\mathrm{out}}{T}_{\mathrm{repl}}}},$$

其中 $k_{\mathrm{in}}$ 是输入态拷贝份数(交换测试、密度矩阵指数化都在逐份消耗拷贝),$Q$ 是对数据 oracle 的相干查询数,$k_{\mathrm{out}}$ 是读出统计的重复次数。“指数加速”指的只是中间项:$T_{\mathrm{query}}=O(\mathrm{polylog}N)$ 对经典 $\mathrm{poly}(N)$。表中全部星号,本质是承认第一、三项可能把总账拉回多项式——星号的原文指向 Aaronson 2015 的四条 fine print($|b⟩$ 装载、稀疏模拟、条件数、输出形态),恰好分别落在装载项、算法项前提(两条)、读出项上(本词条归纳)。

按三种数据访问模型代入装载项:

$$\begin{array}{rlrl}{T}_{\mathrm{load}}^{(A)}& =O(\mathrm{polylog}S)& & \text{(器件 QRAM,深度口径)},\\ T_{\mathrm{load}}^{(B)}& =\Theta (S)& & \text{(电路加载,每份拷贝重编译)},\\ T_{\mathrm{load}}^{(C)}& =O(\mathrm{polylog}S)& & \text{(经典采样数据结构,经典步)},\end{array}$$

其中 $S$ 为数据条数或振幅总数。模型 B 下总账塌缩:

$$T_{\mathrm{tot}}^{(B)}=\Theta (S)+O(\mathrm{polylog}S)=\Theta (S),\frac{T_{\mathrm{tot}}^{(B)}}{T_{\mathrm{cl}}}=\frac{\Theta (S)}{\Theta (S)}=\Theta (1),$$

即与”经典读一遍数据”只差常数——指数声明整体作废。模型 A 下总账 polylog,指数声明完整成立,但前提是硬件存在:$O(S)$ 个开关在一次访存中相干工作。模型 C 最微妙:装载同样是 polylog,却是经典步——同样的采样-查询能力经典算法也能用,指数分离塌缩为多项式差距(§修订)。

三种货币:深度、总操作、处理器

综述自己的器件口径就把两套货币并置了:”$O(d)$ 次运算,分摊到可并行执行的 $O(\log d)$ 步”——深度货币 $\log d$ 便宜,总操作货币 $O(d)$ 照贵。以 qPCA 为例把三套货币各入一次账(本词条推导):

• 深度货币(并行硬件,依赖表隐含的默认口径):装载 $O(\log d)$ + 算法 $O((\log d{)}^2)$ → polylog,指数领先;
• 总操作货币(串行门数):每份拷贝 $O(d)$ 次操作、$k$ 份拷贝 → $O(kd)$,对经典 $O(d^2)$ 只剩线性对二次的多项式领先;
• 处理器货币(Aaronson 2015 脚注):深度口径隐含 $O(d)$ 个开关同时工作;若把这批并行单元还给经典,Csanky 型并行经典求逆以 $O({\log }^{2}d)$ 步完成——深度差距也被抹平。这就是 passive 论证 的原始形式:QRAM 必须 passive,否则量子加速的深度账被硬件自己的经典并行能力吞掉。

三个指数级行(最小二乘、qPCA、量子 SVM)的指数声明,全部依赖”深度货币 + 并行 qRAM 器件”的合取;缺一个,分别退化为总操作货币下的多项式领先(缺并行硬件)或处理器货币下的无领先(缺 passive 性)。星号正是这份合取的显式标注。

读出项:为什么恰好两行躲过输出问题

HHL 的第一条 caveat:从 $|x⟩$ 读出全部解向量需 $O(N)$ 次重复——读出项按输出维度放大,$k_{\mathrm{out}}=O(N)$ 时总账回到 $O(N)$ 级,算法项的 polylog 无从谈起。综述原文把例外挑明:“除最小二乘拟合与量子 SVM 这两个显著的例外,线性代数类算法都可能苦于输出问题”。依赖表因此藏着一个非巧合:QRAM=Y 的两行恰好也是输出维度最小的两行。装载项与读出项两头都要小,指数声明才完整;任何新宣称指数加速的”量子核方法”行,都应先报这两个头(本词条归纳)。

噪声侧写:多项式查询次数是器件的护身符

依赖表还隐含器件噪声要求。Arunachalam et al. 2015 证明:桶队 QRAM 用作 Grover 预言机($\sqrt{N}$ 次查询)时,单门错误率须 $o(2^{-n/2})$;而”矩阵求逆或量子机器学习这类只需多项式次查询的算法,错误率只须多项式小,量子纠错可能不需要”——其摘要点名的两个对象正是 HHL 与量子 SVM,即表中两个 QRAM=Y 行。依赖表的星号行全是多项式查询算法,恰好落在 QRAM 器件最宽容的噪声区间;反之,依赖表若有一行的加速来自 $\sqrt{N}$ 次查询(感知机这类 Grover 层方法把器件当预言机用),器件侧的误差要求就指数地严苛。查询次数的多项式性由此成为连接依赖表与器件物理的第三根轴(推导见 噪声韧性 与 噪声韧性之争)。

去量子化冲击下的依赖表修订

表外最强行的塌缩

依赖表定稿(2017)时,表外还有一个更强的候选:Kerenidis–Prakash 量子推荐系统 Kerenidis & Prakash 2016。$m\times n$ 偏好矩阵、假设存在好的 rank-$k$ 近似;矩阵存为 KP-tree 数据结构,由此量子访问 $U_M:|i⟩|0⟩\to \frac{1}{\Vert M_i\Vert }{\sum }_j{M}_{ij}|ij⟩$ 与范数查询均以 $O(\mathrm{polylog})$ 实现。按依赖表口径,这一行应标 QRAM=Y、指数加速、带星号——它被广泛视为”可证明指数加速”的最强候选。2019 年 Tang Tang 2019 证明:基于同一数据结构支持的 ${\ell }^2$-范数采样操作,经典算法以 $O(\mathrm{poly}(k)\log (mn))$ 时间输出 rank-$k$ 近似的 ${\ell }^2$ 采样,“仅比量子算法慢多项式因子”。指数分离塌缩为多项式差距(机制细节见 去量子化)。

修订的三条原则

塌缩的直接教训是:QRAM 列的 Y 不再自动兑换速度列的”指数”。本词条把修订归纳为三条(本词条归纳):

1. 拆分数据访问列。 “QRAM=Y” 实际是两件事的合取:算法需要相干查询语义(见 分类学:四分类与主动/被动),且该语义只有 QRAM 器件能以 polylog 成本提供。修订表必须追问第三个问题:同样的”采样-查询访问”,经典数据结构(KP-tree/Tang 型)能否也以 polylog 提供?能,则指数优势作废,量子版只剩多项式领先(常数与硬件开销另算)。要害在于:许多”QRAM 假设”算法的优势来自数据结构允许的乘法采样访问,而这种访问能力经典采样可以复用。
2. 速度列先过星号再发表。 星号指向的 fine print 逐条过账后,“指数”往往降级:装载项 $\Theta (S)$ 时对经典只剩常数竞速(§三项分解的模型 B);读出项 $O(N)$ 时总账回到线性;并行硬件与 passive 性不成立时深度货币不通用(§三种货币)。
3. 新增输出维度列与查询次数列。 输出维度是 $O(N)$ 还是 $O(1)$ 决定读出项是否吞掉算法项;查询次数是 $\mathrm{poly}$ 还是 $\sqrt{N}$ 决定器件噪声档位(§噪声侧写)。老两行(Y 行)在这两列上恰是”小输出 + 多项式查询”的最优组合;新行应先报这两列再谈速度。

修订后的判读示例:推荐系统行——QRAM=Y(KP-tree),速度列由”指数(带星号)“改写为”多项式领先(Tang)“;qPCA 行——量子数据面保留,经典数据面的指数叙事因经典采样复用而降级。依赖表之外的第三条路是换任务形态让数据天然有电路:量子金融的振幅估计流水线把装载电路当显式对象逐门构造,log-concave 分布闭式可积、qGAN 学习任意分布,全程无 QRAM(Stamatopoulos et al. 2020;见 Oracle 假设谱系)。

数值算例:三种数据访问模型下的总复杂度

设三种数据访问模型(本词条口径,$S$ 为数据条数/振幅总数):

模型	单份输入态/单次查询成本	硬件前提
A 器件 QRACM	深度 $O(\log S)$($O(S)$ 总操作由 $2S$ 开关并行吸收)	GLM 型 $2S$ 开关阵列,一次访存相干工作
B 电路加载	$\Theta (S)$ 门(一般振幅下界 $2S-3$),每份拷贝重编译	无(门即全部代价)
C 经典采样数据结构	$O(\mathrm{polylog}S)$ 经典步	经典内存 + KP-tree 型结构

算例 1(qPCA,$d=2^{20}$ 维特征,$ϵ=0.1$)。 经典 PCA 为 $O(d^2)\approx 1.1\times 10^{12}$ 次运算。模型 A:装载 $k=O({ϵ}^{-3})=10^3$ 份拷贝、每份深度 $O({\log }_{2}d)=20$ 层,算法项 $O((\log d{)}^2/ϵ)\approx 4\times 10^3$,深度总账 $\approx 2.4\times 10^4$ 步;换总操作货币:$10^3\times 2^{20}\approx 1.0\times 10^9$ 次操作——比经典少三个数量级,但这是线性对二次的多项式领先,不是指数。模型 B:$k$ 份拷贝各 $\Theta (d)=1.0\times 10^6$ 门,合计 $10^9$ 门,外加同量级的经典角度编译账——对经典仍是多项式竞速。“指数叙事”(数百步对 $10^{12}$)只在模型 A 的深度货币下成立。

算例 2(量子 SVM,$N=2^{20}$ 训练点、$d=2^{10}$ 维、$ϵ=0.1$)。 内积估计的拷贝账为 $O({ϵ}^{-2})=100$ 份(§交换测试)。模型 A:polylog 算法项 + $100$ 份 $\times$ $O({\log }_{2}Nd)\approx 30$ 层装载,合计数千步量级(本词条示意估算);经典核化 SVM 的主导项是核矩阵构建 $O(N^{2}d)$。模型 B:把 $N$ 个 $d$ 维训练向量逐份制备并逐对估内积,装载主导项 $\Theta (Nd)=2^{30}\approx 1.1\times 10^9$ 门再乘拷贝因子——不低于经典把数据读一遍,优势消失。恢复优势靠提高对同一张表的查询复用率——QRAM 器件”一次建造、多次查询”的摊销逻辑,临界查询数 $Q^{\ast }\approx S/\mathrm{polylog}S$(摊销推导见 边界:态制备电路)。

算例 3(推荐系统,$m=2^{20}$ 用户、$n=2^{14}$ 商品,$S=mn=2^{34}\approx 1.7\times 10^{10}$,$k=10$,$\kappa =10$)。 模型 A:KP 算法 $\mathrm{poly}(k,\kappa )\cdot \mathrm{polylog}(mn)$;示意取 $\mathrm{poly}(k,\kappa )\sim 10^5$(本词条示意估算,${\log }_2(mn)=34$),得 $\sim 3\times 10^6$ 步级;朴素经典 $O(Sk)\approx 1.7\times 10^{11}$——表面分离约 $5\times 10^4$ 倍。模型 B:整矩阵振幅编码 $\Theta (S)=1.7\times 10^{10}$ 门,装载项已超经典读一遍数据,无优势。模型 C:Tang 算法 $O(\mathrm{poly}(k)\log (mn))$,示意 $10^{3-5}\times 34\approx 10^{5-7}$ 经典步——与模型 A 仅差多项式因子,指数优势塌缩。同时模型 A 的硬件账必须入册:$2S\approx 3.4\times 10^{10}$ 个相干开关;按 机会成本批判 的能量口径,这一规模的相干存储与访问正是综述”成本可能令人望而却步”一句的物理内容(成本口径 有逐项货币辨析)。

三例的共同读法:依赖表的 QRAM 列只控制算法项的货币;把装载项与读出项按同一货币入账后,三行总复杂度分别是——模型 A:polylog 对 poly(成立,但带并行硬件前提);模型 B:常数竞速(不成立);模型 C:多项式领先(塌缩)。“QML 是否需要 QRAM”的正确问法因此不是”哪行标 Y”,而是”总账在哪列货币下入账”。

自我批评:四项问题与器件口径

综述的总体承认更为直白:先把大量数据装载进量子系统本身可能需要指数时间,“原则上可用 qRAM 解决,但对大数据问题这样做的成本可能令人望而却步”——原文脚注把这句引向 Arunachalam et al. 2015 的桶队鲁棒性分析;器件方面,“原理性演示已有,但构建大规模量子开关阵列是一个困难的技术问题”。器件侧描述沿用 GLM 的理想化设定:访问 $N$ 项数据的 qRAM 由 $2N$ 个量子开关组成的分支阵列构成,必须在一次访存中相干地工作,耗时 $O({\log }_{2}N)$,每开关可容忍最高 $O(1/{\log }_{2}N)$ 的错误率。HHL 的四条 caveat 中也有同款表述:“输入向量 $|b⟩$ 需要制备,或在量子计算机上、或用 qRAM,而这可能昂贵” HHL;成本侧,综述还引了具体资源核算——某个 HHL 实现方案的电路规模膨胀至 $\sim 10^{25}$ 量级。

综述收尾把这批 caveat 收拢为四个基本问题:输入问题(读入数据的代价可主导总账)、输出问题(完整解向量需指数多比特)、成本问题(真实门数鲜有精细核算)、基准问题(与现代启发式经典方法系统性对标缺失)。这份自我批评点到为止——没有量化 prohibitive 到什么程度,$2N$ 开关与 $O(1/\log N)$ 容差的表述也未讨论几乎同期的 passive 论证 与 机会成本批判 所指的主动干预、路径独立性问题。四个问题在后来数年分别长成:输入问题定理化为 passive 论证、算法面兑现为 去量子化、成本问题沉淀为 成本口径 的记账纪律、基准问题清单化为 评价指标:六维打分卡。

判读与边界

依赖表的价值在于把隐性假设显性化:一篇 QML 论文标 QRAM=Y,即意味着整套 桶队架构式的硬件前提连同其成本口径一并成立。批判接力见 passive 论证(2015)与 去量子化(2019);假设谱系的两端——稀疏 oracle 与量子访问——见 算法的输入模型谱系;“以 QRAM 为前提”的正向设计(把装载算法绑定桶队硬件压进 $O({\log }^2(MN))$)见 架构感知数据加载。

本词条的使用守则:表是 2017 年的快照,读它先过三道账——装载货币(模型 A/B/C 之下总账完全不同)、查询次数的多项式性(决定器件噪声档位)、输出维度(决定读出项是否吞掉算法项)。三道账过完,Y 行的指数声明才完整成立;optional 行要再问数据来源是量子还是经典;N 行则应追问加速的真正来源——电路编译(贝叶斯)、内部记忆(强化学习)、在线生成(持久同调),三条路都不需要 QRAM,也不应被读成”无需 QRAM 的指数加速”。

延伸阅读

• 算法的输入模型谱系
• passive 论证
• 去量子化
• 机会成本批判
• 边界:态制备电路不是 QRAM
• 分类学:四分类与主动/被动
• 架构感知数据加载