切换到宽版

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

作者:佚名 来源:中国科学院金属研究所 时间:2020-07-22 12:15 阅读:116 [投稿]
在近期的研究工作中,张志东研究员确定了自旋玻璃三维伊辛模型的计算复杂度的下限,为一个绝对极小核模型的计算复杂度,它包含一个与其最近邻平面相互作用的自旋玻璃二维伊辛模型,是亚指数时间,超多项式时间。

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

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

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

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

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

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

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

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

论文链接:

扫一扫,关注光行天下的微信订阅号!
【温馨提示】本频道长期接受投稿,内容可以是:
1.行业新闻、市场分析。 2.新品新技术(最新研发出来的产品技术介绍,包括产品性能参数、作用、应用领域及图片); 3.解决方案/专业论文(针对问题及需求,提出一个解决问题的执行方案); 4.技术文章、白皮书,光学软件运用技术(光电行业内技术文档);
如果想要将你的内容出现在这里,欢迎联系我们,投稿邮箱:service@dolapcim.com
文章点评
充值送彩金的彩票网 送彩金的彩票网 送彩金100可提款mg游戏 时时彩飞单机器人 白菜大全自动送彩金 三亚赌博送彩金 澳客彩票 免费送彩金可提款 时时彩飞单机器人 北京赛车Pk10全自动下注q群微信群机器人