组合优化问题在科学和工程领域应用广泛 。 很多组合优化问题 ， 如旅行商问题、图染色问题等都是NP难问题 。 统计物理中关心的自旋玻璃模型的基态问题也属于NP难的组合优化问题 。 为此 ， 物理学家发明了各种各样严格和近似的方法寻找系统的基态 。 此外 ， 当自旋玻璃模型的基态存在简并时 ， 严格计算基态的个数（即零点熵）属于更难的一类被称为#P难的问题 。 近期 ， 中国科学院理论物理研究所研究员张潘与哈佛大学博士后刘金国、中科院物理研究所研究员王磊合作 ， 提出了一种基于张量网络的严格求解组合优化问题最优解和零点熵的方法 。
该工作将张量网络收缩中的加乘运算替换为定义在极大-加法半环上的“热带”代数（Tropical Algebra） ， 称为热带张量网络(Tropical Tensor Network) 。 通过收缩热带张量网络 ， 可以计算自旋玻璃模型的基态能量和熵 ， 从而直接研究零温下的统计物理问题 。 结合机器学习中的可微分编程 ， 此方法可充分发挥量子线路模拟器Yao.jl和高效并行计算设备GPU的计算能力 。 科研人员利用此方法研究了二维、三维、随机图、D-wave公司量子退火计算机上使用的Chimera图上的自旋玻璃模型 ， 以及Potts玻璃模型和最大约束满足等物理和计算机科学中的组合优化问题 。 在一些情况下 ， Tropical张量网络方法比分支界定等传统计算方法算得更快且可以求解更大尺寸的问题 。 该进展融合了统计物理、张量网络、机器学习以及量子计算等领域中的概念与方法 ， 为求解组合优化问题提供了新工具和新思路 。
相关研究成果发表在《物理评论快报》上 。
文章插图
热带张量网络方法在富勒烯图上所定义的自旋玻璃模型中所找到的基态构型
【基态|科研人员提出求解组合优化问题新方法】来源：中国科学院理论物理研究所
推荐阅读
- 导师|要取得科研成功，什么最重要？
- 肥料|广西执法人员查获40吨假化肥
- 河马|如何给一头河马挤奶？
- 天问一号|天问一号即将登陆，美国呼吁共享科研成果，要求交出火星轨道数据
- 新冠病毒|巴西研究人员发现新冠病毒新变种
- 口罩|研究人员发现棉口罩潮湿后过滤性能提高33％，可有效减缓新冠病毒传播
- 古脊椎所|古脊椎所两项科研成果领衔入选“2020年度中国古生物学十大进展”
- 施肥|农技人员提醒：这6种施肥方式，都是错误的！怎么才正确？
- 核酸检测|刚刚！沈阳复阳病例目前排查的密接者等相关人员核酸检测结果公布
- 丙肝|乙肝丙肝共感细胞模型，我国科研人员揭示，两者相互干扰机制