作者: Amin Shiraz Gilani, Nikhil S. Mande, Subhasree Patro, Nithish Raja

1. 核心物理图象

• 任务：本文研究的是量子查询复杂性（Quantum Query Complexity）——即用量子算法解决图论问题时，最少需要查询多少次图的邻接矩阵。论文的核心贡献是确定了两个基本图问题的量子查询复杂度的紧确界：在无向图中寻找最大度顶点、在竞赛图中寻找最大出度顶点，两者都需要 Θ(n^{3/2}) 次查询。此外，论文还将最大度问题推广到 Maximum (k, n−k)-Cut 问题，给出了量子上界，并通过归约建立了与 k-Graph Collision 问题的联系，从而获得了一系列下界。

• 目标：直观地说，这篇论文告诉我们：在量子计算机上，找图中度数最大的顶点，既不可能比 n^{3/2} 更快，也存在达到这个速度的算法。对于更一般的“找大小为 k 的一侧的最大割”问题，论文给出了一个随 k 增大而逐渐接近经典查询复杂度 n^2 的量子算法，并证明了当 k 较大时该问题严格比找最大度更难。

2. 关键术语解释

• 最大度 (Maximum Degree, MD)：在一个无向图中，某个顶点的度数是与它相连的边数；最大度就是所有顶点中度数的最大值。本文证明：在量子查询模型下，找到最大度顶点（或仅计算最大度）需要 Θ(n^{3/2}) 次查询。这是论文最核心的结果之一，解决了该问题量子查询复杂度的紧确界。

• 竞赛图与最大出度 (Tournament & Maximum Out-Degree, MOD)：竞赛图是完全图的一种定向——每对顶点之间恰好有一条有向边。出度是从某顶点出发的边数。本文证明：在竞赛图中找到最大出度顶点也需要 Θ(n^{3/2}) 次量子查询，从而解决了 Mande、Paraashar 和 Saurabh [FSTTCS'23] 提出的猜想。

• k-Graph Collision (GC_k^G)：给定一个已知图 G 和每个顶点的标记位（0 或 1），问标记顶点中是否包含一个 k-团（k-clique）。当 k=2 时就是标准的 Graph Collision 问题。本文通过将 GC_k^G ◦ PrMaj 归约到 Maximum (k, n−k)-Cut，利用该问题的下界来推导最大割问题的下界，是论文下界证明的核心工具。

3. 主要贡献 (Key Contributions)

• 贡献一：解决了最大出度问题的量子查询复杂度猜想。论文证明了在 n 个顶点的竞赛图中找到最大出度顶点需要 Θ(n^{3/2}) 次量子查询，严格匹配了已知的上界。这直接回答了 Mande、Paraashar 和 Saurabh [FSTTCS'23] 提出的公开猜想，是该领域的一个长期悬而未决的问题。

• 贡献二：给出了无向图最大度问题的直接下界证明。虽然该下界隐含在 Apers 和 Lee [CCC'21] 的工作中，但本文通过从 OR ◦ PrMaj 的归约给出了一个直接且更简洁的证明，统一了无向图和竞赛图两种情形的下界技术路线。

• 贡献三：首次研究 Maximum (k, n−k)-Cut 的量子查询复杂度。论文给出了 O(n^{2−1/(k+1)}) 的量子上界算法，并证明了 Ω(n^{3/2}) 的无条件下界。对于 k≥3，通过归约到 k-Graph Collision，获得了指数严格大于 3/2 的无条件下界，表明该问题严格比计算最大度更难。

• 贡献四：提出了 k-Graph Collision 的紧确性猜想。论文猜想对于每个常数 k≥2，存在 N 顶点图 G 使得 Q(GC_k^G) = Ω(N^{1−1/(k+1)})。在此猜想下，Maximum (k, n−k)-Cut 的量子查询复杂度被完全确定为 Θ(n^{2−1/(k+1)})，为后续研究指明了方向。

4. 研究方法 (Methodology)

• 下界方法：从 OR ◦ PrMaj 的归约。论文的核心下界技术是将 OR_m ◦ PrMaj_m 问题（判断 m 个字符串中是否存在一个汉明重量为 m/2+1 的字符串）归约到最大度/最大出度问题。具体构造是：对于无向图，构造一个包含团 L 和独立集 R 的图 G_x，使得 L 中顶点的度数编码了输入字符串的汉明重量；对于竞赛图，构造一个包含正则竞赛图 L 和固定结构的 R 的竞赛图 T_x，使得 L 中顶点的出度编码了输入信息。由于 Q(OR_m ◦ PrMaj_m) = Ω(m^{3/2})（由 Q(OR_m)=Ω(√m) 和 Q(PrMaj_m)=Ω(m) 以及复合函数下界定理得到），归约即给出 Ω(n^{3/2}) 的下界。

• 上界方法：量子最大值查找。对于最大度和最大出度问题，上界来自一个简单算法：先用量子最大值查找（Durr–Høyer 算法，O(√n) 次评估）找到最大化顶点，每次评估计算一个顶点的度数需要 O(n) 次查询，总计 O(n^{3/2}) 次查询。

• Maximum (k, n−k)-Cut 的上界：量子游走 + 二分搜索。算法首先找到度数最高的 k 个顶点，其度数和 A 给出了最大割的上界，且 A − k(k−1) 是下界。然后在这个长度为 O(k²) 的区间内二分搜索，每次阈值测试使用 MNRS 量子游走框架在 Johnson 图 J(n, r) 上搜索是否存在 k 顶点集合诱导的割 ≥ t。通过优化参数 r = ⌈(en)^{k/(k+1)}⌉，将查询复杂度控制在 O(n^{2−1/(k+1)})。

• Maximum (k, n−k)-Cut 的下界：从 k-Graph Collision 的归约。构造一个三层图 H_x（顶点集 V ∪ L ∪ R，各含 n 个顶点），使得 V 中每个顶点的度数编码了标记信息（n + wt(x_v)），而 L 和 R 中顶点度数严格更小。于是，大小为 k 的割达到阈值 k(3n/2+1) 当且仅当 V 中存在一个由标记顶点组成的 k-团，即 (GC_k^G ◦ PrMaj_N)(x) = 1。该归约是查询保持的，因此 Q(MaxCut_{k,3N}) = Ω(N · Q(GC_k^G))。结合 Gilani 和 Zhou [GZ26] 对 k-Graph Collision 的下界，即得 Corollary 1.4 中的无条件下界。

5. 实验结果与结论 (Results and Conclusion)

• 核心结论一：Q(MD_n) = Θ(n^{3/2})。无向图中找到最大度顶点（或计算最大度）的量子查询复杂度紧确为 Θ(n^{3/2})。

• 核心结论二：Q(MOD_n) = Θ(n^{3/2})。竞赛图中找到最大出度顶点（或计算最大出度）的量子查询复杂度紧确为 Θ(n^{3/2})，解决了 MPS23 的猜想。

• 核心结论三：对于 Maximum (k, n−k)-Cut，有 Ω(n^{3/2}) = Q(MaxCut_{k,n}) = O(n^{2−1/(k+1)})。对于 k≥3，无条件下界为 Q(MaxCut_{k,n}) = Ω(n^{1+ℓ(2k−ℓ+1)/(2k(ℓ+1))−o(1)})，其中 ℓ = ⌈(√(8k+9)−3)/2⌉。例如 k=3 时下界为 n^{14/9−o(1)}，k=4 时为 n^{19/12−o(1)}，k=5 时为 n^{8/5−o(1)}。

• 核心结论四：在 Conjecture 1.5（k-Graph Collision 的紧确下界猜想）成立的前提下，Q(MaxCut_{k,n}) = Θ(n^{2−1/(k+1)})，即上界与下界完全匹配。

• 对领域的意义：这篇论文首次确定了最大度/最大出度问题的量子查询复杂度紧确界，标志着图论中基础优化问题的量子查询复杂性研究的一个重要里程碑。对于 Maximum (k, n−k)-Cut，论文揭示了该问题的复杂度随 k 增大而平滑地从 n^{3/2}（k=1，即最大度）过渡到 n²（k→∞，接近经典穷举），并在 k≥3 时严格超越最大度问题的难度。

• 开放性问题：

1. Conjecture 1.5 的验证：k-Graph Collision 的 Ω(N^{1−1/(k+1)}) 下界猜想是否成立？这是确定 Maximum (k, n−k)-Cut 紧确复杂度的关键。
2. k=2 的情形：对于 Maximum (2, n−2)-Cut，下界是否也是 n^{2−1/3} = n^{5/3}？目前只知道 Ω(n^{3/2})，上界为 O(n^{5/3})，存在间隙。
3. 更一般的图优化问题：论文的技术是否可以推广到其他参数化图优化问题（如参数化 Vertex Cover、Matching 等）的量子查询复杂度研究？
4. k-Graph Collision 本身的量子查询复杂度：对于一般图 G，GC_k^G 的量子查询复杂度是否真的达到 N^{1−1/(k+1)}？这需要构造更难的图实例或证明更强的下界。

6. 论文标签 (Tags)

量子算法, 量子复杂性, 量子信息, 编译与优化, 模拟

📄 点击此处展开/折叠原文 PDF

原文链接： Quantum Query Complexity of Maximum Degree and its Generalizations