搜索空间大的高维优化问题是当今世界社会和行业面临的许多具有挑战性的科学问题或紧迫问题的基础。量子计算的应用有望为我们看待优化的方式带来重大转变。商业中有各种各样的优化任务,物流是最直接的任务之一。约束优化通过识别最佳前进路径来帮助制造供应链,因为动态条件会影响采购和物流选项。物流中最著名的问题之一是旅行商问题。本文介绍了使用两种量子计算范式——基于门的模型和绝热量子计算,为旅行商问题提供不同的解决方案。简要讨论了这些方法的特性,并提供了对它们未来前景的展望。
旅行商问题(TSP) 是经典的 NP-hard问题之一,它提出了以下问题:“给定城市列表和每对城市之间的距离,访问每个城市一次并返回原点城市的最短路线是什么?在供应链方面也可以提出类似的问题:“给定客户名单和每对客户之间的距离,访问客户一次并返回仓库的最短路线是什么?因此,它可以与卡车路线以及如何优化路线以及卡车进行比较

图:最短路径问题的示例。
TSP 可以用Dantzig-Fulkerson-Johnson 公式表示。用数字 1、2、…、n 标记城市并定义

取 为 市到 市的距离。

受制于

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

二次无约束二元优化 (QUBO) 问题包括寻找一个使函数最小化的二元向量 。量子退火问题可以简化为 QUBO 问题,反之亦然。
经典解决方案
人们已经发明了许多算法来解决这个问题。例如,一些蛮力算法(例如分支和边界算法)允许我们找到精确的解决方案,但不适用于大问题。这种方法的运行时间估计为 ,尽管算法显著减少了搜索,但在最坏的情况下,它仍然是一个阶乘。例如,有 10 个停靠点的旅行商问题会产生 3,628,800 个路线选项,40 个停靠点将产生大约 1,000,000,000,000,000,000 个路径选项。
在实际应用中,可采用近似算法或启发式算法求解该问题。例如,考虑一个遗传算法。为将来的杂交和突变创建初始种群。在迭代结束时,最佳解决方案仍然存在,并且该过程将重复。对于此算法,我们可以手动设置参数以尝试改进解决方案。
传统的计算算法无法在短时间内解决多个变量的复杂场景。然而,使用量子计算技术的算法可以使用应用量子技术的经典系统或同时使用量子和经典的混合解决方案快速实现这种模拟。
量子方法
量子计算在物流中最有前途的应用之一是优化路径调度。这样的任务通常被称为“旅行推销员问题”。它已经被研究了很长时间,但仍然无法在传统计算机上得到有效的解决。然而,在量子算法的帮助下,有多种技术可以应对这一挑战。
下面讨论两种显著的方法,即量子退火和相位估计。
相位估计
使用相位估计方法,我们应该将包含 个城市之间距离的矩阵 表示为矩阵 ,其元素写为

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

下一步是将最终的酉算子与整个映射关联起来

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

其中 函数返回我们前往 的城市 。因为这个构造,我们将有 特征向量和乘法

返回哈密顿循环的长度。

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

这不是多项式的。
量子退火
另一种处理TSP的方法使用绝热量子计算,其中一个量子比特系统在与哈密顿量 相关的初始基态中制备,系统逐渐演化到目标态,其哈密顿量由 给出。

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

在目前 D-Waves 的包含 5436量子位的量子计算机中,最多可以解决 8 个节点的 TS 问题。事实上,在这种情况下可以使用的逻辑量子比特数是 73,这就是为什么只有这么小的规模可用。该模型的求解过程大约需要 2 毫秒。相比之下,用 Python 实现的经典求解器耗时不到一毫秒。
结论
旅行推销员问题的解决方案也因其概括性而在物流中开辟了广泛的视角。例如,旅行购买者问题和车辆路径问题都是 TSP 的推广。作为 QUBO 任务,该行业特定部分的进展在很大程度上取决于量子计算的成就。
随着量子随机存取存储器概念的发展及其实际应用,相位估计方法将得到进一步的发展。但在目前的技术水平上,更现实的是量子退火方法。根据D-Wave的路线图,到2024年,它有望拥有7000多个物理量子比特。之后,随着新的量子比特的增加和技术质量的提高,可以在不久的将来实现早期的量子优势。
---煤油灯科技victorlamp.com翻译整理---









