Mathematical Problems of Computer Science 44, 22–32, 2015.
Computation Statistical Properties of Disordered Spin
Systems from the First Principles of Classical
Mechanics
Ashot S. Gevorkyan1,2 and Vahe V. Sahakyan1
1 Institute for Informatics and Automation Problems of NAS RA
2 Institute of Chemical Physics of NAS of RA
e-mail: g ashot@sci.am
Abstract
We study the classical 1D spin glasses in the framework of Heisenberg model.
Based on the Hamilton equations we obtained the system of recurrence equations,
which allows performing node-by-node calculations of a spin-chain. It is shown that
the calculations from the first principles of classical mechanics lead to NP hard prob-
lem, that however, in the limit of the statistical equilibrium can be calculated by P
algorithm. For the partition function of the ensemble a new representation is offered
in the form of one-dimensional integral of spin-chains’ energy distribution.
Keywords: Disordered system, Heisenberg spin glass, Ergodic ensemble, NP hard
problem, P algorithm.
1. Introduction
A wide class of phenomena in physics, chemistry, material science, biology, nanoscience, neu-
ral network, evolution, organization dynamics, hard-optimization, environmental and social
structures, human logic systems, financial mathematics etc., are well described mathemati-
cally by models of spin glasses [1]–[10]. Despite of numerous studies there are still a number
of topical issues in the field of spin glasses and disordered systems as a whole, the solution
of which is extremely important and useful in terms of developing modern technology. We
can mention a few important ones;
a) The simulation of spin glasses far from thermodynamic equilibrium. Obviously, in such
cases, we cannot enter the ambient temperature and, respectively, write and use a standard
representation for partition function.
b) Even if it is assumed that spin glass is in the state of the thermodynamic equilibrium in
the frameworks of standard theoretical and numerical methods it remains an open research
question of metastable states. Recall that the Monte Carlo simulation methods allow us to
study the spin systems only in the ground state, at the time when the real statistical system,
moreover spin glasses, always are in metastable states, where parameters characterizing spin
glass have some distributions.
22
A. Gevorkyan and V. Sahakyan 23
c) At definition of the partition function, a priori is assumed that the total weight of
nonphysical spin configurations in the configuration space is a zero that in a number of cases
may be an incorrect assumption. Recall, that under the nonphysical spin configurations, we
mean spin-chains which are unstable from the point of view of basic principles of classical
mechanics.
d) The computational complexity of spin glasses often applies to the class of the NP hard
problems. This circumstance requires development of new efficient algorithms for a numerical
simulation of spin glasses that one way or another leads to the problem of reduction of the
NP to the P problem.
As it was shown in works [11, 12, 13, 14], the problem of spin glasses even in the state of
the thermodynamic equilibrium often are NP hard problems, whose source is in the diverging
equilibration at simulations by the Monte Carlo methods [15]. Recently in the statistical
physics a rapid growth of the number of works has accurred which are using combinatorial
optimization methods [16, 17, 18]. In particular, a number of disordered statistical systems
have been mapped onto combinatorial problems for which fast combinatorial optimization al-
gorithms are available [19, 20]. So, combinatorial methods and the corresponding algorithms
are often used for simulation of spin glasses especially when studying the phenomena such
as phase transitions where they have given valuable insights about questions that are hard
to study by traditional techniques, for example, by Monte Carlo simulations [11]). However,
the above-mentioned problems, for which we want to receive clear answers obviously require
the development of principally new approaches.
In this paper we will study the classical 1D spin glass problem suggesting that only the
nearest neighboring spins interact. Recall that despite the simplicity of the model, since
in a known sense it is an exactly solvable model [21], as it will be shown below, all the
aforementioned problems in considered model are present, if we solve the task from the first
principles of classical mechanics.
And lastly, one of the important purposes of this work is argumentation of the possibility
of reduction of the initial NP-hard problem to the P problem, when the spin-chains’ ensemble
comes to the statistical equilibrium state.
2. Definition of Model
The disordered 1D spin system, in the nearest-neighboring model is written as ([21]):
H = −
∑
i ∈ N
Ji, i+1sisi+1, si ∈ R3, ||si|| = ||si+1|| = 1, (1)
where N = (1, ..., n) is the set of nodes on 1D lattice, the couplings Ji, i+1 are indepen-
dent random variables characterizing the power of interactions between the spatial spins.
The distribution of the coupling constants will be found below, in the result of numerical
modeling.
Since the norm of vector si = (xi, yi, zi) is equal to the unit, then the projection, zi can
be represented in the following form:
zi = qi|zi|, zi = (1 − x2i − y
2
i )
1/2 > 0, qi = sign(zi). (2)
Substituting (1) into the Hamilton equations (see, for example, ([22])) we can find:
−ẍi = Ji−1, i(xi−1 − xizi−1zi−1) + Ji, i+1(xi+1 − xizi−1zi+1),
−ÿi = Ji−1, i(yi−1 − yizi−1zi−1) + Ji, i+1(yi+1 − yizi−1zi+1), (3)
24 Computation Statistical Properties of Disordered Systems from the First Principles of Mechanics
where the following notations are made, ξ̈i = ∂
2ξi/∂t
2 and ξ = (x, y), in addition ”t”
denotes the usual time. We will assume that near the nodes spins are localized and quasi-
periodic movements commit, ξi(t) = ξ
0
i + δ
ξ
i (t), where ξ
0
i and δi(t) denote the position of the
equilibrium and quasi-periodic function of the time, respectively. Below we will study the
statistical properties of the system, which are formed on time scales τ >> τ0, where τ0 is a
characteristic time of spins oscillation and obviously, in this case; ⟨ẍ⟩τ0 = ⟨ÿ⟩τ0 ≈ 0.
Averaging equations (3) on the period τ0 can be found:
Ji−1, i(xi−1 − xizi−1zi−1) + Ji, i+1(xi+1 − xizi−1zi+1) = 0,
Ji−1, i(yi−1 − yizi−1zi−1) + Ji, i+1(yi+1 − yizi−1zi+1) = 0, (4)
where for simplicity in equations the index ”0” over of variables are omitted, i.e., x0i →
xi, y
0
i → yi and z0i → zi. As it is easy to verify these equations define the condition at which
the Hamiltonian (1) in the i-th node takes an extremal value.
Solving the system of equations (4) with respect to variables xi+1 and yi+1 may be found:
xi+1 = Cx/Ji, i+1, yi+1 = Cy/Ji, i+1, (5)
where the following notations are made:
Cx(y) =
Ax(y) − By(x)(C ±
√
D)
1 + B2x + B
2
y
, Aη = ηizi
−1zi−1 − ηi−1, Bη = ηizi−1qi+1,
D = (1 + B2x + B
2
y − A
2
x − A
2
y − C
2) > 0, C = AxBy − AyBx, η = (x, y).
Now, for the Hamiltonian (1) the conditions of a local minimum can be set. It is obvious
i-th spin is in stable equilibrium if the following inequalities are satisfied:
Axixi(s
0
i ) > 0, Axixi(s
0
i )Ayiyi(s
0
i ) − A
2
xiyi
(s0i ) > 0, (6)
where Aηiηi = ∂
2H/∂η2i and Axiyi = ∂
2H/∂xi∂yi; in addition s
0
i denotes i-th spin which is
in a stable equilibrium.
Using (2), (4) and (6), the explicit forms of the second order derivatives can be calculated:
Aηiηi = (η
2
i + z
2
i )z
−3
i ∆i, Axiyi = xiyiz
−3
i ∆i, ∆i = (Ji−1, izi−1 + Ji+1, izi+1), (7)
and taking into account (6) and (7) the conditions of a local minimum energy may be found:
Axixi = (1 − y
2
i )z
−3
i ∆i > 0, AxixiAyiyi − A
2
xiyi
= z−4i ∆
2
i > 0. (8)
Since, at the zi > 0 both conditions in (8) are satisfied:
∆i = (Ji−1, izi−1 + Ji+1, izi+1) > 0. (9)
Thus, in each node the solutions determining the orientation of the spin in the state of the
local equilibrium can be found. If there is such coupling constants Ji, i+1, for which not only
the conditions (8) or (9) are satisfied, but also the following inequality holds:
J2i, i+1 ≥ C
2
x + C
2
y > 0. (10)
A. Gevorkyan and V. Sahakyan 25
3. The Statistical Ensemble of 1D Disordered Spin-Chains
It is easy to show, that the solutions of equations (5) satisfying inequalities (8) can be of
two types:
a. If Ji−1, isi−1 · si ≤ 0 and |Ji, i+1| > |Ji−1, i|, then there is only one solution, which we
denote by; s+i+1 (queen), and respectively,
b. If Ji−1, isi−1 · si > 0 and |Ji, i+1| ≥ |J0,1| · |s0 × s1|, then s+i+1 is the solution, in addition
there is another solution, s−i+1 (drone) under the condition that, |Ji, i+1| < |Ji−1, i|.
Note that the solutions which are denoted with signs ”+” and ”−” are characterized as
follows, if the previous solution is the queen ”+”, up to two different solutions may be found;
s+i+1 and s
−
i+1, while after the drone
”−” the solution is only one s+i+1. Taking into account
this we can construct solutions graphically in the form of separate Fibonacci subtrees (F̂sT i)
(see Fig. 2).
The mathematical expectation of branchings number depending on the height of F̂sT i
can be calculated as follows:
M(n) = M(n − 1)⌊ (2ξn)⌋ = ⌊2nη(n)⌋, η(n) = 1 + n−1
n∑
k=1
log2(ξk) > 0, (11)
where M(n − 1) number of branchings at the height (n − 1) and ξk denotes a random
coefficient which belongs to the interval [1/2, 1]. For simplification in the expression (11)
the subtree’s number i is omitted. Since each F̂sT i consists of the set of nodes and the
set of edges (the set of constants {J} = [J1,2, J2,3, ...Jn−1,n]), it can be represented as a
graph Gi(n) ∼= {gj(n), j ∈ M}, where gj(n) denotes a random string by length n, which is
characterized by Kolmogorov’s complexity [23, 24].
subtree1 subtree2
J6,7 J6,7
J7,8 J7,8
J3,4 J3,4
J4,5 J4,5
J6,7
J7,8
J5,6 J5,6 J5,6 J5,6
J6,7 J6,7
J1,2
J2,3
J7,8J7,8 J7,8
+
s6
+
s7 - s7
+
s8
+
s3
+
s4 - s4
-
s6
+
s7
+
s8
+
s5 + s5
+
s6 - s6
-
s1
+
s2
+
s7
+
s8+ s8
+
s7
+
s8 - s8
J6,7
J7,8 J7,8 J7,8
J5,6 J5,6
J6,7 J6,7J6,7 J6,7
J7,8 J7,8
J3,4 J3,4
J4,5 J4,5 J4,5
J5,6 J5,6
J1,2
J2,3
J7,8 J7,8
J6,7
-
s6
+
s7 + s7
+
s8
-
s7
+
s8
+
s5
+
s6+ s6
+
s7 - s7
+
s3
+
s4 - s4
-
s5 + s5
-
s1
+
s2
+
s8
+
s7
-
s8 + s8 + s8
+
s6
+
s8
subtree3 subtree4
J7,8
J5,6
J6,7 J6,7
J7,8
J4,5 J4,5
J5,6
J6,7 J6,7
J7,8
J3,4
J1,2
J2,3
J7,8
s7
s8
s5
s6
s7
s8
s4
s5
s6
s7
s8
s3
s1
s2
s7
s8
J7,8
J6,7
J7,8 J7,8
J5,6 J5,6
J6,7 J6,7
J3,4 J3,4
J4,5 J4,5
J1,2
J2,3
J6,7
J7,8 J7,8
J5,6 J5,6
J7,8 J7,8
s7
s8
s6
s7
s5
s6 s6
s8 s8
s3
s4 s4
s1
s2
s6
s7
s5
s8 s8
s7
s8 s8
subtree5 subtree6
J6,7
J7,8 J7,8
J5,6
J6,7 J6,7
J7,8 J7,8
J4,5
J5,6 J5,6
J7,8 J7,8
J6,7
J7,8 J7,8
J4,5 J4,5
J5,6
J6,7 J6,7
J3,4 J3,4
J1,2
J2,3
s6
s7
s5
s6
s7 s7
s8
s4
s5
s7
s8
s7
s8
s6
s7
s4
s5
s6
s3
s1
s2
s8 s8 s8s8 s8
J7,8
J5,6 J5,6
J6,7 J6,7 J6,7
J7,8 J7,8 J7,8 J7,8 J7,8 J7,8
J1,2
J2,3
J6,7 J6,7
J3,4 J3,4
J4,5 J4,5
J5,6
s7
s8
s5
s6 s6
s7 s7 s7
s8 s8s8
s7
s8 s8s8
s1
s2
s6
s3
s4 s4
s5
Fig. 1. Two different Fibonacci subtrees (graphs) each with the height 8. Both of graphs grow
from the same initial data (root) in the result of two independent numerical experiments. The
same symbols si and Ji,j on different graphs can have completely different values.
Thus, for calculations of different physical parameters of the statistical ensemble, it
is necessary to take into account the contribution of all independent graphs {G(n)} =
[G1(n), ...Gi(n), ...].
26 Computation Statistical Properties of Disordered Systems from the First Principles of Mechanics
With regard to the graph computation complexity, it is easy to prove that:
KG(n) ∝ M(n)Ks(n), (12)
where M(n) ∝ 2n is the value of branching on the step n, Ks(n) denotes Kolmogorov’s com-
plexity of the string gj(n), while KG(n) denote the complexity of the graph Gi(n) ⊂ {G(n)}N.
The computational complexity of {G(n)}N obviously will be Kens ∝ NM(n)Ks(n), where
N is the total number of graphs in the ensemble.
The mathematical expectation of random variable f characterizing the ensemble {G(n)}N
can be calculated by the formula:
E[f] = f̄ =
∑N
i=1 wif̄i∑N
i=1 wi
, wi = Ni/N̄, (13)
where Ni and N̄ denote the number of strings of the graph Gi(n) and the total number of
strings in the ensemble, respectively, in addition f̄i =
∑
Gi(n)
f denotes the expectation of
random variable f in the Gi(n), which is calculated similarly to formula (13).
Lemma. If statistical weights of all independent graphs Gi(n) ⊂ {G(n)}N are approxi-
mately the same it can be shown that the statistical weights of all strings gj(n) ⊂ {G(n)}N
are equal exactly. In this case we can use the law of large numbers and simplify the expression
(13) writing it as:
E[f] = f̄ =
1
N
N∑
j=1
f̃j + O(N
−1/3), (14)
where f̃j =
∑
gj
f denotes the expectation of the random variable f on a randomly selected
string gj(n) ⊂ Gi(n).
Thus, the computation of statistical parameters of the disordered spin system by the
formula (13) is algorithmically equivalent to solving of NP hard problem, while the simulation
by the formula (14) is the P problem.
4. The Numerical Experiments
As a rule the problems of spin glasses are studied in the framework of the partition function
representation by methods of Monte Carlo which, however, do not allow to answer many
important questions of the statistical ensemble. In particular an important problem is the
fact that the spin glass in the state of a statistical equilibrium generally speaking is in a
metastable state and has some distribution near the ground state. The system in this state,
obviously, cannot be studied using Monte Carlo methods, because these methods are adapted
only for calculating the ground state.
At first let us consider one set of initial data Ω1i (roots) which includes orientations of the
first two spins of the chain and the coupling constant between them, which are generated
randomly from the corresponding homogeneous distributions. Using the system of recur-
rence equations (5), with consideration of inequality conditions (8), we perform successive
calculations of spin-chain. Recall that this system of equations connects three consecutive
spins, so that knowing the configuration of two previous spins, we can generate from log-
normal distribution ([25]) a random constant Ji, i+1 and exactly to calculate the orientation
of spin in the subsequent node. Conducting the consecutive node-by-node calculations on
A. Gevorkyan and V. Sahakyan 27
the n-th step, we generate a random graph Gi(n) ⊂ {G(n)}N at internal nodes of which the
spins are in local minima of energies. With regard to spins in the external nodes, then it is
supposed that they are in local minima of energies on the basis of other considerations.
We calculated the characteristic distributions and parameters of the 1D spin glass, which
is in the state of the statistical equilibrium using two algorithms which are based on for-
mulas (13) and (14), respectively. For the simulation of the problem, first of all we need
min max Μ Σ
-35. -2.9 -14.2 3.
-34.4 -2.8 -14.2 3.
chains
trees
-25 -20 -15 -10 -5
0.00
0.02
0.04
0.06
0.08
0.10
0.12
0.14
¶
PH¶L
0.00
0.05
0.10
0.15
0.20
0.25
0.30
P
HJ
L
P
min max Μ Σ
-6.3 6.2 0. 1.5
-5.8 5.8 0. 1.5
chain
tree
-4 -2 0 2 4
0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.35
J
PHJL
Fig. 2. The distributions of energies and spin-spin coupling constant. The beige curves denote
the results of calculations using the algorithm with the complete enumeration of all branches of
graphs (conditionally we will call NP algorithm), while black curves are constructed in the result
of calculations by P algorithm.
to specify initial conditions in the form of a large number of independent configurations
(roots), i.e., the large set of the first two spins and coupling constants between them;
{Ω11 = (s11, s11; J11,2)1, ...Ω1N = (s
1
1, s
1
2; J
1
1,2)N} = Ω̂.
The steps of simulation using the algorithm NP are as follows. Using the initial data,
Ω̂ we perform parallel calculations of all graphs Gi(n) of the ensemble Gi(n) ⊂ {G(n)}N.
Note that each of these graphs in terms of classical mechanics represents the set of classical
trajectories that go out from one initial value (root). The database which is obtained in
the result of simulation using NP algorithm allows to construct distributions of the main
parameters of the statistically equilibrium ensemble.
The simulation by P algorithm which is based on the formula (14), is performed in a
similar way but with the difference that in this case instead of the set of graphs {G(n)}N we
grow the set of strings {g(n)}N. In this case from each graph we choose only one string as a
representative. Note, that the string (branch) gj(n) ⊂ {G(n)}N we grow by way of randomly
selecting only one solution in each node. In the result of parallel simulation of the set of
strings, we get the database which allows to construct the distributions of main parameters
of the statistical equilibrium ensemble {G(n)}N with accuracy O(N−1/3).
We compared the results of numerical simulations on the example of the statistical ensem-
ble, {G(20)}5·104 consisting from 5 · 104 graphs by heights 20 with the ensemble {g(20)}5·104
which consists of the 5 · 104 strings of lengths 20. As it can be seen from Fig. 2, the dis-
tributions of various parameters of the statistical ensemble that have been calculated in the
limit of statistical equilibrium using two NP and P algorithms coincide ideally.
28 Computation Statistical Properties of Disordered Systems from the First Principles of Mechanics
Thus, we have shown on the example of 1D Heisenberg spin glass, that the NP hard
problem with the given accuracy may be reduced to the P problem.
5. Partition Function
Now we can return to the definition of the main object of statistical physics, i.e., the par-
tition function. As known the multiparticle classical system in the state of the statistical
equilibrium in the configuration space is described by the partition function of type:
Z(β) =
∫
...
∫
exp{−β H({r})}⌈r∞..., ⌈rN , β = ∞/∥BT , {r} = (r∞, ..., rN ), (15)
where H({r}) is the Hamiltonian of the system in the configuration space, kB and T are the
Boltzmann constant and temperature of the system, respectively.
For the considered model the partition function is calculated exactly and has the following
form ([21]):
Z(β, {J}) =
n∏
i=1
sinh(ai)
ai
, ai = βJi, i+1, (16)
where the coupling constant Ji, i+1 ∈ {J} = (J1, 2, J2, 3, ...Jn−1, n) is the random variable.
The average value of the partition function for the ensemble, can be found by way of aver-
aging over the distribution of the coupling constant. It is often assumed that the distribution
is Gaussian:
W(J) =
1
σJ
√
2π
exp
{
−
(J − J0)2
2σ2J
}
, (17)
where σJ is the variance and J0 is the average value of coupling constant.
Averaging of the partition function (16) by the distribution (17) can find:
Z̄(β) =
∫ +∞
−∞
Z(β, {J})W(J)dJ =
K(β)
√
2π
∫ +∞
−∞
(sinh(σJβx)
σJβx
)n
e−
1
2
(x−x0)2dx, (18)
where x = J/σJ and x0 = J0/σJ, in addition K(β) is the normalization factor:
K−1(β) =
1
2J̄
∫ J̄
−J̄
(sinh(Jβ)
Jβ
)n
dJ =
1
ȳ
∫ ȳ
0
(sinh(y)
y
)n
dy, J ∈ [J̄, −J̄],
with J̄ > 0 and ȳ = J̄β. Recall that the coefficient K(β) is constructed in such a way that
the Helmholtz free energy converges to zero in the limit of β → ∞.
The Helmholtz free energy per one spin in chain is calculated by the following formula:
F(β) = −
1
nβ
ln Z̄(β). (19)
Since the integration in representation (15) is carried out over the complete configuration
space, then obviously we take into account also the contributions of physically unrealizable
spin configurations. Recall that usually the measure of a set of such spin configurations is
assumed to be equal to zero without any serious proof, that not only groundless, but in
some cases may be wrong. Taking into account the fact that a set of strings describing
the statistical ensemble in configuration space formally can be represented as a trajectory
A. Gevorkyan and V. Sahakyan 29
0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4
0
1
2
3
4
5
Fig. 3. The free energy of the ensemble. The red curve is obtained at using of the expression (20),
while the blue curve is obtained in the result of calculation by the expression (19). Note that
parameters of ε0 and σε are found by the way of simulation of problem from the first principles,
whereas parameters J0 and σJ are chosen for reasons of the best approximation to red curve.
of dynamical system, in the limit of ergodicity of system (see [26, 27]), for the partition
function the following representation may be written:
Z⋆(β) =
∫ −n/β
−nε0
P̄(ε)dε, P̄(ε) = c−1P(ε), c =
∫ 0
−nε0
P(ε)dε, (20)
where ε < 0 and ε0 = µ < 0 (see Fig. 2) denote the energy of 1D spin-chain and its average
energy, respectively, P̄(ε) is the normalized energy distribution. If the energy distribution
(see Fig. 2) to approximate by Gaussian function (see expression (17)), then using the
representation (20), for the free energy attributable to a single spin we obtain the following
analytical expression:
F⋆(β) = −
1
nβ
ln
{1
2
[
1 − erf
(ε0 + n/β√
2σε
)]}
, (21)
where σε denotes the variance of spin-chains energy distribution. Comparing Helmholtz’s
free energies F(β) and F⋆(β) for the ensemble {g(20)}5·105 shows that these curves diverge
sharply already at finite temperatures (see Fig. 3 ). As we can see, near the temperature
β ≃ 0.3, the ensemble of spin-chains exhibits a critical behavior, since the free energy tends
to infinity (the red curve) that is characteristic to the phase transitions of the first order. The
latter obviously is connected with the fact that in the expression (21), only the physically
realizable spin configurations are taken into account.
30 Computation Statistical Properties of Disordered Systems from the First Principles of Mechanics
6. Conclusion
We studied 1D spin glass in the framework of Heisenberg’s nearest-neighboring Hamiltonian
from the first principles of the classical mechanics. It was shown that in the framework
of the considered approach, even this simple task, which in a sense, is exactly solvable,
corresponds to the category of NP-hard (see the estimation of complexity (11)). It was
proved that in the limit of the statistical equilibrium the computational NP-hard problem,
with a given accuracy to the P problem is reduced. The developed method as opposed to
standard approach allows to calculate the statistical distributions of all parameters of the
ensemble, including the distribution of coupling constant (see Fig. 2).
In the paper, a new representation was suggested for the partition function in the form of
one dimensional integral from the spin-chains’ energy distribution (see the expression (20)).
We have compared the Helmholtz’s free energies which were calculated by using the usual
(19) and new (21) representations. As it is shown (see Fig. 3), the corresponding curves are
significantly different already at finite temperatures, moreover, near the value β ∼ 0.3 the
ensemble of spin-chains demonstrates a critical property, that usually occurs at first-order
phase transitions. This is obviously due to the fact that in the formula (21), only such spin
configurations are presented which satisfy the basic principles of classical mechanics (see
expressions (4)-(9).
Thus, the main advantages of the developed approach are that we have received clear
answers to all the raised questions on the example of study 1D spin glass from the first
principles of the classical mechanics without using any additional assumptions.
The ideas lying in the base of the developed approach are enough universal and allow the
generalization of model for a multidimensional case and at presence of external fields ([28]).
Lastly, note that the new formulation of the problem of spin glasses and disordered
systems in general might become very useful for investigation of the more global problem:
namely, the problem of reduction of NP hard to the P problem.
References
[1] K. Binder and A. Young, “Spin glasses, Experimental facts, theoretical concepts and
open questions”, Rev. Mod. Phys., vol. 58, pp. 801-976, 1986.
[2] M. Mézard, G. Parisi and M. Virasoro, “Spin Glass Theory and Beyond (World Scien-
tific)”, Singapore 1987.
[3] A. Young, Spin Glasses and Random Fields, World Scientific, Singapore, 1998.
[4] R. Fisch and A. Harris, “Spin-glass model in continuous dimensionality”, Phys. Rev.
Lett., vol. 47, page 620, 1981.
[5] C. Ancona-Torres, D. Silevitch, G. Aeppli and T. Rosenbaum, “Quantum and classical
glass transitions in LiHoxY1-xF4”, Phys. Rev. Lett., vol. 101, no. 5, 057201, 2008.
[6] A. Bovier, Statistical Mechanics of Disordered Systems, A Mathematical Perspective,
Cambridge Series in Statistical and Probabilistic Mathematics, 2006.
[7] Y. Tu, J. Tersoff and G. Grinstein, “Properties of a Continuous-Random-Network model
for amorphous systems”, Phys. Rev. Let., vol. 81 ,page 2490, 1998.
[8] K. Chary and G. Govil, “NMR in biological systems, from molecules to human”,
Springer, vol. 6, page 511, 2008.
[9] E. Baake, M. Baake and H. Wagner, “Ising quantum chain is a equivalent to a model
of biological evolution”, Phys. Rev. Let., vol. 78, page 559, 1997.
A. Gevorkyan and V. Sahakyan 31
[10] A. S. Gevorkyan and H. G. Abajyan, “A new parallel algorithm for simulation of spin
glasses on scales of space-time periods of external fields with consideration of relaxation
effects”, Phys. of Particles and Nuclei Letters, vol. 9, no. 6-7, page 530, 2012.
[11] F. Liers, M. Palassini, A. K. Hartmann and M. Jünger,“Ground state of the Bethe
lattice spin glass and running time of an exact optimization algorithm”,Phys. Rev. B,
68, 094406, 2003.
[12] J. C. Angles, D′Auriac, M. Preissmann and A. Sebo Leibniz-Imag, “Optimal cuts in
graphs and statistical mechanics”, Mathl. Comput. Modeling, 26, no. S-10, page 11,
1997.
[13] C. Papadimitriou, Computational Complexity, (1st ed.). Addison-Wesley. Section 2.7:
Nondeterministic machines, 1993.
[14] H. R. Lewis and C. Papadimitriou, Elements of the Theory of Computation, (1st ed.).
Prentice-Hall. Section 4.6: Nondeterministic Turing Machines, 1981.
[15] N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller and E. Teller, “Equation of
State Calculations by Fast Computing Machines”, J. Chem. Phys., vol. 21, no. 6, page
1087, 1953.
[16] B. Hayes, “Can’t get no satisfaction”, Am. Scientist, vol. 85, page 108, 1997.
[17] R. Monasson et all, Diameter of the world wide web, Nature, London, 400, 133, 1999.
[18] Special issue of Theor. Comput. Sci. 265, edited by O. Dubois, R. Monasson, B. Selman,
and R. Zecchina, 2001.
[19] M. J. Alava, P. M. Duxbury, C. F. Moukarzel and H. Rieger, Phase Transitions and
Critical Phenomena, edited by C. Domb and J. Lebowitz, Academic Press, New York,
18, 2001.
[20] A. K. Hartmann and H. Rieger, Optimization Algorithms in Physics, While-VCH,
Berlin, 2001.
[21] C. J. Thompson, “Phase Transitions and Critical Phenomena”, Academic Press, vol. 1,
pp. 177-226, 1972.
[22] H. Goldstein, Classical Mechanics, Reading, MA: Addison-Wesley, 2nd ed., 1980.
[23] A. N. Kolmogorov, “Logical basis for information theory and probability theory”, IEEE
Transactions on Information Theory, vol. 14, no. 5, pp. 662–664, 1968.
[24] M. Li and P. Vitányi, An introduction to Kolmogorov Complexity and its Applications,
New York, Springer-Verlag, 1997.
[25] S. Y. Park and A. K. Bera, “Maximum entropy autoregressive conditional heteroskedas-
ticity model”, Journal of Econometrics, Elsevier, vol. 50, no. 2, pp. 219–230, 2009.
[26] G. D. Birkhoff, “What is the ergodic theorem?”, The American Mathematical Monthly,
vol. 49, no. 4, pp. 222–226, 1942.
[27] V. I. Arnol’d and A. Avez, Ergodic Problems of Classical Mechanics, New York, W.A.
Benjamin, 1968.
[28] E. A. Ayryan, A. S. Gevorkyan and V. V. Sahakyan, “New algorithm for simulation of
3D classical spin glasses under the influence of external electromagnetic fields”, Physics
of Particles and Nuclei Letters, vol. 2, no. 3, pp. 380–384, 2015.
Submitted 15.07.2015, accepted 27.11.2015
3 2 Computation Statistical Properties of Disordered Systems from the First Principles of Mechanics
âϳñ·³íáñí³Í ëåÇݳÛÇÝ Ñ³Ù³Ï³ñ·»ñÇ íÇ׳ϳ·ñ³Ï³Ý
ѳïÏáõÃÛáõÝÝ»ñÇ Ñ³ßí³ñÏÁ »ÉÝ»Éáí ¹³ë³Ï³Ý ٻ˳ÝÇϳÛÇ
ÑÇÙݳñ³ñ ëϽµáõÝùÝ»ñÇó
². ¶¨áñ·Û³Ý ¨ ì. ê³Ñ³ÏÛ³Ý
²Ù÷á÷áõÙ
Ø»Ýù ѻﳽáï»É »Ýù ¹³ë³Ï³Ý 1D ëåÇݳÛÇÝ ³å³ÏÇÝ»ñÁ г۽»Ýµ»ñ·Ç Ùá¹»ÉÇ
ßñç³Ý³ÏÝ»ñáõÙ: ÐÇÙÝí»Éáí гÙÇÉïáÝÇ Ñ³í³ë³ñáõÙÝ»Ç íñ³ ¹áõñë ¿ µ»ñí³Í é»Ïáõñ»Ýï
ѳí³ë³ñáõÙÝ»ñÇ Ñ³Ù³Ï³ñ·, áñÁ ÃáõÛÉ ¿ï³ÉÇë Çñ³Ï³Ý³óÝ»É ëåÇݳÛÇÝ ßÕóݻñÇ
ѳßí³ñÏÁ ѳݷáõÛó ³é ѳݷáõÛó: òáõÛó ¿ ïñí³Í, áñÁ ¹³ë³Ï³Ý ٻ˳ÝÇϳÛÇ
ÑÇÙݳñ³ñ ëϽµáõÝùÝ»ñÇ ÑÇÙ³Ý íñ³ ѳßí³ñÏÝ»ñÁ µ»ñáõÙ »Ý NP µ³ñ¹ ËݹñÇ,
áñÁ ë³Ï³ÛÝ íÇ׳ϳ·ñ³Ï³Ý ѳí³ë³ñ³ÏßéáõÃÛ³Ý ë³ÑÙ³ÝáõÙ ïñí³Í ÅßïáõÃÛ³Ùµ
ѳßííáõÙ ¿ P ³É·áñÇÃÙÇ ÙÇçáóáí: ²Ýë³ÙµÉÇ íÇ׳ϳ·ñ³Ï³Ý ·áõÙ³ñÇ Ñ³Ù³ñ
³é³ç³ñÏí³Í ¿ Ù»Ïã³÷³ÝÇ ÇÝï»·ñ³É³ÛÇÝ Ý»ñϳ۳óáõÙ ëåÇݳÛÇÝ ßÕóݻñÇ
¿Ý»ñ·Ç³ÛÇ µ³ßËÙ³Ý ýáõÝÏódzÛÇó:
Âû÷èñëåíèå ñòàòèñòè÷åñêèå ñâîéñòâà íåóïîðÿäî÷åííûõ
ñïèíîâûõ ñèñòåì èç ïåðâûõ ïðèíöèïîâ
êëàññè÷åñêîé ìåõàíèêè
À. Ãåâîðêÿí è Â. Ñààêÿí
Àííîòàöèÿ
Ìû èññëåäîâàëè êëàññè÷åñêèå ñïèíîâûå ñòåêëà â ðàìêàõ 1D ìîäåëè
Ãåéçåíáåðãà. Îñíîâûâàÿñü íà óðàâíåíèÿõ Ãàìèëüòîíà, âûâåäåía ñèñòåìà
ðåêóððåíòíûõ óðàâíåíèé, êîòîðàÿ ïîçâîëÿåò îñóùåñòâëÿòü âû÷èñëåíèå ñïèíîâîé
öåïî÷êè óçåë çà óçåëîì. Ïîêàçàíî, ÷òî ïðîâåäåííûå íà îñíîâå îñíîâíûõ
ïðèíöèïîâ êëàññè÷åñêîé ìåõàíèêè ðàñ÷åòû ñâîäÿòñÿ ê NP òðóäíîé çàäà÷å,
êîòîðàÿ, òåì íå ìåíåå, â ïðåäåëå ñòàòèñòè÷åñêîãî ðàâíîâåñèÿ ñ çàäàííîé
òî÷íîñòüþ âû÷èñëÿåòñÿ P àëãîðèòìîì. Äëÿ ñòàòèñòè÷åñêîé ñóììû àíñàìáëÿ
ïðåäëîæåíî îäíîìåðíîå èíòåãðàëüíîå ïðåäñòàâëåíèå îò ðàñïðåäåëåíèÿ ýíåðãèè
ñïèíîâîé öåïî÷êè.
Article.pdf (p.1-10)
02.pdf (p.11)