Max-Cut QAOA on Non-Hardware-Native Graphs via MinLA Surrogates and Configuration Recovery
本文提出了一种混合量子-经典工作流,该工作流通过构建具有更少相互作用的基于 MinLA 的代理模型,随后通过经典精炼策略恢复原始 MAX-CUT 问题的近优解,从而降低了非硬件原生图上的 QAOA 电路深度。
原始论文采用 CC BY 4.0 许可(http://creativecommons.org/licenses/by/4.0/)。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性,请参阅原始论文。 阅读完整免责声明
在构建实用量子计算机的竞赛中,科学家们目前正处于一个艰难的中间地带。他们拥有的机器虽然可以执行某些特定计算,速度远快于传统计算机,但这些机器仍然非常脆弱且规模有限。使用它们最有效的方法之一是解决被称为优化问题的复杂谜题,即在数百万种可能的排列组合中寻找最优解。一种领先的方法被称为量子近似优化算法(QAOA)。它的工作原理是准备一个同时代表许多可能答案的量子态,然后对其进行精炼以找到最佳答案。然而,一个主要的障碍在于:真实的量子芯片并非为直接处理每种类型的谜题而设计。芯片在微小的处理单元之间具有特定的、稀疏的连接布局,而许多有趣的题目则涉及复杂的密集网络,无法与之匹配。为了将不匹配的问题强行映射到芯片上,工程师必须插入额外的步骤来在相距较远的单元之间移动信息,这一过程增加了复杂性和噪声。这种噪声往往会在答案被找到之前就破坏了脆弱的量子信息,导致机器无法解决它原本旨在解决的问题。
IBM 研究院和印度理工学院马德拉斯分校的研究人员开发了一种新策略来绕过这一瓶颈,使量子计算机能够解决比以往更大、更复杂的图论问题。他们的这种方法在 156 量子比特处理器上进行了测试,涉及一种巧妙的两步工作流,平衡了量子机器的能力与经典计算机的修正能力。该团队并没有试图将整个复杂的题目一次性强加给芯片,而是首先创建一个符合芯片物理限制的简化版“代理”问题。他们通过重新排列问题的组件,使得最重要的连接变得短促且局部化,然后仅选择那些可以在不产生过多错误路由步骤的情况下执行的连接。这使得量子计算机能够运行一个更短、更干净的电路,并生成一组候选解。
真正的创新在于接下来的步骤。研究人员并不简单地接受量子计算机的输出作为最终答案。相反,他们将简化量子电路生成的最佳候选解输入到经典计算机中。随后,这台经典计算机会执行一个严格的、逐步的精炼过程,以修复在简化过程中遗漏的信息。它根据原始的、完整的复杂问题对候选解进行评估,并系统地改进它们,直到达到近乎完美的水平。通过将繁重的采样任务与答案的最终打磨分离,该团队成功解决了包含多达 100 个顶点的经典图论问题——MAX-CUT 问题。这些图的密度过高,无法直接在硬件上运行,但这种混合方法产生的解几乎达到了理论上的最优解。
该方法的核心在于如何在数据到达量子芯片之前对其进行特定的组织方式。研究人员使用了一种称为“最小线性排列”(Minimum Linear Arrangement)的数学技术来重新排列图的顶点。想象一下,这个问题就像一张由道路连接城市的地图;目标是找到一种方法将城市分为两组,使得跨越这两组之间的道路数量最大化。在标准的量子芯片上,城市之间的连接是固定且稀疏的。如果问题中的城市在地图上相距甚远,芯片就必须建立长而曲折的桥梁来连接它们,这会引入误差。研究人员的排序技术重新排列了城市,使得那些彼此之间有许多连接的城市在序列中紧挨在一起。这使得他们可以选择一个“带状”(band)的相互作用,这些相互作用都集中在较近的范围内,从而舍弃了那些需要过多易错步骤才能执行的长距离、高成本连接。
这一选择过程受限于电路深度的严格预算,深度本质上是衡量量子计算机必须连续执行多少步的度量。研究人员确定了在特定硬件的深度限制内,能够容纳的最宽连接带。他们确保问题中的每一个城市都仍然是简化模型的一部分,即使其中一些连接被暂时忽略了。这创建了一个代理哈密顿量(surrogate Hamiltonian),即一个量子计算机实际可以运行的简化版能量景观。当他们在 IBM 处理器上运行这个简化电路时,他们发现与尝试运行完整问题相比,所需的步骤减少了一半以上,同时仍保留了原始图的大部分结构。对于测试的规模接近一千个连接的最大图,该方法保留了大约一半的相互作用,这在以往那种将图简化为简单链结构的技巧中是不可能实现的。
随后,量子计算机从这个简化的景观中采样了数千个潜在解。由于电路更短且更干净,它产生的解比在充满噪声的完整深度尝试中产生的解质量更高。然而,这些解仍然是基于一个不完整的图像。为了解决这个问题,团队采用了两种不同的经典恢复策略。第一种是贪婪法,它观察每个城市个体,如果改变其分组归属能增加跨越道路的总数,则进行翻转。第二种更高级的策略则观察城市的分组对,并通过解决一种特定类型的优化问题来寻找协同重新排列它们的最佳方式。这种方法使用了与寻找网络最小割相关的技术,它允许系统跳出那些“单点改变无效、但协同改变有效”的局部陷阱。
这种混合工作流的结果令人瞩目。在处理具有 100 个顶点的图时,即使经过简化,量子计算机的原始输出已经相当不错了。但在经过经典恢复步骤后,解的质量大幅提升。恢复后的最佳解达到了接近 0.997 的近似比,这意味着它们与绝对最优解之间的差距仅为 0.3%。尽管量子计算机从未执行过原始问题所需的完整复杂交互,结果依然如此。研究人员证实,这种提升完全来自于经典精炼过程,因为恢复过程是在每个候选解上独立运行的,不需要再消耗任何量子处理器的运行时间。
这项工作证明,当前硬件的局限性并不一定会阻碍其解决大规模复杂问题。通过承认硬件的约束并设计一种尊重这些约束的工作流,研究人员展示了如何从简化的量子执行中提取有用的信号,并通过经典计算将其放大。该方法之所以强大,是因为它具有可扩展性:随着量子处理器的改进和能够容忍更深的电路,相互作用的“带”可以拓宽,从而包含更多的原始问题,从而减少对经典计算机的工作量。反之,对于当今带有噪声的机器,该方法提供了一条切实可行的路径,证明了“硬件感知型简化”与“经典恢复”相结合,可以为以前无法触及的问题提供高质量的解。研究证实,量子优化的未来或许不在于等待完美、无误差的机器,而在于构建能够利用现有不完美工具进行智能协作的混合系统。
您所在领域的论文太多了?
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要,使用您的语言。