A 0.651-approximation to quantum Max Cut via Rydberg atoms

技术摘要：通过里德堡原子实现量子最大割问题的 0.651 近似

问题定义
本文研究了量子最大割（Quantum Max Cut, QMC）问题，该问题等价于寻找反铁磁海森堡哈密顿量的基态能量。该问题属于 QMA 完全类，这意味着即使使用通用量子计算机也无法高效解决。目标是找到一种近似算法，其保证解在最优基态能量的特定比例 ($\alpha$) 之内。目前最先进的经典方法主要依赖半正定规划（SDP）松弛，其实现的近似比为 $\alpha = 0.614$。

方法论：一种混合量子-经典方法
作者提出了一种结合了里德堡原子系统自然量子动力学与经典优化技术的混合算法。该方法分为四个阶段进行：

1. 编码与退火：
   将定义在图 $G=(V, E, \omega)$ 上的 QMC 实例编码进里德堡原子阵列中。构建里德堡哈密顿量 $H_r$ 的静态部分，使其包含对应于图边的 $XX + YY$ 相互作用项：
   $$H_r = \sum_{(ij) \in E} \omega_{ij} (X_i X_j + Y_i Y_j)$$
   系统经历退火过程以准备出一个近似基态，记作 $\varrho_r$。

2. 测量与约束构建：
   针对退火态 $\varrho_r$ 中的所有边，测量其期望值 $\langle X_i X_j + Y_i Y_j \rangle$。这些值将作为后续经典优化步骤的经验约束。

3. 半正定规划与舍入：
   通过 SDP 优化一个伪矩矩阵 $\Delta$，并受限于从里德堡测量中获得的约束以及泡利算符的代数关系。随后，利用随机投影技术（采用 Cholesky 分解，并将 $\mathbb{R}^{4n}$ 随机投影至 $\mathbb{R}^3$）将该矩阵舍入为一个乘积态 $\varrho_p$。

4. 最终状态选择：
   算法返回能量较低的状态：即里德堡基态 $\varrho_r$ 或经典舍入后的乘积态 $\varrho_p$。

核心理论贡献
本文确立了一个条件近似比 0.651，超越了此前已知的 0.614 的最佳比例。其推导基于两个主要的理论见解：

• 通过里德堡基态建立下界： 作者证明，可以通过里德堡哈密顿量 ($H_r$) 的能量来为完整 QMC 哈密顿量 ($H_{qmc}$) 的基态能量建立下界。通过利用海森堡模型的 $SU(2)$不变性，他们展示了在最优基态下，$XX$、$YY$和$ZZ$的期望值是相等的。这使得能够从里德堡系统获得的局部$XX+YY$ 测量值中重建完整的 QMC 能量。
• 通过舍入建立上界： 本文分析了由 SDP 舍入生成的乘积态 $\varrho_p$ 的能量。根据测得的相关性，推导出了该状态期望能量的解析表达式。
• 比例优化： 通过结合下界（源自里德堡态）与上界（分别来自里德堡态和乘积态），作者构建了一个关于相关参数 $t_{ij}$ 的最小化问题。通过求解该问题，得到了 0.651 的比例。

结果与鲁棒性

• 近似比： 该算法实现了 0.651 的条件近似比 $\kappa$。
• 对噪声的鲁棒性： 一个重要的发现是该算法对不完美基态准备的韧性。作者证明，即使里德堡退火过程产生的状态仅达到真实里德堡基态能量的 89% ($\eta = 0.89$)，0.651 的优势依然存在。低于此阈值时，其相对于纯经典 SDP 方法的优势才会减弱。
• 计算复杂度： 这种混合方法降低了经典优化问题的维度。虽然针对纠缠态的经典方案需要 $O(n^4)$ 个实变量，但这种混合方法利用 $O(n^2)$ 个变量进行操作，通过利用量子系统来处理纠缠结构的复杂性。

意义
本文声称开辟了混合量子-经典算法的新途径。它表明，将量子硬件（特别是里德堡原子阵列）与经典优化相结合，可以产生比纯经典方法更强的近似保证，即使量子硬件并未完美解决底层的哈密顿量问题。这项工作表明，量子平台可以作为有效的“代理”，提供高质量的下界和经典舍入程序的起点，从而有效地绕过纯经典方法中存在的某些计算缩放限制。