# 量子梯度估计：Phase Kickback、$d$ 维逆 QFT 与高阶导数

数值优化是科学计算中最常见的任务之一：训练一个机器学习模型要最小化损失函数，拟合一个物理模型要最小化残差，求解变分问题要最小化能量。几乎所有一阶优化方法（梯度下降及其无数变体）的每一步都需要知道目标函数在当前点的**梯度 (gradient)**

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

其中 $f:\mathbb R^d\to\mathbb R$ 是一个光滑的标量函数，$x_0\in\mathbb R^d$ 是当前迭代点。当 $f$ 没有解析表达式、只能通过某种"黑箱"求值（例如 $f$ 的值来自一次昂贵的数值模拟或一次实验测量）时，经典算法的标准做法是**有限差分 (finite difference)**：对每个坐标 $j$ 单独取一个小步长 $h$，用

$$
\frac{\partial f}{\partial x_j}(x_0)\approx\frac{f(x_0+h e_j)-f(x_0)}{h}
$$

逼近第 $j$ 个偏导数，其中 $e_j$ 是第 $j$ 个坐标方向的单位矢量。$d$ 个坐标方向各需要至少一次额外的函数求值，因此恢复整个梯度至少需要 $d+1$ 次查询。当维数 $d$ 很大时（现代机器学习中 $d$ 可以是 $10^6$ 甚至更高），这个随维数线性增长的查询开销成为一阶方法的瓶颈。

2005 年，Stephen Jordan 提出了一个引人注目的量子算法（Zoo 编号 61）：如果函数求值由一个**相干量子预言机**提供，那么只需**一次**查询就能同时读出全部 $d$ 个梯度分量——查询次数与维数 $d$ 完全无关。核心思想可以一句话概括：在 $x_0$ 附近的一个 $d$ 维网格的均匀叠加上查询一次函数，函数在 $x_0$ 附近的线性 Taylor 项会变成每个坐标寄存器上的一个相位因子 $e^{2\pi i z_j g_j/G_0}$，而这恰好是 Fourier 基矢的形状；再对每个坐标做一次逆量子 Fourier 变换（inverse QFT），就能把斜率 $g_j$ 逐个"解码"到计算基上测量出来。这本质上是相位估计思想在数值分析中的一次直接应用：QFT 是相位信息的读出装置，而梯度被巧妙地编码进了相位。

需要立刻强调的是，"一次查询"并不等于"成本与 $d$ 无关"：

- 制备 $d$ 维网格叠加、逐坐标做 QFT、最后测量并读出 $d$ 个经典数字，这些**门操作与输出成本仍然随 $d$ 增长**（至多多项式地快于经典有限差分的整体运行时间）；
- 一次查询必须把整个 $d$ 维输入的函数值**相干地**写进相位，这比经典黑箱求值强得多，不是所有应用场景都能提供；
- 算法对预言机的数值精度、函数的光滑性都有明确要求，精度 $\epsilon$ 越小，对预言机的要求越高。

因此 Jordan 算法给出的是**查询复杂度 (query complexity)** 意义上的指数级（对 $d$ 而言）分离，而不是端到端运行时间的指数加速。后续工作（Zoo 436–439）改进了精度与光滑性假设下的分析，Gilyén–Arunachalam–Wiebe 等人用高阶有限差分与更精细的相位调度把精度依赖相对早期分析做了平方量级的改善；同一思想还延伸到 Hessian 矩阵学习、高阶导数张量估计与谱方法（Zoo 20、62、94）。本教程从经典下界讲起，逐步推导 Jordan 算法的每一步，逐项分析误差预算，最后讨论二次型/Hessian 学习、高阶导数推广，以及它与变分量子算法中参数平移法的本质区别。

**前置知识**：本教程默认读者已掌握量子 Fourier 变换与相位估计（本站第 3 章），知道 QFT 把相位 $e^{2\pi i \omega k}$ 编码的叠加态映回频率 $|k\rangle$ 附近；我们不再重新推导 QFT 本身。

:::{admonition} 本课知识点
:class: tip

1. **[数值预言机与相位预言机](#oracle-forms)**——能写出两种预言机的定义，并用 Fourier 态上的 phase kickback 推导从数值预言机获得相位预言机，说明后者比经典黑箱求值强在哪里。
2. **[经典查询下界](#classical-query-lower-bound-gradient-estimation)**——能对线性函数族证明经典算法恢复梯度至少需要 $d+1$ 次查询（含适应性选点），并解释相干叠加查询为何不受该下界约束。
3. **[网格叠加与可分离相位](#separable-taylor-phase)**——能从 Taylor 展开推导一次相位查询后的态因子化为 $d$ 个单坐标平面波的乘积，并解释编码单位 $G_0$、相位尺度 $S=N/(hG_0)$ 的取法与全局相位被丢弃的原因。
4. **[逆 QFT 读出与解码](#inverse-qft-readout)**——能用等比数列求和推导 Dirichlet 核振幅公式，写出解码式 $\widetilde g_j=G_0k_j/N$ 与符号回绕规则，并说明 $d$ 个坐标同时读出时查询成本与门/输出成本如何分开记账。
5. **[误差预算与参数平衡](#error-budget)**——能列出 Fourier 离散化、非线性、预言机舍入三类误差并推导各自约束，进而构造 $h$、$N$、$S$、$\eta$ 的一组可行尺度，解释减小 $h$ 的两难。
6. **[二次型与 Hessian 学习](#hessian-learning)**——能用 $d+1$ 次梯度查询恢复对称矩阵 $A$ 与线性项 $b$，并对照经典 $\Omega(d^2)$ 下界说明查询意义上的平方分离与输出成本的边界。
7. **[高阶导数与谱方法](#higher-derivatives-spectral)**——能解释梯度 oracle 如何逐层递归估计 $p$ 阶导数张量（$O(d^{p-1})$ 次查询），并说明谱微分观点与"采样→QFT→乘频率→读出"流水线的对应。
8. **[与参数平移法的区别](#parameter-shift-comparison)**——能从 oracle 访问模型、每分量成本与适用场景三个维度比较 Jordan 梯度估计与参数平移法，并对给定问题判断该用哪一个。

:::

## 1. Oracle 与目标

(oracle-forms)=
### 1.1 两种等价的预言机形式

算法通过预言机访问函数 $f$。第一种是**数值预言机 (value oracle)**，以定点数 (fixed-point) 形式把函数值可逆地写入加法寄存器：

$$
O_f|x,z\rangle
=|x,z\oplus\widetilde f(x)\rangle,
$$

其中 $\widetilde f(x)$ 是 $f(x)$ 按某个定点格式舍入后的二进制表示，$\oplus$ 表示按位异或（或模加法）。这是"可逆计算"意义下最自然的黑箱求值：任何能经典高效计算的函数都能以可逆线路的形式实现这样的预言机，代价是若干辅助比特。

第二种是**相位预言机 (phase oracle)**，直接把函数值编码为相位：

$$
|x\rangle\mapsto
e^{2\pi iS f(x)}|x\rangle,
$$

其中 $S>0$ 是我们选择的**相位尺度 (phase scale)**，量纲是 $1/f$ 的量纲，作用是把这个无量纲化的相位角调到合适的范围。

两种形式通过本站已熟悉的 **phase kickback** 技巧互相转换。具体地，先对加法寄存器制备 Fourier 态

$$
|\chi\rangle=\frac1{\sqrt M}\sum_{y=0}^{M-1}e^{-2\pi i S y/M}|y\rangle
$$

（$M$ 是加法寄存器能表示的格点数），再用数值预言机把 $\widetilde f(x)$ 加进去：

$$
|x\rangle|\chi\rangle
\;\xrightarrow{\;O_f\;}\;
\frac1{\sqrt M}\sum_y e^{-2\pi i S y/M}|x,\,y\oplus\widetilde f(x)\rangle
=e^{2\pi iS\widetilde f(x)/M}|x\rangle|\chi'\rangle,
$$

最后一步是因为平移 $y\mapsto y+\widetilde f(x)$ 只是把求和指标整体搬动，$|\chi\rangle$ 作为 Fourier 基矢在平移下只拾取一个相位——这正是"加法群的特征标被平移算子对角化"这一事实，与相位估计中受控-$U$ 把本征相位踢回控制寄存器是同一种机制。加法寄存器前后不变（仍是一个 Fourier 态，可复位复用），净效果就是相位预言机。因此下文一律假设我们有相位预言机可用，并把 $S$ 吸收进相位尺度的定义中。

### 1.2 任务与前提条件

**任务**：在点 $x_0$ 处输出梯度

$$
g=\nabla f(x_0)
$$

的全部分量，每个分量 $g_j$ 达到加性精度 $\epsilon$，即输出 $\widetilde g_j$ 满足 $|\widetilde g_j-g_j|\le\epsilon$。

仅有黑箱求值而没有对 $f$ 的任何承诺，梯度是不可学习的（函数可以在任意小的尺度上剧烈振荡）。算法需要以下前提，它们在误差分析中会逐一登场：

- **梯度范围已知**：存在常数 $G$ 使 $|g_j|\le G$ 对所有分量成立。这让相位编码的"频率窗口"有界，否则一个分量就能占满整个 Fourier 谱。
- **局部光滑性**：在以 $x_0$ 为中心、半径 $h$（网格的物理半径，见第 2 节）的区域内，$f$ 的 Hessian（二阶导数矩阵）有界，记为 $\|\nabla^2 f\|$（算子范数，即最大方向曲率）。这控制 Taylor 展开中二阶余项的大小。更精细的分析会用更高阶导数界或平均意义的光滑性，见第 4 节。

(classical-query-lower-bound-gradient-estimation)=
### 1.3 经典查询下界：$d+1$

在给出量子算法之前，先严格说明为什么经典算法至少需要 $d+1$ 次查询。看最简单的线性函数族

$$
f_a(x)=a_0+a\cdot x,
$$

参数为未知矢量 $a\in\mathbb R^d$ 与标量 $a_0\in\mathbb R$，共 $d+1$ 个未知实参数。这个函数族的梯度恒为 $\nabla f_a=a$，所以"估计梯度"等价于"确定 $a$"。

每查询一次某点 $x^{(t)}$ 的函数值，我们得到一个关于未知数的线性方程

$$
a_0+\sum_{j=1}^d a_j x^{(t)}_j=f_a(x^{(t)}),
$$

即对 $(a_0,a)$ 施加了一个线性约束。$t$ 次查询后，可解集是 $\mathbb R^{d+1}$ 中余维数至多为 $t$ 的仿射子空间。即使允许**适应性 (adaptive)** 选点（后面的查询点依赖前面的答案），$t\le d$ 次查询后这个子空间仍然至少是一维的：其中存在方向 $(\delta_0,\delta)\neq0$，沿它扰动参数不改变任何已查询点的函数值，却把梯度 $a$ 改变了 $\delta$。也就是说，两个梯度不同的函数在所有被查询的点上取值完全相同，任何算法都无法区分它们。因此经典确定性（或随机化，经标准的 minimax/Yao 原理论证）算法要恢复梯度，**至少需要 $d+1$ 次查询**。

这个下界只针对"逐点查询函数值"这一访问模型。Jordan 算法的突破在于换了一个访问模型：允许对输入位置做**相干叠加查询**。下界论证中"每次查询只暴露一个线性方程"的前提被打破了——一次相干查询可以在指数多个格点的叠加上同时写入相位，下界不再适用。

## 2. 网格叠加与 Taylor phase

本节完成算法的第一步：制备网格叠加，并通过一次相位查询把梯度写进可分离的相位。

### 2.1 网格与叠加态

每个坐标分配一个 $n$ 比特寄存器，共 $N=2^n$ 个格点。为了让网格关于 $x_0$ 对称，用**中心化整数**标记格点：

$$
z_j\in\left\{-\frac N2,\,-\frac N2+1,\,\ldots,\,\frac N2-1\right\}.
$$

（在电路上，$z_j$ 以二进制补码形式存储；中心化只是数学记号，目的是让正、负位移共用同一套格点，简化后面符号的处理。）$d$ 个坐标的寄存器合起来标记 $d$ 维网格点 $z=(z_1,\ldots,z_d)\in\mathbb Z_N^d$。

第一步，把每个坐标寄存器从 $|0\rangle$ 经 Hadamard 变换制备成均匀叠加（按中心化记号重写），张量积给出 $d$ 维网格上的均匀叠加态

$$
\frac1{N^{d/2}}
\sum_{z\in\mathbb Z_N^d}|z\rangle.
$$

这一步需要 $O(nd)$ 个单比特门，与第 3 节的 QFT 成本一样属于"随 $d$ 线性增长"的部分。

第二步，把格点标签 $z$ 映到实际采样位置。取物理步长 $h/N$（$h$ 是网格的物理半径），定义

$$
x(z)=x_0+\frac hN\,z,
$$

即第 $j$ 个坐标为 $x_0+\frac hN z_j\,e_j$。这个映射 $z\mapsto x(z)$ 本身不需要额外查询——它只决定我们"声称"每个基矢代表哪个位置；真正实现是在相位预言机内部把 $f$ 求值在 $x(z)$ 上。为书写方便，下文直接把相位查询写成在 $|z\rangle$ 上施加相位 $e^{2\pi i S f(x(z))}$。

网格上有 $N^d$ 个点，每个点距 $x_0$ 至多为 $\frac hN\|z\|\le h\sqrt d/2$。注意这个网格的点数是 $d$ 的指数，但我们从未逐个访问它们——它们以振幅 $N^{-d/2}$ 均匀地叠加在量子态里。

(separable-taylor-phase)=
### 2.2 Taylor 展开：线性项的分离

在每个格点上对 $f$ 做关于 $x_0$ 的 Taylor 展开。带二阶余项的形式为

$$
f(x(z))
=f(x_0)+\frac hN\, g\cdot z
+O\!\left(\frac{h^2}{N^2}\|z\|^2\,\|\nabla^2f\|\right),
$$

其中 $g=\nabla f(x_0)$，内积 $g\cdot z=\sum_j g_j z_j$。逐项说明三个部分的来历：

- 第零项 $f(x_0)$：展开点的函数值，与 $z$ 无关；
- 一阶项 $\frac hN g\cdot z$：位移矢量 $x(z)-x_0=\frac hN z$ 与梯度的内积，这是 Taylor 定理的一阶项 $f(x_0+\delta)=f(x_0)+\nabla f(x_0)\cdot\delta+\cdots$ 代入 $\delta=\frac hN z$ 的结果；
- 二阶余项：Taylor 定理给出的量级是 $\frac12\delta^T\nabla^2f(\xi)\,\delta$（$\xi$ 是线段上某点），用算子范数放缩为 $O(\|\delta\|^2\|\nabla^2f\|)=O(\frac{h^2}{N^2}\|z\|^2\|\nabla^2f\|)$。这就是第 1.2 节要求 Hessian 有界的原因。

记余项为 $R(z)$。现在对叠加态施加一次相位预言机查询，每个基矢拾取相位 $e^{2\pi i S f(x(z))}$。把 Taylor 展开代入指数，利用指数函数把加法变乘法：

$$
e^{2\pi i S f(x(z))}
=\underbrace{e^{2\pi i S f(x_0)}}_{\text{常数}}
\cdot\prod_{j=1}^d e^{2\pi i S\,\frac hN g_j z_j}
\cdot e^{2\pi i S R(z)}.
$$

关键观察是线性项 $g\cdot z=\sum_j g_j z_j$ 是各坐标的**和**，所以它的指数分解成各坐标相位的**乘积**——这就是"separable phase"的含义。定义**编码单位** $G_0$（一个与 $g_j$ 同量纲的常数，稍后由误差预算确定，大致取为梯度范围 $G$ 的量级），并选择相位尺度

$$
S=\frac{N}{hG_0},
$$

则一阶项中第 $j$ 个坐标的相位恰好是

$$
2\pi S\frac hN g_j z_j=2\pi\,\frac{g_j}{G_0}\,z_j.
$$

$S$ 的这个取法是刻意设计的：$S\cdot\frac hN=\frac1{G_0}$ 把物理步长与相位尺度对消，使相位只依赖无量纲比值 $g_j/G_0$。于是一次查询后（暂时忽略余项因子 $e^{2\pi i S R(z)}$，第 4 节再处理它）态近似为

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

两点说明：

- **全局相位 $e^{2\pi iS f(x_0)}$ 不可观测**：它与 $z$ 无关，是整个态的共同相位，测量任何可观测量都看不到它。常数项 $f(x_0)$ 因此被自动丢弃——这正是我们想要的，因为梯度不含 $f(x_0)$ 的信息。
- **态完全因子化**：它是 $d$ 个单坐标态的张量积，第 $j$ 个因子里只含 $g_j$。每个坐标态是"频率"为 $g_j/G_0$ 的平面波，而平面波正是 QFT 的基矢。一次查询同时把 $d$ 个斜率写进了 $d$ 个寄存器的相位里，这就是查询数与 $d$ 无关的全部秘密。

### 2.3 直觉：为什么这样做是对的

在继续形式化推导之前，用一句话收拢直觉。相位估计告诉我们：如果一个酉算子以 $|k\rangle$ 为本征矢、本征相位为 $e^{2\pi i\omega k}$，那么在叠加 $\sum_k e^{2\pi i\omega k}|k\rangle$ 上做逆 QFT 就能把 $\omega$ 读出来。这里的处境完全一样，只是"酉算子的本征相位"换成了"函数在相邻格点间的相位增量"：沿第 $j$ 个坐标每走一格，相位增加 $2\pi g_j/G_0$，增量正比于斜率 $g_j$。函数值的黑箱被转换成一台"相位合成器"，梯度越大，波形振荡越快；QFT 就是频谱分析仪，一次性报出每个坐标上的振荡频率。Taylor 展开保证在网格尺度 $h$ 内波形确实近似是单频的，余项 $R(z)$ 是频率的轻微抖动——第 4 节的误差预算就是控制这个抖动不破坏频谱读出。

## 3. 逆 QFT 读出全部分量

(inverse-qft-readout)=
### 3.1 单坐标的精确分析

固定一个坐标 $j$，暂时省略下标。该寄存器的态为

$$
|\phi\rangle=\frac1{\sqrt N}\sum_{z=-N/2}^{N/2-1}e^{2\pi i\omega z}|z\rangle,
\qquad \omega:=\frac{g_j}{G_0}.
$$

对它做 $N$ 点逆 QFT（采用中心化约定），再测量。输出为整数 $k$ 的振幅是

$$
\widetilde a(k)=\frac1N\sum_{z=-N/2}^{N/2-1}e^{2\pi i(\omega-k/N)z}.
$$

这是一个等比数列求和，公比 $r=e^{2\pi i(\omega-k/N)}$。用等比公式 $\sum_{z}r^z=r^{z_{\min}}\frac{1-r^N}{1-r}$（$r\neq1$ 时），分子 $r^N=e^{2\pi i(N\omega-k)}=e^{2\pi iN\omega}$ 与 $k$ 无关，故振幅的模为

$$
|\widetilde a(k)|
=\frac1N\left|\frac{\sin\big(\pi N(\omega-k/N)\big)}{\sin\big(\pi(\omega-k/N)\big)}\right|
=\frac1N\left|\frac{\sin(\pi N\omega-\pi k)}{\sin\big(\pi(\omega-k/N)\big)}\right|,
$$

第一步用了恒等式 $|1-e^{i\theta}|=2|\sin(\theta/2)|$ 分别作用于分子分母。这是标准的 Dirichlet 核：当 $\omega$ 恰好等于某个 $k_j/N$ 时，$k=k_j$ 处 $r=1$，求和退化为 $N$ 项同相相加，$\widetilde a(k_j)=1$——测量必然给出 $k_j$。当 $\omega$ 不落在格点上时，振幅集中在离 $\omega$ 最近的整数 $k$ 附近，旁瓣按 $1/|k-k_j|$ 衰减；与相位估计中相同的界给出：以高概率（例如 $\ge 8/\pi^2\approx 0.81$），测得的 $k$ 是 $\omega N$ 四舍五入的结果。

若 $g_j/G_0\approx k_j/N$，测量后按

$$
\widetilde g_j=\frac{G_0\,k_j}{N}
$$

解码。由于 $\omega=g_j/G_0$ 可正可负，而 QFT 输出的是模 $N$ 的整数，需要处理**符号回绕 (signed wrap-around)**：中心化约定下 $k$ 本来取值在 $\{-N/2,\ldots,N/2-1\}$；若电路输出的是 $0$ 到 $N-1$ 的无符号整数 $k'$，则把 $k'>N/2$ 的结果解释为负数 $k=k'-N$。这就是为什么第 1.2 节要求梯度范围 $|g_j|\le G$：取 $G_0\ge 2G$（留出一倍余量），可以保证 $|\omega|\le1/2$，正负斜率不会跨越 $\pm N/2$ 的边界互相混淆。

### 3.2 $d$ 个坐标同时读出

由于查询后的态是 $d$ 个单坐标平面波的张量积（第 2.2 节），对每个坐标寄存器**各自**做 $QFT_N^{-1}$，整个操作同样是张量积结构：

$$
\bigotimes_{j=1}^d QFT_N^{-1}
\left(\frac1{\sqrt N}\sum_{z_j}e^{2\pi iz_jg_j/G_0}|z_j\rangle\right)
\approx\bigotimes_{j=1}^d|k_j\rangle,
\qquad k_j\approx\frac{Ng_j}{G_0}.
$$

一次计算基测量同时给出 $(k_1,\ldots,k_d)$，逐分量解码即得全部梯度分量。单坐标 QFT 的门数为 $O(n^2)=O(\log^2N)$（用快速 QFT 线路；近似 QFT 可降到 $O(\log N\log\log N)$ 量级），$d$ 个坐标合计

$$
O\!\left(d\,\operatorname{polylog}N\right)
$$

个门，测量与经典解码同样只需 $O(d)$ 次操作。所以"一次查询读出 $d$ 个数"**不违反**任何输出下界：查询模型只数预言机调用次数，而写出 $d$ 个经典数字本身就需要 $\Omega(d)$ 时间。量子优势体现在预言机查询从 $\Theta(d)$ 降到 $1$，门与时间复杂度仍是 $O(d\,\operatorname{polylog}N)$。

### 3.3 一个可手算的小例子

取 $d=1$、$N=4$，格点 $z\in\{-2,-1,0,1\}$。设函数在 $x_0$ 附近恰为线性 $f(x)=f(x_0)+g\,(x-x_0)$，且斜率恰好使得 $\omega=g/G_0=1/4$（即 $k=1$，恰在 Fourier 格点上）。忽略全局相位后，相位查询给出的态为

$$
|\phi\rangle=\frac12\sum_{z=-2}^{1}e^{2\pi i z/4}|z\rangle
=\frac12\Big(e^{-\pi i}|-2\rangle+e^{-\pi i/2}|-1\rangle+|0\rangle+e^{\pi i/2}|1\rangle\Big)
=\frac12\Big({-}|-2\rangle-i|-1\rangle+|0\rangle+i|1\rangle\Big).
$$

按第 3.1 节的公式计算逆 QFT 后输出 $k$ 的振幅 $\widetilde a(k)=\frac14\sum_z e^{2\pi i(1/4-k/4)z}$：

- $k=1$：公比为 $1$，$\widetilde a(1)=\frac14\cdot4=1$；
- $k=0$：公比为 $e^{\pi i/2}$，逐项相加 $\sum_{z}e^{\pi i z/2}=e^{-\pi i}+e^{-\pi i/2}+1+e^{\pi i/2}=-1-i+1+i=0$，故 $\widetilde a(0)=0$；
- $k=-1$（即 $k=3 \bmod 4$）：$\sum_z e^{\pi i z}=1-1+1-1=0$，振幅为零；
- $k=2$：公比为 $e^{-\pi i/2}$，$\sum_z e^{-\pi i z/2}=e^{\pi i}+e^{\pi i/2}+1+e^{-\pi i/2}=-1+i+1-i=0$，同样为零。

测量以概率 $1$ 给出 $k=1$，解码 $\widetilde g=G_0\cdot 1/4=g$，一次查询精确命中。若斜率改为 $\omega=0.3$（不在格点上），同一公式给出 $|\widetilde a(1)|^2=\frac1{16}\left|\frac{\sin(4\pi\cdot0.3-\pi)}{\sin(\pi(0.3-0.25))}\right|^2=\frac1{16}\left|\frac{\sin(0.2\pi)}{\sin(0.05\pi)}\right|^2\approx\frac1{16}\left(\frac{0.588}{0.156}\right)^2\approx0.88$，即约 $88\%$ 的概率落在最近格点 $k=1$ 上，其余概率散在旁瓣。这演示了"非格点频率仍以高概率四舍五入到最近整数"的结论。

再验证第 2.2 节的因子化：取 $d=2$、$f$ 线性、斜率 $(g_1,g_2)$，查询后相位为 $e^{2\pi i(z_1g_1+z_2g_2)/G_0}=e^{2\pi iz_1g_1/G_0}\cdot e^{2\pi iz_2g_2/G_0}$，整个态是两个寄存器的张量积，两次独立的单坐标 QFT 各读出各的斜率，互不干扰。

(error-budget)=
## 4. 误差预算与参数平衡

算法有 $h$（网格物理半径）、$N$（每坐标格点数）、$S=N/(hG_0)$（相位尺度）三个可调参数，以及预言机自身的精度。误差来自三个互相牵制的来源，我们逐项分析，最后展示如何把参数配平。

### 4.1 三类误差

**第一类：Fourier 离散化误差。** 解码公式 $\widetilde g_j=G_0 k_j/N$ 的输出步长是 $G_0/N$：即使其他误差全为零，四舍五入也引入至多 $G_0/(2N)$ 的偏差。要达到加性精度 $\epsilon$，需要

$$
\frac{G_0}{N}\lesssim\epsilon,
\qquad\text{即}\qquad
N\gtrsim\frac{G_0}{\epsilon}.
$$

这一项决定格点数 $N$ 的下限，从而决定每个坐标寄存器的比特数 $n=\log_2N\approx\log_2(G_0/\epsilon)$。

**第二类：非线性误差。** 第 2.2 节忽略的余项因子 $e^{2\pi iSR(z)}$ 会轻微扰动每个格点的相位，使单频波形"抖动"。用 Taylor 余项 $R(z)=O(\frac{h^2}{N^2}\|z\|^2\|\nabla^2f\|)$ 与 $\|z\|^2\le dN^2/4$（最坏情形），相位扰动的量级为

$$
S\,|R(z)|
\lesssim \frac{N}{hG_0}\cdot\frac{h^2}{N^2}\cdot dN^2\,\|\nabla^2f\|
=S\,h^2 d\,\|\nabla^2f\|,
$$

其中代入了 $\|z\|^2=O(dN^2)$。要保证扰动远小于一个相位周期、不破坏 QFT 的相干求和，需要

$$
S\,h^2 d\,\|\nabla^2f\|\ll1.
$$

注意上式中 $d$ 的因子来自 $\|z\|^2$ 按最坏情形的放缩（所有坐标同时取最大位移）。更精细的分析指出这是过度悲观的：随机选取方向上的余项平均来说小得多，利用平均意义的光滑性或更高阶导数界可以改善这个 $d$ 依赖——这是原文保留的"启发式/模型依赖"条款，严格的端到端复杂度与所假设的光滑性模型绑定。

**第三类：预言机数值误差。** 相位预言机实际编码的是舍入值 $\widetilde f$，若 $|\widetilde f-f|\le\eta$，则每个格点引入附加相位误差 $2\pi S\eta$。同样要求它远小于一个周期：

$$
S\eta\ll1.
$$

这一项是纯预言机性质：相位尺度 $S$ 越大（编码越灵敏），对函数值定点表示的精度要求越高，即 $\eta$ 必须小于 $1/S$ 的量级。

### 4.2 参数平衡：为什么 $h$ 不能随意取

第二、三类误差暴露了一个两难：**减小 $h$** 使网格更局域、Taylor 近似更好（第二类误差 $\propto h^2$ 下降），但由 $S=N/(hG_0)$，$h$ 减小使 $S$ 成反比增大，从而**放大**对预言机精度的要求（第三类误差 $\propto S$ 上升）。反之亦然。这就是原文"减小 $h$ 抑制 Taylor error，却增大 $S$ 并要求更精确 value oracle"的含义。

把三类约束联立，可以演示一组可行的参数配平。记 $M:=\|\nabla^2f\|$，并取 $G_0=\Theta(G)$。由第一类约束取最小的 $N\sim G/\epsilon$。把 $S=N/(hG)$ 代入第二类约束：

$$
\frac{N}{hG}\cdot h^2 d M=\frac{NhdM}{G}\ll1
\quad\Longrightarrow\quad
h\ll\frac{G}{NdM}\sim\frac{\epsilon}{dM}.
$$

于是可行取法是 $h\sim\epsilon/(dM)$（差常数因子），相应的相位尺度为

$$
S=\frac{N}{hG}\sim\frac{G/\epsilon}{G\cdot\epsilon/(dM)}=\frac{dM}{\epsilon^2},
$$

预言机精度需满足 $\eta\ll1/S\sim\epsilon^2/(dM)$。这组尺度说明：梯度估计的精度 $\epsilon$ 越小，预言机数值精度按 $\epsilon^{-2}$ 收紧（在这一直接分析下）——预言机精度成为算法的主要瓶颈之一。

**改进。** Gilyén–Arunachalam–Wiebe 等工作（Zoo 436–439）系统优化了这一分析：用**高阶有限差分**模板替代朴素的线性 Taylor 项（消去低阶余项，让有效光滑阶数更高），配合更精细的**相位调度 (phase schedules)** 与概率放大，使复杂度对精度 $1/\epsilon$ 的依赖相对早期分析得到**平方量级**的改善；若函数满足更强的 Gevrey 类或解析 (analytic) 光滑性假设，高阶余项可以被进一步控制，从而换取更优的参数折中。这些改进不改变"一次查询读出 $d$ 个分量"的基本结构，改的是误差预算的配平点。

## 5. 复杂度总览

把各成本来源并列，可以看清"指数分离"究竟发生在哪个复杂度度量里：

- **预言机查询**：量子 $1$ 次（加常数倍的重复以提高成功概率），经典 $\Theta(d)$ 次——这是对 $d$ 的无限制分离；
- **门操作**：网格制备 $O(nd)$，$d$ 个 QFT 共 $O(d\,\operatorname{polylog}N)$，其中 $n=\log_2N=O(\log(G/\epsilon))$；
- **经典输出**：写出 $d$ 个梯度分量本身就是 $\Omega(d)$；
- **预言机内部成本**：相位预言机要在叠加态上对所有 $N^d$ 个格点相干地求值 $f$，其实现成本取决于 $f$ 本身的可计算性，不计入查询模型。

结论：Jordan 算法在**查询复杂度**上把对 $d$ 的依赖从线性降到零，而端到端运行时间仍是 $d$ 的多项式（因为要输出 $d$ 个数）。第 1.3 节的经典下界与量子算法不矛盾，因为两者基于不同的访问模型。评估实际应用价值时，必须问清三件事：所需的相干相位预言机能否以低于经典 $d$ 次求值的成本实现？精度预算（第 4 节）是否可行？最终需要的是全部 $d$ 个分量的经典描述，还是一个内积/方向等低维信息（后者可能有更省的办法）？

(hessian-learning)=
## 6. Quadratic form 与 Hessian 学习

梯度 oracle 一旦建成（即第 2–3 节的整体流程封装为一个子程序），就可以作为更高级学习任务的积木。最重要的例子是二次型。设

$$
f(x)=\tfrac12x^TAx+b^Tx+c,\qquad A=A^T,
$$

其中 $A\in\mathbb R^{d\times d}$ 是对称矩阵（Hessian 处处等于 $A$），$b\in\mathbb R^d$，$c\in\mathbb R$。直接求导：

$$
\nabla f(x)=Ax+b.
$$

（验证：第 $j$ 个分量 $\partial_j f=\frac12\sum_k(A_{jk}+A_{kj})x_k+b_j=\sum_kA_{jk}x_k+b_j$，用了对称性 $A_{jk}=A_{kj}$。）

对二次型，梯度是仿射函数，差商恰好消去 $b$：在 $d$ 个坐标基矢点 $e_j$ 处各做一次梯度查询，与 $x=0$ 处的结果相减，

$$
\nabla f(e_j)-\nabla f(0)=(Ae_j+b)-b=Ae_j,
$$

而 $Ae_j$ 正是 $A$ 的第 $j$ 列。于是：

- $1$ 次梯度查询（在 $x=0$）得到 $b$；
- 再做 $d$ 次（在 $e_1,\ldots,e_d$）并相减，逐列得到整个 $A$。

每次梯度查询内部只用 $O(1)$ 次函数相位查询，故总共 $O(d)$ 次 value-oracle 查询就能提取 $A$ 的全部 $d^2$ 个矩阵元（由对称性独立元为 $d(d+1)/2$ 个）。作为对照，经典的黑箱函数值学习需要 $\Omega(d^2)$ 次查询：粗略地说，$d$ 阶多项式族的二阶系数有 $\Theta(d^2)$ 个自由度，每次函数求值只提供一个线性方程，论证与第 1.3 节平行。Yao 下界对相应的经典查询模型给出严格的**平方级分离**（$\Omega(d^2)$ 对 $O(d)$）。

同样必须声明输出成本：打印 $A$ 的 $d^2$ 个矩阵元需要 $\Omega(d^2)$ 的经典时间，优势仅在**查询**而非打印。这个区分决定了应用方式：

- 若 $A\succ0$（正定），二次型的最小值点是

$$
x_*=-A^{-1}b,
$$

学出 $A,b$ 后可经典求解（适合 $d$ 不大、但需要省函数求值的场景）；
- 或者不把 $A$ 打印出来，而是把学得的 Hessian 信息结合量子线性方程组算法（如 HHL 类，见本站第 6 章）直接输出解的量子态 $|x_*\rangle$，绕开经典描述的成本——但此时引入条件数、态制备与读出等新的端到端考量。

(higher-derivatives-spectral)=
## 7. 高阶导数与 spectral 方法

同一思想可向两个方向推广。

**高阶导数张量。** 梯度的第 $j$ 个分量 $\partial_j f$ 本身仍是 $\mathbb R^d$ 上的标量函数，对它再跑一遍梯度估计就得到二阶导数行 $(\partial_1\partial_jf,\ldots,\partial_d\partial_jf)$。递归地逐层施加，或用多维相位多项式一次性编码，可以估计 $p$ 阶导数张量

$$
\partial_{j_1}\cdots\partial_{j_p}f(x_0)
$$

的全部 $d^p$ 个分量。在固定阶数 $p$ 与相应光滑性承诺（$p+1$ 阶导数有界）下，所需 value-oracle 查询约为

$$
O(d^{\,p-1})
$$

次：$p=1$ 时退化为 Jordan 的 $O(1)$，$p=2$ 时为 $O(d)$（与第 6 节二次型/一般 Hessian 学习一致）。同样地，输出 $d^p$ 个经典数字需要相应的时间，查询优势与输出成本要分开记账。

**谱微分观点。** 更系统的看法（Zoo 436–439 中的 spectral gradient/Hessian 方法）是把有限差分模板视为**三角/多项式谱微分 (spectral differentiation)**：在等间距网格上，微分算子在 Fourier 基下是对角的（乘以频率），所以"函数值网格采样 → QFT → 乘以频率 → 读出"这条流水线与谱方法求导的结构逐一对上；QFT 一次提取多个频率成分，恰好对应梯度的多个分量。这个视角把 Jordan 算法安置在经典数值分析的谱方法谱系里，也解释了为什么光滑性（谱衰减）直接决定精度。

**复值函数的注意事项。** 上述谱方法可以处理复值 $f$，但此时预言机的定义必须说清楚：相位预言机 $|x\rangle\mapsto e^{2\pi iSf(x)}|x\rangle$ 只有在 $f$ 取实值时才是酉的——复函数的虚部会使"相位"带上模长衰减，不能作为物理上的全局相位。处理复值函数需要改用数值预言机加受控旋转等显式构造，并在复杂度中计入相应成本。

(parameter-shift-comparison)=
## 8. 与 parameter-shift 的区别

学过变分量子算法（本站第 2 章）的读者会问：[参数平移法](../ch02-quantum-nn/parameter-shift-appendix.md)也能用少量测量给出梯度，和 Jordan 算法是什么关系？两者的前提与结论完全不同，不能互相替代。

参数平移法针对的函数形如

$$
f(\theta)=\langle\psi|U(\theta)^\dagger\,O\,U(\theta)|\psi\rangle,
$$

即量子线路期望值对线路参数的依赖。它利用 generator 只有少数几个特定本征值（例如单比特旋转的生成元本征值为 $\pm1/2$）这一结构，把 $f$ 对某个参数 $\theta_j$ 的依赖归结为有限频率的三角多项式，于是**两个**移位点处的期望值 $\frac{f(\theta_j+s)-f(\theta_j-s)}{2\sin s}$ 就精确给出该分量的导数。但每换一个参数 $\theta_j$ 都要重新跑线路、重新估计两个期望值，$d$ 个参数需要 $\Theta(d)$ 组测量；且它假设 $f$ 本来就是一台量子计算机产生的期望值，根本不存在"在输入位置上做叠加"的自由度。

Jordan 梯度估计则假设一个强得多的访问模型：可以**在输入位置的相干叠加上**查询整个标量函数预言机，一次相位查询同时编码所有坐标方向的斜率，再用 $d$ 维逆 QFT 一次返回全部坐标 slopes。

结论：硬件上的变分量子算法 (VQA) 通常并不提供这种强预言机——损失函数只能通过制备含参态、测量期望值来访问，正是参数平移法的场景；那里不能用"一次查询"替代 $d$ 组参数平移测量。反过来，若有经典的黑箱函数可被相干求值（如可逆数值模拟），参数平移法无从下手，Jordan 算法才有用武之地。选择方法的第一步永远是先厘清手头的 oracle 访问模型。

## 9. 小结

- 一次相位查询把 $x_0$ 附近的线性 Taylor 项变成 $d$ 个可分离的 Fourier 相位，第 $j$ 个坐标的相位频率正比于 $g_j/G_0$。
- 对每个坐标做逆 QFT 同时解码全部梯度分量；查询数与 $d$ 无关，但网格制备、QFT 与经典输出的门/时间成本仍至少线性于 $d$，因此不违反输出下界。
- 网格半径 $h$、格点数 $N$ 与预言机精度 $\eta$ 三者需联合平衡：Fourier 离散化要求 $N\gtrsim G_0/\epsilon$，非线性要求 $Sh^2d\|\nabla^2f\|\ll1$，预言机舍入要求 $S\eta\ll1$，且减小 $h$ 会以 $S=N/(hG_0)$ 为代价收紧对预言机的要求。
- 二次型/Hessian 学习用 $O(d)$ 次查询提取 $d^2$ 个矩阵元，相对经典 $\Omega(d^2)$ 有查询上的平方分离，但完整经典输出仍消耗 $\Omega(d^2)$ 时间；$p$ 阶导数张量约需 $O(d^{p-1})$ 次查询。
- 与参数平移法的根本区别在于 oracle 访问模型：能否在输入位置上做相干叠加查询，决定了两者的适用场景。

## 练习题

**练习 1【数值预言机与相位预言机】**（→ [1.1 节](#oracle-forms)）

1. 写出数值预言机 $O_f|x,z\rangle=|x,z\oplus\widetilde f(x)\rangle$ 与相位预言机 $|x\rangle\mapsto e^{2\pi iSf(x)}|x\rangle$ 的作用方式，并说明相位尺度 $S$ 的量纲与作用。
2. 补全 phase kickback 推导：先对加法寄存器制备 Fourier 态 $|\chi\rangle=\frac1{\sqrt M}\sum_{y=0}^{M-1}e^{-2\pi iSy/M}|y\rangle$，再施加 $O_f$，验证寄存器内容只是被平移 $y\mapsto y+\widetilde f(x)$、净效果为拾取相位 $e^{2\pi iS\widetilde f(x)/M}$，并说明加法寄存器为什么可以复位复用。

> 提示：对求和指标做换元 $y'=y+\widetilde f(x)$（模 $M$），求和范围不变。

**练习 2【经典查询下界】**（→ [1.3 节](#classical-query-lower-bound-gradient-estimation)）

1. 对线性函数族 $f_a(x)=a_0+a\cdot x$，说明"估计梯度"为什么等价于"确定 $d+1$ 个未知参数"，并写出一次函数值查询所施加的线性约束。
2. 第 1.3 节证明了经典需要 $d+1$ 次查询。把该论证推广：若允许每次查询返回 $f$ 在一点处的函数值**和**任意一个偏导数值，下界会变成多少？由此解释"每次查询的信息量"如何决定分离的程度。

> 提示：这样一次查询给出关于未知数的两个独立线性方程。

**练习 3【网格叠加与可分离相位】**（→ [2.2 节](#separable-taylor-phase)）

1. 写出 $d$ 维网格上的均匀叠加态与位置映射 $x(z)=x_0+\frac hN z$，并指出归一化因子与制备成本各是多少。
2. 证明：取 $S=N/(hG_0)$ 时，对线性函数 $f(x)=a_0+a\cdot x$，一次相位查询后的态（忽略余项）恰好因子化为 $d$ 个单坐标平面波的乘积，且 $a_0$ 只贡献一个不可观测的全局相位。

> 提示：$e^{2\pi iS\frac hN\sum_j g_jz_j}=\prod_{j=1}^d e^{2\pi iz_jg_j/G_0}$。

**练习 4【逆 QFT 读出与解码】**（→ [3.1 节](#inverse-qft-readout)）

1. 写出逆 QFT 后输出 $k$ 的振幅 $\widetilde a(k)$、解码公式 $\widetilde g_j=G_0k_j/N$ 与符号回绕规则，并解释取 $G_0\ge2G$ 的用意。
2. 取 $d=1$、$N=8$、$\omega=g/G_0=0.4$，用第 3.1 节的 Dirichlet 核公式计算测量结果落在最近整数 $k=3$ 上的概率，并与落在 $k=2$ 上的概率比较。
3. 对线性函数 $f(x)=a_0+a\cdot x$，从网格叠加出发完整推导逆 QFT 后的输出态：证明当 $a_j/G_0=k_j/N$ 恰为格点频率时，测量以概率 $1$ 给出 $(k_1,\ldots,k_d)$，并说明常数项 $a_0$ 去了哪里。

> 提示：格点频率处公比为 $1$，$N$ 项同相相加，可参照第 3.3 节 $N=4$ 的手算。

**练习 5【误差预算与参数平衡】**（→ [第 4 节](#error-budget)）

1. 列出三类误差并各写出其控制条件（$N\gtrsim G_0/\epsilon$、$Sh^2d\|\nabla^2f\|\ll1$、$S\eta\ll1$），说明每一条分别限制哪个参数。
2. 给定 Hessian 界 $\|\nabla^2f\|\le M$、目标精度 $\epsilon$ 与梯度范围 $G$，参照第 4.2 节写出 $h$、$N$、$S$ 与预言机精度 $\eta$ 的一组可行尺度，并验证三类误差约束同时满足。

> 提示：先取 $N\sim G/\epsilon$ 与 $h\sim\epsilon/(dM)$，$S=N/(hG)$ 与 $\eta\ll1/S$ 随之确定。

**练习 6【二次型与 Hessian 学习】**（→ [第 6 节](#hessian-learning)）

1. 对 $f(x)=\frac12x^TAx+b^Tx+c$（$A$ 对称），逐分量验证 $\nabla f(x)=Ax+b$，并计算 $\nabla f(e_j)-\nabla f(0)$。
2. 对 $d=2$ 的二次型 $f(x)=\frac12x^TAx+b^Tx+c$（$A$ 为一般 $2\times2$ 对称矩阵），具体写出三次梯度查询（在 $0,e_1,e_2$）如何恢复 $A$ 的全部三个独立矩阵元与 $b$，并数一数经典有限差分完成同样任务至少需要几次函数求值。

> 提示：一般二元二次型有 6 个未知系数，每次函数求值只提供一个线性方程。

**练习 7【高阶导数与谱方法】**（→ [第 7 节](#higher-derivatives-spectral)）

1. 说明对 $\partial_jf$ 再跑一遍梯度估计如何给出 Hessian 的第 $j$ 行，并写出估计 $p$ 阶导数张量所需的查询次数及其在 $p=1,2$ 时的特例。
2. 解释谱微分观点（微分算子在 Fourier 基下是对角的）如何与"函数值网格采样 → QFT → 乘以频率 → 读出"这条流水线一一对应，并说明复值函数为什么不能直接套用相位预言机。

> 提示：相位预言机的酉性要求 $|e^{2\pi iSf(x)}|=1$，即 $f$ 取实值。

**练习 8【与参数平移法的区别】**（→ [第 8 节](#parameter-shift-comparison)）

1. 分别写出参数平移法与 Jordan 算法的前提（oracle 访问模型），并比较读出全部 $d$ 个分量各需要多少次线路运行或相位查询。
2. 各举一个适合 Jordan 梯度 oracle 与适合参数平移法的实际场景，说明各自 oracle 的实现方式，并解释为什么把两者混用会高估量子优势。

> 提示：先问"损失函数能否在输入位置的相干叠加上求值"。

## 参考文献与 Zoo 覆盖

- Zoo 编号 61：Stephen Jordan, [Fast Quantum Algorithm for Numerical Gradient Estimation](https://arxiv.org/abs/quant-ph/0405146).
- Zoo 436--439：precision/smoothness、Gevrey/general polynomial 与 complex spectral gradient/Hessian 改进。
- Zoo 20、62、94：basin hopping、quadratic minima/高阶 derivatives 与 classical lower bound。