去量子化

去量子化(dequantization)指把依赖 QRAM 式量子数据访问的算法改造为使用同类经典数据结构采样技术的多项式时间经典算法——Tang 对推荐系统的处理是开山之作,也是 passive 论证的第一次大规模兑现。

机制回顾:量子推荐系统与它的经典镜像

KP-tree 与量子访问三原语

Kerenidis–Prakash Kerenidis & Prakash 2016 的量子推荐系统建立在专用数据结构上:矩阵 $M$($w$ 个非零元)存为 KP-tree,占用 $O(w{\log }^2(n^{\prime 2}))$ 经典空间、单元素更新 $O(\log (n^{\prime 2}))$($n^{\prime }$ 记较大维数,$n^{\prime 2}\sim mn$);量子访问 $U_M:|i⟩|0⟩\to \frac{1}{\Vert M_i\Vert }{\sum }_j{M}_{ij}|ij⟩$ 与范数查询均可在 $O(\mathrm{polylog}(n^{\prime }/ϵ))$ 时间内实现。这类”样本即访问”的数据结构后来被 Jaques–Rattew 归类为电路 QRACM 的 select–swap 一支:KP 式分页可把 T-cost 与深度都做到 $O(\sqrt{N})$(页大小 $2^{\ell }\approx \sqrt{N}$,可借用脏辅助比特)Jaques-Rattew。

把数据结构的接口拆开,量子算法实际能使用的只有三个原语:范数查询(输入行标 $i$,返回 $\Vert M_i\Vert$ 与全局量 $\Vert M{\Vert }_F$)、逐点查询(输入 $(i,j)$,返回 $M_{ij}$)、采样访问(输出按 $M_{ij}^2/\Vert M_i{\Vert }^2$ 分布的列标 $j$,或不加输入、按 $\Vert M_i{\Vert }^2/\Vert M{\Vert }_F^2$ 分布的行标 $i$)。采样一条并不神秘:对 $U_M$ 制备的态在计算基上测量,得到的经典输出分布恰好就是这两个 ${\ell }_2$ 采样分布。这个平凡观察是整条去量子化路线的种子:数据结构对量子算法的一切供氧,最终都以经典测量统计的形式被消费。

经典镜像:长度平方采样与游走树

KP-tree 本身就是经典数据结构(先于量子算法存在)。在行标上挂一棵二叉树,叶子存 $w_i=\Vert M_i{\Vert }^2$,内部节点存子树权重和,根即 $\Vert M{\Vert }_F^2$;每行内部再挂一棵以 $M_{ij}^2$ 为叶权的树(只挂非零元)。这套结构支持与量子侧逐条对应的三个经典原语:读累计和得范数、下走到叶子得逐点值、游走树采样(walk-tree sampling)——从根出发,每层按子树权重比例抽签选子节点,走到底即得一个样本。三者代价都是树高 $O(\log m)$ 或 $O(\log w)$,与量子原语同阶。Tang Tang 2019 的全部论证建立在这个逐条对应上:量子算法消费数据的每一条通道在经典侧都有同价镜像,指数分离无处可藏。

推导一:样本-查询对偶——游走树采样与量子访问等价

量子访问触碰数据的三条通道

任何以 $U_M$ 为输入接口的量子算法,与数据结构的信息交换只有三种:(α) 制备样本态(行分布 $\propto \Vert M_i{\Vert }^2$,或行内列分布 $\propto M_{ij}^2$);(β) 查询范数与矩阵元;(γ) 对制备好的态做酉演化与测量。(α)(β) 就是原语的量子实现,(γ) 不接触数据。故”量子访问”的全部增量,等价于”能以 $O(\mathrm{polylog})$ 代价产生上述分布与数值”——反面读法就是去量子化的纲领:若经典侧能以同价产生同样的分布与数值,量子访问作为资源可被完全替换(本词条推导,依据 Tang 的算法结构归纳)。

望远镜积:游走树采样的目标分布

设行树中节点 $v$ 的权重为 $W_v$(子树叶权之和),根权重 $W_{\varnothing }={\sum }_i\Vert M_i{\Vert }^2=\Vert M{\Vert }_F^2$;在节点 $v$ 处以 $W_{v,\text{左}}/(W_{v,\text{左}}+W_{v,\text{右}})$ 选左子。叶子 $i$ 的到达概率是路径各层抽签概率的乘积:

$$\mathrm{Pr}(\text{到达叶子 }i)=\prod _{v\in \mathrm{path}(i)}\frac{W_{\mathrm{child}(v)}}{W_v}=\frac{\Vert M_i{\Vert }^2}{\Vert M{\Vert }_F^2},$$

即望远镜积(telescoping product):每个内部节点的权重在相邻两级各出现一次(一次作分子、一次作分母),逐层相消后只剩”叶权/根权”。这正是量子侧测量样本态得到的行分布;行内列树同理给出 $M_{ij}^2/\Vert M_i{\Vert }^2$。代价:每层一次伯努利抽签,共树高 $\lceil {\log }_{2}m\rceil$ 层(本词条推导;与 Tang 2019 采用的 ${\ell }_2$-sampling 数据结构一致)。

量子侧的严格对应:沿同一棵树制备分支叠加,第 $\ell$ 层后的态为 ${\sum }_{\text{前缀 }p}\sqrt{\mathrm{Pr}(p)}|p⟩$——把随机游走”薛定谔化”;测量的经典输出分布与游走树采样逐比特相同,而制备只花 $O(\log m)$ 个受控旋转。量子性在这里没有创造任何经典采样造不出的分布,它只是以叠加方式同时走了所有路径。

原语对照:经典侧只强不弱

量子原语	量子实现代价	经典镜像	经典代价
行采样 $\propto \Vert M_i{\Vert }^2$	沿树受控旋转 + 测量	游走树下降	$O(\log m)$ 次抽签
列采样 $\propto M_{ij}^2$	测量 $U_M	i\rangle	0\rangle$ 输出
逐点查询 $M_{ij}$	$U_M$ 之逆 + 读出	下走到叶子	$O(\log w)$
范数查询 $\Vert M_i\Vert$	相位估计/SWAP 测试,${ϵ}^{-1}$ 开销	读叶子的累计和	$O(1)$

范数一行值得停一下:量子侧靠振幅估计把 $\Vert M_i\Vert$ 读到精度 $ϵ$,付出 $1/ϵ$;经典侧树里存着 $\Vert M_i{\Vert }^2$,直接读——经典镜像在范数原语上严格更便宜(本词条对照;与 Tang 2019 的原语清单一致)。对照表合读:给定”数据已在树里”前提,量子访问对经典样本-查询访问(sample-and-query access)没有任何分布或数值上的净增益。

数值算例:一个 $3\times 2$ 矩阵的全流程

取

$$M=\left(\begin{array}{cc}3& 0\\ 4& 0\\ 0& 1\end{array}\right),\Vert M_1\Vert =3,\Vert M_2\Vert =4,\Vert M_3\Vert =1,\Vert M{\Vert }_F^2=26.$$

行树:根权重 $26$,左节点(行 1、2)权重 $25$,右节点(行 3)权重 $1$。游走采样:第一步以 $25/26\approx 0.962$ 向左,第二步按 $9:16$ 分给行 1、行 2;合计 $\mathrm{Pr}(\text{行 }1)=25/26\times 9/25=9/26\approx 0.346$,$\mathrm{Pr}(\text{行 }2)=16/26\approx 0.615$,$\mathrm{Pr}(\text{行 }3)=1/26\approx 0.038$——两次抽签、望远镜积分给出目标分布。量子侧同一棵树:制备 $|\psi ⟩=\frac{1}{\sqrt{26}}(3|1⟩|10⟩+4|2⟩|10⟩+1|3⟩|01⟩)$(行向量已归一化),测量一次得到同一分布 $(9,16,1)/26$;但要 $c$ 个样本须重复制备 $c$ 次——与经典侧重复下降 $c$ 次同价。此矩阵行 1、2 共线,奇异值为 $5$ 与 $1$,右奇异向量 $(1,0)$、$(0,1)$,左奇异向量 $(3,4,0)/5$、$(0,0,1)$,推导二要用。

直觉

量子数据结构的”魔法”不在量子,而在树形累计结构本身:它把”按平方范数抽签”从 $O(m)$ 降为 $O(\log m)$,谁会走这棵树,谁就拿到全部访问能力。量子算法以叠加态走树,经典算法以伯努利抽签走树。两侧能从数据里拿到的东西(哪些分布、哪些数值、多便宜)逐条相等,任何只靠”访问数据”支撑的指数优势都必然是账目错觉——样本-查询对偶由此得名。

推导二:把相位估计换成子采样特征分解——Tang 算法的内核

样本态的约化密度矩阵

KP 量子算法的线性代数心脏是一个样本态。定义未归一行向量 $|M_i⟩⟩$(Hilbert 空间记号,与经典行向量同一对象),行样本态为

$$|A⟩=\frac{1}{\Vert M{\Vert }_F}\sum _i\Vert M_i\Vert |i⟩\widehat{|M_i⟩},\widehat{|M_i⟩}=\frac{|M_i⟩⟩}{\Vert M_i\Vert }.$$

对第一个寄存器(行标)求偏迹,特征空间寄存器上的约化密度矩阵为

$${\rho }_A=\frac{1}{\Vert M{\Vert }_F^2}\sum _{i,i^{\prime }}\Vert M_i\Vert \Vert M_{i^{\prime }}\Vert ⟨i^{\prime }|i⟩\widehat{|M_i⟩}⟨\widehat{M_{i^{\prime }}}|=\frac{1}{\Vert M{\Vert }_F^2}\sum _i|M_i⟩⟩⟨⟨M_i|=\frac{M^{\mathsf{T}}M}{\Vert M{\Vert }_F^2}=:G/\Vert M{\Vert }_F^2.$$

第二个等号用正交性 $⟨i^{\prime }|i⟩={\delta }_{i{i}^{\prime }}$ 杀掉全部跨行交叉项。${\rho }_A$ 的谱分解就是 $M$ 的 SVD 的平方版:特征向量是右奇异向量,特征值是 ${\sigma }_j^2/\Vert M{\Vert }_F^2$。这正是 qPCA 记录过的同一恒等式(对列约定为 $A^{†}A$,见 算法的输入模型谱系 引 Lloyd, Mohseni & Rebentrost 2014)。量子推荐系统的全部谱信息,装在一个”行采样分布”的二阶矩里——这是去量子化可行的结构性原因。

量子路线:密度矩阵指数化与相位估计

量子路线对 $n$ 份 $|A⟩$ 拷贝施加无穷小交换门,实现 $e^{-i{\rho }_{A}t}$,再相位估计,把态投影到 ${\sigma }_1,\dots ,{\sigma }_k$ 张成的右奇异子空间;递归交换网络深度随拷贝数指数增长,整体开销为 $\mathrm{poly}(k)\cdot \mathrm{polylog}(mn)$ 乘精度因子 Lloyd, Mohseni & Rebentrost 2014。该路线的输入假设已是 QRAQM 级(按列返回量子态及其范数),而对数据的接触仍不外乎”制备样本态 + 读范数”——推导一的结论在这里继续生效。

经典路线:重要性采样估计量与方差账

Tang 的经典替换从同一目标出发,但用显式重建代替相干投影。以概率 $p_i=\Vert M_i{\Vert }^2/\Vert M{\Vert }_F^2$ 采 $c$ 个行标 $i_1,\dots ,i_c$(游走树,推导一),构造 Gram 矩阵 $G=M^{\mathsf{T}}M$ 的重要性采样估计量

$$\hat{G}=\frac{1}{c}\sum _{\ell =1}^c\frac{|M_{i_{\ell }}⟩⟩⟨⟨M_{i_{\ell }}|}{p_{i_{\ell }}}.$$

无偏性逐项可查:$\mathbb{E}[\hat{G}]={\sum }_i{p}_i\cdot \frac{|M_i⟩⟩⟨⟨M_i|}{p_i}={\sum }_i|M_i⟩⟩⟨⟨M_i|=G$。方差账(本词条推导,教科书级):单样本估计量 $Z$ 的平方期望为

$$\mathbb{E}\mathrm{Tr}[Z^2]=\sum _i{p}_i\cdot \frac{\Vert M_i{\Vert }^4}{p_i^2}=\Vert M{\Vert }_F^2\sum _i\Vert M_i{\Vert }^2=\Vert M{\Vert }_F^4,$$

其中用到 $p_i\cdot \Vert M{\Vert }_F^2=\Vert M_i{\Vert }^2$。于是 $c$ 样本平均的 Hilbert–Schmidt 误差

$$\mathbb{E}\Vert \hat{G}-G{\Vert }_F^2=\frac{1}{c}(\Vert M{\Vert }_F^4-\Vert G{\Vert }_F^2)\le \frac{\Vert M{\Vert }_F^4}{c},$$

差项非负,因 $\Vert G{\Vert }_F^2={\sum }_j{\sigma }_j^4\le ({\sum }_j{\sigma }_j^2{)}^2=\Vert M{\Vert }_F^4$。相对方差 $\le 1/c$:${\ell }_2$ 平方采样把方差压到与维数 $m,n$ 无关——数据结构不仅便宜,而且统计上最优,这解释了去量子化为何不需要任何 $m$ 或 $n$ 的线性代价。

集中不等式与 Davis–Kahan

把估计量归一化 $Y_i=\frac{1}{p_i}\frac{|M_i⟩⟩⟨⟨M_i|}{\Vert M{\Vert }_F^2}$,则每个 $Y_i$ 幂等:$Y_i^2=Y_i$(用 $p_i=\Vert M_i{\Vert }^2/\Vert M{\Vert }_F^2$ 直接验证),故 ${\lambda }_{\max }(Y_i)=1$,矩阵 Chernoff 的取值区间宽度为常数,不随 $m,n$ 增长(本词条推导)。由此,$c=\tilde{O}({ϵ}^{-2})$ 量级的样本即可高概率保证算子范数意义下

$$\Vert \hat{G}-G\Vert \le ϵ\Vert M{\Vert }_F^2$$

成立(对数因子来自并集与秩参数,口径与 Tang 2019 的 $\mathrm{poly}(k,1/ϵ)\cdot \mathrm{polylog}(mn)$ 一致)。再由 Davis–Kahan 扰动定理:若谱隙 $\delta ={\sigma }_k^2-{\sigma }_{k+1}^2>0$,采样重建的顶-$k$ 特征子空间与真子空间的夹角满足

$$\Vert \sin \Theta ({\hat{U}}_k,U_k)\Vert \le \frac{\Vert \hat{G}-G\Vert }{\delta }\le \frac{ϵ\Vert M{\Vert }_F^2}{\delta }.$$

子空间误差 = 扰动误差/谱隙:量子相位估计是”相干地”做这件事,经典子采样是”显式重建后做特征分解”地做这件事,两者精度-代价曲线同形状。这就是 Tang 摘要里那句”输出秩 $k$ 逼近的 ${\ell }_2$ 范数采样,时间 $O(\mathrm{poly}(k)\log (mn))$,只比量子算法慢多项式因子”的来历 Tang 2019。

回归与拒绝采样:poly(k,1/ε) 的出处

完整算法还有两段,各贡献多项式因子(本词条推导,机制归属 Tang 2019):最小二乘回归——把用户向量对采样子空间做投影回归,回归子问题用同一套重要性采样压规模,条件数类参数(最小可接受奇异值/谱隙归一)以 $\mathrm{poly}(\kappa )$、精度以 $\mathrm{poly}(1/ϵ)$ 进入样本数;拒绝采样——量子侧用振幅放大把”采到好推荐”的概率平方根式抬升,经典侧只能拒绝重采、线性付出 $1/p$;只要接受概率 $p\ge 1/\mathrm{poly}(k,\kappa ,1/ϵ)$(定理条件保证),损失就停留在多项式——振幅放大的平方优势在这里只值多项式,不足以重开指数鸿沟。

合起来的输出保证(定理口径 Tang 2019):输出 $\tilde{u}$ 满足 $\Vert \tilde{u}-M_k(u)\Vert \le ϵ\Vert M{\Vert }_F$,其中 $M_k$ 是最佳秩 $k$ 逼近、$u$ 为目标用户行;总时间 $\mathrm{poly}(k,\kappa ,1/ϵ)\cdot \mathrm{polylog}(mn)$。

数值算例:顶-1 子空间的采样重建

沿用推导一的 $3\times 2$ 矩阵:$G=M^{\mathsf{T}}M=\left(\begin{array}{cc}25& 0\\ 0& 1\end{array}\right)$,谱隙 $\delta =24$。采样重建可精确对账:行 1 的样本贡献 $\frac{26}{9}|M_1⟩⟩⟨⟨M_1|=26\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right)$,行 2 的贡献 $\frac{26}{16}|M_2⟩⟩⟨⟨M_2|$ 与之完全相同(两行共线),行 3 贡献 $26\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right)$;故 $c$ 样本估计 $\hat{G}=26\frac{c_{12}}{c}\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right)+26\frac{c_3}{c}\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right)$ 随 $c\to \infty$($c_{12}/c\to 25/26$)精确收敛到 $G$。误差实现例:若扰动达 $\Vert \hat{G}-G\Vert =2.4$,则 $\Vert \sin \Theta \Vert \le 2.4/24=0.1$,顶特征向量偏离真方向不超过约 $5.7^{\circ }$;夹角压半须样本翻倍——$1/{ϵ}^2$ 标度的直接体感。链条每一环(望远镜积 → 二阶矩 → 方差 $1/c$ → Chernoff → Davis–Kahan)都可手工复核。

直觉

量子相位估计与经典子采样在做同一件事:从行分布的二阶矩里榨取顶谱。量子路线把二阶矩编码进密度矩阵、用相干演化读谱;经典路线把二阶矩用 $c$ 个样本显式重建、用数值代数读谱。当输入接口只是”能采样、能查值”时,两条路线的精度都由同两个参数控制:样本数(或拷贝数)与谱隙。量子性唯一占优的地方是把 $c$ 次采样的集中换成相干干涉的放大——那份优势按拒绝采样的账是平方级的,是多项式,不是指数。

推导三:多项式账——“指数”住在哪里

三栏账目与描述长度标尺

把推荐系统(及其同族低秩线性代数任务)的复杂度并排放下,记 $L={\log }_2(mn)$ 为问题实例描述长度的量级、$k$ 为秩参数、$\kappa$ 为条件数、$ϵ$ 为精度:

$$\begin{array}{rl}\text{全读经典(数据结构前)}:& T=\Theta (mn)=\Theta (2^L);\\ \text{量子(KP,需 QRAM/KP-tree)}:& T=\mathrm{poly}(k,\kappa ,1/ϵ)\cdot \mathrm{poly}(L);\\ \text{去量子化经典(Tang,需同一棵树)}:& T={\mathrm{poly}}^{\prime }(k,\kappa ,1/ϵ)\cdot \mathrm{poly}(L).\end{array}$$

第一行对 $L$ 是指数——经典推荐系统”运行时间线性于 $m$ 与 $n$“(Tang 2019 摘要原文);第二、三行对 $L$ 只有多项式。“指数加速”的全部指数部分都住在规模变量 $L$ 上,而推导一已证明样本-查询接口下量子与经典共享 $\mathrm{poly}(L)$ 因子,于是差距只能来自 $k,\kappa ,1/ϵ$ 上的次数差——分离被夹死在多项式格子里。这不是经验观察,是账目结构:三项里两项同形,指数分离在代数上无处落脚(本词条推导)。

κ 与 ε 的账:HHL 对照共轭梯度

线性方程组一侧的参数账同样只有多项式可争。HHL Harrow, Hassidim & Lloyd 2009 的口径为 $\tilde{O}(\log N\cdot s^2{\kappa }^2/ϵ)$($s$ 为稀疏度);经典共轭梯度迭代 $O(\sqrt{\kappa }\log (1/ϵ))$ 次、每次代价一次矩阵-向量乘。并排看:κ 上量子 ${\kappa }^2$ 对经典 $\sqrt{\kappa }$,精度上 $1/ϵ$ 对 $\log (1/ϵ)$——参数维度上经典迭代法并不吃亏甚至更优,HHL 的卖点从来只在 $N$ 维度(对数 vs 线性以上)。而 $N$ 维度的对数优势,在稠密低秩场景(机器学习数据的真实形态)恰被去量子化经典算法以 $\mathrm{poly}(k,\kappa ,1/ϵ)\cdot \mathrm{polylog}(N)$ 复制;在稀疏可计算场景(模拟类问题),输入本就是行可计算函数而非存储数据,QML 式”大数据指数加速”的叙事从前提上就不适用(见 算法的输入模型谱系)。两条路各走各的,哪条都剩不下指数。

数值算例:同一任务的三个数

取推荐系统规模 $m=n=10^8$、非零元 $w=10^{10}$、$k=10$、$ϵ=0.1$,描述长度 $L={\log }_2(mn)\approx 53.2$。按显式口径估算(本词条估算;量子行以 $\mathrm{poly}(k)=k^3$、经典行以推导二的采样账为准):全读经典 $mn=10^{16}$ 次基本操作量级;量子 KP 以 $k^3\cdot L\cdot {ϵ}^{-1}\approx 5.3\times 10^5$ 计,约 $10^{6\sim 7}$;Tang 行、列各采 $c=\tilde{O}(k{ϵ}^{-2}\log k)\approx 2.3\times 10^3$ 个样本,游走代价 $O(L)$ 计约 $1.2\times 10^5$,$c\times c$ 矩阵的稠密特征分解与回归 $c^3\approx 1.2\times 10^{10}$ 主导总账,合计约 $10^{10}$。

读法:$10^{10}$ 对 $10^{16}$——去量子化把”全读”打低六个数量级,这是 Tang 摘要中”在强输入假设下比以往经典系统指数快”的实际内容;$10^{10}$ 对 $10^{6\sim 7}$——量子与经典的差距约三四个数量级,来自 ${ϵ}^{-2}$ 采样因子与代数重建开销,是多项式差距,随精度参数收敛,与数据规模无关。指数分离塌缩为多项式差距,在这三个数里看得见摸得着。

直觉

“指数加速”在 QML 语境里从未指 $k$ 或 $\kappa$ 维度上的优势——那里只有多项式可谈;它指”对数于数据规模”这一形状本身。去量子化的破坏力在于证明:这个形状不是量子态的属性,而是数据结构的属性。谁被允许以 polylog 代价采样,谁就获得对数形状;量子算法拿到的树,经典算法同样拿得到。于是正确问法变成”哪种访问模型、哪些参数付钱”——这正是本词条与 机会成本批判 互为表里的地方。

推导四:对 HHL/qPCA 类主张的逐条清算

fine print 四条的去量子化读法

Aaronson 2015 的四条 fine print(详见 passive 论证;其脚注预言的”经典分布也能快速生成”与 Csanky 式并行求逆,在此兑现为具体算法),逐条用去量子化账本重读(本词条推导):

1. $|b⟩$ 装载。若 $b$ 是存储数据,样本-查询访问已把它交给经典侧:分布 $\propto b_i^2$ 由游走树给出、逐点值由查叶给出、范数由累计和给出——装载环节贡献零分离。若 $b$ 在线生成,两侧同付生成成本,同样零分离。
2. 稀疏性/结构假设。$s$-稀疏 + 行可计算是”函数型”输入,与存储无关;该场景的分离候选(HHL 对一般稠密迭代法)虽在去量子化射程之外,但也因此与 QRAM 无关。稠密存储数据要进量子算法必须走 QRAM/量子访问,而其低秩部分已被 poly$(k,\kappa ,1/ϵ)$·polylog 的经典算法覆盖。两句拼起来:凡是 QRAM 假设能帮上忙的地方,经典采样也帮得上。
3. 条件数 $\kappa$。两侧同为多项式(推导三),无指数可言。
4. 输出形式。HHL 只给 $|x⟩$ 的样本与期望,Tang 的输出同样是 ${\ell }_2$ 范数采样——读出瓶颈两侧同构,谁也不能把”输出全向量”的成本藏起来。

四条合读:前三条在输入模型层面折断指数主张,第四条两侧均摊——样本-查询接口下,QRAM 假设的 QML 指数加速没有一根柱子经得起重读。

qPCA 清算

qPCA Lloyd, Mohseni & Rebentrost 2014 的三步流水线(样本态制备 → 密度矩阵指数化 → 相位估计)在推导二里已逐条对上经典镜像:行采样 ↔ 制备 $|A⟩$,子采样 Gram 矩阵重建 ↔ ${\rho }_A$,显式特征分解 ↔ 相位估计。恒等式 ${\rho }_A=G/\Vert M{\Vert }_F^2$ 说明两侧读的是同一个矩阵的谱,Davis–Kahan 链条说明精度受同一个谱隙控制。qPCA 的 $O((\log d{)}^2)$ 宣称(以 QRAM 供氧为前提,见 量子机器学习的 QRAM 依赖)与经典账 $\mathrm{poly}(k,1/ϵ)\cdot \mathrm{polylog}(d)$ 同形状,差距仍在参数多项式格子里。Biamonte et al. 2017 依赖表中标 QRAM=Y 的指数加速条目,凡属”存储数据 + 低秩”型均适用本条清算;这也是综述自我批评(“装载可能需要指数时间,QRAM 或可解之但成本可能令人望而却步”)在算法层面的严格化:QRAM 不仅贵,而且就算免费,指数加速也多半不在了。

幸存者名单

清算之后还站着的(本词条归纳,总规则同 passive 论证):

• 行可计算的稀疏/结构化输入:模拟、电磁散射、Betti 数等——oracle 是函数不是存储,经典侧没有树可借,Aaronson 的正面案例仍属此类;
• 真量子数据(QRAQM):样本来自物理器件或实验,没有经典描述,游走树无从建起(读出语义见 查询语义:路由与读出 与 分类学:四分类与主动/被动);
• 多项式级真优势:振幅放大的平方根、$\kappa$ 或查询复杂度上的改进(量子行走类),不涉存储数据的指数主张;
• 低秩失效处的反向出局:$k\to N$ 时去量子化账目失控,但 QRAM 型量子算法同样要付稠密输入的代价——不是量子优势,是双方一起出局。

数值算例:三个规模的复杂度总表

下表把推导三的口径铺到三组参数上(本词条估算;量子行取 $k^3{\kappa }^2{ϵ}^{-1}L$、去量子化行取 $k^2{\kappa }^2{ϵ}^{-2}L+(k{ϵ}^{-2}\log k{)}^3$,代数步按稠密特征分解计;推荐行不含 $\kappa$;仅作量级示意):

任务参数	全读/稠密经典	量子(QRAM 假设)	去量子化经典	量子/经典差距
推荐 $m=n=10^8$,$k=10$,$ϵ=0.1$	$10^{16}$	$\sim 10^{6\sim 7}$	$\sim 10^{10}$	$\sim 10^{3\sim 4}$(多项式)
稠密低秩方程组 $N=2^{30}$,$k=20$,$\kappa =10^2$,$ϵ=0.1$	$\ge N^2=10^{18}$(读一遍)	$\sim 10^{10\sim 11}$	$\sim 10^{11\sim 12}$	$\sim 10$(多项式)
稀疏方程组 $N=2^{30}$,$s=10$,$\kappa =10^2$,$ϵ=10^{-2}$	CG $\sim 5\times 10^{11}$	HHL 口径 $\sim 3\times 10^9$	(行可计算,去量子化不适用)	$\sim 100$(多项式)

三行读法:第一行是 Tang 的主场——对规模指数级领先、对量子多项式落后,“塌缩”的定量形状;第二行是 QML 的主场——稠密存储数据上量子与去量子化经典同享 polylog$(N)$、差距缩到十倍级,而两者对”全读”都保持七八个数量级领先,是指数主张的墓碑;第二行同时暴露去量子化的软肋——精度收紧到 $ϵ=10^{-2}$ 时,样本数 $c=k{ϵ}^{-2}\log k\approx 6\times 10^5$,稠密代数步 $c^3\approx 2\times 10^{17}$ 几乎吃掉全部便宜:多项式因子不毁渐近,但常数真实存在,迭代代数是必要的补丁;第三行提醒边界——稀疏 + 行可计算场景没有存储数据结构,去量子化不适用,HHL 型多项式优势(对数于 $N$)依然成立,是幸存者名单第一类的数值注脚。

讨论:边界、合流与方法论

诚实的输入成本。比较的公平前提是”同一棵 KP-tree 已备好”——建树代价 $O(w{\log }^2(n^{\prime 2}))$ 两侧同付;量子算法从不把建树计入宣称的加速,去量子化也不必付。若数据只以一次性流或显式全表形式存在,连树都不该建,该任务是否需要”采样访问”型算法本身存疑。

三层合流。去量子化是三层批判中最温和的一层:算法层,样本-查询对偶封死指数分离;电路层,即便量子访问是真的,把它编译成电路受 $\tilde{\Omega }(N)$ 门数下界约束(见 边界:qROM 电路与 QROM 模型,Jaques-RattewBabbush 2018);器件层,active QRAM 的控制硬件构成并行经典机会成本,“廉价 QRAM 应视为不可行,除非被证明否则”(见 机会成本批判)。“QRAM 假设的指数加速”必须同时回答三问——访问是否可经典采样、量子访问电路多少门、器件是否 passive 且值得造;三层合砍,幸存主张只剩量子数据与结构化输入两类,与推导四名单一致。噪声侧约束见 评价指标:六维打分卡 与 一般噪声下的韧性。

方法论:输入模型三问。去量子化把 QML 论文的纪律改写成三个必答题:数据存在哪里(函数还是存储)?访问接口是什么(查值、采样、相干读出)?输出承诺是什么(样本、期望还是全向量)?三问之后,“指数加速”通常已自我了结。经典侧的产出也非全然负面:子采样谱算法本身是这次交叉的成果,张量交叉插值(tensor cross interpolation)等经典低秩技术把射程进一步扩到更一般的结构化数据。数据结构化 oracle 作为 QRAM 的替代路线,见 算法的输入模型谱系;正面的”以 QRAM 为前提”算法见 架构感知数据加载。

延伸阅读

• passive 论证
• 机会成本批判
• 算法的输入模型谱系
• 量子机器学习的 QRAM 依赖
• 边界:qROM 电路与 QROM 模型
• 查询语义:路由与读出