哈佛大学和QuEra Computing、麻省理工学院、因斯布鲁克大学及其他机构的科学家合作，展示了中性原子量子处理器在解决实际应用问题方面的突破性应用。他们在哈佛的 289 个量子比特的里德堡（Rydberg）原子阵列上，以模拟模式运行，展示了“最大独立集”问题的量子加速，其有效电路深度高达 32。中性原子量子处理器此前已经被提出，并已有效地编码一些复杂的组合优化问题。而在这个工作中，作者不仅首次在此类量子处理器上部署实现了高效量子优化，还展示了前所未有的量子硬件能力。相关研究成果于5月5日发表在《科学》杂志上。
组合优化在科学技术的许多领域都是普遍存在的。许多这样的问题已经被证明是计算困难的，并且构成了理解现代计算机科学中复杂类的基础。20多年来，人们一直在使用各种量子算法，从理论上探索如何使用量子机器来加速解决此类问题。通常，相关成本函数以量子哈密顿量编码，并且通过绝热演化或变分方法，通过闭合优化循环从通用初始态开始寻找其低能态。此类算法的计算性能已在具有浅量子电路的小型量子系统或缺乏多体相干特性的系统中进行了理论和实验研究。然而，这些研究对算法在涉及大尺寸系统和高电路深度时的性能提供的参考有限。
在本次的工作中，联合团队使用一个基于光镊中中性原子的相干可编程阵列的量子器件来研究39到289个量子比特系统的量子优化算法，以及量子关联在整个图形中传播的有效深度。具体来说，他们研究了图论中的“最大独立集”问题，一个典型的NP-hard优化问题。该团队用“难度参数”来描述优化问题实例的难度，并用中性原子量子处理器更有效地解决了这些实例。与一类经典算法相比，发现了超越线性的量子加速。QuEra的开源软件包GenericTensorNetworks.jl和Bloqade.jl在发现困难实例和理解量子性能方面发挥了重要作用。
问题与量子硬件匹配的重要性是该工作的核心：在不久的将来，要尽可能多地提取量子功率，关键是要找出从能够本地映射到特定量子体系结构中的问题，这可大幅降低计算开销， QuEra Computing高级科学家、本工作所用量子算法的共同发明者之一的Wang说，我们在这个演示中恰好实现了这一点。该团队解决的“最大独立集”问题是计算机科学中的一个典型难题，在物流、网络设计、金融等领域有着广泛的应用。通过量子加速解决方案识别具有经典挑战性的问题实例，为应用量子计算满足现实世界的工业和社会需求铺平了道路。
扩展：一个独立集是图中一些两两不相邻的顶点所形成的集合。换句话说，独立集S由图中若干顶点组成，且S中任意两个顶点之间没有边。可以看出，图中的每条边至多有一个顶点属于集合S。一个独立集的基数是它包含的顶点的数目。如果S是图中所有独立集中基数最大的，那么S就是该图的最大独立集（S可能不唯一）。给定一张图，寻找其最大独立集的问题被称为最大独立集问题。该问题已知是NP-hard的最优化问题，计算机科学家普遍相信不存在解决该问题的高效经典算法，无论是精确求解还是以常数倍近似求解。