从旅行商问题讨论量子计算机在生活中的应用
现在，要通过量子计算机来解决您生活中的需求了。
假设您将会从家出发，然后需要去超市、加油站和五金店，最后回到家里，共有4个目的地点，那么您可以采取六种可行路线方案：
家——超市——加油站——五金店——家
家——超市——五金店——加油站——家
家——加油站——超市——五金店——家
家——加油站——五金店——超市——家
家——五金店——超市——加油站——家
家——五金店——加油站——超市——家
但是，这些路线中哪一条是最高效（最短）的路线呢？在数学领域，这被称为旅行商问题（TSP）[1]。 为了更好的解决多个“停顿”问题，可以肯定的说，我们这需要一台量子计算机，下面让我们一一道来。
如果您要游览的目的地数量众多，那么一定存在一条旅行路线，会比其他所有路线都更加高效：这将使您花费的时间最少和距离最短。
如同文章开篇列出的示例（关于您的家，超市，加油站和五金店），总共有四个目的地，但只有六个可能的路径。事实证明，这些路径中只有3条路径是唯一的，因为对于，家庭⇨超市⇨加油站⇨五金店⇨家庭，这一路径与家庭⇨五金店⇨加油站⇨超市⇨家这一路径只是方向相反，而所花费的时间和距离是一样的。
我们把每个地点视为一个站点，当仅经过几个站点时，这一路径选择会变得相对简单，但是，当所经站点增多，可能路径的数量便会迅速增长：就像数学阶乘一样增长变化[2]。对于5个目的地，有12条可能的唯一路径。在10个目的地中，有181,440条唯一路径；而在15个目的地中，就有超过870亿条唯一的路径（如下图）。
解决此类问题的最简单方法是使用所谓的“暴力计算”。暴力方法将在您旅行的多个目的地之间简单地提取可能的方式，并计算该路径的距离以确定哪个路径最短。但关键问题在于，随着点数增加，可能的结果数量或旅行者的路径数量也指数增长。
这里设需达到的目的地的数量为N，可能的旅行路径数为（N -1）！/ 2。当N=5时，所有12种可能的旅行路线的距离在计算的时候不会花费太长的时间。对于一台经典计算机来说，计算一条旅游路线的时间需要大约一微秒。当N=10时，将花费近一整秒的时间；但是，当N=20时，大约需要2000年；当N=25时，计算机将运行约100亿年才能完成优化路径，这个时间与宇宙的寿命几乎一样长。
这个问题和人们可以用公式表示的许多问题一样，属于计算代价高昂的一类问题。这种问题，要在无数种可能的组合中找到最佳解决方案，需要检查每一条可以想象的合理路径，量化该路径所需的距离(或时间) ，然后选择最短(或最快)的路径为最终的结果。
实际上，暴力**方法并不是唯一的方法[3]，还有更好的方法来找到精确的解决方案(主要是通过排除“明显非最优”的路径) ，类似于计算机国际象棋的进步。最大的精确解出现在2006年，找到了穿过85900个城市的最短路径[4]。花了一个多世纪的CPU计算时间才找到该解决方案。
这种类型的问题虽然简单，但实际上存在大量的应用。比如，如果您有一系列的包裹要送往一系列的地址，那么你就需要选择最佳的路线。如果您正在计划您的旅行路线，从出差到公路旅行，您不想浪费时间或里程。或如果您从事航空业、制造业或者运输业，您会希望您的乘客和货物尽可能快速有效地到达他们的目的地。
但是，如果您的问题过于复杂，例如，您有太多需要到达的目的地点，您将只能提出近似的解决方案；而且，您无法确定自己是否找到了最佳路线，或者是最佳路线之一。您得到的解决方案将受到计算能力和算法质量的限制。这样的问题很简单，但是您却用经典计算机难以得到解决。
幸运的是，许多计算困难的问题， 包括旅行商问题， 使用量子计算机就不那么困难了(而且计算成本也低得多)。就在几年前，量子计算机已经被证明，它在特殊问题上比任何传统计算机都具有计算优势。
当量子计算机在2019年谷歌首次取得优势时(尽管只是针对一个特定的问题) 就说明了很多问题。这是一个惊人的例子，说明量子计算机实际上可以比传统的经典计算机更快、更有效地解决问题。虽然新的算法或方法总是有可能在经典计算机上为任何特定问题带来更快的解决方案，但量子计算机仍具有一些基本优势。
与必须为0或1的经典计算机比特不同，它们处理的是同时存在于0和1的不确定量子比特状态（叠加态）。此外，您还可以直接在这些量子比特上执行量子运算（而不仅仅是经典运算），直到计算结束一直保持所有量子怪异性。
这就是量子计算真正力量的所在：利用这样的事实，使用量子计算机可以有效地解决一些问题，而传统计算机利用量子计算机可以有效地解决一些问题，但是经典计算机只能低效地解决它们。 计算机科学家Ran Raz和Avishay Tal在2018年证明了这一点[5]，他们证明了量子计算机可以有效解决以下问题：
- 一些不能通过经典计算机快速解决的问题；
- 无法通过经典计算机快速检查其解决方案；
- 广义范畴不属于经典计算机理论上可以在多项式时间内解决的所有问题。
回到旅行商的问题。即使使用有史以来最好的算法，经典计算机也不能很快解决这个问题。如果给你一个特定的距离，你可以很容易地检查你找到的任何路径是否比这个距离短，但是不能保证这是所有路径中最短的距离。
但实际上，这就是您想知道的：最短的路径是否等于您找到的最短路径所覆盖的特定距离？
也许有一天，即使在研究此问题的所有时间中都没有发生过，我们仍将能够找到一种可以有效找到该解决方案的经典计算机算法。虽然不能保证存在这样的算法，但是发现一个算法仍然是许多人的希望。
然而，无论该特定问题最终是否会回归让经典计算机解决，仍然存在一些超出了经典计算机可以有效完成的问题。我们可以提出的问题具有“是”或“否”的答案，但是在多项式时间内，经典计算机甚至在理论上都无法解决。
但是，这些复杂的问题中，某些经典计算机无法有效解决的问题，可以由量子计算机有效解决。尽管我们不知道经典计算机是否可以有效解决旅行商问题，但我们确实知道量子计算机可以有效地解决经典计算机不能解决[6]的问题。如果存在经典解，那么量子解也可以。但是，即使不存在经典的解决方案，也可能有一个量子解决方案。
旅行商问题的本质是寻找大量节点之间最有效的路线，它有许多实际应用。体现在比如：DNA测序中，微芯片的计划和制造中，计划观测天文学中许多物体的过程中。并且这对于优化配送路线和供应链物流至关重要。但是，尽管它在人类社会中具有重要性和相关性，我们仍不知道如何有效地解决这个问题：计算机科学家称之为多项式时间[7]。
即使不存在这样的解决方案，并且对于经典计算机也可能不存在，量子计算机的世界也提供了无与伦比的希望。量子计算机可以解决传统计算机无法有效解决的各种问题，也许有朝一日将包括解决旅行商的问题。当您的暴力**选项太过昂贵且无法使用高效的算法时，请不要完全放弃解决问题的方法，量子计算革命可能会使之成为可能。
参考链接：
[1] http://dwz.date/aQ8V
[2] http://dwz.date/aQ8W
[3] http://dwz.date/aQ8D
[4] http://dwz.date/aQ8F
[5] http://dwz.date/aQ8G
[6] http://dwz.date/aQ8H
[7] http://dwz.date/aQ8J
关于量子客
量子客是一家关注量子科技产业化的全链条内容、服务、数据平台，提供一手信息，致力于构建一个全球量子科技创新合作网。
声明：此文出于传递高质量信息之目的，若来源标注错误或侵权，请与我们联系，我们将及时更正、删除，所有图片的版权归属所引用组织机构，此处仅引用，原创文章转载需授权。