作者:刘霞 来源:科技日报 发布时间:2024/3/20 10:34:47
选择字号:
量子计算机能更好解决组合优化问题

 

旅行推销员问题是一个经典的数学问题,也是一个组合优化问题。德国柏林弗雷大学和亥姆霍兹柏林能源与材料研究中心(HZB)科学家开展的一项新研究证明,量子计算机在解决旅行推销员问题上,相较于传统方法,展现出了更高的效率和更快的速度。研究论文发表于最新一期《科学进展》杂志。

  ?

旅行推销员问题是指旅行者要通过最短的路线拜访多个城市,然后返回起点。图片来源:HZB

旅行推销员问题是要寻找一条能让旅行者拜访多个城市并返回出发点的最短路径。虽然问题听起来简单,但随着城市数量的增加,以及由此导致的计算时间的激增,其变得越来越复杂。旅行推销员问题代表了一类具有巨大经济意义的优化问题,涉及铁路网、物流、资源优化等多个领域。

在最新研究中,HZB理论物理学家延斯·艾泽特教授领导的团队,使用纯分析方法来评估量子计算机如何解决旅行推销员等组合优化问题。他们发现,可使用密码学领域的秀尔算法来解决这些优化问题。这意味着,计算时间不再随着城市数量的增加而呈指数级“爆炸”,而只是以多项式的形式增加。结果显示,以这种方式获得的解在质量上比使用传统算法的近似解好得多。

 
特别声明:本文转载仅仅是出于传播信息的需要,并不意味着代表本网站观点或证实其内容的真实性;如其他媒体、网站或个人从本网站转载使用,须保留本网站注明的“来源”,并自负版权等法律责任;作者如果不希望被转载或者联系转载稿费等事宜,请与我们接洽。
 
 打印  发E-mail给: 
    
 
相关新闻 相关论文

图片新闻
老化的哈勃空间望远镜转向单陀螺仪操作 中国科学家首次发现“无摩擦的冰”
冰表面长啥样?原子级分辨图像揭晓答案 北方中纬高频雷达网发布首批科学探测结果
>>更多
 
一周新闻排行
 
编辑部推荐博文