旅行商问题被认为是组合优化问题的一个典型例子。现在，由柏林自由大学和HZB的理论物理学家JensEisert教授教授领导的柏林团队已经证明，与传统方法相比，使用量子计算机实际上可以更好、更快地解决某一类此类问题。

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

“关于它有很多神话，有时还有一定程度的夸夸其谈和炒作。但我们使用数学方法严谨地处理了这个问题，并就这个问题得出了可靠的结果。最重要的是，我们已经澄清了在什么意义上柏林自由大学和柏林亥姆霍兹中心联合研究小组的负责人艾塞特教授博士说。

众所周知的旅行推销员问题就是一个典型的例子：旅行者必须访问许多城市，然后返回自己的家乡。哪条路线最短路?虽然这个问题很容易理解，但随着城市数量的增加，计算时间的爆炸性增长，它变得越来越复杂。旅行商问题代表了一组具有巨大经济重要性的优化问题，无论它们涉及铁路网络、物流还是资源优化。使用近似方法可以找到足够好的解决方案。

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

“无论物理实现如何，我们只是假设有足够的量子位，并研究用它们执行计算操作的可能性，”博士VincentUlitzsch解释道。柏林工业大学的学生。

在此过程中，该团队揭示了与密码学中一个众所周知的问题(即数据加密)的相似之处。

“我们意识到我们可以使用Shor算法来解决这些优化问题的子类，”Ulitzsch说。这意味着计算时间不再随着城市数量(指数，2N)而“爆炸”，而是仅以多项式增加，即随着Nx增加，其中x是常数。这样得到的解在质量上也比使用传统算法得到的近似解要好得多。

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

版权说明：本站所有作品图文均由用户自行上传分享，仅供网友学习交流。若您的权利被侵害，请联系我们

标签：