A Unified Local Light-shifts Encoding For Solving Optimization Problems on a Rydberg Annealer

本文提出了一种统一框架，通过局域光频移编码将各类 NP 难组合优化问题映射为二次无约束二值优化（QUBO）形式，并结合优化的量子退火协议，在里德堡量子退火器上求解这些问题，同时引入广义难度参数以量化问题复杂度。

要点

想象你正在试图解开一个巨大而错综复杂的拼图。有些拼块很容易契合，而另一些似乎彼此对抗，造成一团难以理清的混乱。在计算机世界中，这些拼图被称为优化问题。它们范围从简单的逻辑游戏到复杂的现实世界挑战，例如安排工厂、分组数据，甚至弄清楚蛋白质如何折叠成其三维形状。

本文提出了一种新的统一方法，利用一种由里德伯原子构成的特殊“量子计算机”来解决这些拼图。以下是作者所做工作的分解，辅以简单的类比。

1. 问题："NP 难”迷宫

许多这类拼图属于称为NP 难的类别。想象一下试图在一个墙壁不断变化的迷宫中寻找最短路径。一台普通计算机（如你的笔记本电脑）必须逐一检查每一条路径，随着迷宫变大，这需要耗费永恒的时间。作者希望看看量子机器是否能更快地找到出口。

他们选择了一种特定类型的拼图，称为QUBO（二次无约束二进制优化）。将 QUBO 视为这些拼图的通用语言。无论你是在尝试打包行李箱（集合打包）、将工人分配给任务（二次分配），还是折叠蛋白质，你都可以将规则翻译成这种二进制语言（0 和 1）。

2. 解决方案：里德伯“原子乐团”

作者没有使用通常的量子计算机（它们可能难以捉摸且难以扩展），而是使用了里德伯原子。

• 类比：想象一群被囚禁在网格中的原子，就像管弦乐队中的音乐家。每个原子可以处于两种状态之一：“基态”（睡眠）或“里德伯态”（兴奋/清醒）。
• 相互作用：当一个原子醒来时，它会变得非常大并与邻居相互作用。如果两个邻居都醒着，它们会互相推挤（这称为里德伯阻塞）。
• 创新：通常，为了解决这些拼图，你必须迫使原子以非常具体、复杂的方式相互作用，这需要大量的原子（就像需要 100 名音乐家来演奏一首只需要 10 人的歌曲）。作者开发了一种**“局部光频移”**方法。
  • 隐喻：与其强迫整个乐团更换乐器，指挥（激光）只需向每位音乐家低声传达特定的指令（调整他们的“失谐”）。这使得他们能够演奏确切的歌曲（解决特定的拼图），而无需额外的音乐家或复杂的设置。这使得系统更加高效且可扩展。

3. 过程：引导系统回家

一旦原子被设置好以代表拼图，作者就需要引导它们找到解决方案。

• 旅程：他们使用一种称为量子退火的技术。想象一个球滚下丘陵地带。目标是将球引导至最深山谷的底部（最佳解决方案）。
• 挑战：这片地形充满了小凹陷（局部极小值），球可能会被困在其中，误以为自己已到达底部，而实际上并非如此。
• 技巧：作者使用了一种智能的“控制协议”。他们不只是让球滚动；他们轻轻摇晃地形（使用称为拉比频率的激光脉冲）并以精确的、随时间变化的方式倾斜地面（调整失谐）。这有助于球“隧穿”过山丘或将自己从小的凹陷中摇出，从而找到真正最深的山谷。他们使用智能算法的组合来寻找完美的摇晃模式。

4. 结果：解决不同的拼图

该团队在七种不同类型的拼图上测试了这种方法，从简单到非常困难：

• 简单的：简单的逻辑拼图（如 2-SAT），答案直截了当。该系统以近乎完美的准确率（99.9%）解决了这些问题。
• 困难的：复杂的问题，如蛋白质折叠（弄清楚氨基酸链如何扭曲）和二次分配（优化设施布局）。
  • 结果：对于蛋白质折叠示例，该系统找到了一个非常好的解决方案（98% 的准确率），尽管并非完美。作者解释说，这是因为蛋白质折叠的“地形”非常平坦且令人困惑，有许多看起来像解决方案但实际上并非如此的路径。
  • 关键发现：该方法使用相同的基础设置解决了所有问题，证明它是一个“统一”的框架。

5. 衡量“难度”

为了理解为什么有些拼图比其他拼图更容易，作者发明了一个**“难度参数”**。

• 类比：将其视为拼图能量地形的“难度评级”。
  • 如果最深山谷远离所有其他山谷（存在巨大间隙），则很容易找到。
  • 如果有许多几乎与最佳山谷一样深的山谷，或者地面平坦且令人困惑，则拼图是“困难”的。
• 洞察：他们发现像蛋白质折叠这样的问题是最难的，因为它们的能量地形最为拥挤和平坦，使得系统难以将真正的最佳解决方案与“几乎最佳”的解决方案区分开来。

总结

简而言之，作者利用里德伯原子构建了一个灵活、高效的“量子游乐场”。通过给予每个原子个性化的指令（局部光频移）并以智能、优化的节奏引导它们，他们成功解决了一系列复杂的优化拼图。他们表明，虽然由于结构原因，某些拼图天生比其他拼图更难，但这种统一的方法可以应对所有问题，而无需为每种类型的问题使用不同的机器。

技术摘要

技术摘要：基于里德堡退火器求解优化问题的统一局域光频移编码方案

问题陈述
组合优化问题（其中许多属于 NP 难复杂度类，例如二次分配、蛋白质折叠）对于经典算法而言计算困难，但具有重要的实用价值。虽然量子算法提供了潜在优势，但将这些问题映射到量子硬件上往往会产生巨大的资源开销。具体而言，现有的基于里德堡原子的编码方案通常依赖里德堡阻塞机制，这通常需要在原子数量上相对于问题规模产生二次方开销。此外，变分量子算法往往难以应对巨大的参数空间及其自身参数的 NP 难优化问题。作者旨在通过开发一个统一框架，在里德堡量子平台上编码并求解多样化的二次无约束二值优化（QUBO）问题，从而减少资源开销并提高可扩展性。

方法论
本文提出了一种名为"LOQAL"（Loop 中量子退火的局域最优控制）的统一框架，该框架利用被光镊捕获的里德堡原子。该方法包含三个主要组成部分：

1. 通过局域光频移实现的统一编码：
   作者采用了一种非阻塞编码方案，而非依赖阻塞约束。他们利用单个原子上的局域光频移（失谐），将 QUBO 问题直接映射到伊辛自旋模型。

   • 哈密顿量映射： 系统由一个里德堡哈密顿量描述，该哈密顿量包含全局拉比频率（$\Omega$）和与位置相关的失谐（$\Delta_j$）。在拉比频率为零的极限下，这映射为具有纵向场和成对相互作用的伊辛哈密顿量。
   • 参数控制： 问题的相互作用强度（$J_{ij}$）被映射到原子间的范德华相互作用（$V_{ij}$），后者由原子间距离控制。局域纵向场（$h_i$）被映射到与位置相关的失谐（$\Delta_j$）。这种直接、线性的映射使得物理量子位的数量直接对应于二值变量的数量，从而避免了阻塞方案的二次方开销。
   • 范围： 该框架在七类不同的问题上进行了演示：Two-SAT、XOR-SAT、混合 Two-XOR-SAT、集合打包、二次分配问题（QAP）、二值聚类和蛋白质折叠（HP 模型）。

2. 优化的量子退火协议：
   为了找到目标哈密顿量的基态，作者利用了一种最优控制方法。

   • 脉冲整形： 时间依赖的失谐（$\Delta_j(t)$）和拉比频率（$\Omega(t)$）分布被优化，以引导系统从初始态（例如全基态或全激发态）演化至目标基态。
   • 混合优化： 脉冲形状是通过结合基于梯度和无梯度优化器的混合优化策略确定的。该方法旨在通过到达低能子空间、逃离局部极小值并微调至全局极小值来穿越优化景观。
   • 目标函数： 优化过程最小化瞬时状态相对于目标哈密顿量的期望值，同时监测保真度和近似比率。

3. 难度参数定义：
   为了量化和比较不同问题实例的难度，作者引入了一种通用的、与具体方法无关的难度参数（$H_{PMI}$）。该参数整合了：

   • 基态与第一激发子空间之间的能隙（$G_\Delta$）。
   • 基态的简并度（$D_{opt}$）以及威胁性次优子空间的简并度（$D_\alpha$）。
   • 问题的能量尺度（$|E_{opt}|$）。
     该参数认为，具有小能隙、次优态高简并度或大量“威胁性”子空间的问题在计算上更难求解。

关键结果
作者使用铯里德堡原子（$60S_{1/2}$）对七种问题类型的原型实例（通常涉及 3 到 5 个变量）进行了数值模拟。

• 性能指标： 该协议在大多数问题上实现了高近似比率（$R$），范围约为 0.98 至 0.999。
  • 高保真度： 具有有利结构的问题，如 Two-SAT（无挫败）和二值聚类（原生于里德堡哈密顿量结构），实现了接近 1.0 的近似比率（分别为 $R \sim 0.999$ 和 $R \sim 1.0$）。
  • 具有挑战性的实例： 更复杂或“非原生”的问题显示出较低的保真度。蛋白质折叠实例（HP 模型）的近似比率为 $R \sim 0.98$，保真度约为 0.97，这归因于平坦的能量景观和几何约束。二次分配问题（QAP）也显示出降低的保真度（$R \sim 0.9985$），这是由于其二次方变量缩放和简并性所致。
• 难度分析： 计算出的难度参数（$H_{PMI}$）与模拟结果相关。蛋白质折叠表现出最高的难度（$H_{PMI} \approx 307.81$），这是由于其能隙较小（0.08）以及显著的次优简并性。相比之下，XOR-SAT 和集合打包显示出较低的难度值（分别为 1.13 和 4.79），并以更高的精度求解，这与它们较大的能隙一致。
• 协议动力学： 结果表明，对于较简单的问题，存在多种最优协议。对于较难的问题，优化景观需要更复杂的脉冲形状（例如重叠的拉比峰）和更多迭代才能收敛。

意义与主张
作者声称，这项工作展示了一个统一框架，能够在单一物理架构内处理各种组合优化问题——从多项式时间可解的情况到 NP 难问题。

• 资源效率： 主要意义在于编码方案的线性开销。与随变量数量呈二次方增长的阻塞方法不同，这种局域光频移方法呈线性增长，使其更适合量子位数量有限的近期量子设备。
• 灵活性： 局域失谐的使用允许实现特定于问题的约束，而无需为不同类型的问题采用不同的编码方案。
• 基准测试工具： $H_{PMI}$ 难度参数的引入提供了一种分析 QUBO 问题谱特性的工具，用于预测其对量子退火的难度，且独立于所使用的具体控制方法。
• 可扩展性潜力： 虽然当前结果是在小规模实例上的原理验证，但该框架被提出作为基于里德堡的模拟量子优化器的可扩展发展路径，并为基于门控的量子方法提供了基准。

本文结论指出，虽然该方法显示出前景，但需要进一步研究以评估其对噪声的鲁棒性以及在更大、更复杂实例上的性能。