一些信息论中的直觉
Abstract. 这是本学期信息论的复习笔记。主干内容是证明有噪信道编码定理，佐以一些神秘小结论。
启发式 RSMA 算法
本文收录于 EDA 论文选读，系 Sailesh K. Rao, P. Sadayappan, Frank K. Hwang, Peter W. Shor 所作论文 The Rectilinear Steiner Arborescence Problem 之阅读笔记。
SALT Algorithm
本文收录于 EDA 论文选读，系 Gengjie Chen, Peishan Tu, Evangeline F. Y. Young 所作 ICCAD’17 的论文 SALT: Provably Good Routing Topology by a Novel Steiner Shallow-Light Tree Algorithm 之阅读笔记。
Revision | 随机算法
Abstract. 随机算法的复习笔记。没有复习完，缺的内容用 $\color{red}{\text{Sorry.}}$ 标出，暂时可以补充参考 这个 Note
现在缺少的部分
- 前面几章比较初等的随机算法；
- Lovasz Local Lemma 里面那个数据包路由的证明；
- 网络可靠性里面大割不多的证明；
- The Power of Two Choices；
- 随机图 Hamilton 回路的证明；
- 随机图巨连通块 $c > 1$ 一侧的证明；
- 快速时间的集中性；
- 一些关于 coupling 的理解。
一些证明量子复杂度下界的办法
Posted on
Edited on
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$ 和精度的关系。等以后需要了再看。