一些证明量子查询复杂度下界的办法（2026 Remaster）

Posted on Edited on

Abstract. 主要的阅读材料是 Andrew M. Childs 的讲义和一些其他东西。

记号

考虑计算函数 $f : S\rightarrow T$ 的任务，其中 $S\subseteq \Sigma^n$。

  • 若 $S = \Sigma^n$，则称 $f$ 为完全函数（total function）；
  • 若 $S\subsetneq \Sigma^n$，则称 $f$ 为部分函数（partial function）。

输入 $\boldsymbol{x}\in S$ 将会由一个 oracle $i \mapsto x_i$ 给出。对于量子的情况，Oracle 可以是加性查询（$O_x|i\rangle|z\rangle = |i\rangle|z\oplus x_i\rangle$）或者相位查询（$O_x|i\rangle = e^{2\pi i x_i / |\Sigma|}|i\rangle$）。在均匀叠加态上面使用 QFT 做 phase kickback 得到这两种 oracle 的等价性。一个算法必须从无关于 $\boldsymbol{x}$ 的状态出发，经过一系列 oracle 访问和调用，计算出 $f(\boldsymbol{x})$。

常见的计算模型有以下三种：

  • 经典确定性算法复杂度. $D(f)$。
  • 经典误差有界随机算法复杂度. $R_\epsilon(f)$。该随机算法可以是 bounded-error 的，错误概率至多为 $\epsilon$。注意对于常数 $\epsilon$ 有 $R_\epsilon(f) = \Theta(R_{1/3}(f))$。
  • 误差有界量子算法复杂度 $Q_\epsilon(f)$。该量子算法可以是 bounded-error 的，错误概率至多为 $\epsilon$。同样对于常数 $\epsilon$ 有 $Q_\epsilon(f) = \Theta(Q_{1/3}(f))$。

只考虑询问复杂度时，一个算法总是可以被拆分成：

$$
|0\rangle\rightarrow U_0 \rightarrow O_1 \rightarrow U_1\rightarrow O_2 \rightarrow \cdots \rightarrow U_{T - 1} \rightarrow O_T \rightarrow U_T \rightarrow \mathrm{Measurement.}
$$

其中 $U_i$ 都是酉变换，$O_i$ 表示 oracle 访问。

下面简单起见，我们只考虑 $\Sigma = \{0, 1\}$。其他情况可以用编码解决。

Polynomial Method

这种方法的核心是 phase polynomial。

定理 2.1 一个 $t$ 次询问的量子算法最后测出任意一个态的概率都是关于 $x_1, …, x_n$ 的至多 $2t$ 次的多项式。

证明. 我们直接考察每一个基底的振幅。施归纳于 $T$，证明做完 $U_T$ 后每个基底的振幅都是至多 $T$ 次的多项式。

  • 做完 $U_0$ 后，每个基底的振幅都是常数；
  • 假设做完 $U_{T - 1}$ 后，每个基底的振幅都是 $T - 1$ 次多项式。现在进行了一次 oracle 访问 $O_T$，有 $a_{i, b}|i\rangle|b\rangle$ 将会变成
    $$
    a_{i, b}(-1)^{x_i}|i\rangle|b\rangle = a_{i, b}(1 - 2x_i)|i\rangle|b\rangle
    $$
    振幅的次数只升高了一次。而 $U_T$ 是线性组合，不会升高多项式的次数。

最后测出一个态 $|i\rangle|b\rangle$ 的概率是 $a_{ib}^\dagger a_{ib}$，为 $2t$ 次多项式。

$\blacksquare$

上述定理启发我们量子算法的复杂度下界和多项式的度数之间存在联系。

定义 2.1（布尔函数的 $\varepsilon$-近似度）. 对于布尔函数 $f : \{0, 1\}^n\rightarrow \{0, 1\}$，定义其 $\varepsilon$-近似度为

$$
\widetilde{\deg}_\varepsilon(f) = \inf \{ \mathrm{deg}(p) : \forall \boldsymbol{x}\in \{0, 1\}^n, |p(\boldsymbol{x}) - f(\boldsymbol{x})| < \varepsilon \}
$$

推论 2.1（The Polynomial Method）. 对于任意布尔函数 $f : \{0, 1\}^n \rightarrow \{0, 1\}$，有 $Q_\varepsilon(f) \geq \widetilde{\deg}_\varepsilon(f) / 2$。

Example: PARITY

在使用 Polynomial Method 分析下界的时候，我们经常需要分析多项式的度数。然而，多元多项式对于人类来说还是过于抽象。比如说遇到了下面的问题：

Example 2.1（Quantum Lowerbound for PARITY）. 定义函数 $\mathrm{PARITY}(\boldsymbol{x}) = x_1\oplus \cdots \oplus x_n$。对于 $\varepsilon < \frac 12$，分析 $Q_\varepsilon(\mathrm{PARITY})$。

我们就会对什么样的多项式能够 $\varepsilon$-近似 $\textrm{PARITY}$ 束手无策。实践中，对于此类答案仅和 $\boldsymbol{x}$ 的 Hamming weight 有关的题目，我们有如下的处理技巧。

引理 2.1（Symmetrization）. 设 $p$ 是一个 $n$ 元多重线性多项式（i.e. 在每个项中 $x_i$ 的次数至多是 $1$）。定义 $p$ 的 Symmetrization 为以下的 $P(\cdot)$：

$$
P(k) = \mathbb{E}_{|\boldsymbol{x}| = k}[p(\boldsymbol{x})]
$$

有 $P$ 也是多项式，其次数不超过 $\deg(p)$。

Remark. 此处我们仅考虑多重线性多项式的原因是当 $x\in \{0, 1\}$ 时必然有 $x^2 = x$。

证明. 不妨设

$$
p(\boldsymbol{x}) = \sum_{S\subseteq [n]}c_S\prod_{i \in S} x_i
$$

则

$$
\begin{align}
\mathbb{E}_{|\boldsymbol{x} = k|}[p(\boldsymbol{x})] &= \sum_{S\subseteq [n]}c_S\mathbb{E}_{|\boldsymbol{x}| = k}\left[\prod_{i \in S} x_i\right] \\
&=\sum_{S\subseteq [n]}c_S \binom{n - |S|}{k - |S|} \binom{n}{k}^{-1} \\
&=\sum_{S\subseteq [n]} c_S \frac{(n - |S|)!(n - k)!}{n!}\cdot k^{\underline{|S|}}
\end{align}
$$

这个下降幂多项式的最高次数就是最大的 $|S|$，也就是 $p(\boldsymbol{x})$ 的次数。

$\blacksquare$

很明显，如果 $p$ 能够 $\varepsilon$-近似 $f$，则根据绝对值不等式，$p$ 的 Symmetrization 也应当能 $\varepsilon$-近似 $f$ 的 Symmetrization。那么将 $\mathrm{PARITY}$ Symmetrization 之后，便可以分析多项式的度数：

命题 2.1. 对于任意的 $\varepsilon\in [0, 1/2)$ 有 $Q_\varepsilon(\mathrm{PARITY}) = n / 2$。

证明. 上界是显然的。我们可以将下标两两分组，组内做 Deutsch 算法可以精确求出两个数的异或值，再将其全部异或起来即可，因此 $Q_{\varepsilon}(\mathrm{PARITY}) \leq n / 2$。

下界考虑将 $\mathrm{PARITY}$ Symmetrization 得到

$$
P(k) = \begin{cases}
0 & \text{$k$ is even} \\
1 & \text{$k$ is odd}
\end{cases}
$$

对于 $\varepsilon < 1/2$，要 $\varepsilon$-近似这个函数，多项式和 $y = 1/2$ 至少有 $n / 2$ 个交点，因此次数为 $n / 2$。因此 $Q_\varepsilon(\mathrm{PARITY}) \geq n / 2$。

$\blacksquare$

Example：OR

另一个问题是 $\mathrm{OR}$，这个问题弱于无结构搜索。做 Symmetrization 之后得到

$$
F(k) = \begin{cases}
0 & \text{k = 0} \\
1 & \mathrm{otherwise}
\end{cases}
$$

这里要分析这东西的最低次数，需要用到下面这个引理：

引理 2.2（Markov）. 设 $P$ 是一个多项式。则有

$$
\max_{x\in [0, n]} \frac{\mathrm{d}P}{\mathrm{d}x}(x) \leq \frac{\mathrm{deg}(P)^2}{n}\left(\max_{x\in [0, n]} P(x) - \min_{x\in [0, n]} P(x)\right)
$$

简写作

$$
\mathrm{deg}(P) \geq \sqrt{\frac{Nd}{h}}, \qquad \text{where } d = \max_{x\in [0, n]}, h = \left(\max_{x\in [0, n]} P(x) - \min_{x\in [0, n]} P(x)\right)
$$

这个引理比较平凡，将多项式写成 $\sum a_i x^i$ 之后使劲放缩即可。使用这个引理可以分析出

命题 2.2. 对于任意的 $\varepsilon\in (0, 1/2)$ 有 $Q_\varepsilon(\mathrm{OR}) = \Theta(\sqrt n)$。

证明. 对于一个 $\varepsilon$ 近似了 $F$ 的多项式而言，有：

  1. 在 $[0, 1]$ 这段区间上使用微分中值定理得到 $d \geq 1 - 2\varepsilon$。
  2. 在每段 $[0, 1]$ 之间的最高点（最低点）和与之较远的端点之间使用微分中值定理得到 $h + O(1) \leq 2\cdot d\cdot \frac 12$，因此 $d / h\geq 1 \pm O(1 / h)$。

得到

$$
\mathrm{deg}(P) \geq \sqrt{n\mathrm{max}(1 - 2\varepsilon, 1 \pm O(1 / h))} = \Omega(\sqrt n)
$$

下界得证。而上界就是直接 Grover Search。

$\blacksquare$

Example：COLLISION【未完成】

这部分本来计划讲 COLLISION 问题的复杂度下界，这也是多项式级别量子加速的一个重要例子。

但是 Polynomial Method 纯 ad hoc，我觉得在此处并无裨益，因此暂时先不写。

Adversarial Method

考虑你将系统耦合上一个指示输入的系统 $\mathcal{A}$：从

$$
\sum_{x\in S} a_x|x\rangle|0\rangle
$$

开始演化，每一步要么作用一个 $I\otimes U_t$，要么作用 oracle：

$$
O = \sum_{x\in S} |x\rangle\langle x|\otimes O_x
$$

经过若干轮演化之后，系统的状态必然形如

$$
\sum_{x\in S} a_x|x\rangle|\psi_x^t\rangle
$$

这为我们提供了一个证明量子算法复杂度下界的思路：为了解决这个问题，上述态必须要足够“纠缠”，而一次要让态的纠缠程度发生变化，必须调用 oracle。衡量纠缠程度时，我们有惯用的手法：考虑这个态关于系统 $\mathcal{A}$ 的约化密度矩阵

$$
\sum_{x, y\in S} a_x^* a_y \langle \psi_x^t|\psi_y^t\rangle |x\rangle\langle y|
$$

使用纠缠熵来刻画这个纠缠程度可能要丢失关于 $f$ 的理解，因此我们从测量的角度来审视这个矩阵：既然这个电路能够以不超过 $\varepsilon$ 的概率求出 $f(\boldsymbol{x})$，则对于任意的 $\boldsymbol{x}_1, \boldsymbol{x}_2$ 使得 $f(\boldsymbol{x}_1)\ne f(\boldsymbol{x}_2)$，我们根据计算结果就可以区分 $|\psi_{\boldsymbol{x}_1}^t\rangle$ 和 $|\psi_{\boldsymbol{x}_2}^t\rangle$ 这两个态。我们不加证明地摆出以下常识

引理 1. 对于两个态 $|\phi\rangle, |\psi\rangle$，区分这两个态的错误率不超过 $\varepsilon$ 当且仅当 $|\langle\phi|\psi\rangle| \geq 2\sqrt{\varepsilon(1 - \varepsilon)}$。

对于庞大的输入量而言，逐个分析 $\langle\psi_x^t|\psi_y^t\rangle$ 自然是天方夜谭。一个可能的松弛方法就是配一个直觉上是两个输入的相似程度的系数 $\Gamma_{xy}$ 加权平均起来，这个数必须大于 $2\sqrt{\varepsilon(1 - \varepsilon)}$。

定义 3.1（Adversary Matrix）. 矩阵 $\mathbf{\Gamma} \in \mathbb{R}^{|S|\rightarrow |S|}$ 称为函数 $f: S\rightarrow T$ 的 Adversary Matrix，若

  • $\forall x, y\in S$，$\Gamma_{xy} = \Gamma_{yx}$；
  • $\forall x, y\in S$，若 $f(x) = f(y)$，则 $\Gamma_{xy} = 0$。

对于初级的技术，我们还要求 $\Gamma_{xy}\geq 0$ 成立。

将想要的加权求和定义做 $W^t$（$t$ 表示 oracle 访问次数）。因为初始状态和输入无关，

$$
\begin{align}
W^0 = \sum_{x, y\in S} a_x^* \Gamma_{xy} a^y \langle\psi_x^0|\psi_y^0\rangle = \sum_{x, y\in S} a_x^* \Gamma_{xy} a_y
\end{align}
$$

而按态区分的要求，必须有

$$
\begin{align}
|W^t| &= \sum_{x, y\in S} a_x^* \Gamma_{xy} a_y \langle\psi_x^0|\psi_y^0\rangle \\
&\leq 2\sqrt{\varepsilon(1 - \varepsilon)} \sum_{x, y\in S} a_x^* \Gamma_{xy} a_y
\end{align}
$$

两个式子中都出现了 $\sum_{x, y\in S} a_x^* \Gamma_{xy} a_y$。本质上 $a$ 也是我们需要配置的参数，简明期间，我们直接让它取 $\mathbf{\Gamma}$ 最大特征值所对应的特征向量。此时

$$
\sum_{x, y\in S} a_x^* \Gamma_{xy} a_y = \left\lVert\mathbf{\Gamma}\right\rVert
$$

对于 $\mathbf{\Gamma}$ 可以有负的元的情况，讨论稍微更复杂一些，这里我们先跳过这一段。剩下的工作是，oracle 对 $W^t$ 的影响。我们考虑 $W^t$ 和 $W^{t - 1}$ 之间的递推关系：

$$
\begin{align}
W^t - W^{t - 1} &= \sum_{x, y\in S} \Gamma_{xy} a_x^*a_y\langle\psi_x^{t - 1}|(O_x^\dagger U_t^\dagger U_t O_y - I)|\psi_x^{t - 1}\rangle \\
&= \sum_{x, y\in S} \Gamma_{xy} a_x^*a_y\langle\psi_x^{t - 1}|(O_x^\dagger O_y - I)|\psi_x^{t - 1}\rangle \label{inter:w_diff1} \\
\end{align}
$$

回忆 $O_x$ 是 $x$ 的 phase oracle，因此

$$
O_x = I\otimes \sum_{i = 1}^n (-1)^{x_i}|i\rangle\langle i|, \qquad O_x^\dagger O_y - I = -2\mathbf{I}\otimes \sum_{i: x_i\ne y_i}|i\rangle\langle i|
$$

记 $P_i$ 为向 $|i\rangle$ 的投影：$\mathbf{I}\times |i\rangle\langle i|$，继续算。我们可能想要先交换求和顺序，因此定义

$$
(\mathbf{\Gamma}_i)_{xy} = \begin{cases}
\Gamma_{xy} & x_i\ne y_i \\
0 & \text{otherwise}
\end{cases}
$$

那么记 $(\boldsymbol{v}_i)_x = |a_x| \left\lVert P_i|\psi_x^{t - 1}\rangle \right\rVert$，时刻牢记 $P_i$ 是一组正交投影，$a_x$ 是归一化的。

$$
\begin{align}
(\ref{inter:w_diff1}) &= 2\sum_{i = 1}^n \sum_{x, y\in S} a_x^* a_y (\mathbf{\Gamma}_i)_{xy} \langle\psi_x^{t - 1}|P_i|\psi_y^{t - 1}\rangle \\
&\leq 2\sum_{i = 1}^n \boldsymbol{v}_i^\dagger \mathbf{\Gamma_i} {\boldsymbol{v}_i} \\
&\leq 2\sum_{i = 1}^n \left\lVert\mathbf{\Gamma}_i\right\rVert \left\lVert\boldsymbol{v}_i\right\rVert^2 \\
&\leq 2\max_{i\in [n]}(\left\lVert\mathbf{\Gamma}_i\right\rVert) \sum_{x\in S} |a_x|^2 \sum_{i = 1}^n \left\lVert P_i |\psi_x\rangle^{t - 1}\right\rVert^2 \\
&\leq 2\max_{i\in [n]}(\left\lVert\mathbf{\Gamma}_i\right\rVert) \sum_{x\in S} |a_x|^2 \\
&= 2\max_{i\in [n]}(\left\lVert\mathbf{\Gamma}_i\right\rVert)
\end{align}
$$

综上所述我们证明了：

定理 3.1（Adversary Bound）. 对于函数 $f: S\rightarrow T$，有

$$
Q_\varepsilon(f) \geq \frac{1 - 2\sqrt{\varepsilon(1 - \varepsilon)}}{2} \mathrm{Adv}(f)
$$

其中

$$
\mathrm{Adv}(f) = \sup_{\mathbf{\Gamma}} \frac{\left\lVert\mathbf{\Gamma}\right\rVert}{\max_{i\in [n]}\left\lVert \mathbf{\Gamma}_i\right\rVert}
$$

Example: Unstructured Search

考虑至多有一个 $1$ 的 OR 问题。取一个 $(n + 1)\times (n + 1)$ 的矩阵：

$$
\mathbf{\Gamma} = \begin{pmatrix}
0 & 1 & \cdots & 1 \\
1 & 0 & \cdots & 0 \\
\vdots & \vdots & & \vdots \\
1 & 0 & \cdots & 0
\end{pmatrix}
$$

这个行列式是经典的箭形行列式，可以算出

$$
\det (\lambda \mathbf{I} - \mathbf{\Gamma}) = \lambda^n \left(\lambda - \frac{n}{\lambda}\right) = \lambda^{n - 1}(\lambda + \sqrt n)(\lambda - \sqrt n)
$$

谱范数为 $\sqrt n$。而 $\Gamma_i$ 更是都是对合矩阵，谱范数都是 $1$。对于已知共有 $k$ 个 $1$ 的 OR 问题，计算同样简单，此时

$$
\left\lVert\mathbf{\Gamma}\right\rVert = \sqrt{\binom nk}, \qquad \left\lVert\mathbf{\Gamma}_i\right\rVert = \sqrt{\binom {n - 1}{k - 1}}, \qquad Q_{\varepsilon}(\mathrm{OR}_k) = O\left(\sqrt{\frac{n}{k}}\right)
$$

与熟知的结果匹配。

Example: Binary Search

Example 3.1（Quantum Lowerbound for Binary Search）. 定义函数 $F(\boldsymbol{x}) = \{i : \text{$x_i$ is the first $1$ in $\boldsymbol{x}$}\}$。这个函数只定义在单调的 $0/1$ 向量上。简便起见，我们记有 $i$ 个 $0$，$n - i$ 个 $1$ 的向量为 $\langle i\rangle$

这样定义 $\mathbf{\Gamma}$ 矩阵：

$$
\Gamma_{xy} = \begin{cases}
\frac{1}{|i - j|} & x = \langle i\rangle, y = \langle j\rangle, i\ne j \\
0 & \text{otherwise.}
\end{cases}
$$

首先来求 $\mathbf{\Gamma}$ 的谱范数下界。这里我们直接乘上一个全 $1$ 向量，看看拉伸了多少。注意每一行都至少拉伸了

$$
\sum_{i = 1}^{n / 2} \frac{1}{i} = \Theta(\log n)
$$

因此 $\left\lVert\mathbf{\Gamma}\right\rVert \geq \Theta(\log n)$。接下来考察 $\mathbf{\Gamma}_i$ 是什么。注意 $\langle x\rangle_i \ne \langle y\rangle_i$ 当且仅当这两个东西分居 $i$ 的两侧。限制在可能有 $1$ 的子矩阵上，$\mathbf{\Gamma}_i$ 是

$$
\begin{pmatrix}
& \mathbf{A}_i \\
\mathbf{A}_i^\top &
\end{pmatrix}, \qquad \mathbf{A}_i = \begin{pmatrix}
\frac{1}{i + 1}& \cdots &\frac{1}{n} \\
\vdots & & \vdots \\
1 & \cdots & \frac{1}{n - i}
\end{pmatrix}
$$

这样看来，如果乘上一个 $(\boldsymbol{u}, \boldsymbol{v})^\top$，所得向量的模方为 $\boldsymbol{v}^\top \mathbf{AA}^\top \boldsymbol{v} + \boldsymbol{u}^\top \mathbf{A}^\top \mathbf{A}\boldsymbol{u}$。两部分的放大倍数都是 $\mathbf{A}^\top$ 的最大奇异值。因此 $\left\lVert\mathbf{\Gamma}_1\right\rVert = \sigma_1(\mathbf{A}_i)$。我们把 $\mathbf{A}_i$ 补全成 $N\times N~(N\geq n)$ 的方阵，显然，新矩阵的谱范数必然大于这个矩阵的最大奇异值。这个矩阵整理之后是一个循环矩阵

$$
\widetilde{\mathbf{A}}_i =
\begin{pmatrix}
1 & \frac 12 & \cdots & \frac 1N \\
\frac 12 & \frac 13 & \cdots & 1 \\
\vdots & \vdots & & \vdots \\
\frac 1N & 1 & \cdots & \frac{1}{n - 1}
\end{pmatrix}
$$

也就是 $N$ 阶 Hilbert 矩阵。关于这个矩阵的谱范数的结果，可以参考 Peter Otte (2005) 的 $(5)$ 式，这个数不会超过

$$
\pi + O\left(\frac{1}{\ln n}\right)
$$

综上得到了 $\mathrm{Adv}(\mathrm{F}) = \Omega(\log n)$。因此

命题 3.1. 长度为 $n$ 的二分查找没有量子加速。

$$
Q_\varepsilon(\mathrm{F}) = \Theta(\log n)
$$

高级技巧