一般 Adversary 界 | Codeboy's Blog

带正负权的 adversary 矩阵以全局谱范数和逐坐标进展范数形成 SDP 比值 — 一般 Adversary 界的谱比值

形式陈述

沿用输入差异矩阵 $\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\|}.

矩阵的行列由合法输入 $D$ 标记， $\circ$ 表示逐项乘积， $\|\cdot\|$ 是算子谱范数。商式只对非零 $\Gamma$ 取值：只要 $f$ 非常值，任何非零允许项都连接两个不同输入，至少有一个坐标能区分它们，分母就为正。常函数没有这样的非零矩阵，另约定其 adversary 值为 $0$ ，与零查询相符。

$\Gamma$ 可含正负实数；允许复 Hermitian 矩阵不改变最优值。商式在同时缩放所有权重时不变，所以可令 $\max_i\|\Gamma\circ\Delta_i\|=1$ 。这些谱范数约束可写成线性矩阵不等式；完整的 SDP 表述还需重写目标及引入相应变量，不能仅凭“最大化谱范数”就称它是 SDP。这里没有丢弃 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 看出：输入是 $n$ 个字母，一次查询返回一个完整字母，要求判断是否全异，且字母表必须足够大。存在重复可由两个相同位置作证；证明全异通常要检查全部位置，因此正权的证书屏障至多给出 $O(\sqrt{2n})$ 。而该字母查询模型的量子复杂度为 $\Theta(n^{2/3})$ ，tightness 保证一般 adversary 值达到后者量级。若把一个字母拆成许多 bit 并逐 bit 收费，必须重新核算查询资源。

负号本身并不保证改进：同时缩小分子、分母可能毫无收益；必须让整个矩阵的范数相对于最难的单坐标切片变大。因此任意手写负号矩阵仍需逐坐标计算谱范数分母。

若输出是 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，布尔函数一般 adversary 界的紧性。
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.

形式陈述 ​

反向链接

形式陈述