量子查询的正权 Adversary 方法

形式陈述

设 $f:D\to E$ ， $D\subseteq\Sigma^n$ 。对每个坐标 $i$ 定义差异矩阵

\Delta_i[x,y]=\mathbf1[x_i\ne y_i].

正权 adversary matrix 是以合法输入为行列的非零实对称矩阵 $\Gamma$ ，满足逐项非负 $\Gamma[x,y]\ge0$ ，且 $f(x)=f(y)$ 时 $\Gamma[x,y]=0$ 。注意“逐项非负”不等于 positive semidefinite。定义

\operatorname{Adv}^+(f) =\max_{\substack{ \Gamma=\Gamma^{\mathsf T}\ne0,\ \Gamma[x,y]\ge0\ \forall x,y\\ \Gamma[x,y]=0\text{ if }f(x)=f(y)}} \frac{\|\Gamma\|} {\max_{i\in[n]}\|\Gamma\circ\Delta_i\|},

其中 $\|\cdot\|$ 是矩阵的谱范数 $\|\cdot\|_2$ ， $\circ$ 是 Hadamard product。对任意固定 $\varepsilon<1/2$ ，

Q_\varepsilon(f)=\Omega_\varepsilon(\operatorname{Adv}^+(f))

给出有界误差量子查询下界。

证明选取 $\Gamma$ 的主特征向量权重，跟踪不同输入上算法状态内积的加权和。开始时所有输入状态相同，进度量大；正确输出要求不同函数值的状态接近可区分，进度量显著下降。一次查询只能通过某个 $\Delta_i$ 改变输入对的相位或 answer bit，下降量由 $\max_i\|\Gamma\circ\Delta_i\|$ 控制；总变化除以单步变化即得比值下界。

这不是经典决策树对手。经典方法在线选择一致回答；量子 adversary 固定整个输入对矩阵并分析一族同时演化的量子态，不能让“对手”在运行中观察测量随机性后改输入。

直觉

$\Gamma[x,y]$ 把质量放在函数值不同、却希望算法难以区分的输入对上。分子衡量这些对整体耦合有多强，分母问一次查询某个坐标最多能切断多少耦合。若没有任何坐标能同时解释大量权重，算法就必须多次访问。

非负权重让进度量像真正的“困难输入对质量”，容易构造和计数；代价是不能利用正负抵消来压低所有单坐标分母，因此存在结构性 barrier。

这里取 spectral norm 而不是把所有权重直接相加，因为量子态的最坏可区分方向由矩阵最大奇异方向控制；换成总权重会得到另一个未经证明的进度量。

例子与边界

对 total $\operatorname{OR}_n$ ，只在 $0^n$ 与 $e_1,\ldots,e_n$ 之间放权重 $1$ ，其余为 $0$ 。在这些输入上 $\Gamma$ 是星图邻接矩阵：

\Gamma= \begin{pmatrix} 0&\mathbf1^\mathsf T\\ \mathbf1&0 \end{pmatrix}.

向量 $(\sqrt n,1,\ldots,1)$ 是特征值 $\sqrt n$ 的特征向量，负号版本给 $-\sqrt n$ ，故 $\|\Gamma\|=\sqrt n$ 。固定坐标 $i$ 时， $\Gamma\circ\Delta_i$ 只剩 $0^n$ 与 $e_i$ 的一条边，其非零块为

\begin{pmatrix}0&1\\1&0\end{pmatrix},

谱范数为 $1$ 。所以 $\operatorname{Adv}^+(\operatorname{OR}_n)\ge\sqrt n$ ，立即得到 Grover 搜索的匹配下界量级。

真实失效边界是 certificate barrier：对适用的 total function 查询模型，正权 bound 至多为 $O(\sqrt{C_0C_1})$ 。Element distinctness 的 collision 证书只需两个位置，而“全不相同”证书可能需全部 $n$ 个值，所以正权方法至多给 $O(\sqrt n)$ ，低于真实 $\Theta(n^{2/3})$ 查询复杂度。增加更复杂的非负权重不能突破这个障碍。

推论与应用

Ambainis 的 relation/weight scheme、spectral adversary 与若干早期正权版本可互相转写；实际证明可选最便于构造的一种，但必须核对它对应同一 oracle 和错误常数。

多项式法对 element distinctness 能越过正权 certificate barrier，而允许负权的 general adversary 则从矩阵侧解除限制。方法间的强弱是问题相关的；OR 上二者都给平方根界，并不表示它们一般等价。

参考资料

Andris Ambainis, “Quantum Lower Bounds by Quantum Arguments,” Journal of Computer and System Sciences 64(4), 2002, pp. 750–767.
Robert Špalek and Mario Szegedy, “All Quantum Adversary Methods Are Equivalent,” Theory of Computing 2, 2006, pp. 1–18.
Peter Høyer, Troy Lee, and Robert Špalek, “Negative Weights Make Adversaries Stronger,” Proceedings of STOC 2007, pp. 526–535.

形式陈述 ​

反向链接

形式陈述