A new approach to the study of the ground-state properties of 2D Ising spin glass

ground-state

propertiesof2DIsingspinglass

ZhiFangZhan,LikWeeLee,Jian-ShengWang

DepartmentofComputationalScience,NationalUniversityofSingapore,Singapore119260,RepublicofSingapore

February6,2008

Abstract

Anewapproachknownasflathistogrammethodisusedtostudythe±JIsingspinglassintwodimensions.Temperaturedependenceoftheenergy,theentropy,andotherphysicalquantitiescanbeeasilycalculatedandwegivetheresultsforthezero-temperaturelimit.Fortheground-stateenergyandentropyofaninfinitesystemsize,weestimatee0=−1.4007±0.0085ands0=0.0709±0.006,respectively.Bothofthemagreewellwithpreviouscalculations.Thetimetofindtheground-statesaswellasthetunnelingtimesofthealgorithmarealsoreportedandcomparedwithothermethods.

Keywords:MonteCarlodynamics;Flathistogramsampling;Isingspinglass;Ground-states;Tunnelingtime.

PACSnumbers:02.70.Lq,05.50+q,05.10.Ln,75.10.Nr,75.40.Mg.

1Introduction

Theequilibriumpropertiesofspinglasshaveremainedagreatchallengeinnumericalsimulations.Investigatingtheequilibriumground-statestructureofspinglassisalsoimportantandinteresting.Inthelast20years,therehasbeenagreatdealofworkonspinglass[1].ItisgenerallyagreedthatthesimplestspinglasssystemformosttheoreticalworkistheEdwards-Anderson(EA)model,whoseHamiltonianis

H=−

󰀁

Jijσiσj,(1)

whereσitakesonthevalues±1andthesumgoesoverthenearestneighbors.TheJijaredimensionlessvariableswhichdescribetherandominteractionsbetweenthespinsandaretakenasJij=±1.Intwodimensions,aphasetransitionoccursonlyatzerotemperature[2,3,4]forthiskindof±JIsingspinglasswithnearestneighborinteractions.Thismodelhasbeenstud-iedpreviouslybythetransfermatrixmethod[2,5],replicaMonteCarlomethod[4,6],multicanonicalensemblemethod[7]andmanyothermethods(seeref[1]forareview).

ThetraditionalMonteCarlomethodsmostlyconcentrateongeneratingstandardstatisticalensembles,e.g.,thecanonicalensembleormicrocanonicalensemble.Usingthecanonicalensemblesimulations,weneedtosimulateatdifferenttemperaturestogetfullinformationaboutthesystem.Itistedioustocalculatecertainthermodynamicquantitieslikethefreeenergyandtheentropysincethedensityofstatescannotbeobtaineddirectlyfromthesimu-lationdata.Thecorrelationbetweensubsequentconfigurationsgeneratedbycanonicalensemblesimulationsalsocausestheergodicityproblemforsomesystems.In1991,Bergproposedthemulticanonicalensemblemethod[8]toovercometheaboveshortcomingsofsimulationsoncanonicalensemble.ThemulticanonicalensembleisanensemblewheretheprobabilityP(E)ofhavingenergyEatequilibriumisaconstant.Themulticanonicalmethodhasbeenverysuccessfulinsolvingthesystemsthatinvolveenergybarriers.Recently,Wangproposedadynamics[9]whichcangenerateaflathis-togramintheenergyspaceasthemulticanonicalmethod.Thisdynamicshassomeconnectionswiththebroadhistogrammethod[10],whichdoesnotgivethecorrectmicrocanonicalaverage[9].Similartothebroadhistogrammethod,thenewdynamicsisalsobasedon󰀈N(σ,∆E)󰀆,the(microcanon-ical)averagenumberofpotentialmoveswhichincreasetheenergyby∆E

1

inasinglespinflip.Acumulativeaverage(overMonteCarlosteps)canbeusedasafirstapproximationtotheexactmicrocanonicalaverageinthefliprate.Thermodynamicquantitiescanbethencalculatedfromthesimulationdatawithease.Inthispaper,weusethenewmethodtostudythether-modynamicsaswellasground-statepropertiesforthetwo-dimensionalIsingspinglasssystem.

InSection2,theflathistogramtransitionmatrixMonteCarlodynamicsisdescribed.Usingtheflathistogramsampling,wegettheaveragenumberofpotentialmoves󰀈N(σ,∆E)󰀆E,whichcanbeusedtoconstructatransi-tionmatrixMonteCarlodynamicsintheenergyspace[11].Weapplythenewmethodtotwo-dimensionalIsingspinglassandpresentsomenumericalresultsinSection3.Inthelastsection,wegiveaconclusiontothenewmethod.

2

ThetransitionmatrixMonteCarlodynam-icswiththeflathistogramsampling

Toconnectourdynamicswithsingle-spin-flipGlauberdynamics[12],werestricttheprotocolofeachmovetobesingle-spinflipinthefollowingdis-cussion.ForagivenstateσwithenergyE,considerallpossiblesingle-spinflips.Thesingle-spinflipschangethecurrentstateintoNpossiblenewstates,withnewenergyE′=E+∆E.Fortwo-dimensionalIsingspinglass,∆E=0,±4,and±8.WeclassifytheNnewstatesaccordingto∆EandcountthenumberofN(σ,∆E).SinceeachmovefromthestateσofenergyEtothestateσ′ofenergyE′andthereversemovearebothallowed,thetotalnumberofmovesfromallthestateswithenergyEtoE′isthesameasfromE′toE.Thus,wehave[13]

E(σ)=E

󰀁

N(σ,∆E)=

E(σ′)=E+∆E

󰀁

N(σ′,−∆E).

(2)

ThemicrocanonicalaverageofaquantityA(σ)isdefinedas

󰀈A󰀆E=

1

canrewriteEq.(2)as

n(E)󰀈N(σ,∆E)󰀆E=n(E+∆E)󰀈N(σ′,−∆E)󰀆E+∆E.

(4)

Eq.(4)isthebasicresultofthebroadhistogrammethod[10].Whilethebroadhistogramrandomwalkalgorithmisnotcorrect,Eq.(4)isnotprob-lematicandtakenasthestartingpointoftheflathistogramsampling.

Weselectasitetoflipatrandom.Thefliprateforasingle-spinflipfromstateσwithenergyEtoσ′withenergyE′=E+∆Eischosenas

r(E|E)=min1,

′

󰀅

󰀈N(σ′,−∆E)󰀆E′

n(E)

=const.(7)

Since󰀈N(σ,∆E)󰀆Eisnotknowningeneral,anapproximationschemeshouldbeusedtostartthesimulation.ForthoseEwhichwehavenotvisitedyet,wesimplysetr(E′|E)=1.Thenacumulativeaverage(overMonteCarlosteps)canbeusedasanapproximationtotheexactmicrocanonicalaverageinthefliprate.Wehavenumericalevidencethatthisprocedureconvergestotheexactresult.

WecanthenconstructatransitionmatrixMonteCarlodynamicsintheenergyspace[11]with󰀈N(σ,∆E)󰀆E.Forasingle-spin-flipGlauberdynamicswithenergychange∆E,thefliprateisgivenas

w(∆E)=

1

2kBT

󰀈󰀊

.(8)

Sincethereare(onaverage)󰀈N(σ,∆E)󰀆EdifferentwaysofgoingfromEtoE′=E+∆E,thetotalprobabilityfortransitionfromEtoE′is

W(E+∆E|E)=w(∆E)󰀈N(σ,∆E)󰀆E,

for∆E=0.

(9)

3

Thediagonalelementscanbedeterminedby∆EW(E+∆E|E)=1,sincethetotalprobabilityfromEtoE′is1.ThisnewdynamicsinthespaceofenergyEisrelatedtosingle-spin-flipdynamicsby[11]

󰀆

W(E′|E)=

1

wayforsimulatingthemulticanonicalensemble.

Theflathistogramalsogeneralizeseasilytomulti-variatemodels[14].AnexampleistheIsingSpinGlassmodelwithoverlapparameterqwhichhastheHamiltonian

H2=−

󰀁

11Jijσiσj−

󰀁

22

Jijσiσj−h

󰀁󰀄

i

12

σiσi.q

(12)

󰀇

EreferstothefirsttwointeractiontermsinvolvingthecouplingconstantsJij.

Inthisbivariatecase,thequantity󰀈N(σ,∆E)󰀆generalizeto󰀈N(σ,∆E,∆q)󰀆.Itcanbeeasilyshownthatthedetailedbalanceconditionisnow

n(E,q)󰀈N(σ,∆E,∆q)󰀆E,q=n(E+∆E,q+∆q)󰀈N(σ′,−∆E,−∆q)󰀆E+∆E,q+∆q

(13)

withn(E,q)asthenew“densityofstates”.ThealgorithmgivesaflathistograminbothEandq.

3Numericalresults

WehaveperformedsimulationsonlatticesofsizeL=4,10,16,24and32.Eachsimulationstartswithindependentrandomnumbers.Toillustratetheperformanceofouralgorithm,wedefinethetimeτLastheaveragenumber(overcouplingconstantJij)ofMonteCarlostepsneededtoreachtheground-states.AMonteCarlostepisdefinedasflippingeachspinonthelatticeonce(ontheaverage).Table1givesanoverviewoftypicaltimeinMonteCarlostepstoreachtheground-states,startingfromanarbitraryenergylevel.Thetimetoreachtheground-statesdependsonthesizeofthesystemandalsotherandominteractions.WeconsideralargenumberofrandomcouplingstatestomakethestatisticalerrorsmallenoughinTable1.Thesimulationsarelongenoughtoensurethatthegroundstatesarereallyreached.InFig.1weplotthetimeτLversuslatticesizeLonadoublelogscale.Thedataareconsistentwithastraight-linefit,whichgivesthefinite-sizebehavior

τL∝L4.71,

MCsteps.

(14)

ThecorrespondingCPUtimeforaDigitalAlpha600MworkstationisalsoshowninTable1.Foraccuracy,5independentrunsareperformedforeach

5

latticesizetoobtaintheaverageCPUtime.UptoL=32theCPUtimecanbeapproximatedbyapolynomialfunctionofL6.08.

L

τL(MCSteps)

CPUtime(second)

L

FlatHistogram(F.H.)Multicanonical(M.C.)Bivariateinq(q)

N

lnn(E).(17)

Sincen(E)canbecalculatedfromthesimulationdatadirectly,wethenobtainS(E)withease.

Tocomparewiththeresultsobtainedintheliterature,wefitourdatausingtheformfL=f∞+c/L2andgete0=−1.4007±0.0085,s0=0.0709±0.006.TheenergyfitisplottedinFig.3,andtheentropyfitinFig.4.Ourenergyestimatee0=−1.4007±0.0085isconsistentwiththepreviousMCestimate[4]e0=−1.407±0.008aswellaswiththetransfermatrixresult[5]e0=−1.4024±0.0012.Ourentropyestimates0=0.0709±0.006isalsoconsistentwiththeMCestimate[4]s0=0.071±0.007aswellasthetransfermatrixresult[5]s0=0.0701±0.005.Forthetwo-dimensionalIsingspinglasssystem,DeSimoneetal.[16]useanexactalgorithmbasedonthebranch-and-cuttechniquetofindtheexactground-stateswithsystemsizeupto50×50.Theyobtaintheextrapolatedresulte0=−1.4022±0.0003.WhencomparedwithBerg’sresult,e0=−1.394±0.007,s0=0.081±0.004,itseemsthatourmethodgivesamoreaccurateestimateforground-stateenergyandentropyforaninfinitesystem.

7

106105(τL ~ L1044.71)τL1031021011248163263LFigure1:τLvslatticesizeonadoublelogscale.

105104(τq ~ L4.45)τq10310210112481632LFigure2:Tunnelingtimeofbivariatemodelonadoublelogscale.

8

−1.3−1.32−1.34e = −1.4007 ± 0.00850e0−1.36−1.38−1.4−1.420510152025303540LFigure3:FSSestimateofenergyperspinoftheinfinitesystemsize.

0.20.15 s = 0.0709 ± 0.0060 s00.10.050510152025303540LFigure4:FSSestimateofentropyperspinoftheinfinitesystemsize.

9

4Conclusions

Wehaveusedanewapproachtoinvestigatetheground-statepropertiesofthetwo-dimensionalIsingspinglass.Comparedwithstandardsimulations,theadvantageofourmethodisobvious.Fortheergodicityproblemen-counteredinstandardsimulations,ourmethodbehavesaswellasBerg’smulticanonicalensemblemethod,whileitiseasiertobeimplementedcom-paredwithBerg’smethod.Ourmethodalsogeneralizestraightforwardlytomulti-variatemodelswithoutmucheffortinprogrammingandtheory.

Tofindatrueground-state,weroughlyneedaCPUtimeoforderL6.ItisthesamewithLawler’sexactalgorithm[17].Uptosize50×50,DeSimone’salgorithmalsoneedsatimeoforderL6.Butitisnotclearwhetherhisalgorithmcanbeefficientlyimplementedfor3Dsystems.Howeverourmethodcanalsobeeasilyappliedto3Dspinglasssystem.Ifoneisjustinter-estedinfindingtheground-states,therearealsootheroptimizedalgorithms.Chen’slearningalgorithm[18]isfastinfindingtheground-statescomparedwithmostalgorithms,butitisnotageneralone.Thermodynamicquantitiescannotbeobtainedwiththisalgorithm.

Webelievethattheapproachwepresentinthispaperisusefulinstudyingthethermodynamicsaswellasground-statepropertiesforspinglasssystems.Italsocanbeappliedtoothermodelsbecauseofitsgenerality.

References

[1]K.BinderandA.P.Young,Rev.Mod.Phys.58,801(1986).

[2]I.MorgensternandK.Binder,Phys.Rev.Lett.43,1615(1979);Phys.

Rev.B22,288(1980).[3]W.L.McMillan,Phys.Rev.B28,5216(1983).

[4]R.H.SwendsenandJ.-S.Wang,Phys.Rev.Lett.57,2607(1986).[5]H.-F.CheungandW.L.McMillan,J.Phys.C16,7027(1983).[6]J.-S.WangandR.H.Swendsen,Phys.Rev.B38,4840(1988).[7]B.BergandT.Celik,Phys.Rev.Lett.692292(1992).[8]B.BergandT.Neuhaus,Phys.Lett.B267249(1991).

10

[9]J.-S.Wang,Eur.Phys.J.B8,287(1999).

[10]P.M.C.deOliveira,T.J.P.Penna,andH.J.Herrmann,Braz.J.Phys.

26,677(1996);Eur.Phys.J.B1,205(1998);Braz.J.Phys.30,195(2000).[11]J.-S.Wang,T.K.Tay,R.H.Swendsen,Phys.Rev.Lett.82,476(1999).[12]R.J.GlauberJ.Math.Phys.4,294(1963);B.U.Felderhof,Rep.Math.

Phys.1,215(1970);K.Kawasaki,inPhaseTransitionsandCriticalPhenomena,editedbyC.DombandM.S.Green(AcademicPress,Lon-don,1972),Vol.2,p.443.[13]J.-S.WangandL.W.Lee,cond-mat/9903224(1999).

[14]A.R.Lima,P.M.C.deOliveiraandT.J.P.Penna,cond-mat/9912152

(1999).[15]N.HatanoandJ.E.Gubernatis,MonteCarloandStructureOptimiza-tionMethodsforBiology,ChemistryandPhysics,ElectronicProceed-ings,http://www.scri.fsu.edu/MCatSCRI/proceedings(1999).[16]C.DeSimone,M.Diehl,J¨unger,P.Mutzel,G.ReineltandG.Rinaldi,

J.Stat.Phys.,84,1363(1996).[17]E.L.Lawler,CombinatorialOptimization:NetworksandMatroids

(Holt,Reinehart,andWinston,NewYork,1976).[18]K.Chen,Europhys.Lett.43,635(1998).

11