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

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

## 1. 先写清计算模型

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

1. **显式访问：**逐项读写 $X_{ij}$；读完整数据已需 $\Omega(md)$。
2. **稀疏 oracle：**给行号和位置，可查询非零元及其列号。
3. **sample-and-query：**既能查询元素，又能按 $|X_{ij}|^2$ 分布采样。
4. **QRAM/amplitude access：**在叠加上制备 $|i\rangle|x_i\rangle$ 或 $|X\rangle$。
5. **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.
$$

典型量子流水线是：

1. 制备 $|y\rangle$ 并构造 $X$ 或正规矩阵的 block encoding；
2. 用 HHL 或 QSVT 对奇异值实施
   $$
   \sigma\mapsto\frac{\sigma}{\sigma^2+\lambda};
   $$
3. amplitude amplification 提高成功分支；
4. 只测量预测值 $\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)$，定义

$$
|\phi(x)\rangle=U_\phi(x)|0^n\rangle,
\qquad
K(x,x')=|\langle\phi(x)|\phi(x')\rangle|^2.
$$

可用 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、小训练子集或低秩近似；详细电路见[量子核方法](../ch08-qml/quantum-kernel.md)。

## 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。详见[参数化量子神经网络](../ch02-quantum-nn/quantum-neural-network.md)、[贫瘠高原](../ch02-quantum-nn/barren-plateau.md)和[VQE](../ch08-qml/vqe-tutorial.md)。

## 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 难算、模型可训练和统计泛化是三个不同命题。

1. 推导 ridge filter $\sigma/(\sigma^2+\lambda)$。
2. 对 $m=1000$ 的 kernel matrix 估算逐项精度 $0.01$ 所需 shots 的数量级。
3. 证明 $\partial_{k-1}\partial_k=0$，并解释它为何使 $\ker\Delta_k$ 表示 homology。
4. 为一个 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 分离。