如何用量子计算解决TSP问题？

Ilingis · 发表于 2022-10-4 21:20

带有量子优化的旅行商问题。解决方案和观点。

摘要
具有大搜索空间的高维优化问题是当今世界社会和行业面临的许多具有挑战性的科学问题或紧迫问题的基础。量子计算的应用有望彻底改变我们看待优化的方式。商业中的优化任务范围很广，而物流是最直接的任务之一。约束优化通过识别最佳前进路径来帮助制造供应链，因为动态条件会影响采购和物流选项。物流中最著名的问题之一是所谓的旅行商问题。这项简短工作的目标是使用两种量子计算范式——基于门的模型和绝热量子计算，为旅行商问题提供不同的解决方案。简要讨论了这些方法的特性，并提供了对它们未来前景的展望。

问题介绍
旅行商问题 (TSP) 是经典的 NP-hard [1] 问题之一，它提出以下问题：“给定一个城市列表和每对城市之间的距离，访问每个城市的最短路径是什么？城市正好一次，然后返回原城？”。在供应链方面可以提出类似的问题：“给定客户列表和每对客户之间的距离，访问客户一次并返回仓库的最短路径是什么？”。因此，它可以与卡车路线以及如何优化路线以及卡车进行比较 [2]。

最短路径问题的一个例子

TSP 可以如下公式化（Dantzig-Fulkerson-Johnson 公式）。用数字 1、2、…、n 标记城市并定义

以 Cij > 0 为从城市i到城市j的距离。

受制于

因此，我们有一个由n 个节点和n x n邻接矩阵M组成的全连接无向图，它给出了从节点i到节点j的旅行成本。
允许我们更通用地编写类似 TSP 的问题的模型之一是二次无约束二进制优化 (QUBO)。QUBO 是一个框架，它使我们能够以二次形式对问题进行建模，并在本地受到线性限制。然而，在目标函数的帮助下，可以将大于 2 的任务和不等式约束重新表述为 QUBO 模型 [3]。考虑以下目标函数

二次无约束二元优化 (QUBO) 问题包括找到最小化泛函的二元向量 x*。量子退火问题可以简化为 QUBO 问题，反之亦然。

经典解决方案
已经发明了许多算法来解决这个问题。例如，一些蛮力算法（例如分支边界算法）允许我们找到精确的解决方案，但不适用于大问题。这种方法的运行时间估计为O(n!)，尽管B&B算法显着减少了搜索，但在最坏的情况下，它仍然是一个阶乘。例如，有 10 个停靠点的旅行商问题产生 3,628,800 个路线选项，40 个停靠点将产生大约 1,000,000,000,000,000,000 个路径选项。
在实践中，近似或启发式算法适用于这个问题。例如，考虑一个遗传算法。为未来的杂交和突变创建了一个初始种群。在迭代结束时，保留最佳解决方案并重复该过程。对于这个算法，我们可以手动设置参数来尝试改进解决方案。
经典计算算法无法在短时间内实现旨在解决多个变量的复杂场景。然而，今天使用量子计算技术的算法可以使用应用量子技术的经典系统或同时采用量子和经典的混合解决方案快速实现这种模拟。

量子方法
量子计算在物流中最有前途的应用之一是最优路径调度。这样的任务通常被称为“旅行推销员问题”。它已经研究了很长时间，无法在经典计算机上有效地解决。然而，在量子算法的帮助下，有多种技术可以应对这一挑战。
下面讨论两种显着的方法，即量子退火和相位估计。

相位估计

在参考部分，可以找到 IBM 相位估计的完整描述的链接。

对于这种方法，我们应该将包含 n 个城市之间距离的矩阵C表示为矩阵 B，其元素写为

, 所以 B 可以被认为是一个酉算子。此外，对于每个城市对角酉矩阵，构造U使得

下一步是将最终的酉算子与整个地图相关联

该算子的特征向量可以写成

其中i(j)函数返回我们前往j的城市i。由于构造，我们将有（n-1）！特征向量和乘法

返回哈密顿循环 [4] 的长度。

此设置允许我们使用相位估计算法来获得任何哈密顿量 [5] 循环的长度。我们从相位估计算法中得到二进制输出形式的相位，然后我们可以很容易地执行量子算法来找到最小值[6]。然而，所提出的方法实际上只是解决 TSP 的完整方法的一部分。它只有在准备好所有哈密顿循环的列表时才有效。总的来说，这种方法的复杂性是

这不是多项式复杂度。

量子退火
解决 TSP 的另一种方法是使用绝热量子计算，其中在与哈密顿量 H(0) 相关的初始基态中准备一个量子位系统，并且系统逐渐演化到其哈密顿量由 H(1) 给出的目标状态.

如果我们足够缓慢地改变参数，量子比特将最终处于演化哈密顿量的基态。在实践中，由于技术上的不完善，我们需要多次重复这个过程才能获得合适的结果。绝热量子计算机能够解决哈密顿量被限制为伊辛量的问题。与 Ising 模型的目标状态相关的能量（特征值）由下式给出：

在当今最先进的 D-Waves 的 5436 qubit Advantage 中，最多可以解决 8 个节点的 TS 问题 [7]。事实上，在这种情况下可以使用的逻辑量子比特数是 73，这就是为什么只有这么小的规模可用。该模型的求解过程大约需要 2 毫秒。相比之下，用 Python 实现的经典求解器耗时不到一毫秒。

总结
旅行商问题的解决方案也因为它的概括性打开了物流领域的广泛视角。例如，旅行购买者问题和车辆路径问题都是 TSP 的推广。作为 QUBO 任务，该行业特定部分的进展在很大程度上取决于一般量子计算的成就。
由于量子随机存取存储器概念的发展及其实际实现，相位估计方法在未来可以得到推动。但在当今最先进的情况下，更现实的似乎是量子退火方式。根据 D-Wave 路线图 [8]，到 2024 年，预计将拥有 7000 多个物理量子比特。之后，随着新的量子比特的增加和技术质量的提高，早期的量子优势可以在不久的将来实现。

参考
[1] 旅行商问题：计算研究。普林斯顿大学出版社链接
[2] 量子计算将如何推动物流的未来链接
[3] GPS: A new TSP Formula for its generalisations type QUBO link
[4] 使用相位估计链接解决旅行商问题
[5] 解决旅行商问题的高效量子算法：IBM 量子体验链接
[6] 一种寻找最小链接的量子算法
[7] 在 D-Wave 量子计算机上解决旅行商问题链接
[8] 退火量子计算机：迅速为当今企业的优化问题带来更好的解决方案链接

		自动登录	找回密码
密码			立即注册

如何用量子计算解决TSP问题？

本帖子中包含更多资源