从旅行商问题谈量子计算机在日常生活中的应用

现在，是时候用量子计算机解决您的生活需求了。

假设你从家里出发，然后需要去超市、加油站和五金店，最后回到家，总共有4个目的地，那么你可以有6种可能的路线选择：

但这些路线中哪条路线最有效（最短）？ 在数学中，这被称为旅行商问题 (TSP) [1]。 为了更好地解决多个“暂停”问题量子计算机比特币破解，可以肯定地说，我们需要一台量子计算机，下面我们就一一说说。

“旅行商问题”有大量可能的解决方案。 点代表目的地，将一定数量的点连接在一起代表所有可能的路线组合。 对于多个目的地，要考虑的解决方案数量增加得太快，以至于蛮力方法无法发挥作用。 SAURABH.HARSH/维基

如果你有大量的目的地要访问，那么一定有一条旅行路线比其他所有路线都更有效率：它会花费你最少的时间和距离。

就像文章开头所举的例子（关于你的家、超市、加油站、五金店），总共有四个目的地，但只有六个可能的路径。 原来这些路径中只有3条是唯一的，因为对于，Home⇨Supermarket⇨Gas Station⇨Hardware Store⇨Home，这条路径恰好在Home⇨Hardware Store⇨Gas Station⇨Supermarket⇨Home的反方向，而时间和距离是一样的。

我们将每个位置视为一个站点。 当只经过几个站点时，这个路径选择会变得相对简单。 然而，当经过更多站点时，可能路径的数量将快速增长：就像数学阶乘增长变化 [2]。 对于 5 个目的地，有 12 条可能的唯一路径。 在 10 个目的地中，有 181,440 条独特的路径； 在 15 个目的地中，有超过 870 亿条独特的路径（如下图所示）。

如果在旅行商问题中每条路径的计算都需要一微秒，大约在 12 到 15 个目的地之间，则几乎不可能尝试使用蛮力计算来解决该问题。 马克杰克逊/剑桥量子计算

解决此类问题的最简单方法是使用所谓的“蛮力计算”。 蛮力法会简单地提取您旅行的多个目的地之间的可能方式，并计算该路径的距离以确定哪条路径最短。 但关键问题是，随着点数的增加，可能的结果或旅行者的路径数量呈指数增长。

这里假设要到达的目的地数为N，可能的行进路径数为(N -1)！ / 2. 当N=5时，所有12条可能的行进路线的距离计算起来都不会太长。 对于传统计算机来说，计算一条旅游路线大约需要一微秒。 当N=10时，将近一整秒； 但是，当N=20时，大约需要2000年； 当N=25时，计算机要运行大约100亿年才能完成优化路径，这个时间与宇宙寿命几乎一样长。

IBM 新生的 4 量子位方形电路是计算领域的先驱，有朝一日可能会导致量子计算机强大到足以模拟整个宇宙（量子位的数量目前正在快速增长）。 但量子计算领域仍处于起步阶段，对于实际问题尚未实现量子优势/来源：IBM

与许多可以表述的问题一样，这个问题是一类计算量大的问题。 这类问题，要在无穷多的可能组合中找到最优解，需要考察每一条可以想到的合理路径，量化这条路径所需的距离（或时间），然后选择最短（或最快）的路径作为最终的结果结果。

实际上，暴力法并不是唯一的方法[3]，还有更好的方法来找到精确解（主要是通过排除“明显非最优”的路径），类似于计算机象棋的进步。 最大的精确解出现在 2006 年，找到了通过 85,900 个城市的最短路径 [4]。 花了一个多世纪的 CPU 计算时间才找到解决方案。

旅行商问题适用于蚁群中的蚂蚁。 蚂蚁最初铺设了一条路径 (1)，但随着时间的推移，蚂蚁探索了无限多可能相互关联的路径 (2)，最终，大多数蚂蚁遵​​循了最有效的解决方案 (3)，留下了一条信息素路径, 所有蚂蚁最终都遵循 (4)。 NOJHAN/维基共享资源

这类问题虽然简单，但其实有着大量的应用。 例如，如果您有一系列包裹要发送到一系列地址，那么您需要选择最佳路线。 如果您正在计划您的旅行行程，从商务旅行到公路旅行，您不想浪费时间或里程。 或者，如果您在航空、制造或运输行业工作，您希望您的乘客和货物尽可能快速高效地到达目的地。

但是，如果你的问题太复杂，比如要到达的目的地点太多，你就只能想出近似解； 一。 您获得的解决方案将受到计算能力和算法质量的限制。 这些问题很简单，但用经典计算机很难解决。

显微照片中显示和标记的 9 量子位量子电路。 灰色区域是铝，黑色区域是铝被蚀刻掉并添加颜色以区分各种电路组件的地方。 对于这样一台使用超导量子比特的计算机，该设备必须在超低温下保持过冷才能发挥真正的量子计算机的作用，并且只能在远低于约 50 微秒的时间尺度上正常运行。 C. 尼尔等人。 (2017)，ARXIV：1709.06678V1/QUANT-PH

幸运的是，许多计算困难的问题，包括旅行商问题，使用量子计算机都没有那么困难（而且计算成本也低得多）。 就在几年前，量子计算机被证明在特殊问题上比任何经典计算机都具有计算优势。

当量子计算机在 2019 年首次利用谷歌时（尽管只是针对一个特定问题），它说了很多。 这是一个惊人的例子，说明量子计算机实际上可以比传统的经典计算机更快、更有效地解决问题。 虽然新算法或方法总是有可能在经典计算机上更快地解决任何给定问题，但量子计算机仍然具有一些基本优势。

当您对从 |10100> 开始的量子位状态执行实验并传递 10 个耦合器脉冲（即量子操作）时，您不会得到 10 种可能结果中每一种的概率均等的平坦分布。 相反，有些结果的概率异常高，而有些结果的概率极低。 测量量子计算机的结果可以确定您是保持预期的量子行为还是在实验中失去它。 C. 尼尔等人。 (2017)，ARXIV：1709.06678V1/QUANT-PH

与必须为 0 或 1 的经典计算机位不同，它们处理同时存在于 0 和 1 中的不确定量子位状态（叠加状态）。另外，您可以直接在这些量子位上执行量子运算（而不仅仅是经典运算），保持所有的量子怪异直到计算结束。

这就是量子计算的真正威力所在：利用量子计算机可以有效解决的一些问题，以及使用量子计算机可以用经典计算机有效解决的一些问题，但是这只能用经典计算机低效地解决。 计算机科学家 Ran Raz 和 Avishay Tal [5] 在 2018 年证明了这一点，他们证明量子计算机可以有效解决以下问题：

这是 2016 年洁净室中的量子计算机（稀释冰箱）的组成部分。如果量子计算机可以比经典计算机更快、更高效地进行任何计算，它将实现量子优势。 /盖蒂图片社

回到旅行商问题。 即使使用有史以来最好的算法，经典计算机也无法很快解决这个问题。 如果给你一定的距离，你可以很容易地检查你找到的任何路径是否比这个距离短，但不能保证这是所有路径中最短的距离。

但实际上，这就是您想知道的：最短路径是否等于您找到的最短路径所覆盖的特定距离？

也许有一天，即使在我们研究这个问题的所有时间里都没有发生过这种情况，我们仍然能够找到一种经典的计算机算法来有效地找到这个解决方案。 虽然不能保证存在这样的算法，但发现一个算法仍然是许多人的希望。

蛮力方法不足以解决节点过多的旅行商问题，如此处的 35 节点路径所示。 然而，存在其他算法可以找到候选解决方案，然后可以检查这些解决方案是否低于某个阈值量子计算机比特币破解，然后可以使用该阈值。 XYPRON/公共领域

然而，无论那个特定问题最终是否会回到经典计算机，仍然存在经典计算机无法有效解决的问题。 我们可以问的问题有“是”或“否”的答案，但在多项式时间内，经典计算机甚至无法在理论上解决这些问题。

然而，在这些复杂的问题中，一些经典计算机无法有效解决的问题，量子计算机却可以有效解决。 虽然我们不知道经典计算机能否有效解决旅行商问题，但我们知道量子计算机可以有效解决经典计算机无法解决的问题 [6]。 如果存在经典解，那么量子解也是可能的。 但即使不存在经典解决方案，也可能存在量子解决方案。

在所有量子计算方法中，即使是控制单个量子比特并长时间保持其量子状态也是一个挑战。 此处显示单个量子位由电等离子体控制。 大多数量子位通常由磁场控制，但这个由选择性电脉冲控制。 /盖蒂图片社

旅行商问题的本质是在大量节点之间寻找最有效的路径，有很多实际应用。 例如，体现在 DNA 测序、微芯片的规划和制造、天文学中许多物体的观测规划中。 这对于优化送货路线和供应链物流至关重要。 但是，尽管它在人类社会中具有重要性和相关性，但我们仍然不知道如何有效地解决这个问题：计算机科学家称之为多项式时间 [7]。

即使不存在这样的解决方案，而且对于经典计算机来说可能也不存在，量子计算机的世界提供了无与伦比的希望。 量子计算机可以解决多种经典计算机无法有效解决的问题，也许有一天会包括解决旅行商问题。 当您的蛮力选择过于昂贵且高效算法不可用时，请不要完全放弃解决问题，量子计算革命可能使之成为可能。

参考链接：

[1]

[2]

[3]

[4]

[5]

[6]

[7]