量子梯度估计

引言：问题从哪里来

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

$$g=\nabla f(x_0)=\left(\frac{\partial f}{\partial x_1}(x_0),\dots ,\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$ 维输入的函数值相干地写进相位，这比经典黑箱求值强得多，不是所有应用场景都能提供；
• 算法对预言机的数值精度、函数的光滑性都有明确要求，精度 $ϵ$ 越小，对预言机的要求越高。

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

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

1. Oracle 与目标

1.1 两种等价的预言机形式

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

$$O_f|x,z⟩=|x,z\oplus \tilde{f}(x)⟩,$$

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

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

$$|x⟩\mapsto e^{2\pi iSf(x)}|x⟩,$$

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

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

$$|\chi ⟩=\frac{1}{\sqrt{M}}\sum _{y=0}^{M-1}{e}^{-2\pi iSy/M}|y⟩$$

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

$$|x⟩|\chi ⟩\stackrel{O_f}{\to }\frac{1}{\sqrt{M}}\sum _y{e}^{-2\pi iSy/M}|x,y\oplus \tilde{f}(x)⟩=e^{2\pi iS\tilde{f}(x)/M}|x⟩|{\chi }^{\prime }⟩,$$

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

1.2 任务与前提条件

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

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

的全部分量，每个分量 $g_j$ 达到加性精度 $ϵ$，即输出 ${\tilde{g}}_j$ 满足 $|{\tilde{g}}_j-g_j|\le ϵ$。

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

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

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}_j^{(t)}=f_a(x^{(t)}),$$

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

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

2. 网格叠加与 Taylor phase

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

2.1 网格与叠加态

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

$$z_j\in \left\{-\frac{N}{2},-\frac{N}{2}+1,\dots ,\frac{N}{2}-1\right\}.$$

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

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

$$\frac{1}{N^{d/2}}\sum _{z\in {\mathbb{Z}}_N^d}|z⟩.$$

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

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

$$x(z)=x_0+\frac{h}{N}z,$$

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

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

2.2 Taylor 展开：线性项的分离

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

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

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

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

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

$$e^{2\pi iSf(x(z))}=\underset{\text{常数}}{\underbrace{e^{2\pi iSf(x_0)}}}\cdot \prod _{j=1}^d{e}^{2\pi iS\frac{h}{N}{g}_j{z}_j}\cdot e^{2\pi iSR(z)}.$$

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

$$S=\frac{N}{h{G}_0},$$

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

$$2\pi S\frac{h}{N}{g}_j{z}_j=2\pi \frac{g_j}{G_0}{z}_j.$$

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

$$e^{2\pi iSf(x_0)}\underset{j=1}{\overset{d}{⨂}}\left(\frac{1}{\sqrt{N}}\sum _{z_j}{e}^{2\pi i{z}_j{g}_j/G_0}|z_j⟩\right).$$

两点说明：

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

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

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

3. 逆 QFT 读出全部分量

3.1 单坐标的精确分析

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

$$|\varphi ⟩=\frac{1}{\sqrt{N}}\sum _{z=-N/2}^{N/2-1}{e}^{2\pi i\omega z}|z⟩,\omega :=\frac{g_j}{G_0}.$$

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

$$\tilde{a}(k)=\frac{1}{N}\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\ne 1$ 时），分子 $r^N=e^{2\pi i(N\omega -k)}=e^{2\pi iN\omega }$ 与 $k$ 无关，故振幅的模为

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

第一步用了恒等式 $|1-e^{i\theta }|=2|\sin (\theta /2)|$ 分别作用于分子分母。这是标准的 Dirichlet 核：当 $\omega$ 恰好等于某个 $k_j/N$ 时，$k=k_j$ 处 $r=1$，求和退化为 $N$ 项同相相加，$\tilde{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$，测量后按

$${\tilde{g}}_j=\frac{G_0{k}_j}{N}$$

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

3.2 $d$ 个坐标同时读出

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

$$\underset{j=1}{\overset{d}{⨂}}QF{T}_N^{-1}\left(\frac{1}{\sqrt{N}}\sum _{z_j}{e}^{2\pi i{z}_j{g}_j/G_0}|z_j⟩\right)\approx \underset{j=1}{\overset{d}{⨂}}|k_j⟩,k_j\approx \frac{N{g}_j}{G_0}.$$

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

$$O\left(d\mathrm{polylog}N\right)$$

个门，测量与经典解码同样只需 $O(d)$ 次操作。所以”一次查询读出 $d$ 个数”不违反任何输出下界：查询模型只数预言机调用次数，而写出 $d$ 个经典数字本身就需要 $\Omega (d)$ 时间。量子优势体现在预言机查询从 $\Theta (d)$ 降到 $1$，门与时间复杂度仍是 $O(d\mathrm{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 格点上）。忽略全局相位后，相位查询给出的态为

$$|\varphi ⟩=\frac{1}{2}\sum _{z=-2}^1{e}^{2\pi iz/4}|z⟩=\frac{1}{2}(e^{-\pi i}|-2⟩+e^{-\pi i/2}|-1⟩+|0⟩+e^{\pi i/2}|1⟩)=\frac{1}{2}(-|-2⟩-i|-1⟩+|0⟩+i|1⟩).$$

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

• $k=1$：公比为 $1$，$\tilde{a}(1)=\frac{1}{4}\cdot 4=1$；
• $k=0$：公比为 $e^{\pi i/2}$，逐项相加 ${\sum }_z{e}^{\pi iz/2}=e^{-\pi i}+e^{-\pi i/2}+1+e^{\pi i/2}=-1-i+1+i=0$，故 $\tilde{a}(0)=0$；
• $k=-1$（即 $k=3\mathrm{mod}4$）：${\sum }_z{e}^{\pi iz}=1-1+1-1=0$，振幅为零；
• $k=2$：公比为 $e^{-\pi i/2}$，${\sum }_z{e}^{-\pi iz/2}=e^{\pi i}+e^{\pi i/2}+1+e^{-\pi i/2}=-1+i+1-i=0$，同样为零。

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

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

4. 误差预算与参数平衡

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

4.1 三类误差

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

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

这一项决定格点数 $N$ 的下限，从而决定每个坐标寄存器的比特数 $n={\log }_{2}N\approx {\log }_2(G_0/ϵ)$。

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

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

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

$$S{h}^{2}d\Vert {\nabla }^{2}f\Vert \ll 1.$$

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

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

$$S\eta \ll 1.$$

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

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

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

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

$$\frac{N}{hG}\cdot h^{2}dM=\frac{NhdM}{G}\ll 1⟹h\ll \frac{G}{NdM}\sim \frac{ϵ}{dM}.$$

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

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

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

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

5. 复杂度总览

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

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

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

6. Quadratic form 与 Hessian 学习

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

$$f(x)=\frac{1}{2}{x}^{T}Ax+b^{T}x+c,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=\frac{1}{2}{\sum }_k(A_{jk}+A_{kj})x_k+b_j={\sum }_k{A}_{jk}{x}_k+b_j$，用了对称性 $A_{jk}=A_{kj}$。）

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

$$\nabla f(e_j)-\nabla f(0)=(A{e}_j+b)-b=A{e}_j,$$

而 $A{e}_j$ 正是 $A$ 的第 $j$ 列。于是：

• $1$ 次梯度查询（在 $x=0$）得到 $b$；
• 再做 $d$ 次（在 $e_1,\dots ,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\succ 0$（正定），二次型的最小值点是

$$x_{\ast }=-A^{-1}b,$$

学出 $A,b$ 后可经典求解（适合 $d$ 不大、但需要省函数求值的场景）；

• 或者不把 $A$ 打印出来，而是把学得的 Hessian 信息结合量子线性方程组算法（如 HHL 类）直接输出解的量子态 $|x_{\ast }⟩$，绕开经典描述的成本——但此时引入条件数、态制备与读出等新的端到端考量。

7. 高阶导数与 spectral 方法

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

高阶导数张量。 梯度的第 $j$ 个分量 ${\partial }_{j}f$ 本身仍是 ${\mathbb{R}}^d$ 上的标量函数，对它再跑一遍梯度估计就得到二阶导数行 $({\partial }_1{\partial }_{j}f,\dots ,{\partial }_d{\partial }_{j}f)$。递归地逐层施加，或用多维相位多项式一次性编码，可以估计 $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⟩\mapsto e^{2\pi iSf(x)}|x⟩$ 只有在 $f$ 取实值时才是酉的——复函数的虚部会使”相位”带上模长衰减，不能作为物理上的全局相位。处理复值函数需要改用数值预言机加受控旋转等显式构造，并在复杂度中计入相应成本。

8. 与 parameter-shift 的区别

学过变分量子算法的读者会问：参数平移法也能用少量测量给出梯度，和 Jordan 算法是什么关系？两者的前提与结论完全不同，不能互相替代。

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

$$f(\theta )=⟨\psi |U(\theta {)}^{†}OU(\theta )|\psi ⟩,$$

即量子线路期望值对线路参数的依赖。它利用 generator 只有少数几个特定本征值（例如单比特旋转的生成元本征值为 $\pm 1/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/ϵ$，非线性要求 $S{h}^{2}d\Vert {\nabla }^{2}f\Vert \ll 1$，预言机舍入要求 $S\eta \ll 1$，且减小 $h$ 会以 $S=N/(h{G}_0)$ 为代价收紧对预言机的要求。
• 二次型/Hessian 学习用 $O(d)$ 次查询提取 $d^2$ 个矩阵元，相对经典 $\Omega (d^2)$ 有查询上的平方分离，但完整经典输出仍消耗 $\Omega (d^2)$ 时间；$p$ 阶导数张量约需 $O(d^{p-1})$ 次查询。
• 与参数平移法的根本区别在于 oracle 访问模型：能否在输入位置上做相干叠加查询，决定了两者的适用场景。

习题：

1. （推导）对线性函数 $f(x)=a_0+a\cdot x$，从网格叠加出发完整推导逆 QFT 后的输出态：证明当 $a_j/G_0=k_j/N$ 恰为格点频率时，测量以概率 $1$ 给出 $(k_1,\dots ,k_d)$，并说明常数项 $a_0$ 去了哪里。
2. （计算）取 $d=1$、$N=8$、$\omega =g/G_0=0.4$，用第 3.1 节的 Dirichlet 核公式计算测量结果落在最近整数 $k=3$ 上的概率，并与落在 $k=2$ 上的概率比较。
3. （参数配平）给定 Hessian 界 $\Vert {\nabla }^{2}f\Vert \le M$、目标精度 $ϵ$ 与梯度范围 $G$，参照第 4.2 节写出 $h$、$N$、$S$ 与预言机精度 $\eta$ 的一组可行尺度，并验证三类误差约束同时满足。
4. （Hessian 学习）对 $d=2$ 的二次型 $f(x)=\frac{1}{2}{x}^{T}Ax+b^{T}x+c$（$A$ 为一般 $2\times 2$ 对称矩阵），具体写出三次梯度查询（在 $0,e_1,e_2$）如何恢复 $A$ 的全部三个独立矩阵元与 $b$，并数一数经典有限差分完成同样任务至少需要几次函数求值。
5. （下界理解）第 1.3 节证明了经典需要 $d+1$ 次查询。把该论证推广：若允许每次查询返回 $f$ 在一点处的函数值和任意一个偏导数值，下界会变成多少？由此解释”每次查询的信息量”如何决定分离的程度。
6. （概念辨析）各举一个适合 Jordan 梯度 oracle 与适合参数平移法的实际场景，说明各自 oracle 的实现方式，并解释为什么把两者混用会高估量子优势。

参考文献与 Zoo 覆盖

• Zoo 编号 61：Stephen Jordan, Fast Quantum Algorithm for Numerical Gradient Estimation.
• Zoo 436—439：precision/smoothness、Gevrey/general polynomial 与 complex spectral gradient/Hessian 改进。
• Zoo 20、62、94：basin hopping、quadratic minima/高阶 derivatives 与 classical lower bound。

---

参考资料

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