一般 Adversary 界 | Codeboy's Blog

形式陈述

沿用输入差异矩阵 $\Delta_i[x,y]=\mathbf1[x_i\ne y_i]$ 。一般 adversary 界放开正权 adversary的逐项非负限制：

\operatorname{Adv}^{\pm}(f) =\max_{\substack{\Gamma=\Gamma^*\\ \Gamma[x,y]=0\text{ if }f(x)=f(y)}} \frac{\|\Gamma\|} {\max_i\|\Gamma\circ\Delta_i\|}.

$\Gamma$ 可含正负实数；允许复 Hermitian 矩阵不改变最优值的实质。把每个分母归一化为不超过 $1$ 后，Hermitian 谱范数约束可写成线性矩阵不等式；连同相应对偶，这个最优值有等价的 semidefinite program 表述。这里没有丢弃 rank-one 或整数约束，因而不是把另一个离散问题放宽所得的近似松弛。可行集合包含所有非负矩阵，所以

\operatorname{Adv}^{\pm}(f)\ge\operatorname{Adv}^+(f).

Høyer–Lee–Špalek 证明其仍是 bounded-error quantum query lower bound。随后 Reichardt 的 span program/反射算法以及 Lee–Mittal–Reichardt–Špalek–Szegedy 的 state-conversion 形式给出紧性：对任意有限字母表上的有限 partial function $f:D\to E$ ，固定常数错误（如 $1/3$ ）时

Q_{1/3}(f)=\Theta(\operatorname{Adv}^{\pm}(f)).

常数依赖错误阈值但不依赖输入长度。定理刻画函数求值的查询数，不包含实现最优 SDP 或输入无关 unitary 的计算时间。

直觉

负权不是“负概率”。它让不同困难输入对在单坐标切片 $\Gamma\circ\Delta_i$ 中发生谱抵消，同时保留完整 $\Gamma$ 的大方向，从而越过正权方法的 certificate 与 property-testing barriers。

更惊人的方向是上界：最优矩阵不只证明算法不能更快，还能经 SDP 对偶、span program 或状态转换构造同阶查询算法。这个 tightness 是 general adversary 的专有结论，不能倒推任意下界方法都可自动生成算法。

例子与边界

以 parity 校准谱比值。令 $\Gamma$ 是 $n$ 维 Boolean cube 的邻接矩阵，只连接 Hamming 距离一的输入；每条边两端 parity 相反，所以满足零块条件。Cube 邻接矩阵可写成 $n$ 个坐标翻转矩阵之和，Fourier character $\chi_S$ 的特征值为 $n-2|S|$ ，故

\|\Gamma\|=n.

固定 $i$ 后， $\Gamma\circ\Delta_i$ 只保留第 $i$ 维的 perfect matching，每个非零 $2\times2$ 块为

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

所以范数为 $1$ 。于是 $\operatorname{Adv}^{\pm}(\operatorname{PARITY}_n)\ge n$ 。Lower-bound theorem 给 $\Omega(n)$ ，与精确算法的 $\lceil n/2\rceil$ 及读取全部位的 $O(n)$ 同量级；常数因子不会由该渐近 tightness 固定。

这个例子没有用负权，只说明 general bound 至少保留正权能力。负权的真实必要性可由 element distinctness 看出：正权 certificate barrier 只能到 $O(\sqrt n)$ ，而其量子查询复杂度是 $\Theta(n^{2/3})$ ；tightness 保证某个一般 adversary 解达到后者量级。不能因此假设任意手写负号矩阵都有效，仍须逐坐标计算谱范数分母。

若输出是 relation、域或值域无限、错误随输入长度趋近 $1/2$ ，上述固定常数有限函数定理需要重述。对精确复杂度，general adversary 的 bounded-error tightness也不直接给常数精确刻画。

推论与应用

一般 adversary 提供统一的 lower-bound/algorithm 接口，并支持输入坐标带不同 costs、块组合和 state generation 的扩展。状态转换把函数标签改为目标态 Gram matrix，filtered $\gamma_2$ 正是对应的 query distance。

计算具体最优值仍可能很难。对称性可把 SDP 压缩到少数 orbit，显式矩阵可给可审计下界；只引用 tightness 而不给 adversary 值或独立算法，不会凭空产生某个问题的复杂度结论。

参考资料

Peter Høyer, Troy Lee, and Robert Špalek, “Negative Weights Make Adversaries Stronger,” Proceedings of STOC 2007, pp. 526–535.
Ben W. Reichardt, “Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function,” Proceedings of FOCS 2009, pp. 544–551.
Ben W. Reichardt, “Reflections for Quantum Query Algorithms,” Proceedings of SODA 2011, pp. 560–569.
Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy, “Quantum Query Complexity of State Conversion,” Proceedings of FOCS 2011, pp. 344–353.

形式陈述 ​

反向链接

形式陈述