技术摘要：锦标赛解的量子查询复杂度

问题定义

本文研究了计算各种锦标赛解（tournament solutions）的量子查询复杂度。锦标赛是一个有向图，其中每对不同的顶点之间恰好有一条弧连接，模拟了循环赛或两两多数关系。锦标赛解将一个锦标赛映射到一个非空的“获胜”顶点集合。

在查询模型中，锦标赛是隐式给出的；算法只有通过查询才能了解边 $(u, v)$ 的方向。成本是查询的次数。虽然这些问题的经典查询复杂度通常是统一的（通常为 $\Theta(N^2)$），但本研究探讨了量子算法（利用叠加和 Grover 搜索）是否能实现显著的加速。

研究的具体解包括：

• 孔多塞胜利者 (Condorcet Winner)： 打败所有其他顶点的顶点。
• 科普兰德集合 (Copeland Set, $CO(T)$)： 出度最大的顶点集合。
• 未覆盖集合 (Uncovered Set, $UC(T)$)： “国王”（能在两步之内到达所有其他顶点的顶点）的集合。
• 强国王 (Strong King)： 一个顶点 $v$，使得对于每一个打败 $v$ 的顶点 $u$，$v$ 打败 $u$ 的次数多于 $u$ 打败 $v$ 的次数（具体为 $p(v,u) > p(u,v)$）。
• 顶层循环 (Top Cycle, $TC(T)$)： 唯一的最小支配集（该集合中的每个成员都打败集合外的每个顶点）。

方法论

作者结合使用了量子算法设计和下界技术：

1. 下界（对抗者方法）：

   • 证明下界的主要工具是 Ambainis 的对抗者方法 (Adversary Method)（定理 2.13）。
   • 为了应用此方法，作者引入了一个新的承诺问题——重行问题 (Heavy-Row)：给定一个 $m \times m$ 的布尔矩阵，其中除了可能存在的一个权重为 $k+1$ 的行外，其余每一行的权重均为 $k$，判断是否存在重行。
   • 他们直接使用对抗者方法证明了 $Q(\text{Heavy-Row}) = \Omega(m^{3/2})$，避免了使用先前文献 [14] 中的组合定理。
   • 通过构建特定的锦标赛，将该问题归约为锦标赛问题，其中出度或结构属性（如是否为强国王）取决于重行的存在。
   • 对于科普兰德集合，他们将其推广到 Heavy-Rows$_k$（其中可能存在多个重行），以建立 $\Omega(N^2)$ 的下界。
   • 对于未覆盖集合，他们定义了 Tight-Count 问题，该问题涉及统计“紧凑 (tight)”与“亏损 (deficient)”矩阵，以此建立 $\Omega(N^{3/2})$ 的下界。

2. 上界（算法设计）：

   • 顶层循环 (Top Cycle)： 算法首先通过插入排序使用 $O(N \log N)$ 次查询找到一条 哈密顿路径 (Hamiltonian path)。顶层循环对应于该路径的一个前缀。寻找该前缀末点的问题被归约为区间覆盖问题，通过结合分治策略与量子最小查找 (Dürr-Høyer) 来高效定位回边。
   • 孔多塞胜利者 (Condorcet Winner)： 算法先找到一个国王（使用来自 [25] 的 $O(\sqrt{N} \text{polylog } N)$ 算法），然后执行 Grover 搜索以检查是否有任何顶点打败了该国王。
   • 强国王 (Strong Kings)： 上界通过“每个最大出度顶点都是强国王”这一事实直接得出，并利用寻找最大度顶点所需的 $\Theta(N^{3/2})$ 复杂度。

核心贡献与结果

本文确立了以下量子查询复杂度（其中 $N$ 是顶点数，$\tilde{O}$ 隐藏了多项式对数因子）：

问题	经典复杂度	量子复杂度	关键结果
孔多塞胜利者	$\Theta(N)$	$\tilde{\Theta}(\sqrt{N})$	显著加速；通过“国王 + Grover”找到。
顶层循环	$\Theta(N^2)$	$\tilde{\Theta}(N)$	重大加速。 在三个嵌套集合 ($CO \subseteq UC \subseteq TC$) 中，顶层循环是量子计算中最容易计算的一个。
最大出度顶点	$\Theta(N^2)$	$\Theta(N^{3/2})$	与先前工作 [14] 一致；作者通过 Heavy-Row 归约提供了自洽的证明。
强国王	$\Theta(N^2)$	$\Theta(N^{3/2})$	相比经典 $\Theta(N^2)$ 有多项式加速，但比寻找单个国王 ($\tilde{O}(\sqrt{N})$) 慢。
未覆盖集合 (国王)	$\Theta(N^2)$	$\Omega(N^{3/2}), O(N^2)$	区分了集合问题与单元素问题。寻找所有国王比寻找一个国王更难。
科普兰德集合	$\Theta(N^2)$	$\Theta(N^2)$	无加速。 计算整个最大度顶点集合需要读取常数比例的边，与经典界一致。

具体技术发现：

• 科普兰德集合的难度： 作者表明，虽然寻找单个科普兰德获胜者（最大度顶点）需要 $\Theta(N^{3/2})$，但计算整个此类顶点集合需要 $\Theta(N^2)$ 次查询。这与顶层循环形成对比，在顶层循环中，集合的计算速度比单个最大度顶点更快。
• 强国王： 寻找强国王需要 $\Theta(N^{3/2})$ 次查询。这相对于经典的 $\Theta(N^2)$ 是多项式加速，但明显慢于寻找普通国王 ($\tilde{O}(\sqrt{N})$)。
• 顶层循环算法： 该算法实现了 $O(N \log^2 N)$ 次查询。在忽略对数因子的情况下，这是最优的，因为其下界为 $\Omega(N)$（通过在 $\Theta(N^2)$ 个比特上嵌入 OR 函数得出）。
• 替代证明： 本文提供了一个关于寻找最大度顶点的 $\Theta(N^{3/2})$ 界限的自洽证明，通过直接从 Heavy-Row 问题进行归约并使用对抗者方法，绕过了 [14] 中使用的组合定理。

意义与主张

本文声称，锦标赛解的量子查询复杂度并非统一的，这与经典情况不同。

• 难度层级： 在量子设定下，最大的解集（顶层循环）是最容易计算的 ($\tilde{\Theta}(N)$)，而最小的解集（科普兰德集合）是最难的 ($\Theta(N^2)$)。
• 集合 vs. 元素： 一个核心主题是，计算整个锦标赛解可能严格难于寻找其中的单个成员。
  • 对于国王：寻找一个是 $\tilde{O}(\sqrt{N})$，但寻找整个集合（未覆盖集合）是 $\Omega(N^{3/2})$。
  • 对于科普兰德：寻找一个是 $\Theta(N^{3/2})$，但寻找整个集合是 $\Theta(N^2)$。
• 结构洞察： 这项工作强调，这些问题的困难程度往往源于计数（确定度数或特定结构的计数），而非搜索。虽然 Grover 搜索有助于寻找特定元素，但计数问题往往保留了更高的复杂度，或者需要读取输入的大部分内容。

作者总结道，他们的研究结果要求对量子环境下的锦标赛解进行重新评估，证明了量子加速高度依赖于解集的具体定义以及锦标赛的底层结构属性。