計算・磁石・脳--- Spin Glass --東大物性研究所 川島 直輝
現代物理学入門 ２００５年４月２５日 本郷

強磁性体 「普通の磁石」●磁石は磁石は小さな磁石
さな磁石（＝磁石（＝スピン（＝スピン）スピン）の集まり．
まり．
●個々の磁石の磁石のＮ極は上向きか上向きか下向きか下向き下向き．（簡単化．（簡単化）
簡単化）
個々のスピンにスピンに番号をつけて番号をつけて，をつけて，第 i 番目の番目の磁石の磁石のＮ極が上向き上向きであることを S = 1 で下向きであることを下向きであることを S = −1 で表そう．
そう．
●強磁性体では強磁性体ではエネルギーではエネルギーがエネルギーが以下のように以下のように与のように与えられる．
えられる．
ii

E = −∑ J S i S j(J > 0)( ij )（Σは全ての最隣接格子点ペアについての和）強磁性体の熱力学平衡状態ではF = E − TSが最小になる．つまり，物質の平衡状態はエネルギーを小さくしようとする傾向と，エントロピーを大きくしようとする傾向のバランスした状態．低温になるほど，後者の影響は弱まる．
低温になるほど低温になるほど全になるほど全てのスピンてのスピンがスピンが同じ向きに向きに向いた状態
いた状態が状態が出現しやすくなる
出現しやすくなる．（しやすくなる．（秩序化．（秩序化した秩序化した状態した状態）
状態）

強磁性体のシミュレーション
状態Σ
状態Σの出現確率は出現確率は

P (Σ ) ∝ e− E (Σ ) / k BT

実際にこの実際にこの確率状態を次々に発生させるのが発生させるのが，にこの確率で確率で状態をさせるのが，磁性体の磁性体のモンテカルロシミュレーション実際にやってみる
実際にやってみる．にやってみる．

スピングラス物質 「変わった磁石」
磁場の磁場の下で冷却ののち冷却ののち測定ののち測定

磁性合金 ＣｕＭｎ
Nagata Keesom Harrison 1979率
磁帯

磁場なしで磁場なしで冷却なしで冷却の後に測定
温度履歴現象同じ量を同じ条件で測っているのに，ある温度以下ではそれ以前に系が置かれた状況で結果が異なる．

スピングラスモデル
相互作用 Ｊ がランダムなランダムな値をもつイジングモデルをもつイジングモデルｉｊE = −∑ J ij Si S j(ij )J ij は（ｉ，ｊ ）ごとに統計的に独立なある確率変数．
たとえば + 1 (強磁性的 )J ij = − 1 (反強磁性的 )(確率１２)(確率１２)

スピングラス問題
Ｊｉｊ が与えられたとき，えられたとき，温度が温度が非常に非常に低いときにスピングラスモデル
いときにスピングラスモデル
はどのような振はどのような振る舞いをするか？
いをするか？
エネルギーがもっともエネルギーがもっとも小がもっとも小さくなる状態さくなる状態を状態を求める問題
める問題．
問題．
．．． 最適化問題

スピングラス問題の例
S1J12 = −1J 31 = +1

S2S3J 23 = −1問題：
問題：
Ｊｉｊ が左のように与のように与えられたとき，えられたとき，エネルギーをエネルギーを最小にするような最小にするような
Ｓ１，Ｓ２，Ｓ２，Ｓ３，Ｓ３の組み合わせを求めよ．
めよ．

スピングラス問題の例
S1答え：

J12 = −1

J 31 = +1

S2S3

J 23 = −1

Ｓ１＝－Ｓ２＝－Ｓ２＝Ｓ３＝Ｓ３＝＋１＝＋１
またはＳ１＝－Ｓ２＝－Ｓ２＝Ｓ３＝Ｓ３＝－１＝－１

スピングラス問題の例
S1
J12 = −1

J 31 = −1

S2S3J 23 = −1問題：
問題：
Ｊｉｊ が左のように与のように与えられたとき，えられたとき，エネルギーをエネルギーを最小にするような最小にするような
Ｓ１，Ｓ２，Ｓ２，Ｓ３，Ｓ３の組み合わせを求めよ．
めよ．

スピングラス問題の例
答え：S1
J12 = −1

J 31 = +1

S2

S3J 23 = −1

－Ｓ１
－Ｓ１＝Ｓ２＝Ｓ２＝Ｓ３＝Ｓ３＝＋１＝＋１または－Ｓ１－Ｓ１＝Ｓ２＝Ｓ２＝Ｓ３＝Ｓ３＝－１＝－１または
Ｓ１＝－Ｓ２＝－Ｓ２＝Ｓ３＝Ｓ３＝＋１＝＋１または
Ｓ１＝－Ｓ２＝－Ｓ２＝Ｓ３＝Ｓ３＝－１＝－１または
Ｓ１＝Ｓ２＝Ｓ２＝－Ｓ３＝－Ｓ３＝＋１＝＋１またはＳ１＝Ｓ２＝Ｓ２＝－Ｓ３＝－Ｓ３＝－１＝－１

スピングラス問題の例
S1J 41 = −1

S4

J 24 = +1

J12 = +1

S2

J 23 = −1J 34 = +1

S3

これだと？
これだと？

スピングラス問題の例

これだと？
これだと？
コンピュータをコンピュータを使えばできるか？
できるか？

スピングラス問題の困難
スピングラス問題
スピングラス問題には問題には一般には一般にはうまい
一般にはうまい解にはうまい解き方は存在しない
存在しない．
しない．
普通の計算機を使って解くために必要な計算時間は，どんな方法を使ったとしても，L のべき乗では抑えられないことが「ほぼ証明」されている．

．．．ただし．．．ただし，
ただし，２次元だとうまい次元だとうまい方法が方法が存在する存在する．
する．

系の１辺の長さを L として，L の６乗に比例する計算時間をかけると解ける．

計算上の本質的困難 「ＮＰ困難性」
スピングラス問題
スピングラス問題は問題はＮＰ困難
ＮＰ困難であることが困難であることが証明であることが証明されている
証明されている．
されている．
ＮＰ困難な問題について以下のことが証明されている．
「ＮＰ困難な問題のどれか１つについて，問題のサイズある多項式で抑えられる計算時間（多項式時間）で解けるアルゴリズムが存在するなら，以下のようなおよそありえないことが可能だということになる．
『解の候補が提案されたとき，多項式時間内にそれが本当に解であるかどうか確かめられるような任意の充足可能問題に対して，多項式時間内に答え（yes か no か）を見つける方法も存在する．』」

もしスピングラス問題が解けるなら．．．
●巡回セールスマン
巡回セールスマン問題
セールスマン問題も問題も解ける．
ける．
●「与えられた論理式えられた論理式を論理式を真にできるか（ＳＡＴにできるか（ＳＡＴ問題（ＳＡＴ問題）」問題）」も）」も解ける．
ける．
●最大派閥問題も最大派閥問題も解ける．
ける．
●「配線を配線を最短にする最短にする回路設計にする回路設計の回路設計の問題（問題（グラフ２グラフ２分割）」分割）」も）」も解ける．
ける．
・・・

Garey and Johnson "Computers and Intractability"にはこのような問題が３００以上紹介されている．しかし，これらの問題は多くの「賢い」人たちの試みにもかかわらず今のところ１つも解かれていない．（多分本質的本質的に本質的に解けない．）

では我々に何ができるか？
（１） 問題を問題を変える，える，または近似または近似を近似を考える．
える．
（２） 計算不可能領域にぎりぎりまで計算不可能領域にぎりぎりまで近にぎりぎりまで近づく．
づく．
（３） 計算不可能領域をはっきり計算不可能領域をはっきり知をはっきり知る．

問題を変える，または近似
もとの問題
もとの問題

E = −∑ J ij Si S j
(ij )

ＳＫモデル
ＳＫモデル（モデル（平均場モデル平均場モデル）モデル）

1
E=−J ij Si S j∑
N i, j(i < j )Quenched （急冷） Randomness
計算すべき計算すべき量すべき量： Tr e − βE J (S )Q(S ) [ Q ] =  S − βE J ( S ) e TrS∂
k BT log Tr e − β ( E J ( S )− ΛQ ( S ))= lim
S
Λ → 0 ∂Λ∂（[ ] はＪ に関する平均）F (Λ )= − limΛ →0 ∂Λ(([))()]ｉｊ

F (Λ ) ≡ [− k BT log Z J (Λ )]レプリカ法（１）
一般に一般に quenched random 平均[log Z J ]は計算しにくい計算しにくい．
しにくい．これに対
これに対して，して，annealed random 平均
log[Z J ]なら簡単なら簡単に計算できる．
簡単に計算できるできる．

[Z J ] = ∫  ∏ dJ ij P(J ij )∑ exp β ∑ J ij Si S j 

 (ij )

S N (ij ) β
= ∑∏ ∫ dJ ij P(J ij )exp
J ij Si S j S (ij )  N= ∑∏ eSβ 2 2N(ij )= 2 N e dβ 22（ガウス分布ガウス分布の分布の場合）
場合）

レプリカ法（２）
そこで恒等式
そこで恒等式Z Jn − 1
Z Jn − 1[log Z J ] = lim
 = limn →0n  n →0 n
[ ]を用いて，いて，一種の一種の annealed 平均の平均の形に変形する変形する．
する．
[Z ] = ∫ ∏nJ( )∑∑∑
β J ij n α α dJ ij P J ij  exp
S i S j  (ij ) S
 (ij ) N α =1= ∑∏ ∫S(ij ) = ∑∏S∑ β J ij n α α dJ ij P J ij exp
S i S j 
 N α =1
( )∑2

 K2  n
α α  exp
Si S j  =

2N(ij )
 α =1 ∑(K ≡ β [J ])
222ij

∑∑

 K2
α β α β exp
S i S i S j S j S
 4 N i , j α ,β

これでランダムネス
これでランダムネスのないランダムネスのないモデルのないモデルにモデルに帰着できた
帰着できた．
できた．

鞍点法[Z ]nJ K2α β α β = ∑ exp∑ ∑ Si S i S j S j S 4 N i, j α ,β2 NK 2  1α β  =∑SSexp
ii
 2 N ∑S (α , β )i
 
∏

 NK
−=∑dqexp∫ αβ

2S (α , β )


∏

{ }

2



2+ K 2 qαβ ∑ Siα S iβ qαβ

i

 NK 2 2α β 2 = ∫ d qαβ exp −qKqSexp∑ αβ ∑∑ αβ i S i 2(α , β )(α , β ) i Si


∏

{ }


 NK 2 2α β 2 = ∫ d qαβ exp −qexp
KqSS∑ αβ  ∑∑ αβ 1 1  
2α,,β )
()
S(αβ
 1
{ }

 K22= ∫ d qαβ exp − N qαβ+g∑2(α , β )∂  K22
q+g({q})∑αβαβ  = 0∂qαβ  2 (α , β )N({q }) αβ



1α βqαβ =S∑
i SiN i

２つのレプリカがどのくらい近いかの尺度．

レプリカ対称解（１）
結局次の結局次の自己無同着方程式を
自己無同着方程式を ｎ →０ の極限で極限で解けばよいことになった．
けばよいことになった．
qµν =1µ νS=∑i SiN i 2α β  µ νexp
KqS
∑ αβ 1 S1  S1 S1∑ (α , β ){S1α }α =1,L,n 2α β exp
Kq
S
∑ αβ 1 S1 ∑ (α , β ){S1α }α =1,L,n

この方程式
この方程式は方程式はレプリカインデックスのレプリカインデックスの任意の任意の入れ替えに関えに関して対象して対象だから対象だから，だから，対称解をまず対称解をまず考をまず考える．
える．
1qµν = q(µ = ν )(µ ≠ ν )レプリカ対称解（２）対称性を対称性を課すと方程式
すと方程式は方程式は比較的簡単に簡単に解けて，けて，しかも，しかも，ｎ →０ の極限が極限が簡単にとれる簡単にとれる．にとれる．

ある有限ある有限の有限の温度以下で温度以下で，秩序変数が秩序変数が０でない値でない値を持つようになる．
つようになる．

qq12 は実際に実際に２つの同つの同じＪをもつサンプル間サンプル間の重なりとも解釈なりとも解釈でき解釈できるので，るので，
1
1q=q =
SS = ∑ S∑NN
1 2i i12i

は，

Si ≠ 0 (T < TC )i

TC1iS2iT

12= ∑ Si ≠ 0N iを意味する意味する．（する．（ランダム．（ランダムなランダムな凍結．）凍結．）

レプリカ非対称解（パリシ解）
レプリカ対称解
レプリカ対称解は対称解は転移温度以上では転移温度以上では正では正しいが，しいが，転移温度以下では転移温度以下では，では，非対称解が非対称解が存在し存在し，そちらの方そちらの方が正しい（しい（自由エネルギー自由エネルギーがエネルギーが低い．）
では q ≠ q1213であることは何であることは何を意味するのか意味するのか？
するのか？

11
12
13SS
≠SS
∑
∑
iiii
N i
N i

互いに異いに異なる熱力学的安定状態なる熱力学的安定状態が熱力学的安定状態が存在する存在する．
する．
（しかも，しかも，パリシのパリシの議論によると議論によると無数によると無数に無数に存在する存在する．）する．）

無数の熱力学的安定状態
無数の無数の安定状態が安定状態が存在し，実際に実際に実現される実現される平衡分布はそれらの平衡分布はそれらの線形結合で線形結合で表される．
される．

F

位相空間のある軸

もう１つのシナリオ
状態Ａ
状態Ａと状態Ｂ
状態Ｂは互いに時間反転によって時間反転によって移によって移りあう．
りあう．
多くの準安定状態
くの準安定状態は準安定状態は存在するが，するが，熱力学的に熱力学的に安定な安定な状態はこの状態はこの二はこの二つしかない．
つしかない．

FAB

ドロップレット描像
ドロップレット描像
ドロップレット描像：
描像：「熱力学的な熱力学的な安定状態は安定状態は１つ．
秩序相における秩序相における熱揺における熱揺らぎ
熱揺らぎ効果らぎ効果は効果は全て安定状態からの安定状態からのドロップレットからのドロップレットの励起によって励起によって説明によって説明できる説明できる．」
できる．」
ドロップレット励起
ドロップレット励起エネルギー
励起エネルギー（Ｅ ）の分布関数
1 ~ El P(El ) = θ P  θ Υl  Υl ｌlＰ（ｑ）に関する異なる予言
1q ≡ ∑ S i1S i2
N i
P(q ) =({ }) ({ }))δ  q − N1 ∑ S S Tr exp(− βH ({S }) − βH ({S })){ }(12HSHSTr
exp−−ββ
1 2{S ,S }ii

1 2i ii

12Si1 , S i2

有限系

「平均場描像」
平均場描像」

有限系「ドロップレット描像
ドロップレット描像」
描像」

限界までやった例

Kawashima and Young

有限温度の有限温度のモンテカルロシミュレーション
秩序変数の秩序変数の分布が分布がガウス分布ガウス分布になるかどうかを調になるかどうかを調べて，べて，ある特定ある特定の特定の温度で温度で，何らかの秩序化らかの秩序化がおきることが秩序化がおきることがわかった．
わかった．
しかし，しかし，秩序相（＝秩序相（＝スピングラス（＝スピングラス相スピングラス相）がどんな相どんな相なのか，なのか，という本質的という本質的なこと本質的なことがまだわかっていない．
がまだわかっていない．

g: 秩序変数の分布がどの程度ガウス関数からずれているかをあらわす無次元量

Ｐ（ｑ）の数値計算
Palassini and Youngx(q ) ≡ ∫ dq′ P(q′)
q−q閑話休題 「脳と計算機」
脳 ： １０１２個のニューロン，ニューロン，１０１５個のシナプス，シナプス，動作時間１０
動作時間１０－３
スーパーコンピュータ ： １０３個のＣＰＵ，動作時間
ＣＰＵ，動作時間１０
動作時間１０－９
処理速度において処理速度において，において，まだ６まだ６桁の差がある．
がある．
しかし，
しかし，計算機の計算機の処理速度の処理速度の進歩スピード
進歩スピードはスピードは１０年１０年で１桁．
（６０年６０年で追いつくかもしれない．）
いつくかもしれない．）
また，また，１つのシナプスつのシナプスよりシナプスより１より１つのＣＰＵ
つのＣＰＵのＣＰＵの方が複雑な複雑な処理が処理が可能であることや可能であることや，であることや，脳は全ての部分ての部分が部分が働いているわけではないことを考ことを考えると，えると，もっと短期間もっと短期間に短期間に単純に単純にハードウェア的ハードウェア的な処理速度は速度は追いつく可能性
いつく可能性がある可能性がある．
がある．

脳のモデル化 （Hopfield model)
信号伝達則
σj


σ i (t + 1) = sgn  ∑ J ijσ j (t )
 j

信号の信号の流れ

ニューロン
σi

学習則

σi

シナプス
J ij

J ij = N −1 ∑ ξ iµ ξ jµµ

Hopfield モデルとＳＫモデル
Hopfield

モデルのモデルの信号伝達規則


σ i (t + 1) = sgn  ∑ J ijσ j (t ) j

は，ＳＫモデル，ＳＫモデル

1E=−J ijσ iσ j∑
N i, j(i < j )の絶対零度における絶対零度におけるモンテカルロシミュレーション
におけるモンテカルロシミュレーションとモンテカルロシミュレーションと同じ．
ＳＫモデル
ＳＫモデルとモデルと同じ道具が道具が使える．
える．

Hoppfield モデルの「相図」
1 NP µ µ
J ij = ∑ ξ i ξ j
N µ =1

えさせるパターンのパターンの数）
N P = （覚えさせるパターン
Ｐ： 無秩序相（無秩序相（何も想起しない想起しない）しない）
ＳＧ： 無意味な無意味なパターンをパターンを想起する
想起する
Ｒ１： 覚えさせたパターン
えさせたパターンを想起する（準安定）．
パターンを想起するする（準安定）．
Ｒ２： 覚えさせたパターン
えさせたパターンをパターンを想起する想起する（する（安定）．
安定）．

組み合わせ最適化問題の「物理的」性質
Monasson et al, Nature 400 p. 133 (1999)

問題：
ブール変数の集合 {b ,b ,...,bＮ} 上で定義される論理式に関して，以下の問題を考える．Ｋ個のリテラルの論理和をＫ節とよぶことにして，ｍ個のＫ節の論理積として表せる論理式

K-SAT

1

F = c1 ∧ c2 ∧2L∧ cm( c = z ∨ z ∨ L∨ z )i1i2iKiが与えられたとする．この論理式が真であるような，ブール変数への真理値の割り当て方は存在するか？

ＣｏｏｋのＣｏｏｋの定理：
定理： ＳＡＴ問題
ＳＡＴ問題が問題が解けるなら任意けるなら任意の任意のＮＰ問題
ＮＰ問題が問題が解ける．
ける．
（系）３－ＳＡＴ問題－ＳＡＴ問題が問題が解けるなら任意けるなら任意の任意のＮＰ問題
ＮＰ問題が問題が解ける．
ける．
（なぜならＳＡＴ
なぜならＳＡＴ問題
ＳＡＴ問題は問題は３－ＳＡＴ問題－ＳＡＴ問題に問題に還元できるから還元できるから．）
できるから．）
２－ＳＡＴ問題－ＳＡＴ問題は問題はＰ．（多項式時間Ｐ．（多項式時間で多項式時間で解ける．）
ける．）

スピングラス問題への変換
bi = true, false
ck = z ∨ z ∨1k2k

F = c1 ∧ c2 ∧" satisfiable"↔ Si = +1,−1L∨ zL∧ c1↔ E k = −1 + µ =1 KKkm∏↔ E = ∑ Ekmk =1↔ min(E ) = −mmS2ikµ
=( Si のＫ次多項式 )相転移

α＝ｍ／Ｎ が小さければ，さければ，unsatisfiable である確率である確率（確率（=p）は当然低く当然低く，大きければ，きければ，確率は確率は高い．αを固定して固定して，Ｎして，Ｎを，Ｎを大きくしていくと，きくしていくと，p=0 から p=1 への変化への変化が変化が突然起こるようになる
突然起こるようになる．（こるようになる．（相転移．（相転移）相転移）p

縦線は縦線はレプリカ法から求から求められた転移点（転移点（２次転移なら転移なら厳密なら厳密）
厳密）αＰとＮＰの「物理的」違い

Ｒ：全Ｒ：全ての基底状態ての基底状態において同において同じ値をもつスピンのスピンの割合．
割合．

３－ＳＡＴ

R

α２－ＳＡＴ
２－ＳＡＴに－ＳＡＴに対してはＲしてはＲは連続的に連続的に変化．
変化．
３－ＳＡＴに－ＳＡＴに対しては不連続しては不連続．
不連続．

まとめ
磁石の基底状態「計算の物理」

Spin Glass

計算

Hopfield / SK model

脳