Loop algorithm with non-binary loops
August 2, 2006
Kyoto Univ. (JAPAN)
Kenji Harada

History of quantum
world-line Monte Carlo• Path-integral representation of the partition
function (Feynmann, Suzuki (1976))• Cluster algorithm for classical Monte Carlo(Swendsen & Wang (1987))• Loop algorithm for quantum Monte Carlo(Evertz, Lana & Marcu (1993))

Outline
I. Quantum world-line Monte Carloa. Path-integral representationb. Loop algorithm
II. Non-binary loop algorithma. Non-binary loop
b. Applications
Coworker: Naoki Kawashima (ISSP, Univ. of Tokyo)Canonical ensemble
for a quantum system
Average

TrA exp(−βH)!A" ≡Z
Partition function

Z ≡ Tr exp(−βH) = Trρ(β)
Density operator

ρ(β) ≡ exp(−βH)

Density operator
ρ(β) ≡ e−β(H0 +V )=e

−βH0 "ρ (β)

dρ! (β)!
= −V (β)ρ (β)
dβInteraction picture V (t) ≡ e!

ρ (β) = I −! β0(Bloch eq.)
tH0!

Ve

dt V (t)ρ (t)−tH0

Matsubara formulaρ! (β) = I −! β

dt1 V (t1 ) +0

If V ≡!

! βdt20! t2

dt1 V (t2 )V (t1 ) − · · ·0

Vb , thenb=I−!" βb10dt1 Vb1 (t1 ) +!" βb1 ,b20dt2" t20dt1 Vb2 (t2 )Vb1 (t1 ) − · · ·Path-integral representation!ψ1 |ρ! (β)|ψ1 " = · · · +!

n"({ψi },{bi },{ti }) i=1

E.g.

!ψi+1 |(−Vbi (ti ))|ψi " + · · ·t=β

S=1/2 HAF model on a 4-sites chain

t7 dt

t3 dt
t2 dt
t1 dt

ψ6-V 2t5 dt
t4 dt

ψ7-V 2t6 dt!x=b · S!x=b+1Vb ≡ J S"!
1|ψ! ≡ |z1 z2 z3 z4 !
zi = ±2

ψ1-V 1

ψ5-V 3

ψ4-V 1

ψ3-V 1

ψ2-V 1ψ1

t=0x=1x=2x=3x=4

Path-integral representation ofpartition function∞!
Z ≡ Trρ(β) =
n=0!

!

%

ψn ,···,ψ1 (ψn+1 =ψ1 ) bn ,···,b1 β≥t ≥···≥t ≥0n1

Wn ({ψi }, {bi }, {ti })

Weight of world-line configuration ({ψi }, {bi }, {ti })i=1...nn!
"ψi+1 |(−Vbi (ti ))|ψi $dti
Wn ≡ e−βH0 (ψ1 )i=1Quantum world-line
Monte Carlo• Canonical ensemble average
TrAρ(β)!A" ≡=Z!

{ψi },{bi },{ti }Wn ({ψi }, {bi }, {ti })A(ψ1 )Z• Monte Carlo sampling of world-line
configurations with the probability

Wn ({ψi }, {bi }, {ti })Prob({ψi }, {bi }, {ti }) =Z

Monte Carlo algorithm• Markov chain· · · → S1 → S2 → · · ·• Metropolis’s method(local updates only before loop algorithm)➡ Long correlation times in sequence of samples

at low temperatures and quantum critical points

Loop algorithm
Evertz, et al. (1993)

Global loop updating for world-line configurations• Short correlation times at quantum criticalpoints and low temperatures• Grand canonical sampling
Applicable to quantum critical phenomena forquantum spin and boson models

Procedure of loop algorithm
E.g. s=1/2 HAF model on a 4-sites chain(1) Update vertexes(2) Decompose spin variables into loops(3) Flip each loop with a probability 1/2

Detail balance condition for updatinga vertex: insert and remove
Weight of a world-line configuration· · · {−Vbk+1 (tk+1 )dtk+1 }|ψk+1 "#ψk+1 |{−Vbk (tk )dtk } · · ·tresni(tk+1 ≥ t ≥ tk )removeAlways for a vertex on non-kink
Poisson process!ψk+1 |{−Vb (t)dt}|ψk+1 #Delta operatorσ́iσ́jE.g. s=1/2 HAF interaction
HAF−Hijσiσj≡ −U −1=!

!

1!
!
Si · Sj −41ˆ∆(gH )2"U#U ≡e−iπSjz!
!
1(ifσ+σ=0andσ+
σij! ! ˆij = 0)!σi σj |∆(gH )|σi σj " ≡0 (otherwise)#"1z
σi = ±
Si |σi " = σi |σi "2$

Graph of delta operator
σ́i

σ́j

σ́i

σ́j

E.g.
Horizontal graph
σiσj!
!
!
1(ifσ+σ=0andσ+
σij! ! ˆij = 0)!σi σj |∆(gH )|σi σj " ≡0 (otherwise)#"1z
σi = ±
Si |σi " = σi |σi "2σiσjGraph of delta operatorσ́iσ́jσ́iσ́jσ́i

σ́jσiσjσiσjσiσjThe value of weight is not changed, as long asa modification of spin configuration matches the graphLoop update(i) Each vertex replaces the corresponding graph(ii) Decompose spin variables into a set of loops(iii) Flip each loop randomly with a probability 1/2

Loop algorithm• Update vertexes by a Poisson process• Update spin variables on each loop definedby graphs on vertexes, independently

Very short correlation time between samples!

Applications for loopalgorithm• Quantum S>=1/2 XYZ model in magneticfield• Hardcore and softcore boson model• S=1 bilinear biquadratic model• ...
Note: only not frustrated case!

Outline
I. Quantum world-line Monte Carloa. Path-integral representationb. Loop algorithm
II. Non-binary loop algorithma. Non-binary loop
b. Applications
Coworker: Naoki Kawashima (ISSP, Univ. of Tokyo)

Split-spin technique for an s>1/2 case
(Kawashima & Gubernatis (1994))
S=m spinSα

2m Pauli! spins #Sµα

PSum of permutations P ≡!

⇒S̃ α ≡ P −1"µPπ

S=1/2

S=1S=3/2

S=2π

Map from an s=m spin to s=1/2 spins
Loop algorithm for s=1/2 model
can be applied to s>=1/2 modelSU(N) model
SU(3) model (S=1)

Hij = −(Si · Sj ) − (Si · Sj )2
Hij = −(Si · Sj )2SU(4) model (S=3/2)
2

3

Hij = −93(Si · Sj ) + 20(Si · Sj ) + 16(Si · Sj )Hij = 81(Si · Sj ) − 44(Si · Sj )2 − 16(Si · Sj )3
SU(4) model (Spin & Orbital)!

1
Hij = − Si · Sj −4"!

1
Ti · Tj −4"

SU(N) modelJ β
Hij = Sα (i)Sβα (j)Nδ ββ δδβ[Sα (i), Sγ (j)] = δi,j [δγ Sα (i) − δα Sγ (i)]βSwhere α (i) are the generators of SU(N)

N.Read and S.Sachdev, Physical Review B 42, 4568 (1990)

Symmetry of a model• S=1/2 HAF model

SU(2)Graph with binary (+1/2, -1/2)

2
H=−(S·S)• S=1 bi-quadratic model
ijijSU(3)Graph with non-binary (+1, 0, -1)?

Yes

N. Kawashima & K. Harada, JPSJ 73 (2004) 1379

Graph for bi-quadratic interactiontˆ2(Si · Sj ) − I = U ∆(gH )Uˆ H )|σi σj " ≡!σi! σj! |∆(gσ́iσ́j!

10(S=1)(if σi + σj = 0 and σi! + σj! = 0)(otherwise)(σi = −1, 0, 1)
If the number of states is 3, thenHorizontal graph has SU(3) symmetryσiσjN. Kawashima & K. Harada, JPSJ 73 (2004) 1379

Graph for SU(N)σ́iσ́jˆ H )|σi σj " ≡!σi! σj! |∆(gσiσjσ́iσ́j!

(σi = (−N + 1)/2, . . . , (N − 1)/2)

ˆ C )|σi σj " ≡!σi! σj! |∆(g
σiσj

1 (if σi = −σj and σi! = −σj! )0 (otherwise)!

1 (if σi = σj! and σi! = σj )0 (otherwise)(σi = (−N + 1)/2, . . . , (N − 1)/2)

Proof of SU(N) symmetryˆ C )Ui Uj |zi zj "!zi! zj! |Uit Ujt ∆(gσ́i=! !

!zi! zj! |Uit Ujt |σi! σj! "σi! ,σj! σi ,σjσ́jˆ C )|σi σj "!σi σj |Ui Uj |zi zj "×!σi! σj! |∆(g=!

!zi! zj! |Uit Ujt |σj σi "!σi σj |Ui Uj |zi zj "!

!zi! |Uit |σj "!σj |Uj |zj "!zj! |Ujt |σi "!σi |Ui |zi "σi ,σj=σi ,σjσi

σj="

1 (if zi! = zj and zj! = zi )0(otherwise)

The cross graph operator does not change
under any uniform SU(3) rotation

SU(N) modelσ́iσ́jσiσj2

Hij = −(Si · Sj )Hij = 81(Si · Sj ) − 44(Si · Sj )2 − 16(Si · Sj )3!

1Hij = − Si · Sj −4σ́iσ́j"!

1Ti · Tj −4"

Hij = −(Si · Sj ) − (Si · Sj )2
Hij = −93(Si · Sj ) + 20(Si · Sj )2 + 16(Si · Sj )3σiσjN. Kawashima & K. Harada, JPSJ 73 (2004) 1379

Non-binary loop update

Non-binary loop (+1, or 0, or -1)(i) Each vertex replaces a corresponding graph(ii) Decompose spin variables into a set of loops(iii) Choose one of the N possible states
for each loop with equal probability

Applications• SU(N) quantum antiferromagnets• S=1 bi-linear bi-quadratic modelS=1 bi-linear bi-quadratic model!
"Hij ≡ Jij (cos θ)(Si · Sj ) + (sin θ)(Si · Sj )2
θ/π=-1-3/4-1/2

0SU(3) points : θ/π=-3/4 and -1/2 on bipartite latticeσ́iσ́iσ́jwhich correspond toσ́jandσiσj, respectively
σiσj

We can calculate not only at two special points,
but also between these points!

Non-binary loop algorithmθ
13for − 4 ≤ π ≤ − 2
Decomposition to graph operatorsˆ C ) + (sin θ − cos θ)∆(gˆ H)
Hij = (cos θ)∆(g(a)(b)(c)

Step1

Horizontal graph
⎜+1〉

⎜0〉

Step2

Cross graph⎜-1〉loop algorithm with 3-state loop
cf. loop algorithm for s=1/2 XXZ modelGround states in higher
dimensions with S=1
From mean-field theory
Ferro-πNematic-3π/4

Quadrupolar order

Neel

-π/2

#"!
2z 2Qz ≡(Si ) −3i０

Relation between quadrupole
and loop correlations
σ́iσiσ́iσ́jσjσ́j

Horizontal graph

Cross graphQz (σi ) = Qz (σj )Qz (σi! ) = Qz (σj! )!
Qz (σi ) = Qz (σj )!
Qz (σi ) = Qz (σj )σiσj4!Qz (σ)Qz (σ )" = !δ!(σ),!(σ! ) "9!

!(σ) : loop ID

Improved estimator
0.008<Qzi Qzj >

0.006
0.005

Lx = 32
Lx = 64
Lx = 128(2/9)<δl(i),l(j)>Lx = 32
Lx = 64
Lx = 128

0.007

0.004
0.003
0.002
0.001
00

0.05

0.1

0.15
Jy / Jx

0.2

0.25

0.3

00.05

0.1

0.15
Jy / Jx

0.2

0.25

0.3

Figure: Comparison of a conventional and an improvedmeasurement at θ=-π/2 with an aspect ratio Ly/Lx=1/4.

Efficiency of loop update
The loop correlation between two sites
is equal to the quadrupolar one

Update scale equals to the one of quadrupolar order region

No critical slowing down nearquadrupolar transition point

Summary
I. Non-binary loop algorithma. SU(N) graph with non-binary statesb. Non-binary loop updatec. SU(N) quantum antiferromagnetic on 2D
i. “Emerging spatial structures in SU(N) Heisenberg model” by
N. Kawashima in symposium

d. S=1 bi-linear bi-quadratic modeli. “Quantum Phase Transition between Two Ordered Phaseswith Unrelated Symmetries” by KH in symposium