量子计算在优化问题中有着广泛的应用,并为克服一些著名的挑战提供了新的方法。在这里,我想讨论量子近似优化算法(QAOA),它是用于处理优化任务的最流行的量子计算技术之一。通常,在谈论 QAOA 及其应用时,Max-Cut 是一个说明性示例,但在这篇文章中,我打算展示如何借助该算法解决支配集问题 (DSP)。(所有实现和模拟都是使用 Qiskit 完成的,模型本身基于 IBM Qiskit 关于 QAOA 的教程。)
Github项目的链接:https://github.com/VasilyBokov/Dominated-Set-Problem-QAOA-Qiskit-Bokov.git
1支配集问题
这个设置很容易理解。假设我们有一个特定的地理区域,其中有需要监视的丘陵和山谷。在某些区域之间存在允许监视设备一次查看多个目标的连接。例如,我们可能会使用无人机监视山区的运动或位于山谷中的区域。监视目标可以被认为是图的节点,所有连接都可以被认为是连接节点的边。那么优化问题是调查整个网络所需的最少无人机数量。

图 1. 5 个节点的最佳无人机设置。
数学陈述
我们以 的形式为 DSP 编写了一个解决方案,如果 ,我们将无人机放置在第 个节点上,否则不放置无人机。任何优化问题的关键是创建我们打算最大化或最小化的成本函数 。在我们的例子中,这个函数将由两部分组成,即 和 。第一个子句测量被调查目标的数量(就本定义而言,每个节点都连接到自身)。网络中调查的节点越多,成本函数越大。第二组子句测量使用的无人机数量

它可能想知道为什么 的最大化会导致 DSP 解决方案。实际上,上面定义的子句列表并不完全对应于支配集问题,它需要进一步的算法来向 DSP 输出解决方案。幸运的是,该算法在图上节点数的多项式时间内运行,因此不会影响整体 QAOA。假设 以某种方式找到(经典计算机通过蛮力、QAOA 或其他算法)。首先,如果 ,则将无人机放在第 个节点上,并且不要以其他方式放置无人机。接下来,使用经典计算机检查每个节点,看看它是否受到监视(回想一下,第 个节点上的无人机意味着该节点受到监视)。这一步的一个微不足道的上限是 次操作,因为 节点中的每一个节点最多可以有 条边(我们在此步骤中计算自我监视)。最后,如果某些第 个节点不受监视,则在该节点上放置一架无人机。可以看出,这种代价函数+附加算法的方案为我们提供了DSP的解决方案。精确的数学推导可以在这里看到。
2. 算法实现
QAOA 简要说明

图 2 QAOA 总体方案
QAOA 是一种启发式方法,它根据经典计算机要优化的参数使用一定数量(p = depth )的酉算子。这些酉是通过量子系统的哈密顿量构造的。主要目标之一是构造一个特定的哈密顿量,使其最小值对应于成本函数的最小值。经过多次迭代,我们预计解决方案将是最可能的测量结果。
为了清晰和模拟速度,我想在这里考虑一个非常原始的案例,只有 3 个节点。使用了基本的 QAOA 方法,可以在 Max-Cut 问题的 Q iskit 示例中找到一个示例。

图 3. 我们正在使用这个简单的 3 节点模型。
电路构造
考虑 3 个节点模型并为成本函数的 T 和 D 部分定义量子电路。
与MCP不同,DSP的实现需要一个额外的辅助量子位。因此,对于这个问题,使用了 4 个量子位。如果第 k 个节点与“无人机节点”连接或安装了自己的无人机,则 。因此,我们需要使用描述该节点的所有边的控制或旋转门检查我们图的所有节点,并将结果放入辅助量子比特的一个阶段。在 3 个节点的示例中,我们将为 T 部分提供以下电路:

图 4. T(z) 的电路部分,具有 3 个描述给定图形的量子位和 1 个辅助量子位。
对于 D(z) 部分,我们只是按顺序对每个节点使用简单的控制旋转。此外,就像在每个 QAOA 模型中一样,从一开始我们就应该对所有“节点量子比特”应用 Hadamard 门,即只有辅助量子位没有应用 Hadamard。在测量之前,我们通常在 QAOA 中使用 X 旋转。因此,将所有部分组合在一起后,我们的电路如下所示:

图 5.深度 p = 1 要优化的最终电路
这里应该提到的是,对于较大的深度p,我们重复Hadamards和测量之间的部分p次。
模型性能
首先,我尝试使用 p = 1 和“COBYLA”优化器来实现模型。您可以在下面找到最终测量的结果,这是可以接受的,因为最优解010是最有可能的。但与 MCP 模型相比,性能相当差,即其他解决方案101, 000,001,100也有很高的机会被测量。

图6.p=1 的 QAOA 测量分布概率
现在,性能要好得多,但计算大约需要 10 分钟,对于这样一个简单的模型来说,这个时间很长。

图 7. p=10 的 QAOA 测量分布概率
那么,有人可能会问:更复杂的图呢?
好吧,让我们举一个更复杂的例子:

图 8. 具有一种可能解决方案的 6 量子位模型 — 010010
注意,这里有两种可能的解决方案010010, 101000,Qiskit 对量子比特使用相反的顺序,我们最想要的结果是010010, 000101
取p=7,花了大约30分钟的时间进行优化。最后,我得到了这张照片:

图 9. p = 7 时的 6 量子位模型性能
对于这个分布,我们只有6%的合适结果。
结论
这篇文章的主要目的是展示如何使用Qiskit构建一个DSP模型,以及人们可能期望得到的结果。从最终分布来看,很明显,与 MCP 相比,即使在小维度上,QAOA 的性能也很差。然而,由于电路深度 p 足够大,我们可以期待一个可行的解决方案。
最后,如果您想为 DSP、MCP 等优化问题找到 QAOA 应用程序的准确分析,我强烈建议您使用量子近似优化算法解决组合优化问题。
---煤油灯科技victorlamp.com翻译整理---









