量子机器学习算法谱系

“量子机器学习”（quantum machine learning, QML）不是一个单一算法，而是一整片算法谱系（zoo）。粗略地说，它至少包含三类本质不同的任务：

1. 用量子计算机处理经典数据：训练集是一张普通的经典表格（CSV、图像像素、用户评分矩阵），我们把它装进量子态，再运行量子线性代数、量子核方法或 Grover 型搜索；
2. 学习量子态产生的数据：样本本身就是未知量子态 ${\rho }_x$（例如某个量子实验的输出），任务是对它们分类、回归或提取特征；
3. 用经典优化器训练参数化量子电路：模型是一个含参数 $\theta$ 的量子电路，量子计算机只负责估计 loss 与 gradient，参数更新由经典优化器完成（VQE、QAOA、量子神经网络都属于这一类）。

三类任务使用的资源模型、加速来源和瓶颈完全不同，把它们混为一谈是 QML 文献中最常见的混淆来源。本词条的目的不是罗列算法，而是给出一套统一的审计框架：判断任何一项 QML 加速声称时，必须把数据装载、oracle 构造、条件数、测量次数和经典输出全部计入端到端成本。我们会看到，许多早期文献中的“指数加速”在补全这笔账之后退化为多项式加速，甚至消失；但在明确的模型假设下，真实的优势依然存在。

行文组织如下：第 1 节先把“数据如何进入量子计算机”这件最容易被跳过的事写清楚；第 2–7 节按谱系逐一讨论线性代数型学习、量子核方法、variational 模型、搜索与组合学习、拓扑数据分析、量子数据学习；第 8 节给出可直接套用的审计清单；第 9 节是小结与习题。

读者应已熟悉的 Grover 算法、振幅放大、HHL 算法 与 QSVT；本词条会直接引用这些子程序的结论而不再重新推导。

1. 先写清计算模型

在讨论任何复杂度之前，必须先回答一个问题：**算法以什么方式访问训练数据？**同一个算法在不同的数据访问模型下，复杂度结论可以天差地别——这正是大量“指数加速”争议的发源地。

设训练集为矩阵 $X\in {\mathbb{R}}^{m\times d}$，其中 $m$ 是样本数、$d$ 是特征维数，$X$ 的第 $i$ 行 $x_i\in {\mathbb{R}}^d$ 是第 $i$ 个样本。常见的访问模型从弱到强依次为：

1. **显式访问（explicit access）：**可以逐项读写 $X_{ij}$，就像普通经典程序读数组一样。这是最诚实的模型，但也意味着“把数据完整读一遍”本身已需 $\Omega (md)$ 次操作——$m\times d$ 个元素每个至少看一次。在这个模型下，任何 $\mathrm{polylog}(md)$ 的声称都只能是自欺欺人，因为光是输入就线性大。
2. **稀疏 oracle（sparse access）：**给定行号 $i$ 和序号 $\ell$，可以查询第 $i$ 行第 $\ell$ 个非零元的列号与数值。这是 Hamiltonian simulation 与量子线性求解器（见 HHL 教程）的标准输入模型，适合 $X$ 每行只有 $s\ll d$ 个非零元的情形。
3. **sample-and-query（采样加查询）：**除了查询元素外，还能按正比于 $|X_{ij}{|}^2$ 的分布对下标 $(i,j)$ 采样（通常还辅以按行范数 $\Vert x_i{\Vert }^2$ 采样行号）。这相当于假设经典侧已维护好某种 ${\ell }^2$-采样数据结构。
4. **QRAM / amplitude access（振幅编码）：**可以在相干叠加上一次性制备 ${\sum }_i|i⟩|x_i⟩$ 或整块矩阵态 $|X⟩=\frac{1}{\Vert X{\Vert }_F}{\sum }_{i,j}{X}_{ij}|i⟩|j⟩,$ 其中 $\Vert X{\Vert }_F=\sqrt{{\sum }_{i,j}{X}_{ij}^2}$ 是 Frobenius 范数（归一化因子保证这是单位态）。
5. **quantum examples（量子样本）：**数据本身就是量子态 ${\rho }_x$，由某个物理过程或量子电路直接提供，不能“免费转成完整经典表格”——把 ${\rho }_x$ 经典化本身就是 state tomography，代价高昂（见第 7 节）。

文献中声称的指数级维数优势，几乎全部使用第 3–5 类模型。这本身无可厚非——但必须意识到：模型的获取成本也是成本。若构造一个能振幅编码 $X$ 的 QRAM 需要先逐项扫描 $md$ 个数并写入某种数据结构，那么这次扫描的 $\Omega (md)$ 开销可能直接吞掉算法主体的 $\mathrm{polylog}(md)$ 复杂度。这并不意味着 QRAM 路线一定无用——如果同一份数据要被反复用于很多次训练/查询，装载成本可以摊销（amortize）；但摊销是否成立，必须针对具体应用论证，而不能默认。

输出端同样要写清楚。许多量子线性代数算法的自然输出是归一化量子态

$$|w⟩=\frac{w}{\Vert w\Vert },$$

即解向量 $w$ 的振幅编码。这不等于列出 $w$ 的 $d$ 个分量。直观地说，${\log }_{2}d$ 个量子比特上的一次测量只返回 ${\log }_{2}d$ 个经典比特，而写出 $w$ 的全部 $d$ 个分量需要 $\Omega (d)$ 比特的经典信息；要从 $|w⟩$ 中读出全部分量（即对 $|w⟩$ 做 tomography），一般需要 $\Omega (d)$ 次信息读出，指数级的态空间优势就此消失。因此，一个诚实的 QML 算法应把目标设定为预测、内积或某个 observable 的期望值——例如对新样本 $x$ 输出 $⟨x|w_{\ast }⟩$ 或 $\mathrm{sign}⟨x|w_{\ast }⟩$——而不是输出完整的经典模型参数。这条原则会贯穿全章。

2. 线性代数型学习

机器学习中最成熟的一批问题——最小二乘回归、最小二乘 SVM、PCA、聚类、推荐系统——都可以化成矩阵变换：解线性方程组、求逆、取低秩近似、算奇异向量。既然量子线性代数子程序（HHL、QSVT）对这些操作有 polylog 维数的版本，把它们拼进学习流水线就成了最自然的 QML 路线。本节以 ridge regression（岭回归）为完整例子，把每一步推导和每一个成本因子都摆出来。

2.1 从优化问题到正规方程

给定训练数据 $X\in {\mathbb{R}}^{m\times d}$ 与标签向量 $y\in {\mathbb{R}}^m$，ridge regression 求解

$$\underset{w\in {\mathbb{R}}^d}{\min }L(w),L(w)=\Vert Xw-y{\Vert }^2+\lambda \Vert w{\Vert }^2,$$

其中 $\lambda >0$ 是正则化参数：第一项拟合数据，第二项惩罚过大的权重，防止过拟合。把范数平方展开：

$$L(w)=w^T{X}^{T}Xw-2y^{T}Xw+y^{T}y+\lambda w^{T}w.$$

对 $w$ 求梯度（用到 ${\nabla }_w(w^{T}Aw)=2Aw$ 对对称 $A$ 成立、${\nabla }_w(y^{T}Xw)=X^{T}y$）并令其为零：

$${\nabla }_{w}L(w)=2(X^{T}X+\lambda I)w-2X^{T}y=0⟹(X^{T}X+\lambda I)w=X^{T}y.$$

这就是正规方程（normal equation）。Hessian 矩阵 ${\nabla }^{2}L=2(X^{T}X+\lambda I)$ 正定——因为对任意 $v\ne 0$，$v^T(X^{T}X+\lambda I)v=\Vert Xv{\Vert }^2+\lambda \Vert v{\Vert }^2\ge \lambda \Vert v{\Vert }^2>0$——所以驻点就是全局最小点，最优解为

$$w_{\ast }=(X^{T}X+\lambda I{)}^{-1}{X}^{T}y.$$

到这里为止全是经典线性代数。量子算法的机会在于：$w_{\ast }$ 是“对 $X$ 的奇异值做某种滤波后再合成”的结果，而 QSVT 恰好擅长对奇异值做逐值滤波。下面把这件事算清楚。

2.2 奇异值分解与 ridge 滤波器

设 $X$ 的（紧致）奇异值分解为

$$X=\sum _{i=1}^r{\sigma }_i{u}_i{v}_i^T,$$

其中 $r=\mathrm{rank}(X)$，${\sigma }_1\ge \cdots \ge {\sigma }_r>0$ 是奇异值，$\{u_i\}\subset {\mathbb{R}}^m$ 与 $\{v_i\}\subset {\mathbb{R}}^d$ 分别是左、右奇异向量，各自标准正交，且 $X{v}_i={\sigma }_i{u}_i$、$X^T{u}_i={\sigma }_i{v}_i$。于是

$$X^{T}X=\sum _{i=1}^r{\sigma }_i^2{v}_i{v}_i^T.$$

记 $P_{\perp }=I-{\sum }_i{v}_i{v}_i^T$ 为到 $\{v_i\}$ 正交补上的投影。由于 $X^{T}X$ 在该正交补上为零算子，

$$X^{T}X+\lambda I=\sum _{i=1}^r({\sigma }_i^2+\lambda )v_i{v}_i^T+\lambda P_{\perp }.$$

右端是同一组正交方向上的对角算子，求逆只需逐方向取倒数：

$$(X^{T}X+\lambda I{)}^{-1}=\sum _{i=1}^r\frac{1}{{\sigma }_i^2+\lambda }{v}_i{v}_i^T+\frac{1}{\lambda }{P}_{\perp }.$$

另一方面，$X^{T}y={\sum }_i{\sigma }_i⟨u_i,y⟩v_i$。把两者相乘，注意 $P_{\perp }{v}_i=0$，交叉项全部消失，得到

$$w_{\ast }=\sum _{i=1}^r\frac{{\sigma }_i}{{\sigma }_i^2+\lambda }⟨u_i,y⟩v_i.$$

这就是关键公式：$w_{\ast }$ 是把 $y$ 分解到左奇异向量上、每个方向乘以滤波因子

$$g(\sigma )=\frac{\sigma }{{\sigma }^2+\lambda }$$

后再换到右奇异向量基底合成。当 $\lambda \to 0$ 时，对 $\sigma >0$ 有 $g(\sigma )\to 1/\sigma$，上式退化为 Moore–Penrose 伪逆解 $X^{+}y$；当 $\sigma \ll \sqrt{\lambda }$ 时 $g(\sigma )\approx \sigma /\lambda$，小奇异值方向被强烈压制。这正是正则化的频谱含义：ridge 把 HHL 式滤波器 $1/\sigma$ 在小奇异值端的发散“截断”成一个有界的钟形函数。$g$ 在 $\sigma =\sqrt{\lambda }$ 处取最大值 $1/(2\sqrt{\lambda })$（由均值不等式 ${\sigma }^2+\lambda \ge 2\sqrt{\lambda }\sigma$ 即得），因此对 ${\sigma }_{\min }=0$ 的矩阵，原来 HHL 滤波器 $1/\sigma$ 对 ${\sigma }_{\min }$ 的灾难性依赖被软化成对 $\sqrt{\lambda }$ 的依赖——这是复杂度分析中“有效条件数”的来源（见 2.4 节）。

2.3 量子流水线

典型的量子 ridge regression 流水线分四步：

1. **态制备与 block encoding：**制备标签态 $|y⟩=y/\Vert y\Vert$，并构造 $X$（或正规化后的 $X/\alpha$）的 block encoding，其中 $\alpha \ge \Vert X\Vert$ 是 block-encoding normalization（见 block encoding 教程）；
2. **奇异值滤波：**用 HHL 或 QSVT 对奇异值实施 $\sigma \mapsto g(\sigma )=\frac{\sigma }{{\sigma }^2+\lambda };$ QSVT 把 $g$ 在谱区间上逼近成多项式再逐奇异值作用，HHL 则通过相位估计加受控旋转实现同一滤波；
3. **振幅放大：**滤波是非酉操作，只能以某个成功概率 $p$ 后选择实现；用 amplitude amplification 把重复次数从 $O(1/p)$ 降到 $O(1/\sqrt{p})$；
4. **受控输出：**不读出完整 $w_{\ast }$，而是只测量预测值 $⟨x|w_{\ast }⟩$（对新样本 $x$）或少数统计量——例如用 Hadamard test 把 $⟨x|w_{\ast }⟩$ 变成某个辅助比特上的期望值。

2.4 复杂度：每个因子从哪里来

端到端运行时间依赖以下量，缺一不可：

• **有效条件数 ${\kappa }_{\mathrm{eff}}$：**QSVT 逼近滤波器 $g$ 所需的多项式次数、以及后选择成功概率，都由滤波器在最坏奇异值处的行为控制。由 2.2 节，ridge 滤波器的极值尺度是 $1/(2\sqrt{\lambda })$ 而 $g({\sigma }_1)\approx 1/{\sigma }_1$（当 ${\sigma }_1\gg \sqrt{\lambda }$），两者的比值由 ${\sigma }_1/\sqrt{\lambda }$ 量级控制——于是普通最小二乘的 $\kappa ={\sigma }_1/{\sigma }_{\min }$ 被替换成由 ${\sigma }_1/\sqrt{\lambda }$ 控制的量。正则化参数 $\lambda$ 不只是统计超参数，它直接进入量子复杂度。
• **目标精度 $ϵ$：**多项式逼近误差与最终输出误差，通常以 $\log (1/ϵ)$（QSVT 滤波）或 $1/ϵ$（读出阶段的采样）进入；
• **block-encoding normalization $\alpha$：**滤波后成功分支的振幅含因子 $g(\sigma )/(\text{归一化常数})$，$\alpha$ 越大后选择成功率越低，振幅放大的开销越大；
• **态制备成本：**每轮迭代都要重新制备 $|y⟩$ 与查询态 $|x⟩$，若制备电路本身代价是 $P$，总成本要乘上 $P$（或证明可摊销）；
• **所需 observables 数：**若应用要求对 $q$ 个不同新样本分别预测，读出成本原则上乘 $q$。

早期文献中的“指数加速”声称，常常是把 ${\kappa }_{\mathrm{eff}}$、$\alpha$、态制备与读出当作 $O(1)$ 隐藏起来，只报告对 $md$ 的 $\mathrm{polylog}$ 依赖。正确的读法是：量子线性代数把对维数的依赖压到 polylog，代价是把对结构参数（条件数、稀疏度、归一化）的依赖暴露出来。只有当数据本身满足 ${\kappa }_{\mathrm{eff}}$ 小、低秩或稀疏、且第 1 节的访问模型成立时，端到端优势才成立。

2.5 去量子化：同一模型下的公平比较

Tang 关于 recommendation system 的工作（Zoo 400–401）给整个领域上了词条。其逻辑是：检查量子推荐算法真正用到的输入能力，会发现它只是第 1 节的第 3 类模型——sample-and-query access。而这种访问方式本身就可以被经典计算机以 polylog 时间模拟：给经典数据结构预处理后，按 ${\ell }^2$ 范数采样下标、查询元素都是 $O(\log md)$ 级操作。在此基础上，randomized linear algebra（随机投影、采样式低秩近似）可以“去量子化（dequantize）”许多原先声称指数加速的低秩子程序，得到对维数同样 polylog、只对条件数/秩等指标多项式依赖的经典算法。

对这个结果的正确解读不是“量子机器学习无优势”，而是：

• **加速必须在相同数据模型下比较。**拿“量子算法 + QRAM”对比“经典算法 + 显式访问”是不对等的；把经典算法也放进 sample-and-query 模型后，不少差距从指数缩回多项式。
• 去量子化目前主要覆盖低秩、采样可及的子程序。对高条件数、非低秩、或输入本身是量子态的问题，它并不直接适用。
• QSVT 仍提供统一、精确的 singular-value filter 工具（见 QSVT 教程），在稀疏 oracle 等去量子化够不着的模型中依然是正确的武器；但它不会自动解决输入输出瓶颈——第 1 节的两笔账仍然要付。

3. 量子核方法

核方法（kernel method）是经典机器学习中处理非线性的标准技术：把数据点 $x$ 映射到高维特征空间，$\varphi (x)$，再只通过内积 $K(x,x^{\prime })=⟨\varphi (x),\varphi (x^{\prime })⟩$ 工作。量子版本的想法非常直接：让量子希尔伯特空间充当特征空间。选一个依赖数据的酉 $U_{\varphi }(x)$（feature map circuit），定义

$$|\varphi (x)⟩=U_{\varphi }(x)|0^n⟩,K(x,x^{\prime })=|⟨\varphi (x)|\varphi (x^{\prime })⟩{|}^2.$$

这里 $n$ 个量子比特给出 $2^n$ 维特征空间——特征空间的指数维数正是潜在优势的来源。注意定义中取模平方：这样 $K$ 自动实值、对称、半正定，是合法核函数（半正定因为它本身是某个内积诱导的 Gram 形式：$K(x,x^{\prime })=|⟨\varphi (x)|\varphi (x^{\prime })⟩{|}^2=⟨\varphi (x)|\varphi (x^{\prime })⟩\overline{⟨\varphi (x)|\varphi (x^{\prime })⟩}$，Gram 矩阵 $K_{ij}$ 是向量组 $\{⟨\varphi (x_i)|\varphi (x_j)⟩\}$ 的“模方 Gram 矩阵”，其半正定性可由它等于某矩阵与其共轭转置的逐元乘积（Schur 积定理）得到）。

3.1 核矩阵的量子估计

估计单个 $K(x,x^{\prime })$ 有两种标准电路：

• **inverse circuit：**运行 $U_{\varphi }(x^{\prime }{)}^{†}{U}_{\varphi }(x)|0^n⟩$，测得全 $0$ 字符串的概率恰好是 $\mathrm{Pr}(0^n)=|⟨0^n|U_{\varphi }(x^{\prime }{)}^{†}{U}_{\varphi }(x)|0^n⟩{|}^2=|⟨\varphi (x^{\prime })|\varphi (x)⟩{|}^2=K(x,x^{\prime }).$
• **SWAP test：**在两个寄存器分别制备 $|\varphi (x)⟩$ 与 $|\varphi (x^{\prime })⟩$，用一个辅助比特做受控 SWAP，辅助比特的偏置给出 $|⟨\varphi (x)|\varphi (x^{\prime })⟩{|}^2$。

两条路线都把 $K(x,x^{\prime })$ 归结为一个概率的估计。设重复 $S$ 次、频率估计为 $\hat{K}$，由 Hoeffding 不等式

$$\mathrm{Pr}\left[|\hat{K}-K|\ge ϵ\right]\le 2e^{-2S{ϵ}^2},$$

故单条目达到精度 $ϵ$、置信 $1-\delta$ 需要

$$S=O\left(\frac{1}{{ϵ}^2}\log \frac{1}{\delta }\right)\text{shots}.$$

而训练一个 kernel SVM 需要整个 Gram matrix 的 $m^2$ 个条目（$m$ 为训练集大小）。对所有条目做 union bound——把每条失败概率压到 $\delta /m^2$，即每条 $\log$ 因子变为 $\log (m/\delta )$——总开销为

$$O\left(\frac{m^2}{{ϵ}^2}\log \frac{m}{\delta }\right)\text{次电路执行}.$$

**数值例子（这就是习题 2 的原型，这里完整算一遍）。**取 $m=1000$、$ϵ=0.01$、$\delta =0.01$：条目数 $m^2=10^6$；每条 $1/{ϵ}^2=10^4$，乘 $\log (m/\delta )=\log 10^5\approx 12$（自然对数；换底只差常数因子），每条约 $10^5$ shots；总量约 $10^6\times 10^5=10^{11}$ 次电路执行。即使每次执行只要微秒级，总量也到 $10^5$ 秒量级。**核方法的瓶颈通常不在单个电路的深度，而在 $m^2$ 个条目乘 shot noise 的乘法开销。**实践中可用 kernel alignment（先在小子集上验证核与标签的相关性）、小训练子集或低秩近似（Nyström 方法）削减这笔账；详细电路见量子核方法。

3.2 困难核、可训练性与泛化：三个不同命题

某些基于 discrete logarithm 的 feature map（Zoo 428）给出在复杂度假设下难以经典近似的 kernel：若离散对数问题对经典计算机困难，则存在数据分布使任何经典多项式时间算法都无法以非平凡精度逼近 $K(x,x^{\prime })$，而量子电路可以精确计算。这是 QML 中少见的可证明计算分离。

但必须清醒地指出这个定理证明了什么、没证明什么。它只证明计算 kernel 本身的困难——即“经典算不出这个数”。而一个好的学习算法需要三件事同时成立：

1. **核可算（量子侧）：**量子电路能高效精确地算出 $K$；✔ 由构造保证；
2. **核难算（经典侧）：**经典算法不能高效逼近 $K$；✔ 由复杂度假设保证；
3. 核有用（统计侧）：以 $K$ 为核的 SVM 在真实数据分布上确实有更好的 generalization（泛化误差小）。✘ 计算困难性定理对此不提供任何保证。

一个经典算不出、但同时与标签毫不相关的核，满足前两条却毫无学习价值。把“核难算”直接读成“量子学习优势”，是 QML 文献中最精致的偷换概念。第 9 节的小结还会回到这个三命题结构。

4. Variational 模型与量子神经网络

第三类路线不追求可证明加速，而是把量子电路本身当作可训练模型。参数化电路写成

$$f_{\theta }(x)=⟨0|U_{\theta }(x{)}^{†}O{U}_{\theta }(x)|0⟩,$$

其中 $U_{\theta }(x)$ 是同时依赖输入 $x$ 与参数 $\theta$ 的含参酉电路，$O$ 是某个可观测量，$f_{\theta }(x)$ 是模型输出。训练循环为混合式：量子电路估计 loss 与 gradient（例如用 parameter-shift 规则），经典优化器（梯度下降、Adam 等）更新 $\theta$，如此往复。

这条路线的现实优势是适合近期硬件（电路浅、对量子数据天然）——代价是训练成本结构完全不同：

• **shot noise：**每次估计 $f_{\theta }$ 或梯度分量都是概率性读出，精度 $ϵ$ 需 $O(1/{ϵ}^2)$ 次重复；$P$ 个参数的一次完整梯度原则上要 $O(P)$ 次电路评估，一次训练迭代的成本随参数量线性放大；
• **noise-induced bias：**真实硬件的噪声使估计值系统性偏离理想值，优化器在含偏梯度上可能收敛到错误点；
• **barren plateau：**深而随机的 ansatz 中，梯度方差随比特数指数衰减（见贫瘠高原），训练信号被 shot noise 淹没。

特别强调 parameter-shift 规则的地位：它是一个精确梯度恒等式——对由单参数 Pauli 旋转门构成的电路，${\partial }_{{\theta }_j}f=\frac{1}{2}[f({\theta }_j+\frac{\pi }{2})-f({\theta }_j-\frac{\pi }{2})]$ 精确成立——但它是电路评估层面的恒等式，不是样本无关的免费梯度。等式右端的每个 $f$ 仍要靠有限 shots 估计，${\theta }_j\pm \frac{\pi }{2}$ 两次评估各带 $O(1/{ϵ}^2)$ 的采样成本，且要对每个参数、每个训练样本、每个迭代步重复。

因此，比较 variational 量子模型与经典模型时，唯一诚实的货币是 total circuit executions（训练全程的电路执行总次数），而不是只报告 qubit 数或单次 circuit depth——后两者完全可以很小，同时训练总成本大得离谱。详见参数化量子神经网络、贫瘠高原和 VQE。

5. 搜索、近邻与组合学习

还有一大类 QML 算法的加速来源不是线性代数，而是 Grover/振幅放大的二次查询加速。其共同结构是：学习任务的某个内层循环是“在 $N$ 个候选中找满足某 predicate 的对象”，且该 predicate 可相干计算（即存在翻转解相位或标记解的 oracle）。此时查询数从经典的 $O(N)$ 降到 $O(\sqrt{N})$。由此得到 nearest-neighbor 搜索（在 $N$ 个训练点中找离查询点最近者）、ensemble voting（对 $N$ 个弱分类器的投票做相干计数）、decision-tree 路径搜索等一系列 polynomial speedup。

这类结果的可信度边界同样清晰：

• 加速是二次的，不是指数的。无结构搜索的 $\Omega (\sqrt{N})$ 下界（Grover 教程中已述其最优性）说明：不利用问题额外结构，量子计算机在这类任务上给不出指数加速；
• 距离 oracle 的构造、数据装载和“取回最近点的索引”仍要计费——如果比较两个 $d$ 维点的距离需要逐项读取，oracle 本身的实现成本可能超过 $\sqrt{N}$ 次调用省下的部分；
• 结论应是“在明确的 oracle 模型下查询复杂度二次改善”，而不是“量子近邻搜索指数快”。

另一条组合学习路线是 Quantum annealing 与 QAOA：把 clustering、feature selection、Boltzmann-machine training 等离散优化学习目标编码成 Ising cost Hamiltonian

$$H_C=\sum _i{h}_i{Z}_i+\sum _{i<j}{J}_{ij}{Z}_i{Z}_j,$$

再用绝热演化或变分 Ansatz 找低能态，低能态即近似最优解。必须明确：这给出的是 heuristic solver（启发式求解器）——没有任何普适性定理保证它在此类 NP-hard 实例上优于经典启发式；它与模拟退火、禁忌搜索等 classical heuristic 处于同一竞争层级，唯一公平的比较方式是相同时间预算下的解质量。这不是贬低该方向——启发式在有结构的真实实例上完全可能表现优异——而是指出其声称的性质：实验性的、实例依赖的、模型依赖的，而非复杂度理论意义上的优越性证明。

6. 拓扑数据分析

拓扑数据分析（topological data analysis, TDA）是量子算法谱系中“潜在指数加速”与“约束条件最多”并存的代表。它的目标是从点云中提取拓扑特征——数据在高维空间中围出了多少个洞——而量子算法恰好擅长在指数大的组合空间上估计谱量。

6.1 从点云到单纯复形

给定点云 $V=\{v_0,\dots ,v_{n-1}\}\subset {\mathbb{R}}^d$ 和尺度参数 $r>0$，Vietoris–Rips complex 包含所有两两距离不超过 $r$ 的点集（simplex，单纯形）：$\{v_{i_0},\dots ,v_{i_k}\}$ 是一个 $k$-simplex 当且仅当其中任意两点的距离都 $\le r$。尺度 $r$ 是分析的自由度：$r$ 太小，点云碎成孤点，没有任何结构；$r$ 太大，所有点粘连成一个巨大的实心块，洞被填满——有意义的拓扑信息只出现在中间尺度的窗口里（这正是 persistent homology 要扫描整个 $r$ 轴的原因，见 6.5 节）。

6.2 边界算子与 ${\partial }^2=0$

记 $C_k$ 为以所有 $k$-simplex 为形式基的自由向量空间（实系数），其维数是 $k$-simplex 的个数。边界算子（boundary operator）${\partial }_k:C_k\to C_{k-1}$ 把一个 $k$-simplex 映为它所有 $k+1$ 个面（删去一个顶点得到的 $(k-1)$-simplex）的交错和：

$${\partial }_k[v_0,\dots ,v_k]=\sum _{j=0}^k(-1{)}^j[v_0,\dots ,{\hat{v}}_j,\dots ,v_k],$$

其中 ${\hat{v}}_j$ 表示删去顶点 $v_j$。交错符号 $(-1{)}^j$ 编码定向，它是下面核心恒等式成立的全部原因。

Lemma 1. ${\partial }_{k-1}{\partial }_k=0$：边界的边界为零。

**证明。**对任意 $k$-simplex $[v_0,\dots ,v_k]$ 直接展开。先作用 ${\partial }_k$，再对每一项作用 ${\partial }_{k-1}$；注意删去两个顶点 $v_i,v_j$（$i<j$）时，先删 $v_j$ 后 $v_i$ 的位置仍是 $i$，而先删 $v_i$ 后 $v_j$ 的位置变成 $j-1$：

$$\begin{array}{rl}{\partial }_{k-1}{\partial }_k[v_0,\dots ,v_k]& =\sum _{j=0}^k(-1{)}^j{\partial }_{k-1}[v_0,\dots ,{\hat{v}}_j,\dots ,v_k]\\ & =\sum _{j=0}^k(-1{)}^j[\sum _{i<j}(-1{)}^i[v_0,\dots ,{\hat{v}}_i,\dots ,{\hat{v}}_j,\dots ,v_k]+\sum _{i>j}(-1{)}^{i-1}[v_0,\dots ,{\hat{v}}_j,\dots ,{\hat{v}}_i,\dots ,v_k]].\end{array}$$

交换第二个求和的指标名（把 $i\leftrightarrow j$），每一项 $[v_0,\dots ,{\hat{v}}_a,\dots ,{\hat{v}}_b,\dots ,v_k]$（$a<b$）恰好出现两次：一次来自“先删 $v_b$ 再删 $v_a$”，系数 $(-1{)}^{a+b}$；一次来自“先删 $v_a$ 再删 $v_b$”，系数 $(-1{)}^{a+b-1}$。两者相加为零，故总和为零。Q.E.D.

Lemma 1 的直接推论是 $\mathrm{im}{\partial }_{k+1}\subseteq \ker {\partial }_k$：任何 $(k+1)$-维体的边界，自己作为 $k$-维链必然“无边界”（${\partial }_k$ 核中）。反过来，无边界且自身不是边界的 $k$-维链，正是“$k$ 维的洞”——例如一个正方形框架的四条边加起来无边界（每条边的端点两两抵消），但它不是任何 2 维体的边界，因为正方形内部没有填充。于是 $k$ 阶同调群与 Betti number 定义为

$$H_k=\frac{\ker {\partial }_k}{\mathrm{im}{\partial }_{k+1}},{\beta }_k=\dim H_k=\dim \ker {\partial }_k-\mathrm{rank}{\partial }_{k+1},$$

${\beta }_k$ 计数 $k$ 维 holes：${\beta }_0$ 是连通分量数，${\beta }_1$ 是独立的环（洞）数，${\beta }_2$ 是空腔数，依此类推。

6.3 组合 Laplacian：把同调变成谱问题

直接计算 $\ker {\partial }_k/\mathrm{im}{\partial }_{k+1}$ 需要矩阵的秩与核，量子算法不擅长商空间；擅长的是谱。**组合 Laplacian（combinatorial Laplacian）**完成了这个翻译：

$${\Delta }_k={\partial }_k^{†}{\partial }_k+{\partial }_{k+1}{\partial }_{k+1}^{†}.$$

它把“上下两个方向”的关联信息合成一个作用在 $C_k$ 上的半正定算子。核心事实是：

Lemma 2. $\ker {\Delta }_k=\ker {\partial }_k\cap \ker {\partial }_{k+1}^{†}$，并且 ${\beta }_k=\dim \ker {\Delta }_k$。

**证明。**先证第一个等号。若 ${\partial }_{k}v=0$ 且 ${\partial }_{k+1}^{†}v=0$，代入定义显然 ${\Delta }_{k}v=0$。反之，若 ${\Delta }_{k}v=0$，由半正定性

$$0=⟨v|{\Delta }_k|v⟩=⟨v|{\partial }_k^{†}{\partial }_k|v⟩+⟨v|{\partial }_{k+1}{\partial }_{k+1}^{†}|v⟩=\Vert {\partial }_{k}v{\Vert }^2+\Vert {\partial }_{k+1}^{†}v{\Vert }^2,$$

两个非负实数之和为零当且仅当各自为零，即 ${\partial }_{k}v=0$ 且 ${\partial }_{k+1}^{†}v=0$。

再证与 Betti 数的关系。在 $C_k$ 上做正交分解 $C_k=\mathrm{im}{\partial }_{k+1}\oplus (\mathrm{im}{\partial }_{k+1}{)}^{\perp }$。在 $\mathrm{im}{\partial }_{k+1}$ 内部：由 Lemma 1，其中向量自动落在 $\ker {\partial }_k$ 中，对应同调里被模掉的部分。在其正交补上：$\ker {\partial }_{k+1}^{†}=(\mathrm{im}{\partial }_{k+1}{)}^{\perp }$（核与像的正交补关系，对任意线性算子成立），故此补上 $\ker {\Delta }_k=\ker {\partial }_k\cap (\mathrm{im}{\partial }_{k+1}{)}^{\perp }$。把 $\ker {\partial }_k$ 沿这两个方向分解（注意 $\mathrm{im}{\partial }_{k+1}\subseteq \ker {\partial }_k$）：

$$\ker {\partial }_k=\mathrm{im}{\partial }_{k+1}\oplus (\ker {\partial }_k\cap (\mathrm{im}{\partial }_{k+1}{)}^{\perp })=\mathrm{im}{\partial }_{k+1}\oplus \ker {\Delta }_k,$$

取维数：$\dim \ker {\partial }_k=\mathrm{rank}{\partial }_{k+1}+\dim \ker {\Delta }_k$，与 ${\beta }_k$ 的定义比较即得 ${\beta }_k=\dim \ker {\Delta }_k$。Q.E.D.

（这就是离散 Hodge 分解 $C_k=\mathrm{im}{\partial }_{k+1}\oplus \mathrm{im}{\partial }_k^{†}\oplus \ker {\Delta }_k$ 的一个推论；三个正交分量分别对应“是边界”“边界非零”“调和”三类链。）Lemma 2 的意义在于：数洞 = 数零特征值。而估计一个算子零特征值的权重，正是相位估计/QSVT 的看家本领。

6.4 一个完整手算的小例子

取正方形四角上的四个点，尺度 $r$ 取为恰好容纳四条边但不含对角线（边长 $1$，对角线 $\sqrt{2}$，取 $1\le r<\sqrt{2}$）。Vietoris–Rips complex 含：4 个 0-simplex（顶点）、4 个 1-simplex（边）、没有任何 2-simplex（三角形要求三条边两两相连，但每条三角形都至少包含一条对角线）、更高维全空。因此

$$\dim C_0=4,\dim C_1=4,C_2=0.$$

给顶点编号 $0,1,2,3$（顺时针），四条边为 $e_1=[0,1],e_2=[1,2],e_3=[2,3],e_4=[3,0]$。由定义 ${\partial }_1[a,b]=[b]-[a]$，在基 $\{[0],[1],[2],[3]\}$ 与 $\{e_1,e_2,e_3,e_4\}$ 下（第 $j$ 列是 $e_j$ 的像）：

$${\partial }_1=\left(\begin{array}{cccc}-1& 0& 0& 1\\ 1& -1& 0& 0\\ 0& 1& -1& 0\\ 0& 0& 1& -1\end{array}\right).$$

求 $\ker {\partial }_1$：设 $v=(a,b,c,d{)}^T$（$e_1,\dots ,e_4$ 的系数），逐行写出 ${\partial }_{1}v=0$ 即 $-a+d=0,a-b=0,b-c=0,c-d=0$，得 $a=b=c=d$，故

$$\ker {\partial }_1=\mathrm{span}\{(1,1,1,1{)}^T\},\dim \ker {\partial }_1=1.$$

这就是“沿正方形走一圈”的链——四边首尾相接，边界两两抵消。因 $C_2=0$，${\partial }_2=0$，$\mathrm{im}{\partial }_2=\{0\}$，于是

$${\beta }_1=\dim \ker {\partial }_1-\mathrm{rank}{\partial }_2=1-0=1.$$

用 Lemma 2 验证：${\Delta }_1={\partial }_1^{†}{\partial }_1+{\partial }_2{\partial }_2^{†}={\partial }_1^{†}{\partial }_1$（因 ${\partial }_2=0$），而 $\ker ({\partial }_1^{†}{\partial }_1)=\ker {\partial }_1$（因为 $\Vert {\partial }_{1}v{\Vert }^2=⟨v|{\partial }_1^{†}{\partial }_1|v⟩$），故 $\dim \ker {\Delta }_1=1={\beta }_1$。✔ 几何上这就是正方形中间的那个洞。顺带可算 ${\beta }_0$：${\Delta }_0={\partial }_1{\partial }_1^{†}$，$\dim \ker {\Delta }_0=\dim C_0-\mathrm{rank}{\partial }_1=4-3=1$，对应一个连通分量。✔

6.5 量子算法与它的四项约束

量子 TDA 算法的思路顺承上面的谱刻画：

1. 制备有效 simplex 的叠加态 $|{\psi }_k⟩\propto {\sum }_{\sigma :k\text{-simplex}}|\sigma ⟩$。$n$ 个点的 $k$-simplex 总数为 $\left(\genfrac{}{}{0ex}{}{n}{k+1}\right)$；当 $k$ 随 $n$ 增长（例如 $k\approx n/2$）时，$\left(\genfrac{}{}{0ex}{}{n}{k+1}\right)$ 对 $n$ 指数大，而索引一个 simplex 只需 $O(k\log n)$ 个比特——指数大的状态空间装进多项式个 qubits，这是潜在指数加速的来源；
2. 构造 ${\Delta }_k$ 的 block encoding（${\partial }_k$ 的矩阵元由距离比较局部决定，适合 oracle 化）；
3. 对 ${\Delta }_k$ 做 phase estimation 或 QSVT，区分零特征值与非零特征值；
4. 估计零特征值所占比重 $p={\beta }_k/\dim C_k$，乘以 $\dim C_k$ 即得 ${\beta }_k$。

第 4 步暴露出关键困难：量子测量天然给出的是比例 $p$，而非整数 ${\beta }_k$ 本身。把 $p$ 估到加性误差 $ϵ$ 需 $O(1/{ϵ}^2)$ 次采样（或 $O(1/ϵ)$ 次振幅估计调用）；要分辨 ${\beta }_k$ 与 ${\beta }_k+1$，需要 $ϵ\lesssim 1/\dim C_k$——若 $\dim C_k$ 指数大，这一步就是指数昂贵的，除非 ${\beta }_k$ 本身占 $\dim C_k$ 的不可忽略比例。

因此，潜在优势被四项条件联合约束，缺一不可：

• **态制备：**有效 simplex 的叠加 $|{\psi }_k⟩$ 能否高效制备？在一般 $r$ 下，有效 simplex 的集合由距离结构决定，均匀叠加其上并不平凡；
• 谱隙：${\Delta }_k$ 的最小非零特征值是否足够大？相位估计要分辨“零”与“非零”，精度必须优于谱隙，运行时间反比于谱隙；
• 信号占比：${\beta }_k/\dim C_k$ 是否可测（至少 $1/\mathrm{poly}$）？这决定了第 4 步是否可行；
• **需求范围：**应用是否真的只需要少数几个 Betti numbers？若需要整个 persistence barcode（所有 $k$、所有尺度 $r$ 的完整拓扑指纹），成本要对每个 $(k,r)$ 重复支付。

后续 rigorous resource analyses（Zoo 487–490）指出，在一般输入上这些条件不能省略——即不存在“对任意点云、任意 $k$，多项式时间输出 ${\beta }_k$”的量子算法；这与经典情形一致（精确 Betti 数的计算在高维同样困难）。诚实的结论是：量子 TDA 在特定良性实例类（好制备、大谱隙、高占比、少量目标 Betti 数）上可能有指数级维数优势，而一般性声称需要逐案审计。

7. 学习量子数据

前两节的边界都源于“经典数据进、经典信息出”的转换成本。第 5 类模型（quantum examples）绕开了这个瓶颈：若样本是未知 quantum states ${\rho }_x$——例如量子传感器的输出、量子化学实验制备的态、另一个量子算法的中间产物——那么数据已经在量子计算机里，第 1 节的装载成本根本不存在。

此时，collective measurement（对多份拷贝联合测量）、quantum kernel 或 shadow methods（见经典影子）可能比“先 tomography 再经典学习”省样本。原因很简单：完整 tomography 把每个 ${\rho }_x$ 的经典化代价随维数指数增长，而学习任务往往只需要 ${\rho }_x$ 的少数低维特征——保留 quantum coherence、直接在态上做相干处理，省下的正是“把量子信息强行经典化”的那笔冤枉钱。

一个常见分类器的形式是：对每个候选标签 $y$ 设计可观测量 $M_y$（由训练阶段的量子数据学得），预测

$$\hat{y}=\arg \underset{y}{\max }\mathrm{Tr}(M_y{\rho }_x).$$

审计这类算法仍需逐项明确：训练 copies 的数量与来源、测试 copies 的数量、是否允许 collective measurements（联合测量通常比逐份测量强得多，两者的样本复杂度分离本身是重要研究对象）、以及学得的 classical description 大小（$M_y$ 若需指数多个参数描述，存储与部署成本会反噬样本优势）。最重要的一条纪律是：不能把“输入就是量子态”的优势外推到普通 CSV 数据——一旦数据起点是经典表格，第 1 节的全部问题原样回归。

8. 端到端审计清单

综合全章，对任何一项 QML speedup 声称，逐项回答以下问题。每一项都对应本词条至少一节的分析，任何一项答不上来，加速声称就不成立：

• **输入如何编码？**属于第 1 节五类模型中的哪一类？预处理（QRAM 构建、数据结构维护、${\ell }^2$-采样结构）由谁支付、能否摊销？
• **oracle/QRAM 是否可在所述复杂度内实现？**声称 polylog 访问的同时，访问装置的构建与维护成本是否被隐藏？
• **复杂度对 $\kappa$、rank、gap、precision 和 failure probability 如何依赖？**第 2.4 节的清单：条件数类参数、block-encoding normalization、态制备、读出采样数——全部摆到台面上。
• **输出是 quantum state、一个 scalar 还是完整 classical model？**若应用需要完整经典模型，$\Omega (d)$ 的读出成本是否已被计入？（第 1、2 节）
• **sample-and-query 模型下是否已有 dequantization？**低秩、采样可及的子程序很可能已有同模型经典对手（第 2.5 节）。
• **与最强 classical randomized/approximate baseline 比较了吗？**对手应是相同数据模型、相同误差容忍下的最强经典算法（包括随机化与近似算法），而不是教科书上最笨的精确确定性算法。

只有这些答案同时成立，才可把子程序级 speedup 称为应用级优势。这份清单的严格性不是犬儒：它保护真正有价值的工作（量子数据学习、困难核构造、良性实例上的量子 TDA）不被淹没在夸大的声称里。

9. 小结与习题

• 量子机器学习是一个算法谱系：线性代数、kernel、variational、搜索/组合优化、TDA 与 quantum-data learning 使用不同的资源模型与加速来源，不可混为一谈。
• 端到端成本 = 输入装载 + oracle + 条件数/归一化 + 测量采样 + 经典读出。HHL/QSVT 的 state output、QRAM 和 condition number 是线性代数路线的核心边界；$m^2/{ϵ}^2$ 的 Gram 估计是核方法的核心边界；total circuit executions 是 variational 路线的诚实货币。
• Dequantization 校准数据访问假设——相同模型下比较才有意义；它不否定全部 quantum learning，够不着的角落（稀疏 oracle、量子输入、困难核）依然存在。
• 核难算、模型可训练、统计泛化是三个不同命题（第 3.2 节），任何 QML 优势声称都应指明落在哪一条上。
• 量子 TDA 把数洞翻译成数零特征值（Lemma 2），潜在指数优势受态制备、谱隙、信号占比、需求范围四项条件联合约束。

习题（难度大致递增）：

1. （温故）补全 2.1 节的推导：验证 ${\nabla }_w(w^T{X}^{T}Xw)=2X^{T}Xw$，并证明 ridge 解 $w_{\ast }$ 在 $\lambda \to 0^{+}$ 时收敛到 Moore–Penrose 伪逆解 $X^{+}y$（提示：用 2.2 节的谱分解，逐奇异值取极限）。
2. （估算）对 $m=2000$ 的 kernel matrix、逐项精度 $ϵ=0.005$、整体置信 $1-\delta =0.99$，按 3.1 节的 Hoeffding + union bound 估算所需总 shots 的数量级；若改用振幅估计把单条目成本降到 $O(1/ϵ)$，总量改善多少？
3. （手算）在 6.4 节的正方形例子中加入对角线点集：五个点为正方形四角加中心，取 $r$ 使中心与四角相连、四角之间只有边相连（不含对角线）。列出全部 0/1/2-simplex，写出 ${\partial }_1$ 与 ${\partial }_2$，计算 ${\beta }_0$ 与 ${\beta }_1$，并用 Lemma 2 验证。
4. （证明）不用谱分解，直接由 6.2 节的定义证明 $\mathrm{rank}{\partial }_k+\dim \ker {\partial }_k=\dim C_k$（秩-零化度定理在链群上的形式），并由此推出 ${\beta }_k=\dim C_k-\mathrm{rank}{\partial }_k-\mathrm{rank}{\partial }_{k+1}$。解释为什么这个公式在经典计算上可行（高斯消元）却不适合直接量子化。
5. （审计）找一篇声称指数加速的 QML 论文，按第 8 节的清单逐项填写完整成本表：数据模型、oracle 成本、条件数依赖、输出形式、经典基线。给出你的结论：加速在何种假设下成立。
6. （讨论）去量子化为什么不排除所有量子机器学习优势？结合本词条内容，给出至少三类可能逃脱 dequantization 的情形，并说明各自依赖的模型假设。

参考文献与 Zoo 覆盖

• Zoo 编号 104、214、246、250、251、309、336、433、456：线性代数、clustering/PCA、SVM、recommendation、regression 与 variational learning。
• Zoo 编号 400—401：Ewin Tang 等的 quantum-inspired/dequantized recommendation 与 linear algebra。
• Zoo 编号 428：在复杂度假设下具有 classical hardness 的 quantum kernel construction。
• Zoo 编号 222、487—490：quantum topological data analysis、Betti numbers 与后续资源/限制分析。
• Zoo 编号 489—490：量子数据学习和相关 sample-complexity 分离。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch15-learning-spectral/machine-learning-zoo
• 内容遵循 CC BY-NC-SA 4.0 许可协议