突破！中性原子量子计算实现了开销更低的通用编码

光子盒研究院出品

哈佛-MIT衍生的中性原子量子计算公司QuEra Computing取得新进展，该公司的研究人员和合作者开发了一个通用编码蓝图，它能用于优化中性原子阵列上的任意连通性问题。

组合优化以从大批离散方案中找到一个最优的解决方案，在许多科学技术领域有着普遍应用。不过，类似问题对于经典算法来说难以计算，属于NP-hard复杂度类别：探索解决这些困难问题是现代量子信息科学的主要课题之一。

在QuEra的最新研究中，相干的、可编程的里德堡（Rydberg）原子阵列被证明可以自然编码几何图形上的最大独立集（MIS）的组合优化问题之一——单位圆盘图（UDG），并观察到了比优化的经典模拟退火更高的超线性量子速度，为未来的探索提供了很好的前景。相关论文以《使用里德堡原子阵列进行任意连通性的量子优化》为题[1]提交至arXiv网站上。

今年5月，QuEra参与的研究《使用里德堡原子阵列的最大独立集的量子优化》已经发表在《科学》杂志上。其中采用了289个（17×17阵列）量子比特的中性原子量子处理器。

01

里德堡原子阵列，编码解决优化问题

在过去的二十年里，人们提出了多种量子算法：如量子绝热算法（QAA）、量子近似优化算法（QAOA）。这些方法的核心往往涉及到将优化问题的解决方案编码到可调整的量子哈密顿量的基态中；因此，在物理上可实现的量子哈密顿量的有效编码构成了一个实际挑战。

最近，里德堡原子阵列被证明可以编码一类几何图形上的最大独立集（MIS）的组合优化问题——单位圆盘图（UDG），并观察到了比优化的经典模拟退火法更高的超线性量子速度。对于UDG，使用里德堡原子的编码是无开销的，因为图的每个顶点可以由一个原子表示，硬件连接直接对应于单位盘连接。此次实验中，团队将这种方法扩展到更广泛的优化问题：包括任意图上的最大权重独立集（MWIS）问题、二次无约束二元优化（QUBO）、伊辛问题，以及整数分解等典型问题；所有元素都已被证明可以在当前的里德堡原子阵列平台实现。

使用可编程的里德堡原子阵列解决各种优化问题。原有的计算问题（a）可以映射到（b）中单位圆盘图（UDG）上的最大权重独立集（MWIS）问题。(c)物理平台，(b)中的每个顶点代表一个被光镊捕获的原子。每个两能级原子都可以用拉比频率Ω和失谐∆进行相干驱动，如果两个原子在单位距离内，里德堡阻塞机制就会阻止它们同时被激发到状态|1⟩。(d)UDG-MWIS问题的解编码了原始问题的解。

对于在量子计算机上的实施来说，找到一个低开销的显式映射极其重要，这也是此次实验的关键目标。将里德堡原子阵列的适用性扩展到UDG之外，但它们要么仅限于特定的图类，要么需要三维阵列。其他将任意非局域相互作用映射为局域相互作用的方案在实验上要求更高，需要4体相互作用[2]或可调谐的伊辛相互作用[3]。相比之下，此次方案只依赖于里德堡阻塞，只需要二维阵列；因此，它可以很容易地在目前的里德堡原子阵列实验中实现。

02

三大编码案例，UDG上的MWIS问题映射

这项工作的主要结果是，给定一个计算问题，能够使用一个新的编码方案将其映射为UDG-MWIS问题（即UDG上的MWIS问题）。由此产生的UDG-MWIS是里德堡原子阵列平台的本地问题，允许直接实施QAA或QAOA来解决：将为低开销、高效率和明确的映射提供一个通用框架。下图总结了本工作中详细讨论的三个例子：

三个示例问题的UDG-MWIS映射。(a)在MWIS和二次无约束二元优化（QUBO）问题上，用G=(V, E)表示非UDG的例子。(b)用来构建UDG-MWIS映射的交叉网格。(a)中的顶点是二元变量，可以有效地用线条表示，以构建网格。网格中的交叉点允许变量之间任意连接，抽象地用方块表示。网格模仿上三角邻接矩阵A，对于两个顶点{v，w}∈V，如果（v，w）∈E，Avw=1，否则Avw=0，这里分别用填充和空方块抽象地表示。(c)一般图上原始MWIS问题的最终UDG-MWIS表示。(d)原始QUBO/伊辛问题的最终UDG-MWIS表示。(e), (f), (g) 对6=2×3的整数分解问题的类似编码过程，以及相应的UDG-MWIS表示。

03

下一步探索：高阶多变量问题计算

在这项工作中，研究团队描述了一种编码策略，可以将各种具有任意连通性的计算问题映射为单位圆盘图上的最大加权独立集问题，这些问题在通过里德堡态相互作用的中性原子的量子优化实现。该编码在优化问题的变量数量上最多产生四次开销，因此非常有效。此外，该映射遵循一个明确的、直接的程序：它产生了一个单位圆盘图，可以嵌入到一个正方形格上，对必要的单位圆盘半径有有利的条件，因此可以通过里德堡原子阵列来实际实现。

除此之外，团队提供了三个具体的问题映射例子：任意连接的一般图上的MWIS问题、QUBO问题和整数分解问题。数值模拟表明，量子算法在映射问题上的性能与原始问题的性能直接相关，这表明原始图中的任何二次方量子加速可以转移到单位圆盘图上的等效加速。

未来，以下方向值得进一步探索：首先，方法可以推广到涉及三个或更多变量的相互作用的计算问题，如高阶无约束二元优化（HUBO）问题；考虑二维几何以外的编码方法也很有意义：例如，将交叉格的概念概括为三维的“交叉立方体”；人们可以设计三维中开销较低的编码方法。

参考链接：

[1]https://arxiv.org/abs/2209.03965

[2]https://www.science.org/doi/10.1126/sciadv.1500838

[3]https://journals.aps.org/prxquantum/abstract/10.1103/PRXQuantum.1.020311

相关阅读：

每周一到周五，我们都将与光子盒的新老朋友相聚在微信视频号，不见不散！

你可能会错过：