一些证明量子复杂度下界的办法
Abstract. Under Construction
关于计算模型的说明
这里我们的计算模型是 quantum oracle model，即输入被用一个 oracle function $f : 2^m \rightarrow 2^n$ 给出。关于复杂度，我们只考虑 query complexity，即查询 oracle function 的次数。
Oracle function 对应的酉变换可以为如下两种形式：binary oracle 抑或是 phase oracle。一个 binary oracle 将输出加到一个 register 上，形式化地
$$
O_f |i, b; z\rangle := |i, b \oplus f(i); z\rangle
$$
其中 $\oplus$ 是模意义下的加法，$z$ 是辅助比特。另一种形式，phase oracle 将输出放在量子态的相位上，形式化地
$$
O_f|x, z\rangle = e^{2f(x)\pi / N}|x, z\rangle
$$
其中 $N = 2^n$ 是函数的值域。熟知这两个形式之间的相互转换惟需用 QFT 做一下 phase kickback。虽然前者更符合人类直觉，但是后者更便于数学上的分析。
Hybrid Method
本节主要参考 arXiv:1711.00465v3。
定理 1 (Hybrid method for arbitrary phase oracles). 令 $G$ 是一个有限大小的标号的集合，$\mathcal{H} := \mathrm{Span}(|x\rangle : x\in G)$ 是一个希尔伯特空间。对于函数 $\tilde{f} : G\rightarrow \mathbb{R}$，令 $O_{\tilde{f}}$ 是查询 $\tilde{f}$ 的 phase oracle：
$$
O_{\tilde{f}}|x\rangle = \mathrm{e}^{\mathrm{i}\tilde{f}(x)}|x\rangle
$$
假设 $\mathcal{F}$ 是一族 $G\rightarrow \mathbb{R}$ 的函数，另有一个 $f_*: G \rightarrow \mathbb{R}$ 的函数，$f_*\notin \mathcal{F}$。如果一个量子算法能够调用 $O_{\tilde{f}}$ 或者 $O_{\tilde{f}}^\dagger$ 总计 $T$ 次以后，对于任意的 $f\in \mathcal{F}$ 都能以至少 $2/3$ 的概率判断 $\tilde{f} = f$ 还是 $\tilde{f} = f_*$，则
$$
T\geq \frac{\sqrt{|\mathcal{F}|}}{3} \bigg / \sqrt{\max_{x\in G}\sum_{f\in \mathcal{F}}\min(|f(x) - f_*(x)|^2, 4)}
$$
Remark. 这个定理大概是启发自无结构搜索问题。该问题本质上是在区分 $n$ 个函数（仅在一点上为 $1$）和全部输出 $0$ 的函数，用这个方法可以得到 $\Omega(\sqrt n)$ 的界，证明也和无结构搜索问题的复杂度证明如出一辙。
证明. 在这里，一个使用函数 $f$ 的 phase oracle $O_f$ 的量子算法可以被刻画成
$$
\mathcal{A}_f = U_T O_f’ U_{T - 1}\cdots O_f’ U_1 O_f’ U_0
$$
其中 $O_f’ := O_f \otimes I_{\mathcal{W}}$。这里 $\mathcal{W}$ 是辅助比特所在的希尔伯特空间。
假设 $\mathcal{F}$ 中有 $d$ 个函数，依次是 $f_1, …, f_d$，另外记 $f_0 = f_*$。记 $\mathcal{A}_j$ 表示调用 $f_j$ 的 phase oracle 的量子算法，$|\psi_j\rangle = \mathcal{A}_j |0\rangle$。
为了区分 $f_*$ 和 $f_1$，我们至少需要能够区分 $|\psi_0\rangle$ 和 $|\psi_1\rangle$。这要求 $\lVert|\psi_0\rangle - |\psi_1\rangle\rVert \geq 1/3$。定义
$$
|\psi_j^{(t)}\rangle := \left(\prod_{i=1}^t U_i O’_{f_j}\right) U_0 |0\rangle
$$
我们本质上是要求对于任意的 $j = 1, 2, …, d$ 都有 $\lVert |\psi_j^{(T)}\rangle - |\psi_0^{(T)}\rangle\rVert \geq 1/3$（$\star$）。这里，我们递归地估计一下 $\lVert |\psi_j^{(T)}\rangle - |\psi_0^{(T)}\rangle\rVert$ 的上界：
$$
\begin{aligned}
\lVert |\psi_j^{(t)}\rangle - |\psi_0^{(t)}\rangle\rVert &= \lVert U_tO_{f_j}’|\psi_j^{(t - 1)}\rangle - U_tO_{f_0}’|\psi_0^{(t - 1)}\rangle\rVert \\
&= \lVert O_{f_j}’|\psi_j^{(t - 1)}\rangle - O_{f_0}’|\psi_0^{(t - 1)}\rangle\rVert \\
&\leq \lVert O_{f_j}’|\psi_j^{(t - 1)}\rangle - O_{f_j}’|\psi_0^{(t - 1)}\rangle\rVert + \lVert O_{f_j}’|\psi_0^{(t - 1)}\rangle - O_{f_0}’|\psi_0^{(t - 1)}\rangle\rVert \\
&\leq \sum_{i=1}^{t - 1} \lVert (O_{f_j}’ - O_{f_0}’) |\psi_0^{i}\rangle\rVert
\end{aligned}
$$
根据柯西不等式
$$
\begin{aligned}
\lVert |\psi_j^{(T)}\rangle - |\psi_0^{(T)}\rangle\rVert^2 &\leq T\sum_{i=1}^{T - 1} \lVert (O_{f_j}’ - O_{f_0}’) |\psi_0^{i}\rangle\rVert^2
\end{aligned}
$$
现在将这个式子对于所有的 $d = 1, 2, …, d$ 加起来，为了满足条件（$\star$），我们至少需要
$$
\frac d9 \leq T\sum_{j = 1}^d\sum_{i=1}^{T - 1} \lVert (O_{f_j}’ - O_{f_0}’) |\psi_0^{i}\rangle\rVert^2 \leq T^2 \max_i\left(\sum_{j = 1}^d \lVert (O_{f_j}’ - O_{f_0}’) |\psi_0^{i}\rangle\rVert^2\right)
$$
而 $O_{f_j}’ - O_{f_0}’$ 的特征向量为所有的 $|x\rangle : x\in G$，对应特征值为 $\mathrm{e}^{\mathrm{i} f_j(x)} - \mathrm{e}^{\mathrm{i} f_0(x)}$，我们在 $|x\rangle : x\in G$ 下将 $\psi$ 傅里叶展开可以知道
$$
\begin{align}
\sum_{j = 1}^d \lVert (O_{f_j}’ - O_{f_0}’) |\psi\rangle\rVert^2 &= \sum_{x\in G} \langle x|\psi\rangle^2\sum_{j = 1}^d |\mathrm{e}^{\mathrm{i} f_j(x)} - \mathrm{e}^{\mathrm{i} f_0(x)}|^2 \\
&\leq \max_{x\in G}\left(\sum_{j = 1}^d |\mathrm{e}^{\mathrm{i} f_j(x)} - \mathrm{e}^{\mathrm{i} f_0(x)}|^2\right) \\
&\leq \max_{x\in G}\left(\sum_{j = 1}^d \min(|f_j(x) - f_0(x)|^2, 4)\right)
\end{align}
$$
整理一下上面的所有结果
$$
\frac d9 \leq T^2 \max_{x\in G}\left(\sum_{j = 1}^d \min(|f_j(x) - f_0(x)|^2, 4)\right) \quad \Rightarrow \quad {\color{blue} T\geq \frac{\sqrt{|\mathcal{F}|}}{3} \bigg / \sqrt{\max_{x\in G}\sum_{f\in \mathcal{F}}\min(|f(x) - f_*(x)|^2, 4)}}
$$
上面的证明假设了 $|\psi\rangle$ 都是纯态，这显然是错的，但是改成叠加态只需要很琐碎的一步：定义 $\Pi_i = |i\rangle\langle i|$，$\beta_{j, i} = |\Pi_i|\psi_j^{(t - 1)} - \psi_0^{(t - 1)}\rangle|$，然后拿着 $\boldsymbol{\beta}_j$ 重写证明。
Adversary Method
本节参考 arXiv:0509153。
这是一种 Hybrid Method 的推广。本节我们改一下记号，直接用一个 $\{0, 1\}^N$ 的字符串表示一个 $[N]\rightarrow \{0, 1\}$ 的函数。这里重申：假设量子算法 $\mathcal{A}$ 计算了一个函数 $F:\{0, 1\}^N\rightarrow \{0, 1\}^M$，那么它至少应当能够区分一切 $F(x)\ne F(y)$ 的字符串 $x, y$。
Remark. 在上面的 Hybrid Method 中，我们只是找了一族 hard instance，然后说至少要能区分 $x_0$ 和其他 $x_i$。
回忆为了通过量子算法的输出正确区分两个 oracle，我们至少要求两个 oracle 经过量子算法之后的输出 $|\phi_x\rangle$ 和 $|\phi_y\rangle$ 满足 $\langle \phi_x|\phi_y\rangle$ 足够小。为了区分一切满足 $F(x)\ne F(y)$ 的 $x, y$，我们不妨定义一组权值（这组权值越大表示两个 oracle 越难区分），以便 $\langle\phi_x|\phi_y\rangle$ 的加权和来捕捉全部的信息。
这启发我们定义下面的 spectral adversary matrix $\Gamma$，此处 $\Gamma$ 是一个 $2^N\times 2^N$ 的非负矩阵，即：
$$
\Gamma : \{0, 1\}^N\times \{0, 1\}^N\rightarrow \mathbb{R}_{\geq 0}
$$
满足：
- 若 $F(x) = F(y)$ 则 $\Gamma[x, y] = 0$。（如果两个 oracle 对应相同的输出，那么无需区分）
- $\Gamma$ 为对称矩阵。（我们无需关心是从 $x$ 区分 $y$ 还是从 $y$ 区分 $x$）
Remark. 注意这里你也可以 handle $F$ 是 partial function 的情况。这时只需要将不合法输入对应的行列置为 $0$ 即可。
同样，对于一个 oracle $x$，定义 $|\psi_x^t\rangle$ 是算法 $\mathcal{A}$ 执行时间 $T$ 之后输出的量子态，形式化地
$$
|\psi_x^t\rangle = U_tO_x\cdots U_1O_xU_0|0\rangle
$$
现在，我们基于 $\Gamma$ 的谱性质定义一个量 $W^t$ 表示 $t$ 时间时区分任意两个 oracle 的加权总难度为：
$$
W^t := \sum_{x, y}\Gamma[x, y] \delta_x\delta_y \langle \psi_x^t|\psi_y^t\rangle
$$
其中 $\boldsymbol{\delta}$ 是矩阵 $\Gamma$ 的最大特征值对应的单位特征向量。注意到
$$
W_0 = \boldsymbol{\delta}^\dagger \Gamma \boldsymbol{\delta} = \lambda(\Gamma)
$$
为了保证所有的 oracle 都可区分，必然有 $W_T \leq \epsilon W_0$，故若我们可以控制 $W^{t + 1} - W^t \leq \Delta$，便可以知道问题的复杂度是 $\Omega(\lambda(\Gamma) / \Delta)$。
Remark. 这里为什么用到了谱性质（尤其是 $\delta$ 这个东西）
我们反过来想一下。如果你不要这个 $\boldsymbol{\delta}$ （改成 $\boldsymbol{1} / \sqrt{2^n}$）会推出来什么东西。
你会发现这里推出来 $\Delta$ 的 bound 不会变，但是 $W_0$ 变成了 $\mathbf{1}^\top\Gamma \boldsymbol{1} / \sqrt{2^n} \leq \lambda(\Gamma)$。可能本着加个 $\boldsymbol{\delta}$ 可以获得一些 free lunch 就加上了。但是实际上在用 adversary bound 的时候通常还是用 $\sum_{x, y}\Gamma[x, y] / 2^n$ 来 lowerbound $\lambda(\Gamma)$。
感觉我对谱的理解还是太差了。
定理 2 （Spectral Adversary Method）. 令 $F$ 是一个从 $N\rightarrow \{0, 1\}$ 的 oracle 到 $\{0, 1\}^m$ 的函数。则对于任意的 $\Gamma$ 和计算 $F$ 的 bounded error 的量子算法 $\mathcal{A}$，都有
$$
Q(\mathcal{A}) = \Omega\left(\frac{\lambda(\Gamma)}{\lambda(D_i\circ \Gamma)}\right)
$$
其中 $D_i(x, y) = 1$ 当且仅当 $x_i \ne y_i$。
证明. 这里给出 $\Delta$ 的界即可。
首先考虑放一下 $\langle\psi_x|\psi_y\rangle$ 的变化量的界。令 $\Pi_i = |i\rangle\bra i$，有 $O_x = I - 2\Pi_i$，$\beta_{x, i} = |\Pi_i |\psi_x\rangle|$，有
$$
|\bra{\psi_x}(I - O_xO_y)\ket{\psi_y}| = 2\left|\sum_{x_i\ne y_i} \bra{\psi_x}\Pi_i\ket{\psi_y}\right|\leq 2\sum_{x_i\ne y_i}\beta_{x, i}\beta_{y, i}
$$
定义 $\boldsymbol{a}_i$ 是一个 $\mathbb{R}^{2^n}$ 上的向量，$a_{i, x} = \beta_{x, i}\delta_x$
$$
\begin{aligned}
W_t - W_{t + 1} &\leq \sum_{x, y}\sum_{x_i\ne y_i} \Gamma[x, y]\delta_x\delta_y\beta_{x, i}\beta_{y, i} \\
&= \sum_i\sum_{x, y}\delta_x\beta_{x, i}\Gamma_i[x, y]\delta_y\beta_{y, i} \\
&= \sum_i\boldsymbol{a}_i^\dagger \Gamma_i \boldsymbol{a}_i \\
&\leq \sum_{i}\lambda(\Gamma_i)\lVert \boldsymbol{a}_i\rVert_2^2 \\
&\leq \max \lambda(\Gamma_i)\sum_i \lVert \boldsymbol{a}_i\rVert_2^2 \\
&= \max_i\lambda(\Gamma_i)
\end{aligned}
$$
与上方说理部分合并便可明所欲证。
实例
二分查找 bound
二分查找问题形式定义为在一个满足 $x_i \leq x_{i + 1}, x_n = 1$ 的 $0/1$ 数组里面找第一个 $1$ 的位置。
使用 adversary method，将 $\Gamma$ 定义做
$$
\Gamma = \begin{cases}
\frac{1}{|F(x) - F(y)|} & \text{$x, y$ are sorted $0/1$ arrays, $x\ne y$}\\
0 & \text{otherwise.}
\end{cases}
$$
首先来 bound 这个矩阵的谱范数。令 $\boldsymbol{v}$ 为所有合法输入的 one-hot 向量。回忆经典结论（Cauchy-Schwatz），其中 $H_n$ 是调和级数。
$$
\lambda(\Gamma) \geq \frac{1}{n}\boldsymbol{v}^\dagger \Gamma \boldsymbol{v} \geq \frac{1}{n}\sum_{1\leq x\leq n}\sum_{1\leq y\leq n} \frac{1}{|x - y|} \geq H_n \geq \ln(n)
$$
而 $\Gamma_i$ 的谱范数的上界由无穷维希尔伯特矩阵 $L$ 的谱范数给出，这个值是 $\pi$。这里
$$
\mathbf{L} = \begin{pmatrix}
1 & \frac 12 & \frac 13 & \cdots \\
\frac 12 & \frac 13 & \frac 14 & \cdots \\
\frac 13 & \frac 14 & \frac 15 & \cdots \\
\vdots & \vdots & \vdots & \ddots
\end{pmatrix}
$$
先考虑 $\Gamma_i$ 长什么样子：它必然形如
$$
\begin{pmatrix}
0 & \mathbf{A} \\
\mathbf{A}^\top & 0
\end{pmatrix}
$$
此处 $\mathbf{A}$ 是某个希尔伯特矩阵的左上角。这个矩阵的谱范数不会超过
$$
\max_{\boldsymbol{v}_1, \boldsymbol{v}_2}\left(\frac{|\mathbf{A}\boldsymbol{v}_1 + \mathbf{A}^\top \boldsymbol{v}_2|}{\sqrt{|\boldsymbol{v}_1^2 + \boldsymbol{v}_2^2|}}\right) = \max_{\boldsymbol{v}}\left(\frac{|\mathbf{A}\boldsymbol{v}|}{|\boldsymbol{v}|}\right) \leq \lambda(\mathbf{L})
$$
你可以验证一个矩阵的左上角把向量缩放的最大倍数定不超过其本身能将向量缩放的最大倍数。