Read seminar_inoue_20070130.pdf text version

19130 @

· 1,2...,N · - · · ·

H ( t ) = -h - ( t )

z

x

i

h h

d dt

(t ) = H ( t ) (t )

1 0 0 x = , i = 0 -1 1

z i

1 1 0 = + - + - + , + = , - = 0 0 1

0: - (

1 2

(+

+ - )), (

1 2

(+

- - ))

: - h ( + ), h ( - )

1 2

h2 + 2

(t = 0) =

(+

+ - )

( t = ) = +

- h2 + 2

( t + t ) = exp -

(

i

t +t

t

H ( s )ds ( t )

)

c = 10, h = 0.2

=

c t

2 h = 1 - 64 c4

2

+ (t = )

Kadowaki, Thesis 1998)

2

1 2 = + 1 + 2 = =t (1 0 0 0 ) 0 0

1 1

0 1 1 0 1 0 0 1 1 0 t ^ ^ ^x ^x - (1) I (2) + I (1) (2) = - + = + 1 - 2 = = ( 0 1 0 0) 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 1 0 = - 1 + 2 = =t ( 0 0 1 0 ) 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1 = - + = - 1 0 1 0 0 1 0 1 1 0 0 1 0 0 t 1 = - 1 - 2 = = ( 0 0 0 1) 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 1

{

}

1 0 0 1 1 - H (t ) 1 k ,l =± ( k 1 l 2 ) / 2 = - 2 1 0 0 1 1 = - 1 0 1 1 0 1 1

0 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 = = + 2(0 0 0 1) 1 0 0 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 1

{

}

N

^ ^ ^ H (t ) = - i I (1) (xi ) I ( N )

{

}

1 2N

k =± k

1

N =±

k1 k N / 2 N

H = H + H (t ) ^ ^ ^ H = - ij J ij I (1) (zi ) I ( N )

{

}{I^

0 0 1 . 1 . . 1 . 0 1 . . 0

^ ^ (zj ) I ( N ) (1)

}

2 N × 2 N

-

Z = tr exp ( - H - H (t ) )

M

{

}

= tr lim exp ( - M H ) exp ( - M H (t ) )

{

}

M

Z eff

lim exp eff m J ij ik jk + BM ik ik +1 M i ,k { ik =±1} ij ,k

tr{ }e - H eff Z eff

1

A =

, Z eff = tr{ }e - H eff

BM =

1 2 eff

log cosh ( eff ) , eff =

M

^ ^ ^ H = - J -

ij ij z i z j i x i

Z=

{

{ } e

ik =±1

M

ij Jij^iz^ zj

}

i1

{ } { }

' i1 ' i1 ' i2 ' i2

i ^ix e { i 2}

M

× { i 2 } e

M

ij Jij^iz^ zj ij Jij^iz^ zj

× { iM } e

M

{ } { } { } { } e

M

i ^ix e { i 3} ×

M

' iM

' iM

i ^ix { i1}

{ ik }

= 1k Nk

^ iz ik = ik ik , ik = ±1

z

#2

{ ik } e

M

ij Jij^iz^ zj

{ }

' ik

=e

M

ij Jij ik jk

(

i

ik

, ik ) = e

M

ij Jij ik jk

{ }

' ik

x i ^ix M e { ik +1} = i k e ^ k +1 M

^ = cosh ( M ) k k +1 + sinh ( M ) k x k +1

^ ^ = i k cosh ( M ) I + sinh ( M ) x k +1

= cosh (

M

)

( k + k +1 )2

4

+ sinh (

M

)

( k - k +1 )2

4

=

1 2

{e

M

+ e k k +1

-M

}

= Ae B k k +1

k k +1 = 1: Ae B = cosh ( M ) k k +1 = -1: Ae - B = sinh ( M )

1 2

B = 1 log coth ( M ) , A = { 1 sinh ( M )} 2 2

ST

· (

MCS

·

)

{ }

{ }

{ }

log P ({ } | { } ) = - H eff + const.

2

QMC

Z eff lim exp eff m ik jk + h i ik + BM ik ik +1 M i ,k i ,k { ik =±1} ij ,k

MCMC

A =

tr{ }e - H eff Z eff

, Z eff = tr{ }e

- H eff

BM =

1 2 eff

log coth ( eff ) , eff =

M

:

, M , eff = O(1) < 1

2

0

= M tanh

-1

-1

(t + 2)

N

Morita and Nishimori (2006)

Real spin configuration

P ({ }k )

E

BM

large

P ({ }k )

i

Annealing of

{ }k

k

k +1

Trotter

small

0

E

BM =

1 2 eff

log coth ( eff )

{ }

opt

{ }k

{} {} {}

P ( i | { } ) = P ({ } | { } )

i

^ bi = sgn P( i = +1| { }) - P ( i = -1| { } ) = sgn i 1 ^ M = N i ibi h = 1 log 1-pp , T = Ts 2

= SA QA

-

J N

H =-

Si S j i< j

1 0

H =-

0

J N

i< j

- i

z i z j

x i

x iz = , i = 0 -1 1

m = tanh( Jm / T )

mx = (1 - J ) J + ( J - 1)

mz = (1 - J ) 1 -

2

1 1 0 = + - + - + , + = , - = 0 0 1

J2

Quantum H eff = - m <ij > iz z - h i i iz - i ix j

T

opt m

= Ts

(Nishimori and Wong 1999)

m0 ( s ) = M ( )

(Inoue 2005)

0 Du 02 + ( opt ) 2 eff

-

(

1010101

1+0+1+0+1+0+1= 0 (mod 2)

{1 , 2 ,...., N }

i1i 2 ip = J

:

R=

0 i1i 2ip

N N = C = 1 + p log p + (1 - p) log(1 - p) NB N C p

2 )

= (1/ 2) log(1 + J 02 / J 2 )

P ({ J } , { } | { } ) =

exp J i1,..,ip J i1ip i1 ip + h i i i

(

)

( 2 cosh J )

NB

( 2 cosh h )

N

exp ( - H eff ) P ({ } | { J } , { } ) = {} exp ( -Heff )

H eff = - J i1,..ip J i1ip i1 ip - h i i i - i ix

H = - h -

z x

h2 + 2

2h

- h2 + 2

1XY

J x = 1, J y = 0

1

O ( 1N2 )

2XXZ

a=0

a

O ( 1N2 )

Effective

Jm

1

Cf. -

E 1/ ()

1

2

E 1/ ()

http://chaosweb.complex.eng.hokudai.ac.jp/~j_inoue/

· Static · · LDPCk-SAT

Information

25 pages

Find more like this

Report File (DMCA)

Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:

Report this file as copyright or inappropriate

154555