旅行推销员的问题是数学中的经典之作。旅行者要以最短的路线访问N个城市，然后返回起点。随着 N 数量的增加，可能的路线数量呈爆炸式增长。然后可以使用近似方法解决此问题。量子计算机可以更快地提供更好的解决方案。来源：HZB
旅行推销员问题被认为是组合优化问题的一个典型例子。现在，由柏林自由大学和HZB的理论物理学家Jens Eisert教授领导的柏林团队已经证明，与传统方法相比，量子计算机实际上可以更好，更快地解决某些此类问题。
该团队的研究成果发表在《科学进展》杂志上。
量子计算机使用所谓的量子比特，它不像传统逻辑电路那样是零或一，但可以取介于两者之间的任何值。这些量子比特是通过高度冷却的原子、离子或超导电路实现的，构建具有许多量子比特的量子计算机在物理上仍然非常复杂。然而，数学方法已经可以用来探索容错量子计算机在未来可以实现的目标。
“关于它有很多神话，有时还有一定程度的热空气和炒作。但是，我们严格地处理了这个问题，使用数学方法，并在这个问题上取得了扎实的结果。最重要的是，我们已经阐明了在什么意义上可以有任何优势，“柏林自由大学和柏林亥姆霍兹中心联合研究小组负责人艾塞特教授说。
众所周知的旅行推销员问题就是一个典型的例子：一个旅行者必须访问多个城市，然后返回他的家乡。哪条路线最短？虽然这个问题很容易理解，但随着城市数量的增加和计算时间的爆炸式增长，它变得越来越复杂。旅行推销员问题代表了一组具有巨大经济重要性的优化问题，无论它们涉及铁路网络、物流还是资源优化。使用近似方法可以找到足够好的解。
由Eisert和他的同事Jean-Pierre Seifert领导的团队现在使用纯粹的分析方法来评估具有量子比特的量子计算机如何解决这类问题，这是一个用笔和纸进行的经典思想实验，并拥有大量的专业知识。
“我们只是假设，无论物理实现如何，都有足够的量子比特，并研究用它们执行计算操作的可能性，”柏林工业大学的博士生Vincent Ulitzsch解释道。
在这样做的过程中，该团队揭示了与密码学中一个众所周知的问题的相似之处，即数据加密。
“我们意识到，我们可以使用Shor算法来解决这些优化问题的子类，”Ulitzsch说。这意味着计算时间不再随着城市数量（指数，2N）而“爆炸”，而只是多项式增加，即 Nx 时，其中 x 是一个常数。以这种方式得到的解在质量上也比使用传统算法的近似解要好得多。
“我们已经证明，对于一类特定但非常重要且实际相关的组合优化问题，量子计算机在某些问题实例中比经典计算机具有根本优势，”Eisert说。
更多信息： Niklas Pirnay 等人，通过计算学习理论近似组合优化问题的原则性超多项式量子优势，Science Advances （2024）。DOI： 10.1126/sciadv.adj5170
