科技工作者之家
科技工作者之家APP是专注科技人才,知识分享与人才交流的服务平台。
科技工作者之家 2021-03-24
组合优化问题关注如何找到离散优化问题的最优解,在科学和工程领域有广泛的应用。较多组合优化问题,如旅行商问题、图染色问题等均是NP难问题。因此,也许并不存在一般性高效率的求解方法。
统计物理中关注的自旋玻璃模型的基态问题属于NP难的组合优化问题。为此,物理学家和计算机科学家发明了各种各样的严格的和启发式的方法来寻找系统的基态。此外,当自旋玻璃模型存在简并的基态时,严格地数基态的个数(即计算零点熵)属于更难的一类计数问题。近日, 中国科学院物理研究所/北京凝聚态物理国家研究中心凝聚态理论与材料计算重点实验室T03组博士刘金国(现哈佛大学博士后)、研究员王磊,与中科院理论物理研究所研究员张潘合作,提出了一种基于“热带”张量网络的严格求解组合优化问题的最优解和零点熵的方法。
该研究将张量网络收缩中的加乘运算替换为定义在极大-加法半环上的“热带”代数(Tropical Algebra)。通过收缩“热带”张量网络,可以直接计算自旋玻璃模型的基态能量和熵。对网络收缩过程求导,可以得到基态自旋构型。结合泛型编程,该方法可充分利用量子线路模拟器、自动微分技术和专用硬件的算力。科研人员使用该方法研究了二维、三维、Chimera图、随机图上的自旋玻璃模型,以及Potts玻璃模型和最大约束满足等物理和计算机科学中的组合优化问题。在不少情况下,“热带”张量网络方法比传统的计算方法算得更快或可以求解更大尺寸的问题。该研究融合了统计物理、张量网络、机器学习以及量子计算等领域中的概念与方法,为求解组合优化问题提供了新工具。
相关研究成果发表在《物理评论快报》上,开源实现见https://github.com/TensorBFS/TropicalTensors.jl,另可参考教学程序https://giggleliu.github.io/notebooks/tropical/tropicaltensornetwork.html。研究工作得到国家自然科学基金委员会和科学技术部的资助。
C60晶格上反铁磁伊辛模型的基态构型之一
来源:中国科学院
原文链接:http://www.cas.cn/syky/202103/t20210324_4782108.shtml
版权声明:除非特别注明,本站所载内容来源于互联网、微信公众号等公开渠道,不代表本站观点,仅供参考、交流、公益传播之目的。转载的稿件版权归原作者或机构所有,如有侵权,请联系删除。
电话:(010)86409582
邮箱:kejie@scimall.org.cn
研究提出求解组合优化问题的“热带”张量网络方法
《中国地球物理学学科史》研讨暨专家评审会纪要
求解组合优化问题的“热带”张量网络方法
2016全国“组合优化”研究生暑期学校招生简章
“2016年图论与组合优化国际研讨会”在上海大学召开
【论文精选】非均质物料链式组合称重定量算法优化与试验
国际物理医学与康复医学学会(ISPRM)现已开通网络注册会员
全国排序论和组合最优化第二次学术论坛纪要
NSFC全国非线性组合优化暑期班招生简章
评论:为物理考生“兜底”,高考改革更精准化精细化