从旅行商问题讨论量子计算机在生活中的应用

查看原文

其他

从旅行商问题讨论量子计算机在生活中的应用

Original Ethan Siegel 量子客 2021-06-23

编辑:丁艳, 校对:黄辉晓

现在，要通过量子计算机来解决您生活中的需求了。

假设您将会从家出发，然后需要去超市、加油站和五金店，最后回到家里，共有4个目的地点，那么您可以采取六种可行路线方案：

家——超市——加油站——五金店——家
家——超市——五金店——加油站——家
家——加油站——超市——五金店——家
家——加油站——五金店——超市——家
家——五金店——超市——加油站——家
家——五金店——加油站——超市——家

但是，这些路线中哪一条是最高效（最短）的路线呢？在数学领域，这被称为旅行商问题（TSP）[1]。为了更好的解决多个“停顿”问题，可以肯定的说，我们这需要一台量子计算机，下面让我们一一道来。

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

如果您要游览的目的地数量众多，那么一定存在一条旅行路线，会比其他所有路线都更加高效：这将使您花费的时间最少和距离最短。

如同文章开篇列出的示例（关于您的家，超市，加油站和五金店），总共有四个目的地，但只有六个可能的路径。事实证明，这些路径中只有3条路径是唯一的，因为对于，家庭⇨超市⇨加油站⇨五金店⇨家庭，这一路径与家庭⇨五金店⇨加油站⇨超市⇨家这一路径只是方向相反，而所花费的时间和距离是一样的。

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

如果在旅行商问题中每条路径的计算要花费一微秒，那么在大约12到15个目的地之间，几乎不可能尝试使用暴力计算解决该问题。MARK JACKSON/剑桥量子计算

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

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

IBM的初期4-Qubit方电路是计算领域的先驱，有朝一日可能会发展出强大到足以模拟整个宇宙的量子计算机（目前量子比特数在快速增长中）。但是量子计算领域仍处于起步阶段，对于实际应用中的问题尚未实现量子优势 /来源：IBM

这个问题和人们可以用公式表示的许多问题一样，属于计算代价高昂的一类问题。这种问题，要在无数种可能的组合中找到最佳解决方案，需要检查每一条可以想象的合理路径，量化该路径所需的距离(或时间) ，然后选择最短(或最快)的路径为最终的结果。

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

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

这种类型的问题虽然简单，但实际上存在大量的应用。比如，如果您有一系列的包裹要送往一系列的地址，那么你就需要选择最佳的路线。如果您正在计划您的旅行路线，从出差到公路旅行，您不想浪费时间或里程。或如果您从事航空业、制造业或者运输业，您会希望您的乘客和货物尽可能快速有效地到达他们的目的地。

但是，如果您的问题过于复杂，例如，您有太多需要到达的目的地点，您将只能提出近似的解决方案；而且，您无法确定自己是否找到了最佳路线，或者是最佳路线之一。您得到的解决方案将受到计算能力和算法质量的限制。这样的问题很简单，但是您却用经典计算机难以得到解决。

一个9-Qubit的量子电路，如显微照片所示和标记的。灰色区域是铝，黑暗区域是铝被蚀刻掉的地方，并添加了颜色以区分各种电路元件。对于使用超导量子比特的此类计算机，该设备必须在超低温度下保持过冷状态，才能用作真正的量子计算机，并且只能在远低于约50微秒的时标上正常运行。C.NEILL等人。（2017），ARXIV：1709.06678V1/QUANT-PH

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

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

当您对以| 10100>开始的量子比特状态执行实验并通过10个耦合器脉冲（即量子运算），对于10种可能的结果中的每一种，您都不会得到具有相等概率的平坦分布。相反，某些结果将具有异常高的概率，而某些结果将具有极低的概率。测量量子计算机的结果可以确定您是维持预期的量子行为还是在实验中失去它。C.NEILL等人。（2017），ARXIV：1709.06678V1/QUANT-PH

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

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

一些不能通过经典计算机快速解决的问题；
无法通过经典计算机快速检查其解决方案；
广义范畴不属于经典计算机理论上可以在多项式时间内解决的所有问题。

此处是2016年洁净室里的量子计算机（稀释制冷机）一个组件部分，如果量子计算机能够比传统计算机更快，更有效地完成任何计算，那么它将实现量子优势。 /盖蒂图片社

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

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

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

暴力破解方法不足以解决节点过多的旅行商问题，如此处的35节点路径所示。但是，存在其他允许找到候选解的算法，然后可以检查这些解是否低于某个阈值，满足阈值就可以用。XYPRON /公共领域

然而，无论该特定问题最终是否会回归让经典计算机解决，仍然存在一些超出了经典计算机可以有效完成的问题。我们可以提出的问题具有“是”或“否”的答案，但是在多项式时间内，经典计算机甚至在理论上都无法解决。

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

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

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

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