Iterative quantum algorithms for the minimum vertex cover problem based on continuous-time quantum walks

技术摘要：基于连续时间量子行走算法的迭代式最小顶点覆盖算法

问题陈述
本文探讨了最小顶点覆盖（Minimum Vertex Cover, MVC）和最大独立集（Maximum Independent Set, MIS）问题，这两者都是经典的 NP 完全组合优化任务。给定一个图 $G=(V, E)$，目标是找到一个最小规模的顶点子集，以覆盖所有的边。本文将此建模为一个约束优化问题，其可行子空间由满足边约束（对于所有 $(i,j) \in E$，有 $x_i + x_j \geq 1$）的比特串组成。传统的贪心启发式算法（如最大度优先法，Largest-Degree-First）受限于对局部图结构的依赖，往往会忽略全局相关性。相比之下，标准的量子算法（如 QAOA 或 VQE）通常通过惩罚项将问题映射到无约束哈密顿量，这引入了参数调优问题，并创造了充满不可行低能态的能量景观。

方法论
作者提出了一种保持约束的混合量子-经典贪心框架，该框架避免了使用惩罚项和变分训练。其核心方法论包含三个阶段：

1. 保持约束的算符：
   可行子空间由投影泡利-X 算符 $\hat{X}_i = \Pi_{N(i)} X_i$ 定义，其中 $\Pi_{N(i)}$ 是将状态投影到“顶点 $i$ 的所有邻居已在覆盖集合中”这一子空间的算符。这确保了翻转比特 $i$（即从覆盖中移除该顶点）仅在不违反任何边约束的情况下才被允许。这些算符生成了一个连续时间量子行走（CTQW）哈密顿量 $H_{MVC} = \sum_i \hat{X}_i$。

2. 诱导可行状态图与 CTQW：
   $H_{MVC}$ 的动力学过程可以被解释为在诱导可行状态图 $G_{VC}(G)$ 上的 CTQW。该图的顶点是有效的顶点覆盖，边连接着通过单个保持可行性的比特翻转而产生差异的覆盖状态。该图以“全在覆盖中”的状态（$\Omega = |1\rangle^{\otimes |V|}$）为根节点且是连通的；因此，量子行走可以从 $\Omega$ 到达任何可行覆盖。该行走将振幅从根节点向汉明重量递减的层级传播。

3. 迭代贪心缩减：
   算法并非试图直接测量最小覆盖（论文指出，对于大型系统，直接测量的概率呈指数级衰减），而是利用 CTQW 状态来生成顶点评分，从而指导递归式的经典缩减：

   • 量子概率贪心 (QPG)： 根据顶点在 CTQW 状态中的边缘占据概率 $P_v(t) = \langle \psi(t) | \Pi_v | \psi(t) \rangle$ 进行评分。
   • 量子能量贪心 (QEG)： 通过在固定特定顶点 $v$ 在覆盖集合中的条件下，计算预期的覆盖规模来进行评分。这涉及为每个候选顶点运行一次独立的条件化行走。
   • 缩减规则： 在每一步中，算法根据这些评分（要么选择高分顶点加入覆盖，要么选择低分顶点并将其邻居纳入覆盖）选择一个顶点，并缩减图结构。该过程重复进行，直到图为空或变为可由经典方法求解。

主要贡献

• 无惩罚项框架： 本研究引入了一种通过投影泡利算符强制执行可行性的方法，消除了对惩罚项或变分参数优化的需求。
• 诱导图视角： 研究确立了受限动力学对应于在连通的、分层的可行覆盖图上的 CTQW 运动，这为量子行走为何能有效探索解空间提供了理论基础。
• 两种量子启发式算法： 论文定义并基准测试了 QPG 和 QEG 算法。QEG 被强调能够通过评估固定每个顶点带来的成本来聚合全局结构信息，而 QPG 则依赖于局部边缘概率。
• 低深度鲁棒性： 该框架专为近期的量子设备设计。对于定阶图（bounded-degree graphs），每个 Trotter 层级的电路深度与系统规模无关。作者证明，即使在低 Trotter 深度（$p=4$）下，QEG 仍能保持接近精确连续时间极限的性能。

结果
在 3-正则、4-正则以及 Erdős–Rényi 随机图（$n \in \{8, \dots, 20\}$）上进行了数值基准测试。

• 性能： 与经典贪心基准（Greedy LDF, Greedy SDF）和 FastVC 本地搜索启发式算法相比，量子启发式算法（尤其是 QEG-LDF）实现了更低的平均近似比，并能求解更大比例的最优实例。
• Trotter 化： 由于 QPG 对细粒度的概率对比度非常敏感，其性能在低 Trotter 深度（$p=4$）时显著下降；而 QEG 表现稳健，且接近精确的连续时间极限。这表明 QEG 更适合电路深度有限的硬件。
• 行走时间： 算法需要特定的行走时间 $t$（在独立系综上进行校准）来最大化顶点评分之间的差异。最优时间通常出现在波前遍历各层并建立排序模式之后，而非波前首次到达最小覆盖层之时。

意义与主张
论文声称，量子组件的主要用途不在于直接输出完整解，而在于生成逐顶点评分，这些评分编码了可行状态空间的非局部结构信息。这些评分引导递归式的经典缩减，有效地结合了受限量子探索与经典简化过程。

作者对其意义进行了审慎的界定：

• 该方法为组合优化提供了一种实用的、无惩罚项的变分算法替代方案。
• 它证明了受约束的量子行走可以生成有用的排序，从而超越纯粹的局部经典启发式算法。
• 研究识别了一种权衡：基于能量的评分（QEG）提供了更好的对 Trotter 误差的鲁棒性，但代价是更高的测量开销（每步需 $O(|V|)$ 次评估）；而基于概率的评分（QPG）虽然成本较低，但对噪声更为敏感。
• 论文结论指出，关键的开放性问题不在于此类行走是否能生成有用的排序，而在于竞争评分之间的统计分离度如何随问题规模缩放，这将决定其实际应用优势的范畴。

作者明确表示，该框架并不声称能在多项式时间内解决 MVC，也不旨在提供容错计算意义下的精确优化量子加速；相反，它为近期的混合算法提供了一种启发式改进方案。