# 量子梯度估计：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. 误差预算

三类误差：

1. **Fourier discretization：**$G_0/N\lesssim\epsilon$；
2. **Nonlinearity：**phase remainder 要小：
   $$
   S h^2 d\|\nabla^2f\|\ll1
   $$
   （更精细分析用平均/高阶 smoothness，改善 $d$）；
3. **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 的区别

[参数平移法](../ch02-quantum-nn/parameter-shift-appendix.md)针对

$$
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 优势，但完整经典输出消耗相应时间。

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

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