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

给 smooth scalar function $f:\mathbb R^d\to\mathbb R$ 的 value oracle，经典 finite difference 至少查询 $d+1$ 个点才能恢复 gradient。Jordan 算法在一个 $d$ 维网格叠加上查询一次，把线性 Taylor 项写成 separable phase，再对每个坐标逆 QFT，同时得到全部 $d$ 个分量。查询数与维数无关，但 oracle 精度、smoothness 和输出 $d$ 个数的门/读出成本仍增长。

1. Oracle 与目标¶

Value oracle 以 fixed-point 形式

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

或 phase form

\[ |x\rangle\mapsto e^{2\pi iS f(x)}|x\rangle. \]

目标在 $x_0$ 输出

\[ g=\nabla f(x_0) \]

每分量到加性精度 $\epsilon$。需已知 gradient range $|g_j|\le G$，并在半径 $h$ 区域有 Hessian/更高 derivative bound。

经典 $d+1$ lower bound 可看线性函数族

\[ f_a(x)=a_0+a\cdot x. \]

每次 value 是未知 $(d+1)$ parameters 的一个线性方程；少于 $d+1$ 个适应性点仍有不可辨方向。

2. 网格叠加与 Taylor phase¶

每坐标用 $N=2^n$ 个格点，中心化整数

\[ z_j\in\{-N/2,\ldots,N/2-1\}. \]

制备

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

并映到位置

\[ x(z)=x_0+\frac hN z. \]

Taylor：

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

选择 phase scale $S=N/(hG_0)$（$G_0$ 是编码单位），一次 query 得近似

\[ e^{2\pi iS f(x_0)} \prod_{j=1}^d e^{2\pi i z_jg_j/G_0}|z_j\rangle. \]

全局 $f(x_0)$ phase 无关。线性项在各坐标 factorize，正是 QFT basis state。

3. 逆 QFT 读出全部分量¶

对每个坐标 register 做 $QFT_N^{-1}$。若

\[ g_j/G_0\approx k_j/N, \]

振幅集中在整数 $k_j$，测量后解码

\[ \widetilde g_j=G_0k_j/N \]

（处理 signed wrap-around）。一次函数 phase query 同时编码 $d$ 个 slopes；QFT 与测量成本 $O(d\,\operatorname{polylog}N)$，所以 query speedup 不违反输出下界。

4. 误差预算¶

三类误差：

Fourier discretization：$G_0/N\lesssim\epsilon$；
**Nonlinearity：**phase remainder 要小： $$ S h^2 d\|\nabla^2f\|\ll1 $$ （更精细分析用平均/高阶 smoothness，改善 $d$）；
**Oracle value error：**若 $|\widetilde f-f|\le\eta$，需 $$ S\eta\ll1. $$

减小 $h$ 抑制 Taylor error，却增大 $S=N/(hG_0)$ 并要求更精确 value oracle。Gilyén--Arunachalam--Wiebe 等优化高阶 finite differences/phase schedules，使 precision 依赖相对早期分析平方改善；Gevrey/analytic smoothness 可进一步控制高阶 remainder。

5. Quadratic form 与 Hessian 学习¶

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

Gradient

\[ \nabla f(x)=Ax+b. \]

一次 gradient query at $x=0$ 得 $b$；在 $d$ 个 basis points $e_j$ 得

\[ \nabla f(e_j)-\nabla f(0)=Ae_j, \]

即第 $j$ 列。总 $O(d)$ value-oracle queries 提取 $d^2$ matrix entries，经典 black-box value learning 需 $\Omega(d^2)$ queries。输出/经典线性代数仍需 $\Omega(d^2)$ 时间，优势是 query 而非打印成本。

若 $A\succ0$，minimum

\[ x_*=-A^{-1}b. \]

学出 $A,b$ 后求解；或结合 quantum linear systems 输出 state。Yao lower bound 对相应经典 query model 给出 quadratic separation。

6. 高阶导数与 spectral 方法¶

递归对 gradient components 或用多维 phase polynomial，可估计 order-$p$ derivative tensor 的 $d^p$ entries，query 约

\[ O(d^{p-1}) \]

在固定 $p$ 与 smoothness promise 下。Again 输出 $d^p$ numbers 需相应时间。

Quantum spectral gradient/Hessian methods 把 finite-difference stencil 视为 trigonometric/polynomial spectral differentiation，QFT 提取多个 frequencies；可处理 complex-valued $f$，但 phase/amplitude oracle 定义必须说明，复函数不能直接作为物理全局 phase。

7. 与 parameter-shift 的区别¶

参数平移法针对

\[ f(\theta)=\langle\psi|U(\theta)^\dagger OU(\theta)|\psi\rangle \]

且 generator 有特定少数 eigenvalues，用两个 shifted circuit expectations 得单个 derivative。Jordan gradient 假设可在输入位置叠加上相干查询整个 scalar value oracle，一次返回所有坐标 slopes。硬件 VQA 通常不提供这种强 oracle，不能用“一 query”替代 $d$ 个 parameter-shift measurements。

8. 小结与习题¶

一次相位查询把局部线性 Taylor 项变成 $d$ 个 separable Fourier phases。
逆 QFT 同时解码全部 gradient components；门/输出仍至少线性于 $d$。
Grid、Taylor 与 oracle precision 三者需联合平衡。
Quadratic/Hessian learning 有 query 优势，但完整经典输出消耗相应时间。

对线性 $f(x)=a\cdot x$ 完整推导 QFT 输出。
给 Hessian bound $M$，写 $h,N,S$ 的一组可行误差尺度。
用 $d=2$ quadratic form 演示三次 gradient query 恢复 $A,b$。
比较 Jordan oracle 与 parameter-shift 可访问性。

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

量子梯度估计：Phase Kickback、\(d\) 维逆 QFT 与高阶导数¶