中科院科学家合作研究提出求解组合优化问题的“热带”张量网络方法

组合优化问题关注如何找到离散优化问题的最优解，在科学和工程领域有广泛的应用。较多组合优化问题，如旅行商问题、图染色问题等均是NP难问题。因此，也许并不存在一般性高效率的求解方法。

统计物理中关注的自旋玻璃模型的基态问题属于NP难的组合优化问题。为此，物理学家和计算机科学家发明了各种各样的严格的和启发式的方法来寻找系统的基态。此外，当自旋玻璃模型存在简并的基态时，严格地数基态的个数（即计算零点熵）属于更难的一类计数问题。近日，中国科学院科学家团队——物理研究所/北京凝聚态物理国家研究中心凝聚态理论与材料计算重点实验室T03组博士刘金国（现哈佛大学博士后）、研究员王磊，与中科院理论物理研究所研究员张潘合作，提出了一种基于“热带”张量网络的严格求解组合优化问题的最优解和零点熵的方法。

该研究将张量网络收缩中的加乘运算替换为定义在极大-加法半环上的“热带”代数（Tropical Algebra）。通过收缩“热带”张量网络，可以直接计算自旋玻璃模型的基态能量和熵。对网络收缩过程求导，可以得到基态自旋构型。结合泛型编程，该方法可充分利用量子线路模拟器、自动微分技术和专用硬件的算力。科研人员使用该方法研究了二维、三维、Chimera图、随机图上的自旋玻璃模型，以及Potts玻璃模型和最大约束满足等物理和计算机科学中的组合优化问题。在不少情况下，“热带”张量网络方法比传统的计算方法算得更快或可以求解更大尺寸的问题。该研究融合了统计物理、张量网络、机器学习以及量子计算等领域中的概念与方法，为求解组合优化问题提供了新工具。