组合优化问题是具有离散但大量可能解决方案的复杂问题。这些问题的一些最著名的例子是旅行推销员、装箱问题和车间调度问题。作为 AWS 智能和高级计算机技术实验室的一部分，亚马逊量子解决方案实验室的研究人员最近开发了一种新工具来解决基于图神经网络 (GNN) 的组合优化问题。Schuetz、Brubaker 和 Katzgraber 开发的方法发表在Nature Machine Intelligence上，可用于优化各种现实世界的问题。

“我们的工作非常受客户需求的启发，”进行这项研究的研究人员之一 Martin Schuetz 告诉 TechXplore。“在我们在亚马逊量子解决方案实验室的日常工作中，我们与各个垂直领域的许多客户在他们准备量子的旅程中进行互动，即为这种新兴技术在商业上可行的未来做好准备。大多数客户用例都涉及组合优化问题。”

在消费者服务的上下文中，组合优化问题可以有许多不同的形式。这些问题的两个值得注意的例子是财务中的投资组合优化问题和制造业中的车间调度任务。投资组合优化一词是指在一组可用投资组合中为特定情况选择最佳投资组合或资产分配的过程。

另一方面，作业车间调度问题发生在必须执行一组作业或任务并且执行这些任务的资源/工具集有限的情况下。在这些情况下，可能会要求人们找到一个最佳时间表，该时间表利用可用工具在尽可能短的时间内执行任务。

由于量子技术仍处于早期发展阶段，研究人员一直在尝试开发不完全依赖量子计算机的优化工具，至少在这些计算机在商业上可行之前是这样。因此，在他们的论文中，Schuetz 和他的同事介绍了一种基于 GNN 的优化技术，该技术受到物理学的启发。

“鉴于其固有的可扩展性，受物理启发的 GNN 目前可用于近似解决(大规模)量子原生模型的组合优化问题，同时通过使用量子设备理解的数学表示来帮助我们的客户做好量子准备，”布鲁贝克说。

Schuetz 和他的同事开发的方法首先确定了哈密顿量(即成本函数)，它编码了人们试图解决的特定优化问题。随后，它将相应的决策变量与图中的节点相关联。

“我们的关键思想是将组合优化问题构建为无监督的节点分类任务，由此 GNN 学习每个节点的颜色(换句话说，自旋或变量)分配，”Schuetz 解释说。“为此，GNN 通过自定义损失函数进行迭代训练，该损失函数对感兴趣的特定优化问题进行编码，与原始哈密顿量一一对应，从而为 GNN 的损失函数提供原则性选择。”

在训练 GNN 之后，该团队将其生成的软节点分配的最终值预测为硬类分配。这最终使他们能够近似地解决感兴趣的大规模组合优化问题。

Schuetz 和他的同事提出的方法与其他解决组合优化问题的方法相比具有几个优点。最值得注意的是，他们的方法具有高度可扩展性，这意味着它可以用于计算优化具有数亿个节点的复杂问题。

“我们的 GNN 优化器基于原型 Ising 自旋哈密顿量与我们用来训练 GNN 的可微损失函数之间的直接和一般数学关系，从而为广泛的组合优化问题提供了一个统一的框架，并打开了强大的工具箱物理学到现代深度学习方法，”布鲁贝克说。“将物理学概念与现代机器学习工具相结合，我们提出了一种简单、通用且强大的求解器，它不依赖于手工制作的损失函数。”

值得注意的是，Schuetz 和他的同事设计的方法可以近似地解决优化问题，而不需要训练标签，这是所有监督学习方法的关键要求。由于该技术将优化问题转换为伊辛哈密顿量，它也可以在量子硬件上本地运行。

“我们为优化问题提供了一个统一的跨学科框架，该框架结合了物理学的见解和现代深度学习的工具，”Schuetz 解释说。“有了这个框架，我们就有了一个广泛适用于典型 NP-hard 问题的工具;突出的例子包括最大切割、最小顶点覆盖、最大独立集问题以及伊辛自旋玻璃。”

未来，这组研究人员引入的基于 GNN 的新方法可用于解决各种复杂的现实优化问题。由于它本质上具有可扩展性，亚马逊量子解决方案实验室和 AWS 计划将其作为一种工具提供给他们的客户，以促进他们向量子技术的过渡。事实上，他们的技术可以让客户在量子原生建模框架中解决与特定用例相关的两个问题，无论是在小规模还是与行业相关的规模上。

“未来，我们将继续研究概念性、理论性以及更多应用研究问题。一方面我们有几个想法如何改进和扩展所提出的 GNN 优化器的能力，另一方面有我们可以尝试使用这个新工具解决许多应用用例。我们将继续使用客户反馈来帮助我们指导和优先考虑我们的研究议程，”Katzgraber 说。