新聞動態
·綜合新聞
·科研動態
·學術活動
·媒體聚焦
·通知公告
您現在的位置:首頁 > 新聞動態 > 科研動態
自旋玻璃三維伊辛模型的計算複雜度下限研究進展
 
2020-07-13 | 文章来源:功能材料与器件研究部        【 】【打印】【關閉

  我所張志東研究員在解決鐵磁性三維伊辛模型精確解這個物理學難題後,又在計算機領域計算複雜性理論研究方面取得重要進展。在近期的研究工作中,張志東研究員確定了自旋玻璃三維伊辛模型的計算複雜度的下限,爲一個絕對極小核模型的計算複雜度,它包含一個與其最近鄰平面相互作用的自旋玻璃二維伊辛模型,是亞指數時間,超多項式時間。論文發表在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)。它是亞指數,但是超多項式的。 

  本項工作確定了自旋玻璃三維伊辛模型的計算複雜度的下限爲亞指數時間,超多項式時間。自旋玻璃三維伊辛模型可以被映射爲許多其他的科學問題,所以項工作的結論可以直接推廣應用,解決物理、化學、生物、數學、材料科學以及計算機領域一系列相關問題,特別是解決計算機領域的重大基礎科學問題。 

  論文鏈接

文檔附件

相關信息
聯系我們 | 友情鏈接
地址: 沈阳市沈河区文化路72号 邮编: 110016
管理员邮箱: office@imr.ac.cn
中國科學院金属研究所 版权所有 辽ICP备05005387号

官方微博

官方微信