Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings

技术摘要：通过部分纠缠匹配改进量子 MaxCut 算法

问题陈述
本文研究了近似定义在图 $G(V, E, w)$ 上的 2-局部哈密顿量最大能量 $\lambda_{\max}(H_G)$ 的问题。具体而言，它关注两种不同的局部项：

1. 量子 MaxCut (QMC)： 由单态投影算子 $h^{\text{QMC}}_{ij} = 2|\psi^-\rangle\langle\psi^-|$ 定义。该问题的判定版本是 QMA-难的。
2. EPR 哈密顿量： 由 Bell 态投影算子 $h^{\text{EPR}}_{ij} = 2|\phi^+\rangle\langle\phi^+|$ 定义。虽然它是定标性的（stoquastic）且可能比 QMC 更容易解决，但其多项式时间可解性仍是一个开放问题。

目标是找到高效可计算的能量下界 $\ell(G)$，使得近似比 $\alpha = \min_G \ell(G)/\lambda_{\max}(H_G)$ 最大化。现有的方法依赖于半正定规划 (SDP) 松弛（特别是量子矩-SOS 或 Lasserre 层级）来获取上界，并利用各种态制备策略（积态、匹配、变分电路）来获取下界。在此工作之前，已知的最佳比例分别为 QMC 的 $\alpha \ge 0.603$ 和 EPR 的 $\alpha \ge (1+\sqrt{5})/4 \approx 0.809$。

方法论
所提算法的核心创新在于构建一种量子态，它能够部分纠缠与匹配中边相关的比特对，同时保持单比特布洛赫向量的方向（仅允许模长缩放）。这种技术允许作者使用可调参数 $\theta$，在积态与基于匹配的全纠缠态之间进行平滑插值。

关键方法论组成部分包括：

• 边缘性质保持 (Preservation of Marginals)： 与以往在纠缠时可能会破坏局部性质的方法不同，这些算法确保单比特的约化密度矩阵仍与原始积态的边缘分布成比例（加上一个缩放的单位矩阵）。这一性质对于根据初始积态能量来解析地限定不在匹配中的边的能量至关重要。
• EPR 算法 (分数匹配)： 该算法利用分数匹配 $m$ 来定义一个幺正电路。它对初始积态 $|0\rangle^{\otimes n}$ 应用旋转 $e^{i\gamma_{uv} P_u P_v}$，其中旋转角度 $\gamma_{uv}$ 由分数匹配权重和固定参数 $\theta = \frac{1}{2}\ln(\phi)$（其中 $\phi$ 是黄金比例）决定。
• QMC 算法 (部分匹配)： 该方法结合了两种策略：
  1. PMATCH： 一个子程序，它接收一个源自 SDP 的积态，识别出在重加权边上的最大权整匹配，并将匹配边上的积态替换为满足边缘保持约束的、由参数 $\theta$ 参数化的部分纠缠双比特态。未匹配的比特也会进行缩放。
  2. 混合选择 (Hybrid Selection)： 最终算法输出标准 MATCH 算法（全纠缠匹配）与 PMATCH 算法（部分纠缠）中能量较高的那个态。
• 重加权策略： 对于 QMC，算法根据重加权边 $w'_{ij} = w_{ij} \cdot (\sin \theta (1 - t_{ij}(1+\sin \theta)))^+$ 选择匹配，其中 $t_{ij}$ 是积态中布洛赫向量的内积。这有效地扩大了搜索空间，超越了标准的极大权匹配。

主要贡献与结果
论文提出了两个主要定理，确立了改进的近似比：

1. 定理 1 (EPR)： 所提算法实现的近似比为 $\alpha \ge \frac{1+\sqrt{5}}{4} \approx 0.809$。

   • 注： 作者承认该特定比例曾由 [JN25] 使用不同的算法同时且独立地实现，但作者声称其算法和分析更为简单。分析表明，该算法对于某些图（如单边图）是最优的。

2. 定理 2 (QMC)： 所提算法实现的近似比为 $\alpha \ge 0.611$。

   • 该结果依赖于用于上界的第 13 层 Lasserre 层级。
   • 作者指出，如果纠缠单配性 (monogamy-of-entanglement) 不等式中的上界常数 $d$ 改进为 1（正如 [APS25] 使用分离算子所建议的那样），则仅使用第 2 层层级即可将比例提升至 $\alpha \ge 0.614$。

意义与主张
本文声称其意义主要在于引入了“部分纠缠匹配”技术。通过在积态与匹配态之间进行插值并保持单比特边缘性质，作者可以利用初始积态的能量来严格限定整个系统的能量。这允许通过优化纠缠参数 $\theta$ 来最大化最坏情况下的近似比。

这项工作改进了 QMC 的现有技术水平（将界限从 0.603 提高到 0.611），并为 EPR 提供了概念上更简单的推导。作者强调，其针对 EPR 的分析在特定图结构下是紧致的；而对于 QMC，如果能结合更紧致的 $\lambda_{\max}(H_G)$ 上界，则仍存在进一步提升的空间。这些算法是构造性的，提供了能够实现这些能量保证的具体量子态（或电路）。