量子机器学习算法谱系：从线性代数、核方法到拓扑数据分析¶

“量子机器学习”不是一个单一算法。它至少包含三种不同任务：用量子计算机处理经典数据、学习量子态产生的数据，以及用经典优化器训练参数化量子电路。判断加速时必须把数据装载、oracle 构造、条件数、测量次数和经典输出全部计入。

1. 先写清计算模型¶

设训练集为 $X\in\mathbb R^{m\times d}$。常见访问模型从弱到强依次为：

**显式访问：**逐项读写 $X_{ij}$；读完整数据已需 $\Omega(md)$。
**稀疏 oracle：**给行号和位置，可查询非零元及其列号。
**sample-and-query：**既能查询元素，又能按 $|X_{ij}|^2$ 分布采样。
**QRAM/amplitude access：**在叠加上制备 $|i\rangle|x_i\rangle$ 或 $|X\rangle$。
**quantum examples：**数据本身是量子态，不能免费转成完整经典表格。

指数级维数优势通常使用第 3--5 类模型。若构造 QRAM 需要逐项扫描 $md$ 个数，装载成本可能吞掉算法主体的 $\operatorname{polylog}(md)$ 复杂度。

输出也要说明。返回

\[ |w\rangle=\frac{w}{\|w\|} \]

不等于列出 $d$ 个权重；后者一般需 $\Omega(d)$ 次信息读出。实际目标常应是预测、内积或某个 observable，而不是完整向量。

2. 线性代数型学习¶

最小二乘、最小二乘 SVM、PCA、聚类和推荐系统都可化成矩阵变换。以 ridge regression 为例，

\[ w_*=(X^TX+\lambda I)^{-1}X^Ty. \]

典型量子流水线是：

制备 $|y\rangle$ 并构造 $X$ 或正规矩阵的 block encoding；
用 HHL 或 QSVT 对奇异值实施 $$ \sigma\mapsto\frac{\sigma}{\sigma^2+\lambda}; $$
amplitude amplification 提高成功分支；
只测量预测值 $\langle x|w_*\rangle$ 或少数统计量。

运行时间依赖 condition number $\kappa$、目标误差、block-encoding normalization、state-preparation 成本及所需 observables 数。早期“指数加速”常把这些量隐藏起来。

Tang 的 recommendation-system 工作表明：若量子算法只使用可经典模拟的 sample-and-query access，则 randomized linear algebra 可“去量子化”许多低秩子程序。结论不是量子机器学习无优势，而是相同数据模型下比较才有意义。QSVT 仍提供统一、精确的 singular-value filter 工具，但不会自动解决输入输出瓶颈。

3. 量子核方法¶

选 feature map $U_\phi(x)$，定义

可用 inverse circuit 或 SWAP test 估计 $K_{ij}$，再把 Gram matrix 交给 classical SVM。某些基于 discrete logarithm 的 feature map 给出在复杂度假设下难以经典近似的 kernel，但这只证明计算 kernel 的困难，不保证它在真实分布上有更好的 generalization。

端到端代价还包括 $m^2$ 个 Gram entries 和每项 $O(1/\epsilon^2)$ shots。实践中可用 kernel alignment、小训练子集或低秩近似；详细电路见量子核方法。

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

参数化电路写成

\[ f_\theta(x)=\langle0|U_\theta(x)^\dagger O U_\theta(x)|0\rangle. \]

训练循环由量子电路估计 loss/gradient，经典优化器更新 $\theta$。它适合近期硬件和量子数据，但每步有 shot noise、noise-induced bias 和 optimizer cost；深随机 ansatz 还可能出现 barren plateau。Parameter-shift 是精确梯度恒等式，不是样本无关的免费梯度。

因此应报告 total circuit executions，而不只报告 qubit 数或单次 circuit depth。详见参数化量子神经网络、贫瘠高原和VQE。

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

若 predicate 可相干计算，Grover/amplitude amplification 可把搜索 $N$ 个候选的查询数从 $O(N)$ 降到 $O(\sqrt N)$。由此得到 nearest-neighbor、ensemble voting、decision-tree 路径搜索等 polynomial speedup。距离 oracle 的构造、数据装载和取回最近点索引仍要计费；一般没有无结构问题的指数加速。

Quantum annealing 或 QAOA 可把 clustering、feature selection、Boltzmann-machine training 编码成 Ising cost Hamiltonian，

\[ H_C=\sum_i h_iZ_i+\sum_{i<j}J_{ij}Z_iZ_j. \]

这给出 heuristic solver，而不是普适优越性证明；应与相同时间预算的 classical heuristic 比较。

6. 拓扑数据分析¶

给点云和尺度 $r$，Vietoris--Rips complex 包含所有两两距离不超过 $r$ 的 simplices。边界算子

\[ \partial_k:C_k\to C_{k-1}, \qquad \partial_k[v_0,\ldots,v_k] =\sum_{j=0}^{k}(-1)^j[v_0,\ldots,\widehat v_j,\ldots,v_k], \]

满足 $\partial_{k-1}\partial_k=0$。组合 Laplacian 为

\[ \Delta_k=\partial_k^\dagger\partial_k +\partial_{k+1}\partial_{k+1}^\dagger, \]

而 Betti number

\[ \beta_k=\dim\ker\Delta_k \]

计数 $k$ 维 holes。量子算法制备有效 simplex 的叠加，对 $\Delta_k$ 做 phase estimation 或 QSVT，再估计零特征值权重。

潜在优势来自 simplex 空间指数大，却被四项条件约束：有效 simplex state 能否高效制备、spectral gap 是否足够大、$\beta_k$ 占比是否可测，以及是否只需少数 Betti numbers 而非整个 persistence barcode。后续 rigorous resource analyses 指出，在一般输入上这些条件不能省略。

7. 学习量子数据¶

若样本是未知 quantum states $\rho_x$，collective measurement、quantum kernel 或 shadow methods 可能比“先 tomography 再经典学习”省样本。此时优势来自保留 quantum coherence；把每个态完整经典化本来就代价高。

一个常见分类器用 observables $M_y$，预测

\[ \widehat y=\arg\max_y\operatorname{Tr}(M_y\rho_x). \]

仍需明确训练 copies、测试 copies、允许的 collective measurements 和 classical description 大小。不能把“输入就是量子态”的优势外推到普通 CSV 数据。

8. 端到端审计清单¶

对任何 QML speedup，逐项回答：

输入如何编码？预处理由谁支付？
oracle/QRAM 是否可在所述复杂度内实现？
复杂度对 $\kappa$、rank、gap、precision 和 failure probability 如何依赖？
输出是 quantum state、一个 scalar 还是完整 classical model？
sample-and-query 模型下是否已有 dequantization？
与最强 classical randomized/approximate baseline 比较了吗？

只有这些答案同时成立，才可把子程序级 speedup 称为应用级优势。

9. 小结与习题¶

线性代数、kernel、variational、search/TDA 与 quantum-data learning 使用不同资源模型。
HHL/QSVT 的 state output、QRAM 和 condition number 是核心边界。
Dequantization 校准数据访问假设；它不否定全部 quantum learning。
Kernel 难算、模型可训练和统计泛化是三个不同命题。

推导 ridge filter $\sigma/(\sigma^2+\lambda)$。
对 $m=1000$ 的 kernel matrix 估算逐项精度 $0.01$ 所需 shots 的数量级。
证明 $\partial_{k-1}\partial_k=0$，并解释它为何使 $\ker\Delta_k$ 表示 homology。
为一个 QML 论文按第 8 节填写完整成本表。

参考文献与 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 分离。