Stephen P. Jordan, Fast Quantum Algorithm for Numerical Gradient Estimation (2005)
本文收录于 泛 AI 论文选读。
TL;DR
做零阶优化的量子算法，只需要一次查询。大概思路是用 phase kickback 把函数值信息挂在相位上，然后用 IQFT 提取。
似乎倒着考虑这个解法更为自然？
问题设定
在只给定 $d$ 元函数 $f : \mathbb{R}^d\rightarrow \mathbb{R}$ 的零阶 oracle 的情况下，想要估计一个函数在 $\boldsymbol{0}$ 处的梯度（当然，也可以做一次加法平移到任意的 $\boldsymbol{x}$ 处）$\nabla f$，可以想象的比较简单的经典算法是利用
$$
(\nabla f)_1 \approx \frac 1l (f(l / 2, 0, …, 0) - f(-l / 2, 0, …, 0))
$$
进行 $d$ 次查询。
然而量子算法可以做到更好。
在接下来的推导中我们假设我们的量子计算机可以做常见的定点数运算。事先需要约定下面几个记号的意义：
- $N = 2^n$，其中 $n$ 是 $f$ 输入的定点数的位数；
- $N_o = 2^{n_o}$，其中 $n_o$ 是输出定点数的位数；
- $l$ 是梯度的置信域的大小（i.e. 可以用函数的一阶展开近似函数的闭球的半径）；
- $m$ 是梯度各分量的最大大小（i.e. Lipschitz 常数等）。
并假设量子计算机可以使用下面的 oracle 来把查询结果装载至一个 $n_o$ qubit 的寄存器中（这个 oracle 大致是原始 oracle 配上一些经典线路）：
$$
O_f|\boldsymbol{x}\rangle|a\rangle \mapsto |\boldsymbol{x}\rangle\left|a\oplus \left[\frac{NN_o}{ml}f(\boldsymbol{x})\right]\right\rangle
$$
其中 $[\cdot]$ 是取整，$\oplus$ 是 $\bmod N_o$ 的加法。
算法
首先可以用 Quantum Hadamard Transformation 和 Quantum Fourier Transform 制备下面的态：
$$
\frac{1}{\sqrt{N^dN_o}}\sum_{\delta_1 = 0}^{N - 1}\cdots\sum_{\delta_d = 0}^{N - 1}|\delta_1\rangle\cdots|\delta_d\rangle\sum_{a = 0}^{N - 1}\mathrm{e}^{2\pi\mathrm{i}a / N_o} |a\rangle
$$
简写作
$$
\frac{1}{\sqrt{N^dN_o}}\sum |\boldsymbol{\delta}\rangle\sum_{a = 0}^{N - 1}\mathrm{e}^{2\pi\mathrm{i}a / N_o} |a\rangle
$$
用 QFT 制备后面的叠加态，主要是做 phase kickback 之用。此时对 oracle 进行一次查询，得到
$$
\frac{1}{\sqrt{N^dN_o}}\sum \exp\left(2\pi\mathrm{i}\frac{N}{ml}f\left(\frac{l}{N}\left(\boldsymbol{\delta} - \frac{N}{2}\right)\right)\right)|\boldsymbol{\delta}\rangle\sum_a \mathrm{e}^{2\pi\mathrm{i}a / N_o} |a\rangle \label{afterphasekickback}
$$
注意在 $l$ 充分小之时，有
$$
f\left(\frac{l}{N}\left(\boldsymbol{\delta} - \frac{N}{2}\right)\right) \approx f(\boldsymbol{0}) + \frac{l}{N}\left(\boldsymbol{\delta} - \frac N2\right) \cdot \nabla f = C + \sum_{i=1}^d \frac{l}{N}\delta_i\frac{\partial f}{\partial x_i}
$$
代回 $\ref{afterphasekickback}$ 中，注意此时前半部分实际上等于（忽略全局相位）下面的乘积态：
$$
\bigotimes_{i=1}^d \exp\left(\frac{2\pi\mathrm{i}}{m}\delta_i \frac{\partial f}{\partial x_i}\right)|\delta_i\rangle \label{productstate}
$$
因此只需要对每个 Register 做 $\mathrm{QFT}^{-1}$，回忆
$$
\mathrm{QFT}^{-1} : \frac{1}{\sqrt N}\sum_{j=1}^N e^{2\pi\mathrm{i}jk / N}|j\rangle \mapsto |k\rangle
$$
即得到
$$
\bigotimes_{i=1}^d \left|\frac{N}{m}\frac{\partial f}{\partial x_i}\right\rangle
$$
遂成功提取梯度。过程中只查询了一次 Oracle。
误差分析
这部分应该是通过仔细考察余项，分析了 $l$ 和精度的关系。等以后需要了再看。