利用多用途量子比特的量子计算机，在解决复杂的优化问题(如旅行推销员困境)方面处于领先地位，这些问题传统上受到计算效率低下的困扰。通过严格的数学分析，研究人员已经证明，量子计算可以从根本上改变问题的解决方式，与经典方法相比，量子计算在计算时间上提供了更有效的多项式增长，并产生了更好的解决方案。

　　旅行推销员的问题是考虑了组合优化问题的一个基本例子。现在，由Freie Universit?t柏林和HZB的理论物理学家延斯·艾瑟特(Jens Eisert)教授领导的柏林团队已经证明，使用量子计算机实际上可以比使用co更好、更快地解决某些类型的此类问题nventional方法。

　　量子计算机使用所谓的量子位，它不是传统逻辑电路中的零或一，而是可以取两者之间的任何值。这些量子比特是通过高度冷却的原子、离子或超导电路来实现的，而且从物理上讲，构建具有许多量子比特的量子计算机仍然非常复杂。然而，数学方法已经可以用来探索未来容错量子计算机可以实现的目标。

　　“关于它有很多神话，有时还会有一些热空气和炒作。但我们已经用数学方法严格地处理了这个问题，并在这个问题上取得了可靠的结果。最重要的是，我们已经明确了在什么意义上可以有任何优势，”Jens Eisert教授博士说，他是柏林自由Universit?t和柏林亥姆霍兹中心的联合研究小组的负责人。

　　旅行推销员的问题是一个经典的数学问题。旅行者按最短路线游览N个城市，然后返回起点。随着N的增加，可能的路由数量会激增。这个问题可以用近似方法来解决。量子计算机可以更快地提供更好的解决方案。信贷:HZB

　　解决复杂问题

　　著名的旅行推销员问题就是一个典型的例子:一个旅行者必须访问许多城市，然后回到他的家乡。哪条路线最短?虽然这个问题很容易理解，但随着城市数量的增加和计算时间的激增，它变得越来越复杂。

　　旅行推销员问题代表了一组具有巨大经济重要性的优化问题，无论是涉及铁路网络、物流还是资源优化。用近似方法可以找到足够好的解。

　　目前的工作(箭头)表明，组合问题的某些部分可以用量子计算机更好地解决，甚至可能完全解决。信贷:HZB / Eisert

　　量子解决方案和进展

　　由Jens Eisert和他的同事Jean-Pierre Seifert领导的团队现在已经使用纯分析方法来评估具有量子位的量子计算机如何解决这类问题。一个经典的思想实验，用笔、纸和很多专业知识。

　　柏林工业大学的博士生Vincent Ulitzsch解释说:“我们只是假设，不管物理实现如何，有足够的量子位，并研究用它们执行计算操作的可能性。”在此过程中，他们揭示了密码学中一个众所周知的问题的相似之处，即数据加密。“我们意识到我们可以使用肖尔算法来解决这些优化问题的一个子类，”乌利奇说。

　　这意味着计算时间不再随着城市数量(指数，2N)而“爆炸”，而只是多项式地增加，即与Nx一起增加，其中x是常数。用这种方法得到的解在质量上也比用常规算法得到的近似解好得多。

　　“我们已经证明，对于一类特定但非常重要且与实际相关的组合优化问题，量子计算机在某些情况下比经典计算机具有根本优势，”Eisert说。

　　参考文献:Niklas Pirnay, Vincent Ulitzsch, Frederik Wilde, Jens Eisert和Jean-Pierre Seifert, 2024年3月15日，Science Advances，“通过计算学习理论近似组合优化问题的原则上的超多项式量子优势”。DOI: 10.1126 / sciadv.adj5170