# 第15章 梯度、谱方法与量子机器学习

## 引言：本章在学什么

到本章为止，我们已经见过了量子算法的主要"武器库"：相位估计把本征相位读成经典数字（第 3 章），振幅放大把成功概率 $p$ 的子过程加速到 $O(1/\sqrt{p})$ 次调用（第 3 章），QSP/QSVT 能对矩阵的奇异值施加任意多项式变换（第 5 章），HHL 类算法能输出线性方程组解的量子态（第 6 章）。本章要问的是一个更面向应用的问题：**这些武器能不能加速"学习"与"谱估计"类任务**——从函数、矩阵、张量或数据集中提取我们想要的量，例如梯度、行列式、主特征向量、隐藏的方向？

这类问题在经典计算中都是大头：训练模型要算梯度，贝叶斯推断要算对数行列式，数据分析要做 PCA，统计物理要算谱和。它们有一个共同的结构：输入是一个庞大的数学对象（$d$ 元函数、$D\times D$ 矩阵、$N^p$ 个分量的张量），输出却往往小得多（一个标量、一个方向）。量子计算机的态空间随比特数指数增长，天然适合"隐式地"携带这些大对象；问题是**提取**——我们能合法、便宜地把答案从量子态里拿出来多少？

本章汇总量子 Fourier gradient、spectral sums、经典输出 principal eigenvector、量子机器学习输入模型与 spiked tensor PCA 这五个主题（各对应一篇详细教程，见第 8 节）。与前面章节不同，本章的重点不是某一个算法的推导细节，而是三把统一的"尺子"，用它们可以丈量本章（以及文献中几乎所有量子学习算法）的每一个加速声明：

- **区分三种输出形态**：query complexity、quantum-state output 和 classical-description output——算法声称的复杂度是在哪个意义下计的？
- **区分输入访问模型**：显式数组、稀疏 oracle、sample-and-query、QRAM/幅度编码、量子样本——数据是怎么进来的，装载成本谁付？
- **端到端成本观**：把 condition number、state preparation、tomography 与 dequantization 全部计入总账，而不是只看核心子程序的复杂度。

先把历史脉络交代清楚，它与文末参考文献一一对应。2005 年 Jordan 的数值梯度估计算法（Zoo 61）是这一谱系的源头之一：它第一次展示了对维数 $d$ 的**查询复杂度无限制分离**——一次相干查询读出全部 $d$ 个梯度分量，而经典需要 $\Theta(d)$ 次。2009 年 HHL 算法（本站第 6 章）之后，量子线性代数迅速发展，催生了量子机器学习的大量提案：最小二乘、SVM、PCA、推荐系统、聚类都被改写为量子子程序的组合。2018 年起，Tang 等人的**去量子化 (dequantization)** 工作（Zoo 400–401）给这个领域校准了坐标：许多声称指数加速的算法其实暗中假设了 sample-and-query 这一数据访问模型，而同一模型下经典随机算法也能做到多项式可比——教训是**只有固定访问模型的比较才有意义**。与此同时，谱和方向有 Luongo–Shao 的系统算法（Zoo 527）与 determinant estimation 的新结果（Zoo 528）；在"必须输出经典向量"这一更严要求下，Chen–Gilyén–de Wolf 2024 年给出主特征向量经典输出的 $d^{1.5+o(1)}$ 算法（Zoo 462），并几乎匹配量子下界；张量方向有 Rebentrost 等人的 spiked tensor PCA 算法（Zoo 424），在特定弱信号模型下给出四次方的指数率改善。这些工作的共性正是本章的主题：声明的加速越来越精细，而评估它们需要的会计工作也越来越多。

**前置知识**：本章默认读者已掌握第 3 章的相位估计与振幅放大、第 5 章的 block encoding 与 QSVT、第 6 章的 HHL 与态制备基本概念。引用这些结果时我们只做简述，不重新推导。

## 1. 第一把尺子：三种输出形态

量子算法文献中最常见的误解来源，是把三种完全不同的"输出"混为一谈。我们逐一给出定义、各自的下界，以及本章哪些算法属于哪一类。

### 1.1 形态一：查询复杂度分离

在**查询模型 (query model)** 中，我们只数对预言机（oracle）的调用次数，预言机内部的实现成本不计。这是理论上最干净的复杂度度量，下界可以用信息论或多项式方法严格证明。

本章的代表是 Jordan 梯度估计（详见[量子梯度估计](gradient-estimation.md)）：估计 $d$ 元光滑函数在一点处的全部 $d$ 个偏导数，经典黑箱求值需要 $\Theta(d)$ 次查询（第 3 节给出完整下界论证），量子算法用**一次**相干相位查询加 $d$ 个单坐标逆 QFT 就能读出。这是对 $d$ 的**无限制分离 (unbounded separation)**：查询次数从随 $d$ 线性增长变成与 $d$ 无关。

但必须立刻记住查询模型不数的东西：制备 $d$ 维网格叠加要 $O(d\log N)$ 个门，$d$ 个 QFT 要 $O(d\,\mathrm{polylog}\,N)$ 个门，读出并写下 $d$ 个经典数字要 $\Omega(d)$ 次操作。**查询的分离是指数的，端到端的时间却仍是 $d$ 的多项式**——这不是矛盾，而是复杂度度量不同。评估任何"一次查询"型结果时，第一问永远是：这个预言机（把函数值相干地写进相位）在真实场景里值多少次经典求值？

### 1.2 形态二：量子态输出

第二类算法的输出本身就是一个量子态。典型流程是：把答案编码为某个矩阵变换的结果，例如线性方程组的解

$$
|x\rangle=\frac{A^{-1}|b\rangle}{\|A^{-1}|b\rangle\|},
$$

由 HHL 或 QSVT 在 $\mathrm{poly}(\kappa,\log D,1/\epsilon)$ 量级的资源下制备出来（$\kappa$ 是条件数，定义见第 5 节）。谱和算法（第 4 节）的中间步骤、tensor PCA 算法（第 6 节）的中间产物也都是量子态。

量子态输出的关键事实是：**态本身不是经典答案**。$n$ 比特的态有 $D=2^n$ 个振幅，但从这个态做一次测量只能拿到 $n$ 个经典比特；若要把全部振幅读成经典数字，就需要**层析 (tomography)**，其成本一般随维数多项式增长——高精度全层析可达 $O(D^2/\epsilon^2)$ 量级，这往往把整个加速吃回去。因此，凡是以量子态收尾的算法，都必须回答"然后呢"：

- 若下游只需要一个**标量**（某个内积 $\langle x|y\rangle$、某个可观测量期望值 $\langle x|O|x\rangle$、一个预测值），通常可以用 Hadamard test 或 swap test 以小代价读出，加速得以保留；
- 若下游坚持要**完整的经典向量**，就落入了下一小节的世界，复杂度要重新算账。

### 1.3 形态三：经典描述输出

第三类算法坚持输出 $d$ 个经典数字，例如主特征向量 $v_1\in\mathbb R^d$ 的逐坐标近似（详见[主特征向量的经典输出](principal-eigenvector.md)）。这里有一条不容谈判的地板：

$$
\text{写出 } d \text{ 个经典数字本身需要 } \Omega(d) \text{ 次操作。}
$$

这是平凡的输出下界，却界定了所有"经典描述输出"算法的最好可能：任何此类算法的运行时间至少是 $\Omega(d)$，不可能因为对数是量子算法而变成 $O(\log d)$。在这个约束下，问题的全部内容变成"在 $\Omega(d)$ 之上乘多大的因子"：经典逐元素查询矩阵的算法需要 $\Omega(d^2)$（每次查询看一个矩阵元，$d^2$ 个元里可以藏住决定主特征向量的信息），而量子算法把 matvec 做成相干操作、配合无偏层析，可以把总时间压到 $d^{1.5+o(1)}$——输出地板之上的乘法开销从 $d$ 降到约 $\sqrt{d}$，并且这个 $\sqrt{d}$ 也已被证明接近最优（第 5 节细讲）。

### 1.4 一张对照表

把本章五个主题按输出形态归位（各自的访问模型与复杂度细节见后文）：

| 主题 | 输出形态 | 核心声明 |
| --- | --- | --- |
| 梯度估计（Zoo 61） | 经典描述（$d$ 个数） | 查询 $1$ vs 经典 $\Theta(d)$；时间与输出仍 $\Omega(d)$ |
| Hessian/高阶导数（Zoo 436–439） | 经典描述（$d^2$ 或 $d^p$ 个数） | 查询 $O(d)$ vs 经典 $\Omega(d^2)$；打印仍 $\Omega(d^2)$ |
| 谱和（Zoo 527–528） | 单个标量 | 估计 $\operatorname{Tr}f(A)/D$ 到加性误差 $\epsilon$ |
| 主特征向量（Zoo 462） | 经典描述（$d$ 个数） | 时间 $d^{1.5+o(1)}$ vs 经典 $\Omega(d^2)$ |
| Tensor PCA（Zoo 424） | 量子态或少量坐标 | 指数率 $\log T_Q/\log T_C\to 1/4$（模型依赖） |

这张表已经能看出本章的会计原则：**同一列里的算法互相比较才有意义；跨列引用复杂度数字几乎必然是误导。**

## 2. 第二把尺子：输入访问模型

输出侧有了分级，输入侧同样要分级。设数据是一个 $m\times d$ 的矩阵 $X$（训练集、矩阵、张量的 flattening 都行）。常见的访问模型从弱到强依次是：

1. **显式访问**：$X$ 以普通数组形式存放在经典内存里，逐项读写 $X_{ij}$。读完整数据本身就要 $\Omega(md)$ 次操作，任何声称"对数维数"的算法在这个模型下连输入都读不完。
2. **稀疏 oracle**：$X$ 每行至多 $s$ 个非零元，预言机回答"第 $i$ 行第 $k$ 个非零元在哪一列、值是多少"。这是 Hamiltonian simulation 与 block encoding 的标准输入（第 5 章），有效复杂度随 $s$ 而非 $d$ 增长。
3. **sample-and-query**：除了查询元素，还能按 $|X_{ij}|^2$ 的比例对下标采样（行采样加行内采样）。这个模型初看是为量子态制备量身定做的，但 Frieze–Kannan–Vempala 以来的经典随机线性代数表明它也能支撑强大的**经典**算法——这正是 dequantization 的入口（第 7.3 节）。
4. **QRAM / 幅度访问**：可以在相干叠加上直接制备

$$
\frac{1}{\|X\|_F}\sum_{ij}X_{ij}|i\rangle|j\rangle
$$

这样的"幅度编码态"。这是最理想化的模型，也是多数指数加速声明的栖息地。问题在于：如果 $X$ 起初只是磁盘上的数组，把它装载成这样的量子态需要逐项扫描，成本 $\Omega(md)$，可能一次性吞掉算法主体 $\mathrm{polylog}(md)$ 的全部优势。只有在数据本身由量子过程产生、或可离线一次装载多次复用的场景，这一级才是诚实的假设。
5. **量子样本 (quantum examples)**：数据本身就是量子态 $\rho_x$（例如别的量子实验的输出），根本不存在"先读成经典表格"的免费选项。此时量子算法的优势来自保留相干性，但这条优势**不能外推**到普通经典数据集。

逐级记住一句口诀：**指数级维数优势通常出现在第 3–5 级；判断声明是否可信，先看它站在哪一级，再问这一级在你的应用里要多少钱。**本站第 7 章的[数据 QRAM 教程](../ch07-quantum-info/data-qram-tutorial.md)讨论了第 4 级的实现成本；本章各篇教程在分析具体算法时都会先声明自己的访问模型。

## 3. 案例一：梯度估计——查询分离的范本

本节把第 1.1 节的声明拆开，给出完整但紧凑的推导；更细的误差预算见[量子梯度估计](gradient-estimation.md)。

### 3.1 任务与经典下界

设 $f:\mathbb R^d\to\mathbb R$ 光滑，给定 $x_0$，要求输出梯度

$$
g=\nabla f(x_0)=\left(\frac{\partial f}{\partial x_1}(x_0),\ldots,\frac{\partial f}{\partial x_d}(x_0)\right)
$$

的全部分量，每个分量达到加性精度 $\epsilon$。经典算法只能用逐点函数值查询，标准做法是有限差分：对每个坐标 $j$ 取小步长 $h$，用 $(f(x_0+he_j)-f(x_0))/h$ 逼近第 $j$ 个偏导，共需 $d+1$ 次求值。

这不是算法不够好，而是**下界**：考虑线性函数族 $f_a(x)=a_0+a\cdot x$（未知数 $a_0\in\mathbb R$、$a\in\mathbb R^d$，共 $d+1$ 个实参数，梯度恒为 $a$）。每查询一个点 $x^{(t)}$ 得到线性方程 $a_0+\sum_j a_j x^{(t)}_j=f_a(x^{(t)})$，即对 $(a_0,a)$ 施加一个线性约束。$t$ 次查询后，可解参数集是 $\mathbb R^{d+1}$ 中余维数至多为 $t$ 的仿射子空间；只要 $t\le d$，它至少一维，其中存在两个梯度不同的函数在所有已查询点上取值相同——任何算法都无法区分。故经典需要至少 $d+1$ 次查询。**这个论证的关键前提是"每次查询只暴露一个线性方程"，它将在相干查询下失效。**

### 3.2 量子算法：一次查询编码 $d$ 个斜率

假设我们有**相位预言机**：可以在输入位置的相干叠加上施加 $|x\rangle\mapsto e^{2\pi i S f(x)}|x\rangle$（$S$ 是相位尺度，由数值预言机经 phase kickback 转换而来，细节见专篇）。算法三步：

第一步，每个坐标分配一个 $n$ 比特寄存器（$N=2^n$ 个格点，用中心化整数 $z_j\in\{-N/2,\ldots,N/2-1\}$ 标记），Hadamard 制备 $d$ 维网格均匀叠加

$$
\frac{1}{N^{d/2}}\sum_{z\in\mathbb Z_N^d}|z\rangle,
$$

其中基矢 $|z\rangle$ 代表物理位置 $x(z)=x_0+\frac hN z$，$h$ 是网格物理半径。

第二步，一次相位查询。对每个格点做 Taylor 展开（$g=\nabla f(x_0)$，余项 $R(z)$ 由 Hessian 界控制）：

$$
f(x(z))=f(x_0)+\frac hN\, g\cdot z+R(z).
$$

代入相位并用指数把加法变乘法（线性项 $g\cdot z=\sum_j g_j z_j$ 是各坐标之和，故其指数分解为各坐标相位之积），取 $S=\frac{N}{hG_0}$（$G_0$ 是编码单位，量级取梯度范围 $G$），一阶项在第 $j$ 个坐标上的相位恰为 $2\pi z_j g_j/G_0$。暂时忽略余项因子，查询后的态为

$$
e^{2\pi i S f(x_0)}\;\bigotimes_{j=1}^d\left(\frac{1}{\sqrt N}\sum_{z_j}e^{2\pi i z_j g_j/G_0}|z_j\rangle\right).
$$

两点观察：常数项 $f(x_0)$ 只贡献不可观测的全局相位，自动被丢弃；态**完全因子化**为 $d$ 个单坐标平面波，第 $j$ 个的频率正是 $g_j/G_0$。一次查询把 $d$ 个斜率同时写进 $d$ 个寄存器，查询数与 $d$ 无关的全部秘密就在这个因子化里。

第三步，对每个坐标寄存器各自做逆 QFT 并测量。单坐标的输出振幅是等比求和给出的 Dirichlet 核，当 $g_j/G_0$ 不落在 Fourier 格点上时仍以高概率（$\ge 8/\pi^2$）四舍五入到最近整数 $k_j$，按 $\widetilde g_j=G_0 k_j/N$ 解码。这一步的正确性正是相位估计的标准分析（第 3 章），不再重证。

### 3.3 误差预算与保留条款

算法有三个可调参数（$h$、$N$、$S=N/(hG_0)$）与三类误差，互相牵制：

- Fourier 离散化：解码步长 $G_0/N$，要求 $N\gtrsim G_0/\epsilon$；
- 非线性：Taylor 余项扰动相位，按最坏情形 $\|z\|^2=O(dN^2)$ 放缩得到约束 $S h^2 d\,\|\nabla^2 f\|\ll 1$；
- 预言机舍入：若函数值定点表示误差为 $\eta$，要求 $S\eta\ll 1$。

第二、三项之间存在两难：减小 $h$ 改善 Taylor 近似，但由 $S=N/(hG_0)$ 会成反比地收紧对预言机精度的要求。把 $N\sim G/\epsilon$ 代入第二项，解出可行尺度

$$
h\sim\frac{\epsilon}{dM},\qquad S\sim\frac{dM}{\epsilon^2},\qquad \eta\ll\frac{\epsilon^2}{dM},
$$

其中 $M:=\|\nabla^2 f\|$。也就是说，在这一直接分析下，预言机的数值精度要按 $\epsilon^{-2}$ 收紧——**精度成本被转嫁到了预言机身上**。

这里必须保留原文的"启发式/模型依赖"条款并解释清楚：约束中的 $d$ 因子来自把 $\|z\|^2$ 按最坏情形放缩（所有坐标同时取最大位移），这是过度悲观的；更精细的分析利用平均意义的光滑性、高阶有限差分模板与相位调度（Zoo 436–439），可以改善这个 $d$ 依赖，并使对 $1/\epsilon$ 的依赖相对早期分析得到平方量级的改善。但严格的端到端复杂度始终与所假设的光滑性模型绑定——**光滑性承诺本身就是复杂度的一部分**，这一点在第 7 节的方法论中还会回来。

## 4. 案例二：谱和——一个标量背后的尺度换算

谱和问题（详见[谱和与行列式](spectral-sums.md)）在形式上换了个方向：给维数 $D=2^n$ 的 Hermitian 矩阵 $A$（稀疏 oracle 或 block encoding 访问），不求单个本征值，而是估计

$$
\operatorname{Tr}f(A)=\sum_{j=1}^D f(\lambda_j),
$$

例如 $f=\log$ 给出对数行列式、$f(x)=-x\log x$ 给出 von Neumann 熵、$f(x)=x^p$ 给出 Schatten $p$-范数的 $p$ 次幂、$f(x)=1/x$ 给出逆迹。这是本章中输出最小的任务——**一个标量**——因此也是"读出瓶颈"最轻的任务；它的全部微妙之处在**尺度**。

### 4.1 为什么必须先归一化

定义归一化谱和

$$
s_f(A)=\frac{1}{D}\operatorname{Tr}f(A)=\mathbb E_{j\sim U[D]}[f(\lambda_j)],
$$

即把本征值看作均匀随机变量后期望 $f$。量子算法自然估计的是 $s_f$ 到加性误差 $\epsilon$；由原式乘以 $D$，原谱和的误差是 $D\epsilon$。这不是技术细节而是根本约束：若应用需要原谱和的绝对误差为 $1$（例如精确的整数计数），就必须取 $\epsilon=1/D$——对 $D=2^n$ 而言是指数小的精度，通常意味着指数昂贵。因此文献中"superpolynomial in dimension"式的谱和加速，对应的都是 **normalized/additive 的承诺**，而不是精确整数谱和。读任何谱和结果，先做这道乘法。

### 4.2 两条量子路线

**路线一：maximally mixed 本征值采样。** 制备 $n$ 对 Bell 态

$$
|\Phi\rangle=D^{-1/2}\sum_{x=0}^{D-1}|x\rangle|x\rangle,
$$

只对第一个寄存器做关于 $e^{iAt}$ 的相位估计。写谱分解 $A=\sum_j\lambda_j|u_j\rangle\langle u_j|$，第一个寄存器的约化态是

$$
I/D=\frac1D\sum_j|u_j\rangle\langle u_j|
$$

（第一步是 Bell 态的标准性质：对 maximally entangled 态求偏迹得 maximally mixed 态；第二步是因为对任何正交归一基都有 $\sum_j|u_j\rangle\langle u_j|=I$）。于是相位估计以精确均匀的概率 $1/D$（按重数计）输出各个本征值；对输出 $\widetilde\lambda$ 经典地算 $f(\widetilde\lambda)$，$M$ 次重复后平均：

$$
\widehat s_f=\frac1M\sum_{r=1}^M f(\widetilde\lambda_r).
$$

若 $|f|\le B$，Hoeffding 不等式要求 $M=O(B^2/\epsilon^2)$ 才能把 Monte Carlo 误差压到 $\epsilon$；若 $f$ 可相干计算，改用振幅估计把依赖改善到 $O(B/\epsilon)$ 次调用——这正是 Grover 二次加速在"估计一个均值"上的体现。相位估计的分辨率要细到 $|f(\lambda)-f(\widetilde\lambda)|\lesssim\epsilon$，本征值精度与 $f$ 的 Lipschitz 常数挂钩。

**路线二：QSVT + maximally entangled expectation。** 若有 $A/\alpha$ 的 block encoding，选多项式 $p$ 在谱区间上一致逼近 $f(\alpha x)/B$，QSVT 构造出 $f(A)/B$ 的近似 block。然后用恒等式

$$
\langle\Phi|\,(f(A)\otimes I)\,|\Phi\rangle=\frac1D\operatorname{Tr}f(A)
$$

把归一化迹变成一个可观测量期望值，用 Hadamard test 或振幅估计读出。这个恒等式值得完整证一遍，因为它是"纠缠把迹变成振幅"的标准技巧。把 $|\Phi\rangle$ 的定义代入，利用内积的双线性：

$$
\langle\Phi|(f(A)\otimes I)|\Phi\rangle
=\frac1D\sum_{x,y}\langle x|f(A)|y\rangle\,\langle x|y\rangle.
$$

第一步只是把两个求和写开：左矢取 $\langle\Phi|=D^{-1/2}\sum_x\langle x|\langle x|$，右矢取 $D^{-1/2}\sum_y|y\rangle|y\rangle$，算子 $f(A)\otimes I$ 分别作用在两边寄存器上，得到矩阵元 $\langle x|f(A)|y\rangle$ 与 $\langle x|I|y\rangle=\langle x|y\rangle$ 的乘积。第二步用正交归一性 $\langle x|y\rangle=\delta_{xy}$ 消去一重求和：

$$
=\frac1D\sum_x\langle x|f(A)|x\rangle=\frac1D\operatorname{Tr}f(A),
$$

最后一步正是迹的定义（任意正交归一基下对角元之和）。Q.E.D. 多项式次数由 $f$ 的光滑性、谱区间与逼近误差决定；对 $1/x$、$\log x$ 这类在区间端点有奇性的函数，次数会带上条件数 $\kappa$ 或 $\log\kappa$（奇性越靠近谱区间，多项式逼近越贵——这与第 5 章 QSP 的逼近论一致）。

### 4.3 小例子：尺度换算手算一遍

取 $D=3$ 的对角矩阵 $A=\operatorname{diag}(4,2,1)$（对角矩阵使谱一目了然，论证对一般情形不变）。本征值即 $4,2,1$。对 $f=\log$（自然对数）：

$$
\log\det A=\log 4+\log 2+\log 1=\log 8\approx 2.079,
\qquad
s_{\log}(A)=\frac{2.079}{3}\approx 0.693.
$$

设算法把 $s_{\log}$ 估到 $\epsilon=0.01$。乘回 $D=3$：$\log\det A$ 的误差为 $D\epsilon=0.03$，于是行列式本身只确定到乘性区间

$$
\det A\in\left[8e^{-0.03},\,8e^{0.03}\right]\approx[7.76,\,8.24],
$$

即约 $\pm 3\%$ 的相对不确定度——对 $D=3$ 尚可接受。但同一个 $\epsilon=0.01$ 放到 $D=2^{20}\approx 10^6$ 的矩阵上：$\log\det$ 的误差是 $D\epsilon\approx 10^4$，行列式的乘性不确定度是 $e^{\pm 10^4}$，**估计完全失去意义**。反过来，若应用坚持要行列式的 $(1\pm\eta)$ 相对精度，取对数后要求 $\log\det$ 的绝对误差 $O(\eta)$，即归一化误差 $O(\eta/D)$——随维数指数缩小的精度要求。这就是为什么实践中更常直接需要 per-dimension 的量 $\ell=\frac1D\log\det A$（例如贝叶斯模型的逐维对数证据），而不是行列式本身。另有一条保留条款：以上以正定（PSD）矩阵为主；非 PSD 矩阵的行列式还含符号/复相位，需要分别估计负本征值个数或改用奇异值。

### 4.4 应用速查

- **图谱**：图 Laplacian $L$ 的非零本征值 $\lambda_2,\ldots,\lambda_n$ 由 matrix-tree 定理给出生成树计数 $\tau(G)=\frac1n\prod_{j\ge2}\lambda_j$，取对数化为谱和 $\log\tau(G)=\sum_{j\ge2}\log\lambda_j-\log n$（零本征值需投影排除）；三角形计数 $\#\triangle=\operatorname{Tr}(A_G^3)/6$ 是多项式谱和。
- **熵与范数**：密度矩阵的 von Neumann 熵 $S(\rho)=-\operatorname{Tr}(\rho\log\rho)$、Schatten 范数 $\|A\|_p^p=\operatorname{Tr}|A|^p$、逆迹 $\operatorname{Tr}A^{-1}$ 都是 $s_f$ 的特例；小本征值端点处的行为（cutoff、rank 承诺、条件数）决定难度。
- **经典对照**：经典的随机迹估计（Hutchinson 型）用随机向量与矩阵-向量乘积，成本可以低于平方级；诚实的比较应按"一次 matvec 的成本 × 次数"进行，而不是默认经典只能 $O(D^3)$ 对角化。

## 5. 案例三：主特征向量的经典输出——读出瓶颈的正面交锋

前两个案例分别展示了"查询分离"与"标量输出"。本节面对最硬的组合（详见[主特征向量的经典输出](principal-eigenvector.md)）：**要一个 $d$ 维向量的完整经典描述**。这里量子态输出的捷径被堵死，第 1.3 节的 $\Omega(d)$ 输出地板生效，问题的内容是地板之上的因子。

### 5.1 幂方法：完整推导

设 $A\in\mathbb C^{d\times d}$ Hermitian，本征值 $\lambda_1>\lambda_2\ge\cdots$，对应正交归一本征矢 $v_1,v_2,\ldots$。假设 top eigengap 有已知下界（$\lambda_1/\lambda_2$ 与 $1$ 拉开常数差距；gap 任意小时主特征向量对微扰不稳定，任何算法的复杂度都必须含 $1/\Delta$ 因子）。目标：输出经典向量 $\widetilde v$，在不可消除的全局相位自由度下逼近 $v_1$：

$$
\min_{|\omega|=1}\|\widetilde v-\omega v_1\|_2\le\epsilon.
$$

经典**幂方法 (power method)** 从任意 $x_0=\sum_j c_j v_j$（$c_1\neq 0$）出发，迭代 $x_t=A^t x_0/\|A^t x_0\|$。分析只需把 $x_0$ 按本征基展开并利用 $A^t v_j=\lambda_j^t v_j$（本征矢的定义）：

$$
A^t x_0=\sum_j c_j\lambda_j^t v_j
=\lambda_1^t\left(c_1 v_1+\sum_{j>1}c_j\left(\frac{\lambda_j}{\lambda_1}\right)^t v_j\right).
$$

第二步提出最大本征值的幂。由于 $|\lambda_j/\lambda_1|<1$（$j>1$），括号中除 $c_1v_1$ 外的所有项都按几何速度衰减；归一化不影响方向，故 $x_t$ 收敛到 $v_1$。定量地，利用 $\{v_j\}$ 的正交归一性（交叉项消失，$\|\sum_j w_j v_j\|^2=\sum_j|w_j|^2$），次要分量的总功率为

$$
\left\|\sum_{j>1}c_j\left(\frac{\lambda_j}{\lambda_1}\right)^t v_j\right\|^2
=\sum_{j>1}|c_j|^2\left|\frac{\lambda_j}{\lambda_1}\right|^{2t}
\le(1-|c_1|^2)\left|\frac{\lambda_2}{\lambda_1}\right|^{2t},
$$

最后一步用了 $\sum_{j>1}|c_j|^2=1-|c_1|^2$（$x_0$ 归一）与 $|\lambda_j/\lambda_1|\le|\lambda_2/\lambda_1|$。于是方向误差（到 $\pm v_1$ 的距离）的量级为

$$
\frac{\sqrt{1-|c_1|^2}}{|c_1|}\left|\frac{\lambda_2}{\lambda_1}\right|^t.
$$

两个因子各管一件事：比值 $|\lambda_2/\lambda_1|^t$ 是**每轮的收缩率**，由谱隙控制；前置因子 $1/|c_1|$ 是**初始重叠的代价**。随机取单位向量时，它与任何固定方向的重叠满足 $|c_1|\sim d^{-1/2}$（随机方向在 $d$ 维空间中近似均匀地分摊单位功率）。

现在展示参数求解：要求误差 $\le\epsilon$，对上式取对数（常数 relative gap 下 $\log(\lambda_1/\lambda_2)=\Theta(1)$）：

$$
\left|\frac{\lambda_2}{\lambda_1}\right|^t\le\frac{\epsilon\,|c_1|}{\sqrt{1-|c_1|^2}}
\quad\Longrightarrow\quad
t\ge\frac{\log\!\big(\sqrt{1-|c_1|^2}/(\epsilon|c_1|)\big)}{\log(\lambda_1/\lambda_2)}
=\Theta\!\left(\log\frac{\sqrt d}{\epsilon}\right)=O\!\left(\log\frac{d}{\epsilon}\right).
$$

也就是说，$d$ 只以**对数**进入迭代次数——幂方法本身的收敛很快；瓶颈不在迭代次数，而在每轮的成本：经典 dense matvec 要触碰 $d^2$ 个矩阵元，一轮就已触及整个输入，总时间 $\widetilde O(d^2)$。

**小例子（手算 $t$）**：取 $A=\begin{pmatrix}2&1\\1&2\end{pmatrix}$，$v_1=(1,1)/\sqrt2$、$\lambda_1=3$；$v_2=(1,-1)/\sqrt2$、$\lambda_2=1$。从 $x_0=(1,0)=(v_1+v_2)/\sqrt2$ 出发（$|c_1|=1/\sqrt2$），上面的误差公式给出 $(1/3)^t$。要求 $\epsilon=0.01$：解 $(1/3)^t\le 0.01$，即 $t\ge\log 100/\log 3\approx 4.19$，取 $t=5$。验证：$A^5 x_0=\frac1{\sqrt2}(3^5 v_1+v_2)=\frac1{\sqrt2}(243\,v_1+v_2)$，次要分量占比 $1/243\approx 0.004<0.01$，确已达标。

### 5.2 量子化：为什么态 matvec 不够，缺的是什么

有了 block encoding，一次"量子 matvec"可以实现 $|x\rangle\mapsto A|x\rangle/\|Ax\|$（经振幅放大提升成功分支）。如果下一轮迭代只需要量子态，这看起来已经够了。**真正的障碍在终点**：最终要的是 $d$ 个经典坐标，而从态到坐标需要层析。朴素地在末轮做高精度全层析，成本回到 $d^2/\epsilon^2$ 量级，加速归零。

Chen–Gilyén–de Wolf（Zoo 462）的出路基于两点观察：

- **幂方法对噪声鲁棒，但只对"良性"噪声鲁棒。** 若每轮的 matvec 误差是零均值（无偏）的独立噪声，谱隙的收缩作用会把旧误差逐轮压低，误差不会累积；若是固定方向的偏差（adversarial bias），每轮都往同一个错方向推，误差线性累积。这解释了"unbiased"一词为何是算法设计的核心——**不要求每轮精确，只要求每轮没有系统性偏差**。
- **无偏层析可以比精确层析便宜。** 用 time-efficient unbiased pure-state tomography，每轮输出一个满足 $\mathbb E[\widehat y]\approx y$ 的随机经典估计 $\widehat y$（方差可控、尾界适合鲁棒分析），归一化后进入下一轮。单轮不要求达到最终精度 $\epsilon$。

最终算法（对常数 gap 与常数最终误差）以总时间

$$
d^{3/2+o(1)}
$$

显式输出全部 $d$ 个坐标。这个数字的结构值得拆读：$\Omega(d)$ 是第 1.3 节的输出地板，乘上的约 $\sqrt d$ 来自量子内积/层析相对经典逐项读取的平方根级节省。另一方面，经典算法需要 $\Omega(d^2)$ 次 entry 查询（对手可以把决定主特征向量的低秩微扰藏进 $d^2$ 个矩阵元中的任何位置），量子下界为 $\widetilde\Omega(d^{3/2})$——所以该算法**接近最优**，也证明了不可能仅因输出是 $d$ 个数就做到 $O(d)$ 次查询。推广到 top-$q$ 子空间：维护 $d\times q$ 的经典正交基、量子加速每列 matvec，成本为 $q\cdot d^{3/2+o(1)}$，另含相邻本征值 gap 与再正交化的开销。

## 6. 案例四：Spiked tensor PCA——两次平方根

最后一个案例（详见[Tensor PCA](tensor-pca.md)）展示当问题的"谱定理"本身失效时量子算法能做什么。矩阵 PCA 由幂方法解决（第 5 节），但高阶张量没有同样简单的谱定理。考虑 order-$p$ 对称张量的 **spiked 模型**

$$
T=\lambda v^{\otimes p}+G,
\qquad
v\in\mathbb R^N,\ \|v\|=\sqrt N,
$$

其中 $G$ 是适当归一化的 Gaussian 噪声，$\lambda$ 是信号强度（经典谱方法起作用的区间常写 $\lambda=\alpha N^{-p/4}$；归一化约定会改变表面阈值，比较结果时必须先对齐）。目标不是逐项恢复 $v$，而是输出与 $v$ 有非消失 overlap 的估计 $\widehat v$：$|\langle\widehat v,v\rangle|/(\|\widehat v\|\|v\|)\ge c>0$。

量子构造（Zoo 424）把张量系数改写为 $N$ 个玻色 mode 上、固定总玻色数 $n_{\mathrm{bos}}$ 的多体 Hamiltonian

$$
H(T)=\sum_{i_1,\ldots,i_p}T_{i_1\ldots i_p}\,
a_{i_1}^\dagger\cdots a_{i_{p/2}}^\dagger a_{i_{p/2+1}}\cdots a_{i_p}
$$

（$p$ 为偶数；略去归一化）。若 $T=\lambda v^{\otimes p}$，令 $b_v^\dagger=\frac1{\sqrt N}\sum_i v_i a_i^\dagger$，则信号部分含 $(b_v^\dagger)^{p/2}(b_v)^{p/2}$——它偏好玻色子聚集在未知 mode $v$ 上，噪声则形成随机多体背景。算法流水线：在固定玻色数 sector（维数 $D=\binom{N+n_{\mathrm{bos}}-1}{n_{\mathrm{bos}}}$，即 $n_{\mathrm{bos}}$ 个 $N$ 维 qudit 的对称子空间）制备初态；模拟 $e^{-itH(T)}$；相位估计标记信号主导的谱窗；振幅放大提升落入该窗口的小振幅；最后测量一体约化密度矩阵 $\Gamma_{ij}=\langle a_i^\dagger a_j\rangle/n_{\mathrm{bos}}$，其主特征向量估计 $v$。

相对经典谱方法的两个二次增益各有一处明确来源：

- **Hamiltonian simulation** 在 $D$ 维对称空间中隐式演化，从不显式保存或逐项乘那个 $N^{p/2}\times N^{p/2}$ 的 flattening 矩阵；
- **振幅放大**把命中信号子空间的重复次数从 $1/p_{\mathrm{hit}}$ 降为 $1/\sqrt{p_{\mathrm{hit}}}$（第 3 章）。

在固定弱信号比例、适当取 $n_{\mathrm{bos}}$ 的渐近分析中，论文得到 $\log T_Q/\log T_C\to 1/4$：量子运行时间的指数率约为对应经典谱方法的四分之一（"两次平方根"），同时量子空间为多项式。**保留条款必须说清楚**：这是对**特定经典谱算法族与 oracle 模型**的比较结果，不是对所有经典算法的无条件四次方下界；结论依赖 Gaussian 噪声模型与归一化约定；且 $n_{\mathrm{bos}}$ 随 $\lambda^{-1}$ 多项式增长，弱信号下运行时间仍可能指数。$p=2$ 的 sanity check：单玻色 sector 中 $a_i^\dagger a_j$ 就是 $|i\rangle\langle j|$，$H(T)$ 退化为矩阵 $T$ 本身，算法还原为普通 PCA。

**小例子（对称子空间维数）**：取 $N=4$、$n_{\mathrm{bos}}=3$。固定玻色数 sector 的维数由"stars and bars"给出（把 3 个不可分辨玻色子放进 4 个 mode）：

$$
D=\binom{4+3-1}{3}=\binom{6}{3}=\frac{6\cdot5\cdot4}{3\cdot2\cdot1}=20.
$$

对照：3 个可分辨 qudit 的空间是 $4^3=64$ 维，对称性把它压到 20 维——量子算法正是在这个仍然很大的隐式空间里做谱分析。

## 7. 第三把尺子：端到端成本核算方法论

四个案例过完，现在把贯穿其中的会计方法提炼成清单。

### 7.1 成本清单

对任何量子学习/谱算法的加速声明，逐项回答：

- **输入如何编码？** 访问模型在第 2 节五级中的哪一级？预处理与装载由谁支付？
- **oracle 可实现吗？** 相位预言机、block encoding、QRAM 各自要求在所述复杂度内可构造；把函数值相干写进相位、把矩阵做成 block，都不是免费操作。
- **隐参数依赖如何？** 复杂度表达式中 condition number $\kappa$、rank、谱隙 $\Delta$、光滑性界 $M$、精度 $\epsilon$、失败概率 $\delta$ 各以什么幂次出现？早期"指数加速"声明常把多项式甚至指数级的 $\kappa$、$1/\epsilon$ 依赖藏进记号。
- **输出是什么形态？** 量子态、单个标量，还是 $d$ 个经典数字？形态决定读出成本的下限（第 1 节）。
- **同模型下有经典对手吗？** 特别是 sample-and-query 模型下的 dequantization（下一小节）。
- **比较的 baseline 是最强经典算法吗？** 与对角化比是没意义的，若经典随机算法用同样的访问模型就能做到多项式可比。

### 7.2 参数平衡的通用手法

本章多处出现的"取某参数使两项同阶"值得作为一个方法记住。一般形态是：总成本 $C(r)=A r^a+B r^{-b}$（$r$ 是可调参数，$a,b>0$），两项分别随 $r$ 增、减。最优在两项同阶处取得：令 $A r^a=B r^{-b}$，解出

$$
r_*=\left(\frac{B}{A}\right)^{1/(a+b)},\qquad C(r_*)=O\!\left(A^{b/(a+b)}B^{a/(a+b)}\right).
$$

第 3.3 节的两难正是这个结构：Taylor 误差随 $h$ 以 $h^2$ 下降，预言机精度要求随 $h$ 以 $1/h$ 上升；把 $N\sim G/\epsilon$ 代入约束 $N h d M/G\lesssim 1$ 解出 $h\sim\epsilon/(dM)$，其余参数随之确定。第 5.1 节解 $t$、谱和算法中取相位估计分辨率使 $|f(\lambda)-f(\widetilde\lambda)|\lesssim\epsilon$，都是同一只手法的实例：**先把每一项误差写成参数的显式函数，再联立求解，而不是背结论。**

### 7.3 Dequantization：校准访问模型的镜子

Tang 的推荐系统工作及后续（Zoo 400–401）给出的结论常被误读，值得准确陈述：**若量子算法只使用 sample-and-query 访问模型，则存在使用同一模型的经典随机算法，以多项式可比的成本完成（低秩结构下的）同样任务。**证明的思想是经典随机线性代数（按重要性采样行/列，在低维草图上做全部计算），与量子算法的数学结构惊人地平行——某种意义上，量子算法提示了经典算法的存在。

正确读法是：

- 它**不**否定量子机器学习。基于量子样本（第 2 节第 5 级）、基于稀疏 oracle 的 Hamiltonian 问题、查询模型中的分离（第 3 节），都不受影响；
- 它**改变举证责任**：声称指数优势的一方必须说明为什么对手不能用同一访问模型做经典采样；
- 它提供了最实用的审计问题——"把 QRAM 换成采样数据结构，经典算法能走多远？"如果答案是很远，那么量子优势至多多项式，要按多项式加速的标准（常数、可实现的 oracle、端到端时间）重新评估。

### 7.4 一条总原则

把第 1–2 节合起来，得到本章最重要的一句话：**量子学习算法的复杂度 =（访问模型的实现成本）+（核心子程序的查询/门成本）+（按输出形态计的读出成本），三者必须同账计算；任何只报中间一项的加速声明都是未完成态。**

## 8. 章节导览

本章五篇教程按第 1 节的输出形态与第 2 节的访问模型组织，建议按以下顺序阅读：

- [量子梯度估计](gradient-estimation.md)：查询复杂度分离的范本。Jordan 算法的完整推导、Dirichlet 核读出分析、三类误差的参数配平，以及与变分算法中参数平移法的本质区别。
- [谱和与行列式](spectral-sums.md)：标量输出的代表。maximally mixed 相位估计与 QSVT 两条路线，log-determinant、熵、Schatten 范数，以及 normalized 与 absolute 精度之间的 $D$ 倍换算。
- [主特征向量的经典输出](principal-eigenvector.md)：读出瓶颈的正面交锋。鲁棒幂方法、量子 matvec、无偏层析，以及 $d^{3/2+o(1)}$ 为何接近最优。
- [量子机器学习算法谱系](machine-learning-zoo.md)：访问模型与端到端审计的全景。线性代数型学习、量子核、变分模型、拓扑数据分析，附完整成本清单。
- [Tensor PCA](tensor-pca.md)：谱方法失效处的前沿。spiked tensor、bosonic Hamiltonian 编码与"两次平方根"的来源与边界。

```{toctree}
:maxdepth: 1

gradient-estimation
spectral-sums
principal-eigenvector
machine-learning-zoo
tensor-pca
```

## 9. 小结与习题

**小结：**

- 评估量子学习/谱算法要用三把尺子：输出形态（查询复杂度 / 量子态 / 经典描述）、输入访问模型（五级）、端到端成本（装载 + 子程序 + 读出）。
- 梯度估计给出对 $d$ 的查询无限制分离（$1$ vs $\Theta(d)$），但门数与经典输出仍是 $\Omega(d)$；精度成本被转嫁给预言机，严格复杂度与光滑性承诺绑定。
- 谱和算法估计 $s_f=\operatorname{Tr}f(A)/D$ 到加性 $\epsilon$；乘回 $D$ 的换算决定 logdet 等应用的诚实精度，Monte Carlo $O(B^2/\epsilon^2)$ 可由振幅估计改善到 $O(B/\epsilon)$。
- 主特征向量的经典输出中，幂方法的迭代数只含 $O(\log(d/\epsilon))$，瓶颈在每轮 matvec 与末轮读出；无偏层析使总时间 $d^{3/2+o(1)}$ 成为可能并接近量子下界 $\widetilde\Omega(d^{3/2})$。
- Tensor PCA 的"四次方"指数率来自 Hamiltonian simulation 与振幅放大各一次平方根，结论依赖噪声模型、归一化与比较对象。
- Dequantization 的教训：只有固定访问模型的比较才有意义；sample-and-query 模型下的多项式经典对手是每一次指数声明的必答题。

**习题：**

1. （归类）把以下五个任务分别归入第 1 节的三种输出形态，并各写出一个"平凡下界"：(a) Jordan 梯度估计；(b) HHL 输出 $|x\rangle$；(c) 谱和 $\operatorname{Tr}f(A)/D$；(d) 主特征向量的 $d$ 坐标经典近似；(e) tensor PCA 中输出与 $v$ 的 overlap。哪些任务的读出成本可能成为主导项？
2. （尺度换算）取 $A=\operatorname{diag}(4,2,1)$（$D=3$）。(i) 计算 $\log\det A$ 与 $s_{\log}(A)$；(ii) 若 $s_{\log}$ 被估到 $\epsilon=0.01$，行列式的乘性不确定区间是什么？(iii) 同一 $\epsilon$ 下，$D$ 多大时行列式的相对不确定度超过 $10\%$？（提示：解 $D\epsilon\approx\ln 1.1$。）
3. （推导）证明对 maximally entangled 态 $|\Phi\rangle=D^{-1/2}\sum_x|x\rangle|x\rangle$ 与任意算子 $B$ 有 $\langle\Phi|(I\otimes B)|\Phi\rangle=\frac1D\operatorname{Tr}B$（注意与第 4.2 节中算子位置不同），并由此说明 $\langle\Phi|(B\otimes C)|\Phi\rangle=\frac1D\operatorname{Tr}(B C^T)$ 中 $C^T$ 的来历。
4. （参数求解）幂方法中设 $\lambda_1=5$、$\lambda_2=4$、初始重叠 $|c_1|=0.1$、目标 $\epsilon=0.01$。用第 5.1 节的误差公式求最小整数迭代次数 $t$，并代入 $A^t x_0$ 的展开式验证。（提示：误差 $\approx\frac{\sqrt{1-0.01}}{0.1}(4/5)^t$，取对数求解。）
5. （访问模型判断）对以下三个声称，各判断其访问模型属于第 2 节哪一级，并评估加速声明的诚实性：(a) "我们的数据集是磁盘上的 $10^6\times 10^6$ 稀疏矩阵，量子算法运行时间是维数的对数"；(b) "输入是另一台量子设备输出的态 $\rho_x$，我们用 collective measurement 分类"；(c) "假设有 QRAM 提供幅度编码，推荐系统的采样复杂度与维数无关"——对 (c) 还需回答：dequantization 对这个声明说了什么？
6. （综合审计）某论文声称："对 $d$ 元损失函数，我们的量子优化器每次迭代只需 $O(1)$ 次查询（经典需 $\Theta(d)$），因此训练加速是维数指数的。"按第 7.1 节清单逐项审计这个声明：它用的输出形态是什么？梯度预言机在该论文的应用场景里如何实现？把门数、读出与预言机构造计入后，"指数加速"的哪些部分仍然成立、哪些不成立？

## 参考文献

本章各主题的详细文献与完整 Zoo 覆盖列表见五篇专篇教程的文末；此处汇总与正文历史脉络对应的条目，编号与链接与各专篇一致。

- Zoo 编号 61：Stephen Jordan, [Fast Quantum Algorithm for Numerical Gradient Estimation](https://arxiv.org/abs/quant-ph/0405146)（梯度估计的源头，2005）。
- Zoo 436--439：precision/smoothness、Gevrey/general polynomial 与 complex spectral gradient/Hessian 改进；Zoo 20、62、94：basin hopping、quadratic minima/高阶 derivatives 与 classical lower bound。
- Zoo 编号 527：Luongo 与 Shao, [Quantum Algorithms for Spectral Sums](https://arxiv.org/abs/2011.06475)（谱和的系统算法，2020）。
- Zoo 编号 528：Giovannetti、Lloyd 与 Maccone 关于 determinant estimation 的 2025 算法。
- Zoo 编号 462：Chen、Gilyén 与 de Wolf, [A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix](https://arxiv.org/abs/2405.14765)（主特征向量经典输出，2024）。
- Zoo 编号 424：Rebentrost、Hamoudi、Ray、Wang、Chakraborty 与 Lloyd, [Quantum algorithms for the tensor principal component problem](https://arxiv.org/abs/1907.12724)（spiked tensor PCA，2019）。
- 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（dequantization，2018 起）。
- Zoo 编号 428：在复杂度假设下具有 classical hardness 的 quantum kernel construction。
- Zoo 编号 222、487--490：quantum topological data analysis、Betti numbers 与后续资源/限制分析；Zoo 489--490：量子数据学习与相关 sample-complexity 分离。