Relaxation of the EM Algorithm via Quantum Annealing*

arXiv:1606.01484v1 [stat.ML] 5 Jun 2016

Hideyuki Miyahara and Koji Tsumura

Abstract— The EM algorithm is a novel numerical method
to obtain maximum likelihood estimates and is often used for
practical calculations. However, many of maximum likelihood
estimation problems are nonconvex, and it is known that the EM
algorithm fails to give the optimal estimate by being trapped by
local optima. In order to deal with this difficulty, we propose a
deterministic quantum annealing EM algorithm by introducing
the mathematical mechanism of quantum fluctuations into
the conventional EM algorithm because quantum fluctuations
induce the tunnel effect and are expected to relax the difficulty
of nonconvex optimization problems in the maximum likelihood
estimation problems. We show a theorem that guarantees
its convergence and give numerical experiments to verify its
efficiency.

I. Introduction
Many of practical problems in engineering or the principles to explain the phenomena of nature are reduced
into nonconvex optimization; however, the research activity
for nonconvex optimization is limited compared to that on
convex optimization because it is fundamentally difficult to
solve or analyze the problem in a sophisticated way.
In order to solve this difficulty of nonconvex optimization,
motivated by the physical process of annealing, Kirkpatrick
et al. [1], [2] proposed simulated annealing (SA). SA has
attracted much attention in many fields because SA has the
following two remarkable properties. The first one is that SA
can be applied to any nonconvex problems. The second one
is that its global convergence in some sense is guaranteed by
Geman and Geman [3]. After that, quantum annealing (QA)
was proposed by Apolloni et al. [4]. In QA, the mathematical
mechanism of quantum fluctuations is introduced, and it has
been reported that QA can reduce computational costs in
many difficult problems [5], [6], [7], [8], [9], [10], [11],
[12], [13], [14]. Despite the success of SA and QA, their
computational costs are still huge, because the Monte Carlo
method is used in most of their implementations and it
requires much computational costs for convergence.
On the other hand, in order to solve the nonconvex
problem in data clustering, Rose et al. [15], [16] proposed a
deterministic simulated annealing approach, and it attracted
interest in both of physics and engineering. This is because it
can relax the problem of local optima with almost the same
numerical cost which is required for a conventional approach.
As a generalization of [15], [16], Ueda and Nakano [17]
proposed a deterministic simulated annealing EM algorithm

TABLE I: Classification of the algorithms
Fluctuations
Thermal
Quantum

Annealing 1
Kirkpatrick et al. [1], [2]
Apolloni et al. [4] 5

3

DAEM 2
Ueda & Nakano [17]
This work 6

4

(DSAEM). The EM algorithm (EM), which was originally
proposed by Dempster et al. [18], is a generic approach to
compute the maximum likelihood estimates, but it is known
that it suffers from the problem of local optima. DSAEM was
reported to be more effective than EM when EM is likely
to be trapped by local optima; however the problem of local
optima is still fundamental in optimization and it has been
tackled via many approaches.
From the above discussions, this paper presents a deterministic quantum annealing EM algorithm (DQAEM)
by introducing the mathematical mechanism of quantum
fluctuations to EM. In DQAEM, quantum fluctuations are
introduced because it may induce the tunnel effect and
it is considered to be effective to solve nonconvex optimization problems. However, it is known to be difficult to
evaluate functions with quantum fluctuations, and our key
idea to compromise this difficulty is to apply the Feynman
path integral formulation to DQAEM. In this paper, after
explaining EM, we give the formulation of DQAEM and
how it is approximated through the Feynman path integral
formulation. Then, we present a theorem that ensures the
monotonicity of its cost function, called the “free energy,”
during the iterations in the algorithm. That is, DQAEM
is guaranteed to converge to the global optimum or local
optima. At the end of this paper, in order to show the
efficiency of DQAEM, we apply DQAEM and EM to a
parameter estimation problem and illustrate that DQAEM
is superior to EM. We summarize the algorithms mentioned
above in Table I for convenience.
This paper is organized as follows. In Sec. II, EM proposed
by Dempster et al. [18] is reviewed for preparation of
DQAEM. In Sec. III, we propose DQAEM and give a
theorem on its convergence. In Sec. IV, we show numerical
simulations to verify the theorem and the efficiency of
DQAEM compared with EM. Finally, in Sec. V, we give
the conclusion of this paper.
II. Review of the EM algorithm (EM)

*This work was supported in part by Grant-in-Aid for Scientific Research
(B) (25289127), Japan Society for the Promotion of Science.
H. Miyahara and K. Tsumura are with the Department of Information Physics and Computing, the Graduate School of Information Science and Technology, The University of Tokyo, Japan

hideyuki miyahara@ipc.i.u-tokyo.ac.jp

In this section, we review EM, which was proposed
by Dempster et al. [18] for the preparation of introducing DQAEM. In this paper, Yobs = {y(1) , y(2) , . . . , y(N) } and
{x(1) , x(2) , . . . , x(N) } denote an observable data set and an

unobservable data set, respectively. Moreover, we assume
that each data point y(i) (i = 1, 2, . . ., N) is independent and
identically distributed. Then, at first, we define maximum
likelihood estimation (MLE). In MLE, the cost function,
which is called the log likelihood function, is given by
L(Yobs ; θ) =

N
X

=

N
X

5:

log

Z

dx(i) p(y(i) , x(i) ; θ),

L(Yobs ; θ) ≥ Q(θ; θ )
N Z
X
−
dx(i) p(x(i) |y(i) ; θ′ ) log p(x(i) |y(i) ; θ′ ), (2)
i=1

dx(i) p(x(i) |y(i) ; θ′ ) log p(y(i) , x(i) ; θ),

(3)

i=1

where the parameter θ′ is an arbitrary parameter and Jensen’s
inequality is used to derive the inequality. Note that the Q
function includes a conditional probability density function
p(x|y; θ), and it is computed with Bayes’ rule as
p(x(i) |y(i) ; θ′ ) = R

p(y(i) , x(i) ; θ′ )
dx p(y(i) , x; θ′ )

,

(4)

for i = 1, 2, . . ., N. Then, the parameter θ(t) is updated by θ′ =
θ(t) and
θ(t+1) = arg max Q(θ; θ(t) ).

initialize θ(0) and set t ← 0
while convergence criterion is satisfied do
calculate p(x(i) |y(i) ; θ(t) ) for i (i = 1, 2, . . ., N) with (4)
(E step)
calculate θ(t+1) = arg maxθ Q(θ; θ(t) ) where Q(θ; θ(t) )
is (3) (M step)
end while

(1)

′

N Z
X

2:
3:
4:

where p(y; θ) and p(y, x; θ) are probability density functions
for incomplete data and complete data, respectively, and θ
is a parameter. Then the parameter θ is determined by the
maximization of L(Yobs ; θ) with respect to θ. Note that in
the case that p(y; θ) belongs to the exponential family, the
maximization can be easily attained.
In most practical cases, however, p(y; θ) does not belong
to the exponential family, and then the maximization of
L(Yobs ; θ) is difficult to compute. EM was proposed as an
iterative approach to calculate the maximum likelihood estimates in these cases, and then the maximization of L(Yobs ; θ)
is replaced by its lower bound called the Q function. We then
derive the Q function as follows:

Q(θ; θ′ ) =

1:

log p(y(i) ; θ)

i=1

i=1

Algorithm 1 The EM algorithm (EM)

(5)

θ

The calculation of (3) is called the E step and that of (5)
is called the M step, and they are iterated until termination
conditions are satisfied. We summarize EM in Table 1.
EM is widely used because it has two remarkable properties as follows. The first one is that it can be applied to
mixture models, which often appear in practical applications,
and it gives better performance than conventional methods
in many cases. The second one is that the log likelihood
function monotonically increase via its iterations, and this
implies that it is stable through iterations. However it is also
known to be trapped by local optima and its performance
heavily depends on an initial estimated parameter, and thus
this problem is a motivation of our study.

III. Deterministic quantum annealing EM algorithm
(DQAEM)
Here, we derive DQAEM, which is the main concept of
this paper, by introducing the mechanism of quantum fluctuations into EM. We then give a theorem which guarantees
its convergence.
A. Derivation
First, we define the cost function, which is called the free
energy, as
1
Fβ,Γ (θ) = − log Zβ,Γ (θ),
β

(6)

where
Zβ,Γ (θ) =

N
Y

Z(i)
(θ),
β,Γ

(7)

i=1

Z(i)
β,Γ (θ) =

Z

dx(i) hx(i) |pΓ (y(i) , x̂; θ)β |x(i) i,

pΓ (y(i) , x̂; θ) = exp{−(H(y(i) , x̂; θ) + Hkin )} (i = 1, 2, . . ., N),
(8)
x̂ represents a position operator, H(y(i) , x̂; θ) =
− log p(y(i) , x̂; θ), and Hkin is a function of a momentum
operator π̂. This momentum operator π̂ satisfies the
commutation relation [ x̂, π̂] = ih̄. In this paper, we consider
the form Hkin = π̂2 /2µ to simplify later calculations. From
the definition of the free energy (6) and the log likelihood
function (1), they hold the following identity,
Fβ=1,Γ=0 (θ) = −L(Yobs ; θ).

(9)

We then interpret the negative free energy as an extension
of the log likelihood function.
Second, in order to formulate DQAEM, we divide the free
energy (6) into two parts as follows,
1
Fβ,Γ (θ) = Uβ,Γ (θ; θ′ ) − S β,Γ (θ; θ′ ),
β
Uβ,Γ (θ; θ′ )
N Z
X
i E
D h
=
dx(i) x(i) − fβ,Γ ( x̂(i) |y(i) ; θ′ ) log pΓ (y(i) , x̂(i) ; θ) x(i) ,
i=1

(10)

′

S β,Γ (θ; θ )
N Z
X
i E
D h
=
dx(i) x(i) − fβ,Γ ( x̂(i) |y(i) ; θ′ ) log fβ,Γ ( x̂(i) |y(i) , θ) x(i) ,
i=1

(11)

with the operator of the perturbed conditional probability
density function,
fβ,Γ ( x̂(i) |y(i) ; θ) =

pΓ (y(i) , x̂(i) ; θ)β
Z(i)
(θ)
β,Γ

.

(12)

The function Uβ,Γ (θ, θ′ ) is an extension of the Q function (3),
and satisfies the identity
Uβ=1,Γ=0 (θ, θ′ ) = −Q(θ, θ′ ).
As the Q function is optimized instead of the log likelihood
function in EM, the function Uβ,Γ (θ, θ′ ) is optimized in
DQAEM.
In some special case, the calculations of the free energy (6)
and the energy (10) can be performed analytically; however
those are difficult in general when an assumed model has a
complicated form. We thus use the Feynman’s path integral
formula [19], [20], [21], [22] to simplify the calculation of
Uβ,Γ as
Uβ,Γ (θ; θ′ )
#
"
M
N Z Y
M
X
X
−1
(i) (i) ′
(i) (i)
f
({x
}|y
;
θ
)
log
p(y
,
x
;
θ)
≈
dx(i)
β,Γ
j
j
j
M
j=1
i=1
j=1
+ const.,

(13)

M
(i)
′
2πβΓ
Zβ,Γ (θ )
1

! M/2

M
X
β
′
log p(y(i) , x(i)
j ;θ )
M
j=1
!
M
X
M (i) (i) 2
−
(x j − x j−1 ) ,
2βΓ
j=1

if and only if Uβ,Γ (θ(t+1) ; θ(t) ) = Uβ,Γ (θ(t) ; θ(t) ) and
S β,Γ (θ(t+1) ; θ(t) ) = S β,Γ (θ(t) ; θ(t) ) are satisfied.
By this theorem, we can conclude that DQAEM is guaranteed to converge to the global optimum or a local optimum. It
is known that the monotonicity of the log likelihood function
in EM and some mathematical features of EM are proved by
Dempster et al. [18] and Wu [23], and this theorem clarifies
that the similar monotonicity also holds in DQAEM.
IV. Numerical simulations
In this section, we give numerical simulations to show the
efficiency of DQAEM in comparison with EM. At, first we
begin with the definition of the problem that we consider in
this section. Next, we give the numerical simulations which
support the theorem shown in the previous section. Finally,
we compare DQAEM and EM by applying them to the
problem and discuss the efficiency of DQAEM.

with
(i) ′
fβ,Γ ({x(i)
j }|y ; θ ) =

Algorithm 2 Deterministic quantum annealing EM algorithm
(DQAEM)
1: set β ← βinit (0 < βinit ≤ 1)
2: set Γ ← Γinit (0 ≤ Γinit )
3: initialize θ(0) and set t ← 0
4: while convergence criteria is satisfied do
(i) (t)
5:
calculate fβ,Γ ({x(i)
j }|y ; θ ) for i (i = 1, 2, . . ., N)
with (14) (E step)
6:
calculate θ(t+1) = arg minθ Uβ,Γ (θ; θ(t) ) with (13) (M
step)
7:
increase β and decrease Γ
8: end while

exp

(14)

(i) M
where M is the number of beads, {x(i)
j } represents {x j } j=1
and the periodic boundary conditions x(i)
= x(i)
M for each
0
i (i = 1, 2, . . ., N) are satisfied. The updating equation for the
parameter θ is therefore given by

θ(t+1) = arg min Uβ,Γ (θ; θ(t) ).
θ

We put the above calculations to an algorithm as DQAEM,
which includes two steps called the E step and the M
(i) (t)
step. In the E step of DQAEM, fβ,Γ ({x(i)
j }|y ; θ ) in (14) is
computed, and in the M step of DQAEM, the parameter θ(t) is
updated by the minimization of (13). Finally, we summarize
the algorithm in Table 2.
B. Convergence theorem
In general, stability of an algorithm is not obvious, and
here we give a theorem that guarantees the stability of
DQAEM through iterations as follows.
Theorem 1: Let the parameter θ(t+1) be given
by θ(t+1) = arg minθ Uβ,Γ (θ; θ(t) ). Then the inequality
Fβ,Γ (θ(t+1) ) ≤ Fβ,Γ (θ(t) ) holds. The equality holds

A. Mathematical formulation
We adopt the mixture of factor analysis (MFA) [24], [25]
as the problem to which DQAEM and EM are applied in this
section. MFA is a model to analyze hidden factors in a given
data set, and is a typical nonconvex optimization problem if
the number of factors is larger than 1. Accordingly, EM is
often applied to MFA for practical calculations.
MFA can be considered to assume following two steps to
generate data. In the first step, a factor is identified by an
index parameter w ∈ {1, 2, . . ., m}, which is generated with a
probability P(w), and an unobservable state x is generated
with a probability density function p(x). In the second step,
the observable variable y is generated by the transformation
of x depending on w and an additive noise. This transformation is represented by p(y|x, w; θ). The probability density
function for y is then given by
m Z
X
p(y; θ) =
dx p(y, x, w; θ),
(15)
w=1

p(y, x, w; θ) = p(y|x, w; θ)p(x)P(w),

(16)

where P(w = i) = πi , p(x) = N(0, I), p(y|x, w = i; θ) = N(µi +
Λi x, Φ), and m is the assumed number of factors in MFA.
For simplicity, we denote {πi , µi , Λi , Φ}m
i=1 by θ.

(a)

(a) 8

-200

Y coordinate

4

-600
-800
m=1
m=3
m=7
m = 10
10
100
Iterations (t)

-1000
1

−Fβ,Γ (θ(t+1) ) + Fβ,Γ (θ(t) )

(b) 50

-8
-1.5

1000

30
20
10
0
1

10

100
Iterations (t)

-0.5
0
0.5
X coordinate

1

1.5

In DQAEM for MFA, the Hamiltonian Hkin , which represents the kinetic term, is added to the original model of
MFA, and then we have the following
pΓ (y, x̂, w; θ) = p(y| x̂, w; θ)e−(H+Hkin ) P(w),

-448.4

-500

-550

-600

1000

Fig. 1: Number of iterations vs (a) negative free energy and
(b) difference of negative free energies in each step for 4
models whose numbers of mixtures are m = 1, 3, 7 and 10.

π̂2 /2µ

-1

(b) -400

m=1
m=3
m=7
m = 10

40

0

-4

L(y; θ(t) ) and −Fβ,Γ (θ(t) )

−Fβ,Γ (θ(t) )

-400

Data

(17)
−Γ∂2 /∂x2

where H = − log p( x̂) and Hkin =
(Hkin =
with Γ = h̄2 /µ in x-bases). Suppose we have N data points
Yobs = {y(1) , y(2) , . . . , y(N) }, and then the free energy is given
by
m Z
N
X
X
E
D
1
dx(i) x(i) pΓ (y(i) , x̂(i) , w(i) ; θ)β x(i) .
Fβ,Γ (θ) =
− log
β
(i)
i=1
w =1

(18)
In numerical experiments, M is set to 128, the annealing
parameter Γ, which represents the strength of quantum
fluctuations, is controlled from an initial value to 0 linearly,
and the inverse temperature β is fixed at 1.
B. Numerical results I
We have shown the monotonicity of the free energy (6)
in DQAEM in Sec. III-B, and here we verify Theorem 1
via numerical experiments. In this subsection, we consider 4
models which have 1, 3 ,7 and 10 mixtures, respectively.
The transitions of negative free energies −Fβ,Γ (θ(t) ) for
these models are shown in Fig. 1(a), and the change of them
−Fβ,Γ (θ(t+1) ) + Fβ,Γ (θ(t) ) is plotted in Fig. 1(b). By observing
Fig. 1, we can confirm that the negative free energy varies
monotonically in DQAEM. In the case that m = 1, this
problem is a convex optimization, and thus we can see that

1

EM
DQAEM
Optimal value
10
100
Iterations (t)

1000

Fig. 2: (a) Data set generated by three Gaussian functions
whose means are (X, Y) = (−1, 0), (0, 0) and (1, 0). (b) Number
of iterations (log scale) vs the log likelihood functions in EM
and the negative free energies in DQAEM.

the negative free energies converge to the unique optimal
value in Fig. 1(a).
C. Numerical results II
This subsection is devoted to the comparison between
DQAEM and EM to show the efficiency of DQAEM. We
deal with the data shown in Fig. 2, which are generated by the
Gaussian mixture model whose means are (X, Y) = (−1, 0),
(0, 0) and (1, 0).
In Fig. 2(b), the transients of the log likelihood functions
by EM are plotted by red lines and those of the negative free
energies by DQAEM are plotted by blue lines. The green
line represents the value of −448.4, which corresponds to
the optimal estimation in this problem. Some of red lines
and blue lines converge to the value of −448.4, and thus
DQAEM and EM give the optimal estimation in these cases.
On the other hand, some of red lines and blue lines converge
to lower values than the optimal estimation.
However, the ratios whether DQAEM and EM gives
the optimal estimation are much different. We performed
DQAEM and EM 1000 times with the same initial conditions, and the ratios whether DQAEM and EM succeed or fail
with the same randomized initial parameters are summarized
in Table II. Here, the “success” of DQAEM and EM is
defined as that square errors between the estimated means
of three Gaussian functions and the true means are smaller
than 0.2 times the covariances of three Gaussian functions.
This table shows that DQAEM succeeds with the ratio 90.7%
while EM succeeds with the ratio 36.6%, and that DQAEM

TABLE II: Ratios whether DQAEM and EM succeed or fail
for this problem (The details of the cases labeled by (∗) and
(∗∗) are discussed in Secs. IV-C.1 (Case I(∗) ) and IV-C.2 (Case
II(∗∗) ), respectively).

Success
Fail
Total

EM

Success
36.3 %(∗)
54.4 %(∗∗)
90.7 %

DQAEM
Fail
3.3 %
9.0 %
9.3 %

Total
36.6 %
63.4 %
100.0 %

L(y; θ(t) ) and −F (θ(t) )

(a) -400
-448.4

-500

-550

(b)

Estimated X coordinates of means

-600

0

200

EM
DQAEM
Optimal value
400
600
800
Iterations (t)

1000

1.5
1
0.5
0
-0.5
-1
-1.5
-2

0

200

EM
DQAEM
True value
400
600
800
Iterations (t)

1000

Fig. 3: (a) Number of iterations vs the log likelihood functions of EM and the negative free energies of DQAEM
with the initial estimated parameters with which both EM
and DQAEM give global optimums (Case I(∗) ). Green line
exhibits the optimal value. (b) Number of iterations vs the
estimated X coordinates of means of Gaussian functions by
EM, and those by DQAEM in Case I(∗) . Green lines stand
for the true values.

is superior to EM.
1) Case I(∗) : Here we focus on the convergence rates of
DQAEM and EM in the case that both of them succeed in
parameter estimation.
First, we plot the log likelihood functions and the negative
free energies in Fig. 3(a) and the estimated X coordinates in
Fig. 3(b). In this case, both the log likelihood functions and
the negative free energies converge to the value of −448.4,
and the estimated X coordinates go to the neighbors around
−1.0, 0.0 and 1.0. These figures also imply that DQAEM
converges to the optimal estimation faster than EM.
We also show the number of iterations that are required
until DQAEM and EM satisfy the criteria of the “success” in
Table III. This table tells us that DQAEM is approximately

TABLE III: Numbers of iterations that are required for
DQAEM and EM to satisfy the criteria of the “success.”
DQAEM
65.33 times

EM
243.82 times

3.73 times faster than EM.
2) Case II(∗∗) : At the end of this section, we analyze the
behaviors of DQAEM and EM in the case that DQAEM
succeeds and EM fails. In Fig. 4(a), the log likelihood
functions of EM and the negative free energies of DQAEM
are plotted. It is observed that while DQAEM gives the value
of −448.4, EM gives lower values than that and is trapped
by some local optima. The estimated X coordinates by EM
and DQAEM are shown Figs. 4(b) and (c), respectively.
While the estimated X coordinates by DQAEM converge
in the neighbors around −1.0, 0.0 and 1.0, the estimated X
coordinates by EM go to different values.
V. Conclusion
We have proposed a deterministic quantum annealing
EM algorithm (DQAEM) in this paper. In DQAEM, the
mathematical mechanism of quantum fluctuations is introduced into EM, and then our proposed algorithm is regarded
as a quantum version of that by Ueda and Nakano [17].
Then we show a theorem on the monotonicity of DQAEM
mathematically, that is, it guarantees that DQAEM is stable
in the algorithm iterations. Through numerical experiments,
we also confirmed the monotonicity of DQAEM, and then
we compared DQAEM and EM. In the comparison, we
observe that DQAEM succeeds in parameter estimates with
higher probability and faster than EM. At the end, we
mention our future work. DQAEM in this paper is for models
with continuous latent variables, and then one of our future
works is to formulate DQAEM for models with discrete
latent variables, which usually appear in various engineering
problems.
References
[1] S. Kirkpatrick,
C. D. Gelatt,
and
M. P. Vecchi,
“Optimization by simulated annealing,” Science, vol. 220,
no.
4598,
pp.
671–680,
1983.
[Online].
Available:
http://www.sciencemag.org/content/220/4598/671.abstract
[2] S. Kirkpatrick, “Optimization by simulated annealing: Quantitative
studies,” Journal of Statistical Physics, vol. 34, no. 5-6, pp. 975–986,
1984. [Online]. Available: http://dx.doi.org/10.1007/BF01009452
[3] S. Geman and D. Geman, “Stochastic relaxation, gibbs distributions,
and the bayesian restoration of images,” Pattern Analysis and Machine
Intelligence, IEEE Transactions on, vol. PAMI-6, no. 6, pp. 721–741,
Nov 1984.
[4] B. Apolloni, C. Carvalho, and D. de Falco, “Quantum
stochastic optimization,” Stochastic Processes and their Applications,
vol. 33, no. 2, pp. 233–244, 1989. [Online]. Available:
http://www.sciencedirect.com/science/article/pii/0304414989900409
[5] A. Finnila, M. Gomez, C. Sebenik, C. Stenson, and
J. Doll, “Quantum annealing: A new method for minimizing
multidimensional functions,” Chemical Physics Letters, vol.
219, no. 56, pp. 343–348, 1994. [Online]. Available:
http://www.sciencedirect.com/science/article/pii/0009261494001170
[6] T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse
ising model,” Phys. Rev. E, vol. 58, pp. 5355–5363, Nov 1998.
[Online]. Available: http://link.aps.org/doi/10.1103/PhysRevE.58.5355

L(y; θ(t) ) and −F (θ(t) )

(a) -400
-448.4

[12]
-500

Estimated X coordinates of means

(c)

Estimated X coordinates of means

-600
(b)

[13]

-550

0

200

EM
DQAEM
Optimal value
400
600
800
Iterations (t)

1000

[14]

1.5

[15]
1
0.5

[16]
0
-0.5

[17]
-1
-1.5

0

200

EM
True value
400
600
800
Iterations (t)

1000

[18]

1.5

[19]

1

[20]

0.5

[21]

0
-0.5

[22]

-1
-1.5

0

200

DQAEM
True value
400
600
800
Iterations (t)

1000

Fig. 4: (a) Number of iterations vs the log likelihood functions of EM and the negative free energies of DQAEM with
the initial estimated parameters with which EM fails and
DQAEM succeeds (Case II(∗∗) ). Green line stand for the
optimal value. (b) Number of iterations vs the estimated
X coordinates of means of Gaussian functions by EM in
Case II(∗∗) . Green lines stand for the true values. (c) Number
of iterations vs the estimated X coordinates of means of
Gaussian functions by DQAEM in Case II(∗∗) . Green lines
stand for the true values.

[7] J. Brooke, D. Bitko, T. F., Rosenbaum, and G. Aeppli,
“Quantum annealing of a disordered magnet,” Science, vol.
284, no. 5415, pp. 779–781, 1999. [Online]. Available:
http://www.sciencemag.org/content/284/5415/779.abstract
[8] D. de Falco and D. Tamascelli, “Quantum annealing
and the schrödinger-langevin-kostin equation,” Phys. Rev.
A, vol. 79, p. 012315, Jan 2009. [Online]. Available:
http://link.aps.org/doi/10.1103/PhysRevA.79.012315
[9] ——, “An introduction to quantum annealing,” RAIRO - Theoretical
Informatics and Applications, vol. 45, pp. 99–116, 1 2011.
[10] A. Das and B. K. Chakrabarti, “Colloquium : Quantum
annealing and analog quantum computation,” Rev. Mod. Phys.,
vol. 80, pp. 1061–1081, Sep 2008. [Online]. Available:
http://link.aps.org/doi/10.1103/RevModPhys.80.1061
[11] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and

[23]
[24]
[25]

D. Preda, “A quantum adiabatic evolution algorithm applied
to random instances of an np-complete problem,” Science,
vol. 292, no. 5516, pp. 472–475, 2001. [Online]. Available:
http://www.sciencemag.org/content/292/5516/472.abstract
G. E. Santoro, R. Martoňák, E. Tosatti, and R. Car, “Theory
of quantum annealing of an ising spin glass,” Science, vol.
295, no. 5564, pp. 2427–2430, 2002. [Online]. Available:
http://www.sciencemag.org/content/295/5564/2427.abstract
G. E. Santoro and E. Tosatti, “Optimization using quantum mechanics:
quantum annealing through adiabatic evolution,” Journal of Physics A:
Mathematical and General, vol. 39, no. 36, p. R393, 2006.
R. Martoňák, G. E. Santoro, and E. Tosatti, “Quantum annealing by
the path-integral monte carlo method: The two-dimensional random
ising model,” Phys. Rev. B, vol. 66, p. 094203, Sep 2002. [Online].
Available: http://link.aps.org/doi/10.1103/PhysRevB.66.094203
K. Rose, E. Gurewitz, and G. Fox, “A deterministic
annealing approach to clustering,” Pattern Recognition Letters,
vol. 11, no. 9, pp. 589–594, 1990. [Online]. Available:
http://www.sciencedirect.com/science/article/pii/016786559090010Y
K. Rose, E. Gurewitz, and G. C. Fox, “Statistical
mechanics and phase transitions in clustering,” Phys. Rev.
Lett., vol. 65, pp. 945–948, Aug 1990. [Online]. Available:
http://link.aps.org/doi/10.1103/PhysRevLett.65.945
N. Ueda and R. Nakano, “Deterministic annealing em algorithm,” Neural Networks, vol. 11, no. 2, pp. 271–282, 1998. [Online]. Available:
http://www.sciencedirect.com/science/article/pii/S0893608097001330
A. P. Dempster, N. M. Laird, and D. B. Rubin, “Maximum likelihood
from incomplete data via the em algorithm,” JOURNAL OF THE
ROYAL STATISTICAL SOCIETY, SERIES B, vol. 39, no. 1, pp. 1–38,
1977.
R. P. Feynman and A. R. Hibbs, Quantum mechanics and path
integration. McGrawsHill, 1965.
R. P. Feynman, Statistical Mechanics: A Set of Lectures. Benjamin
Reading, 1972.
M. Takahashi and M. Imada, “Monte carlo calculation of
quantum systems,” Journal of the Physical Society of Japan,
vol. 53, no. 3, pp. 963–974, 1984. [Online]. Available:
http://dx.doi.org/10.1143/JPSJ.53.963
——, “Monte carlo calculation of quantum systems. ii. higher
order correction,” Journal of the Physical Society of Japan,
vol. 53, no. 11, pp. 3765–3769, 1984. [Online]. Available:
http://dx.doi.org/10.1143/JPSJ.53.3765
C. F. J. Wu, “On the convergence properties of the em algorithm,”
Ann. Statist., vol. 11, no. 1, pp. 95–103, 03 1983. [Online]. Available:
http://dx.doi.org/10.1214/aos/1176346060
Z. Ghahramani, G. E. Hinton, et al., “The em algorithm for mixtures
of factor analyzers,” 1996.
K. P. Murphy, Machine learning: a probabilistic perspective. MIT
press, 2012.

