自旋玻璃三维伊辛模型的计算复杂度下限研究获得进展

中国科学院金属研究所张志东研究员在解决铁磁性三维伊辛模型精确解这个物理学难题后，又在计算机领域计算复杂性理论研究方面取得重要进展。在近期的研究工作中，张志东研究员确定了自旋玻璃三维伊辛模型的计算复杂度的下限，为一个绝对极小核模型的计算复杂度，它包含一个与其最近邻平面相互作用的自旋玻璃二维伊辛模型，是亚指数时间，超多项式时间。论文发表在Journal of Materials Science and Technology 44 (2020) 116-120。 

玻璃是我们日常生活中经常使用的用品，理解玻璃的形成机制以及动力学行为是一个重大科学问题。在磁性材料中，与玻璃相对应，存在一种自旋玻璃的状态。自旋玻璃是一个无序的磁体，其中原子的自旋不是按照规则图案排列。与铁磁体中的磁性有序相比较，自旋玻璃中的磁性无序，就类似于玻璃中的位置无序与石英的有序相比较。某种程度上，我们可以把自旋玻璃态看成具有自旋的无序取向的有序状态，在其中自旋在空间无序地取向，但是可能随时间的演化保持有序。非常有必要研究自旋玻璃体系的计算复杂性，它是物理、化学、生物、数学、材料科学以及计算机领域的重要课题。可以用伊辛模型来研究自旋玻璃。伊辛模型每个晶格点上有一个自旋，有自旋向上或者向下两种状态，自旋之间具有相互作用。伊辛模型不仅可以描述一个磁性晶格从顺磁性到铁磁性的相变，也可以描述不同的体系（如反铁磁、格气、大生物分子等）中有序-无序相变。本项工作关注一个具有随机分布正和负的自旋相互作用以及存在阻挫的自旋玻璃三维伊辛模型（爱德华-安德森模型），仅考虑最近邻自旋之间的相互作用。可以通过计算体系所有2^N个可能的状态寻找具有N个格点的自旋玻璃伊辛模型的基态，所以计算复杂度的上限是O(2^N)。自旋玻璃三维伊辛模型有拓扑效应、随机性、阻挫、非遍历性质等特征，导致其计算非常复杂，目前最好的算法获得的结果是O(1.3^N)，人们一直无法确定其计算复杂度的下限。 

张志东研究员证明了自旋玻璃三维伊辛模型（晶格点总数N=lmn）计算复杂度的四个定理： 

定理一，自旋玻璃三维伊辛模型的核心模型比一个绝对极小核心模型复杂得多，绝对极小核心模型包含一个自旋玻璃二维伊辛模型与其最近邻平面相互作用。

定理二，自旋玻璃三维伊辛模型的计算复杂度无法简化为小于l乘以一个绝对极小核心模型的计算复杂度。 

定理三，自旋玻璃三维伊辛模型的绝对极小核心模型的计算复杂度无法被任何算法简化为小于O(2^mn)。它为O((1+ε)^N)，远小于O(2^N)，但是远大于并且无法简化为多项式时间O(N^p) 

定理四，自旋玻璃三维伊辛模型的计算复杂度无法被任何算法简化为小于O(2^mn)。它是亚指数，但是超多项式的。 

本项工作确定了自旋玻璃三维伊辛模型的计算复杂度的下限为亚指数时间，超多项式时间。自旋玻璃三维伊辛模型可以被映射为许多其他的科学问题，所以本项工作的结论可以直接推广应用，解决物理、化学、生物、数学、材料科学以及计算机领域一系列相关问题，特别是解决计算机领域的重大基础科学问题。 

论文链接：https://doi.org/10.1016/j.jmst.2019.12.009