组合优化问题出现在许多不同领域，包括医学、金融、工程、生物学和许多关键行业。最佳解决方案通常很难获得，随着问题规模的扩大，更是如此。这使得各行各业很难找到好的解决方案来满足业务需求，定位理想的网络位置，或优化路由系统。
量子计算为解决复杂的优化问题提供了一种新的范式。这涉及在寻求最佳解决方案时能够实现计算加速的算法，以及适合当今嘈杂的量子硬件的新型启发式方法。对于量子计算的工业成功，了解如何最好地利用当前设备来实施和解决实际用例中的问题至关重要，这使我们能够识别任何相关障碍并设计策略来克服它们。
在这项工作中，Entropica Labs与Rigetti Computing合作研究量子硬件解决范式优化问题的能力：找到图的最小顶点覆盖。为了实现这一目标，Entropica Labs采用了由 Rigetti Computing 开发的最先进的量子设备 Aspen-M-2 芯片，并从生物技术、金融和网络系统领域的真实数据集中提取问题实例。
Aspen-M-2 设备。Rigetti Computing 开发的最新超导量子比特设备。它拥有 80 个量子比特（qubits），在实验时其平均相干时间为 T1 ≃ 28 μs 和 T2≃ 18 μs。
最小顶点覆盖
图的最小顶点覆盖 (MVC) 定义为连接到图中每条边的最小节点集。计算 MVC 已被证明是一个普遍的 NP-hard问题。
该任务还与另外两个常见的图优化问题有关：找到最大独立集 (MIS)，即图中最大的不相连节点集；并找到最大团（MC），即图中最大的全连接节点集。在现实世界的情况下，特定问题可能会作为三者之一的一个实例出现，但它们总是可以被重铸为另一个实例。因此，人们可以等效地说解决MVC、MIS或MC。
求图的最小顶点覆盖、最大独立集和最大团是等价的组合优化问题。
实际用例
Entropica Labs选择专注于MVC问题，以探索跨广泛领域的商业应用程序。问题实例来自于MVC、MIS和MC自然出现的三个不同领域：
- 供水管网：鉴于其物理结构，这些系统通常用图形表示。该领域出现的一个常见问题是如何以最佳方式分布传感器来监控网络。这转化为一个MVC 问题，属于 MVC 的节点决定监控单元应该放置在哪里。
- 合成生物学：在这一领域，基因结构通常是通过组合已知具有特定功能的 DNA 序列来设计和构建的。生成包含许多具有相似序列的部分的合成 DNA 构建体可能会导致细胞稳定性问题。因此，一个关键的挑战是建立序列尽可能多样化的 DNA 部件库。给定一组作为字符串的 DNA 部分，这个问题可以表述为寻找 MIS，通过将字符串映射到图的节点并在字符串共享的字母超过指定长度时在它们之间添加边。
- 投资组合分配：设计投资组合分配策略的一种方法是利用市场图。市场图是通过将一组股票映射到图的节点并在它们之间绘制边来构建的，只要它们在特定时间段内的相关性大于固定阈值。市场图的一个直接应用是获得相关股票的最大数量，这映射到找到图的 MC。
左:放置在网络节点上的传感器用于监控到后续节点的所有出线连接。中:字符串被映射为节点，当它们共享长度为L >的重复(红色字母)时，在它们之间绘制边;Lmax。右:市场图是通过将股票映射到一个节点(在这个例子中是加密货币)，并在它们的相关性(写在边上)高于某个阈值Cth时将它们连接起来来构建的。
问题实现
通过以下三个步骤在硬件上实现了问题实例：
- 量子比特选择：从可以承载问题实例的所有可能的量子比特集合中，保留了具有最高平均保真度的集合。
- 量子比特路由：使用 SWAP 操作，生成了实例中存在但在Aspen-M-2上不存在的连接。
- 门并行化和取消屏蔽：应用 Rigetti 的软件包 Quil-T 托管的脉冲电平控制工具，以实现并行电路门的同时执行。
此外，该研究还包含了一个错误缓解协议(SPAM Twirling)，以在准备和测量阶段消除量子比特之间的虚假相关性。
问题实例的硬件实现。
使用量子计算找到MVC
该实验采用了两种不同的算法来找到 MVC：量子近似优化算法 (QAOA)，它是用嘈杂的量子计算机进行优化的首选算法；及其递归版本（RQAOA），它递归地减小问题的大小，直到它足够小，可以精确地求解。特别是，研究人员开发了RQAOA的自适应版本(Ada-RQAOA)，能够更快地减少问题规模，同时保持可比的性能水平。
该实验揭示了 Ada-RQAOA 相对于 QAOA 的显著优势，前者在某些情况下非常接近最优解，而后者几乎超过了对许多随机解的平均性能。Ada-RQAOA在多次递归运行中仅使用被认为是最可靠的信息来构造解决方案，而QAOA仅从一次运行中进行估计。
硬件性能
实验的质量受到硬件相干时间的限制。为了最大化量子计算的性能，必须最小化电路的深度以在允许的时间范围内运行。
研究人员发现在实现通用问题实例时需要解决三个主要因素：
量子比特选择标准:在实际设备中，每个量子比特具有不同的相干时间。研究人员发现，错误的量子比特选择会极大地影响性能。通过选择保真度最高的集合，获得了很好的结果，但研究人员希望其他方面，如特定量子比特在路由调度中的作用也很重要。
实例中的边数：大量的边将导致要实现的电路更深。因此，对于较大/密集的实例，实验观察到算法的性能有所下降。根据实验，估计可以获得合理的性能，最多可达150条边。
路由调度的最优性：有多种交换量子比特的方法来满足手头实例的结构。以次优方式这样做不可避免地会导致更长的电路执行时间。因此，研究人员执行了一个额外的优化例程，以最大限度地减少构建计划所需的 SWAP 操作的数量。然而，对于某些情况，只有在 Ada-RQAOA 将大小减小到足以使我们在平均相干时间内运行时才观察到一个清晰的优化过程。
使用量子计算寻找 MVC。(a)-(c) 从 QAOA、Ada-RQAOA 和随机解决方案（平均超过 5000 个样本）和精确解决方案获得的成本。更好的解决方案对应于更低的成本。括号中的标签表示节点数 N 和平均度 ⟨d⟩，如 (N,⟨d⟩)。(d)-(f) 递归优化过程。问题实例：(a)配水网络存储库，(b) Hossain 等人的数据集。Nature Biotechnology 38, 1466 (2020) , (c) Kaggle关于加密货币演变的数据集。
结论
本研究探讨了量子计算在解决硬优化问题方面发挥越来越大作用的潜力。说明了与大规模执行 QAOA 和相关算法相关的关键方法和挑战。
一方面，该研究在量子硬件上进行了 RQAOA 的第一个端到端探索。对算法的自适应修改 Ada-RQAOA 使我们能够探索多达 50 个节点的实例。另一方面，确定了对设备性能有很大影响的三个因素：问题实例中的边数、路由调度的质量和量子比特选择标准。随着设备向更长的相干时间和更高的门保真度发展，能够为更大的问题处理更密集的实例将变得越来越可行。
该研究是朝着解决复杂工业问题的大规模量子计算机迈出的重要一步。现在是组织与量子开发人员合作并研究该技术如何成为其解决问题策略的强大工具的好时机。
---煤油灯科技victorlamp.com翻译整理---
