# Convergence condition of simulated quantum annealing for closed and open
systems

Yusuke Kimura  International Research Frontiers Initiative, Tokyo Institute of
Technology, Shibaura, Minato-ku, Tokyo 108-0023, Japan  Hidetoshi Nishimori
International Research Frontiers Initiative, Tokyo Institute of Technology,
Shibaura, Minato-ku, Tokyo 108-0023, Japan  Graduate School of Information
Sciences, Tohoku University, Sendai 980-8579, Japan  RIKEN, Interdisciplinary
Theoretical and Mathematical Sciences (iTHEMS), Wako, Saitama 351-0198, Japan

###### Abstract

Simulated quantum annealing is a generic classical protocol to simulate some
aspects of quantum annealing and is sometimes regarded as a classical
alternative to quantum annealing in finding the ground state of a classical
Ising model. We derive a generic condition for simulated quantum annealing to
converge to thermal equilibrium at a given, typically low, temperature. Both
closed and open systems are treated. We rewrite the classical master equation
for simulated quantum annealing into an imaginary-time Schrödinger equation,
to which we apply the imaginary-time variant of asymptotic adiabatic condition
to deduce the convergence condition. The result agrees qualitatively with a
rigorous convergence condition of simulated quantum annealing for closed
systems, which was derived from the theory of inhomogeneous Markov process.
Also observed is qualitative agreement with a rigorous convergence condition
of quantum annealing for closed systems under the real-time Schrödinger
dynamics. This coincidence of convergence conditions for classical stochastic
processes for simulated quantum annealing and the real-time quantum dynamics
for quantum annealing is highly non-trivial and calls for further scrutiny.

††preprint: APS/123-QED

##  I Introduction

Quantum annealing (QA) is a metaheuristic, a generic approximate algorithm,
for combinatorial optimization problems [1, 2, 3, 4, 5, 6, 7, 8]. Recent years
have seen its developments toward applications to a broader class of problems
beyond combinatorial optimization such as quantum simulations [9, 10, 11, 12,
13, 14, 15, 16] and optimization with continuous variables [17, 18, 19, 20].

The classical algorithm of simulated quantum annealing (SQA) has often been
used to simulate some properties of quantum annealing [21, 3, 22] and shares
the ultimate goal with QA to find the ground state of a classical Ising model.
SQA uses stochastic processes to statistically sample the finite, typically
very low (and ideally zero), temperature equilibrium state of the transverse-
field Ising model written as a classical Ising model by the Suzuki-Trotter
formula [23]. SQA is not designed to reproduce dynamical properties of QA as
the former follows classical stochastic processes whereas the latter is
realized by the time-dependent Schrödinger equation, which are fundamentally
different processes. This point is clear also from the fact that the Suzuki-
Trotter formula is derived by rewriting the equilibrium partition function of
a quantum system into the equilibrium partition function of a corresponding
classical Ising model.

Low-temperature equilibrium behaviors of the transverse-field Ising model are
expected to be captured by SQA as long as the rate of change of time-dependent
parameters in the Hamiltonian is sufficiently slow because then the system
follows quasi-equilibrium state. It is therefore natural to ask how slow is
slow enough for this expectation to stay valid. Equivalently, we may ask,
under what conditions on the time dependence of parameters, SQA successfully
reaches thermal equilibrium.

This question has indeed been answered for generic closed systems, i.e.,
systems isolated from the environment 111As will be discussed later, the term
“environment” here does not refer to classical thermal effects used in
equilibrium simulations of SQA but means experimentally-relevant quantum-
mechanical dissipation coming from interactions with a large number of degrees
of freedom outside of qubit systems [41], where the theory of inhomogeneous
Markov process was used to analyze the stochastic process under SQA [25, 5].
It has been shown that a generic condition for convergence to a finite-
temperature equilibrium state looks qualitatively similar to the corresponding
generic convergence condition of QA for the transverse-field Ising model with
time-dependent coefficients evolving under the real-time Schrödinger dynamics.
More precisely, in both cases of QA and SQA, the coefficient of the
transverse-field term is to be decreased by a power law of time in the long-
time limit with the power inversely proportionally to the system size. This
apparent qualitative coincidence of convergence conditions for completely
different dynamics is highly non-trivial, and it should be useful to provide a
different perspective on this problem. Also from the technical point of view,
the proof provided in Refs. [25, 5] is rather abstract and it is not easy to
extract relevant physics out of it.

To mention a few related studies, Refs. [26, 27] studied the quantum dynamics
of open systems and Ref. [28] discussed the relaxation time of time-
independent models. Though not directly relevant to the present study, those
papers represent interesting developments from the general perspective of
dynamical properties of QA or SQA.

The present paper represents part of efforts toward the above-mentioned goal
concerning convergence conditions by deriving a condition of convergence of
SQA for closed and open systems, based on an approximate, but asymptotically
accurate, adiabatic condition for the imaginary-time Schrödinger equation. The
classical stochastic dynamics of SQA following the master equation is
transformed to the imaginary-time Schrödinger equation through a well-
established prescription [29] (see also Refs. [30, 31]). Then the leading-
order term of the asymptotic expansion of the adiabatic condition for the
imaginary-time Schrödinger dynamics is used to derive our conclusion on the
rate of time development of a coefficient. The logic is not completely
rigorous mathematically because higher-order terms of the asymptotic expansion
are ignored. Nevertheless, it turns out that the resulting convergence
condition is in qualitative agreement with the corresponding rigorous
condition derived from the theory of inhomogeneous Markov process for closed
systems [25].

This paper is structured as follows: In Sec. II, we derive the imaginary-time
Schrödinger equation from the classical master equation for the time-dependent
transverse-field Ising model. In Sec. III, we deduce a convergence condition
for SQA to a thermal equilibrium state by applying the imaginary-time variant
of adiabatic condition. Based on the result in Sec. III, we derive a condition
on the coefficient of the transverse field that ensures the convergence to a
thermal equilibrium state in Sec. IV. This is a central result of this paper.
We discuss the result and conclude the paper in Sec. V.

##  II Simulated quantum annealing and imaginary-time Schrödinger equation

In this section, we recapitulate the general process to rewrite the classical
master equation for the Ising model into an imaginary-time Schrödinger
equation under the context of SQA, closely following Ref. [29].

###  II.1 Classical master equation

Our starting point is the master equation for the Markovian dynamics of the
Ising model [32]:

$\frac{dP_{\sigma}(t)}{dt}=\sum_{\sigma^{\prime}}W_{\sigma\sigma^{\prime}}P_{\sigma^{\prime}}(t).$
(1)

Here, $\sigma$ represents a configuration of $N$ Ising spins,
$\sigma=\\{\sigma_{1},\sigma_{2},\ldots,\sigma_{N}\\}$, and $P_{\sigma}(t)$ is
used to denote the probability of the system in configuration $\sigma$ at time
$t$. We use the notation $\hat{W}$ to denote the transition matrix of size
$2^{N}$ whose entries are:
$(\hat{W})_{\sigma\sigma^{\prime}}=W_{\sigma\sigma^{\prime}}$. An off-diagonal
entry of the matrix $\hat{W}$ can be written as [29]:

$W_{\sigma\sigma^{\prime}}=w_{\sigma\sigma^{\prime}}e^{-\frac{1}{2}\beta\left(H_{0}(\sigma)-H_{0}(\sigma^{\prime})\right)}\hskip
28.45274pt(\sigma\neq\sigma^{\prime}),$ (2)

where $\beta$ is the inverse temperature and $H_{0}(\sigma)$ is the
Hamiltonian of the Ising model under consideration. We employ the heat bath
method with single-spin flips in this paper, where $w_{\sigma\sigma^{\prime}}$
is given by

$w_{\sigma\sigma^{\prime}}=\frac{1}{e^{\frac{1}{2}\beta\left(H_{0}(\sigma^{\prime})-H_{0}(\sigma)\right)}+e^{-\frac{1}{2}\beta\left(H_{0}(\sigma^{\prime})-H_{0}(\sigma)\right)}},$
(3)

where $\sigma$ and $\sigma^{\prime}$ differ only at a single spin. We set
$W_{\sigma\sigma^{\prime}}=0$ for other types of transitions such as multi-
spin flips. Owing to the probability conservation condition
$\sum_{\sigma^{\prime}}W_{\sigma^{\prime}\sigma}=0$, a diagonal entry of the
matrix $\hat{W}$, $W_{\sigma\sigma}$, is expressed as

$W_{\sigma\sigma}=-\sum_{\sigma^{\prime}(\neq\sigma)}W_{\sigma^{\prime}\sigma}=-\sum_{\sigma^{\prime}(\neq\sigma)}e^{-\frac{1}{2}\beta\left(H_{0}(\sigma^{\prime})-H_{0}(\sigma)\right)}\,w_{\sigma^{\prime}\sigma}.$
(4)

###  II.2 Imaginary-time Schrödinger equation for SQA

For simplicity of presentation, we first analyze the case of closed systems,
i.e., systems described solely by the classical representation of the
transverse-field Ising model at finite temperature to be defined below.
Generalization to open systems is relatively straightforward and will be
discussed in a later section.

The Hamiltonian of the transverse-field Ising model for QA is

$H(t)=H_{\rm Ising}+H_{\rm TF}(t),$ (5)

where $H_{\rm Ising}$ denotes the Hamiltonian of the Ising model

$\displaystyle H_{\rm Ising}=-\sum_{\langle
jj^{\prime}\rangle}J_{jj^{\prime}}\,\sigma_{j}^{z}\sigma_{j^{\prime}}^{z}$ (6)

with $\langle jj^{\prime}\rangle$ for pairs of interacting spins, and $H_{\rm
TF}(t)$ is for the transverse field with a time-dependent coefficient:

$\displaystyle H_{\rm TF}(t)=-\Gamma(t)\sum_{j=1}^{N}\sigma_{j}^{x}.$ (7)

Here $\sigma_{j}^{z}$ and $\sigma_{j}^{x}$ are the $z$ and $x$ components of
Pauli matrix at site $j$, respectively.

SQA runs Markov-chain Monte Carlo steps for the transverse-field Ising model
rewritten as the corresponding classical Ising model derived by the Suzuki-
Trotter formula [23] with the Hamiltonian:

$\begin{split}&\beta H_{0}(\sigma)=\\\ &-\sum_{k=1}^{M}\left(\sum_{\langle
jj^{\prime}\rangle}\frac{\beta
J_{jj^{\prime}}}{M}\sigma_{j}^{(k)}\sigma_{j^{\prime}}^{(k)}+\sum_{j=1}^{N}\gamma(t)\sigma_{j}^{(k)}\sigma_{j}^{(k+1)}\right),\end{split}$
(8)

where $M$ is the total number of Trotter slices running from $k=1$ to $M$, and
the time dependent coefficient of the second term $\gamma(t)$ is given by

$\gamma(t)=\frac{1}{2}\log\left({\rm coth}\frac{\beta\Gamma(t)}{M}\right).$
(9)

In Eq. (LABEL:Hamiltonian_H0_in_sec1), $\sigma_{j}^{(k)}(=\pm 1)$ is used to
denote a classical Ising spin at the $j$th site on the $k$th Trotter slice.
Notice that Eq. (LABEL:Hamiltonian_H0_in_sec1) has been derived with
$\Gamma(t)$ regarded as a fixed parameter as can be understood from the fact
that the Suzuki-Trotter formula treats the equilibrium partition function.

In SQA, $\beta$ and $M$ are both kept constant at large values, typically
choosing $\beta/M$ to be of order unity, in order to reproduce the zero-
temperature properties of the original transverse-field Ising model as
faithfully as possible. Only the coefficient $\Gamma(t)$ (and thus
$\gamma(t)$) changes with time $t$. It is important to notice here that the
dynamics of SQA with time-dependent parameters is driven by the classical
stochastic process of Monte Carlo simulation, which is completely different
from the original (zero-temperature) quantum dynamics of the Schrödinger
equation for the transverse-field Ising model of Eq. (5). One should not
expect that the dynamical, i.e. transient, properties of the original quantum
system of Eq. (5) can be reproduced by the classical method of SQA [33].
Nevertheless, QA and SQA share the same goal to find, in the long-time limit
$t\to\infty$, the ground state of the classical Ising model of Eq. (6) by
tuning the parameter $\Gamma(t)$ appropriately as a function of time $t$. The
following discussions are for a condition for SQA with a time-dependent
parameter to converge to a thermal equilibrium state at given finite values of
$\beta$ and $M$ in the long-time limit, which is different from a thermal
relaxation process in a system with time-independent parameters.

The results deduced in this paper hold for any (real and positive) value of
$\beta$. However, for practical applications of the results to a closed
system, we are mainly interested in the limit at which $\beta$ is chosen very
large.

Let us rewrite the classical master equation for SQA in terms of an imaginary-
time Schrödinger equation. The quantum Hamiltonian dictating the latter
equation, $\hat{H}$, can be constructed from the transition matrix $\hat{W}$
as [29]:

$\hat{H}:=-e^{\frac{\beta\hat{H}_{0}}{2}}\hat{W}e^{\frac{-\beta\hat{H}_{0}}{2}}.$
(10)

In Eq. (10), $\hat{H}_{0}$ is used to represent a diagonal matrix whose
diagonal entries are: $(\hat{H}_{0})_{\sigma\sigma}=H_{0}(\sigma)$.

The quantum Hamiltonian has the following explicit expression:

$\hat{H}=\sum_{\sigma}\sum_{\sigma^{\prime}}w_{\sigma\sigma^{\prime}}\left(e^{-\frac{1}{2}\beta\left(H_{0}(\sigma^{\prime})-H_{0}(\sigma)\right)}\ket{\sigma}\bra{\sigma}-\ket{\sigma^{\prime}}\bra{\sigma}\right).$
(11)

Since the configurations $\sigma$ and $\sigma^{\prime}$ differ only at a
single site, the $j$th site on the $k$th Trotter slice, the difference $\beta
H_{0}(\sigma^{\prime})-\beta H_{0}(\sigma)$ is given by the following
expression, owing to the expression (LABEL:Hamiltonian_H0_in_sec1) of the
Hamiltonian $H_{0}$:

$\displaystyle\beta H_{0}(\sigma^{\prime})-\beta H_{0}(\sigma)=$
$\displaystyle\frac{2\beta}{M}\sum_{j^{\prime}\,({\rm
n.n.}\,j)}J_{jj^{\prime}}\sigma_{j}^{(k)}\sigma_{j^{\prime}}^{(k)}$
$\displaystyle+2\gamma(t)\sigma_{j}^{(k)}\left(\sigma_{j}^{(k+1)}+\sigma_{j}^{(k-1)}\right).$

The summation symbol on the right-hand side expresses the sum over sites
$j^{\prime}$ that are interacting with $j$. For notational simplicity, we
denote the difference (II.2) by $-2\beta H_{j,k}$:

$\displaystyle-\beta H_{j,k}:=$
$\displaystyle\frac{\beta}{M}\sum_{j^{\prime}\,({\rm
n.n.}\,j)}J_{jj^{\prime}}\sigma_{j}^{(k)}\sigma_{j^{\prime}}^{(k)}+\gamma(t)\sigma_{j}^{(k)}\left(\sigma_{j}^{(k+1)}+\sigma_{j}^{(k-1)}\right).$
(13)

Utilizing the introduced notation, the diagonal coefficient in Eq. (11) can be
rewritten as:

$w_{\sigma\sigma^{\prime}}e^{-\frac{1}{2}\beta\left(H_{0}(\sigma^{\prime})-H_{0}(\sigma)\right)}=\frac{e^{\beta
H_{j,k}}}{e^{\beta H_{j,k}}+e^{-\beta H_{j,k}}}.$ (14)

Similarly, the off-diagonal coefficient in Eq. (11) is:

$w_{\sigma\sigma^{\prime}}=\frac{1}{e^{\beta H_{j,k}}+e^{-\beta H_{j,k}}}.$
(15)

Using a matrix-vector notation, the master equation (1) can be rewritten as
follows:

$\frac{d\hat{P}(t)}{dt}=\hat{W}(t)\hat{P}(t),$ (16)

where $\hat{P}(t)$ denotes a vector whose $\sigma$th entry
$(\hat{P}(t))_{\sigma}$ is $P_{\sigma}(t)$:
$(\hat{P}(t))_{\sigma}=P_{\sigma}(t)$.

If we define

$\displaystyle\ket{\phi(t)}:=e^{\frac{1}{2}\beta\hat{H}_{0}}\hat{P}(t),$ (17)

it is straightforward to confirm that the master equation (16) is rewritten as
the following imaginary-time Schrödinger equation [29] :

$-\frac{d\ket{\phi(t)}}{dt}=\left(\hat{H}(t)-\frac{1}{2}\frac{d}{dt}(\beta\hat{H}_{0})\right)\,\ket{\phi(t)}.$
(18)

In the long-time limit, time dependence in the Hamiltonian $\hat{H_{0}}$
becomes arbitrarily small as $\Gamma(t)$ gradually approaches zero, and the
expression on the outer parentheses in the above equation approaches
$\hat{H}(t)$. In this limit, the ground state of the Hamiltonian $\hat{H}(t)$
corresponds to the equilibrium state of the master equation (16) as shown in
Ref. [29].

We apply the adiabatic condition [5] to the imaginary-time Schrödinger
equation of Eq. (18) to deduce the convergence condition on SQA.

##  III Imaginary-time variant of adiabatic condition

We next discuss the adiabatic condition for the imaginary-time Schrödinger
equation.

###  III.1 General adiabatic condition for the imaginary-time Schödinger
equation

To formulate the adiabatic condition, it is useful first to keep computation
time to a finite value denoted as $\tau$. Then, $s$ is used for a
dimensionless time scaled by $\tau$, i.e. $s=t/\tau$. We write the Hamiltonian
of a generic quantum system as $\mathcal{H}(t)$. We have in mind the quantity
in the large parentheses on the right-hand side of Eq. (18) for
$\mathcal{H}(t)$ as will be discussed later. We assume that the instantaneous
ground state of $\mathcal{H}(t)$ is non-degenerate. This is justified in the
present system, which is time-evolving by Eq. (18), because the quantity in
the large parentheses on the right-hand side of Eq. (18) is the Hamiltonian of
a transverse-field Ising model with non-vanishing off-diagonal elements only
between those states different by a single-spin flip (and thus expressed by
$\sigma_{i}^{x}$), to which the Perron-Frobenius theorem [34] applies 222 Also
in the long-time limit $t\to\infty$, the ground state is non-degenerate since,
according to Eq. (17), the ground state of $\mathcal{H}(t)$ corresponds to the
equilibrium Boltzmann distribution of the original classical system [29],
which is naturally unique. This should not be confused with the $Z_{2}$
degeneracy of the ground state of the classical Ising model of Eq. (6)..
Notice that this transverse-field Ising model defined in terms of $\hat{H}$ of
Eq. (11) and $d(\beta\hat{H_{0}})/dt$ is different from the original model Eq.
(5).

We define $\overline{\mathcal{H}}(s)$ as

$\overline{\mathcal{H}}(s):=\mathcal{H}(t).$ (19)

Let $\ket{j(s)}$ denote the $j$th excited state, $j=0,1,\ldots$,

$\overline{\mathcal{H}}(s)\ket{j(s)}=\epsilon_{j}(s)\ket{j(s)}.$ (20)

$\Delta_{j}(s)$ is used to denote the instantaneous energy gap between the
$j$th excited state and the ground state,
$\Delta_{j}(s)=\epsilon_{j}(s)-\epsilon_{0}(s)$. The instantaneous energy gap
between the first excited state and the ground state is particularly written
as $\Delta(s)$, i.e. $\Delta(s)=\epsilon_{1}(s)-\epsilon_{0}(s)$.

A variant of the adiabatic condition for the imaginary-time Schrödinger
equation obtained in Ref. [5] states that: For the state vector

$\displaystyle\ket{\psi(s)}=\sum_{j}c_{j}(s)\ket{j(s)}$ (21)

of the imaginary-time Schrödinger equation,

$\displaystyle-\frac{1}{\tau}\frac{d\ket{\psi(s)}}{ds}=\overline{\mathcal{H}}(s)\ket{\psi(s)},$
(22)

the coefficient $c_{j}(s)$ with $j\neq 0$ has the large-$\tau$ asymptotic
expansion as:

$c_{j\neq
0}(s)\approx\frac{1}{\tau}\frac{\bra{j(s)}\frac{d\overline{\mathcal{H}}(s)}{ds}\ket{0(s)}}{\Delta_{j}(s)^{2}}+O(\tau^{-2}).$
(23)

The first term on the right-hand side of Eq. (23), the first-order term in the
asymptotic expansion from the limit of large $\tau$, should be sufficiently
small for the system to be close to the instantaneous ground state
$\ket{0(s)}$. Since we ignore the second- and higher-order terms, our theory
is approximate but is nevertheless expected to be accurate in the asymptotic
limit of large $\tau$.

In terms of the original time variable $t$, the adiabatic condition can be
written as:

$\frac{\lvert\bra{j(t)}\frac{d\mathcal{H}(t)}{dt}\ket{0(t)}\rvert}{\Delta_{j}(t)^{2}}\ll
1$ (24)

for $j\neq 0$. By bounding the numerator of the left-hand side of Eq. (24) by
the operator norm as shown in Appendix A,

$\displaystyle\left\lvert\bra{j(t)}\frac{d\mathcal{H}(t)}{dt}\ket{0(t)}\right\rvert\leq\left\lVert\frac{d\mathcal{H}(t)}{dt}\right\rVert,$
(25)

we find that the condition is satisfied that the original system reaches
thermal equilibrium (the ground state of the imaginary-time Schrödinger
equation) in the long-time limit if the following relation is satisfied:

$\lim_{t\to\infty}\frac{\left\lVert\frac{d\mathcal{H}(t)}{dt}\right\rVert}{\Delta(t)^{2}}\ll
1.$ (26)

Notice that we apply the adiabatic condition only in the long-time limit since
we are interested in minimizing the excitation probability only at the end of
the process such that the system approaches the (low-temperature) equilibrium
state in the long-time limit. It may therefore happen that the adiabatic
condition may not necessarily be satisfied in the intermediate time region,
which we do not care.

###  III.2 Adiabatic condition applied to SQA

Let us apply the condition of Eq. (26) to the problem we are interested in.

We apply the framework in the previous subsection to the case that
$\mathcal{H}(t)$ is the quantity in the large parentheses on right-hand side
of the imaginary-time Schrödinger equation (18):

$\mathcal{\hat{H}}(t)=\hat{H}(t)-\frac{1}{2}\frac{d}{dt}(\beta\hat{H}_{0}).$
(27)

Notice that $\mathcal{H}(t)$ in the previous subsection is for a generic
Hamiltonian, and $\hat{\mathcal{H}}(t)$ here is the above specific one.
According to Eq. (26), convergence of SQA to the equilibrium state is assured
in the long-time limit when the following condition is satisfied:

$\lim_{t\to\infty}\frac{\left\lVert\frac{d\mathcal{\hat{H}}(t)}{dt}\right\rVert}{\Delta(t)^{2}}\ll
1.$ (28)

It is possible to yield an upper bound on the norm in the above numerator
using Eq. (11). Equation (14) together with Eq. (II.2) implies that the
diagonal term can be written as a finite number of terms of interacting spins.
The off-diagonal term is just a transverse-field term with an appropriate
coefficient evaluated by Eq. (15). We thus find:

$\begin{split}&\left\lVert\frac{d\mathcal{\hat{H}}(t)}{dt}\right\rVert\leq\\\
&bMN\left(\Bigg{\lVert}\frac{d}{dt}(w_{\sigma\sigma^{\prime}}e^{-\frac{1}{2}\beta\left(H_{0}(\sigma^{\prime})-H_{0}(\sigma)\right)})\Bigg{\rVert}+\Bigg{\lVert}\frac{d}{dt}w_{\sigma\sigma^{\prime}}\Bigg{\rVert}\right)\\\
&+\frac{1}{2}\Bigg{\lVert}\frac{d^{2}}{dt^{2}}(\beta\hat{H}_{0})\Bigg{\rVert},\end{split}$
(29)

where $b$ is a constant independent of $M,N,\beta$, and $t$ but is determined
by the number of sites interacting with a given site. Utilizing the relation

$\Big{\lVert}\frac{d}{dt}(\beta
H_{j,k})\Big{\rVert}=\Big{\lVert}\gamma^{\prime}(t)\sigma_{j}^{(k)}\left(\sigma_{j}^{(k+1)}+\sigma_{j}^{(k-1)}\right)\Big{\rVert}\leq
2\lvert\gamma^{\prime}(t)\rvert,$ (30)

we have the following bound on the first term on the right-hand side of the
inequality (LABEL:ineq_tilde_H):

$\displaystyle\Big{\lVert}\frac{d}{dt}(w_{\sigma\sigma^{\prime}}e^{-\frac{1}{2}\beta\left(H_{0}(\sigma^{\prime})-H_{0}(\sigma)\right)})\Big{\rVert}$
$\displaystyle=\Bigg{\lVert}\frac{d}{dt}\left(\frac{e^{\beta
H_{j,k}}}{e^{\beta H_{j,k}}+e^{-\beta H_{j,k}}}\right)\Bigg{\rVert}$
$\displaystyle=\frac{1}{2}\Bigg{\lVert}\frac{d}{dt}(\beta H_{j,k})\cdot{\rm
sech}^{2}(\beta H_{j,k})\Bigg{\rVert}\leq\lvert\gamma^{\prime}(t)\rvert.$ (31)

An analogous computation shows that

$\displaystyle\Bigg{\lVert}\frac{d}{dt}w_{\sigma\sigma^{\prime}}\Bigg{\rVert}=\Bigg{\lVert}\frac{d}{dt}\frac{1}{e^{\beta
H_{j,k}}+e^{-\beta H_{j,k}}}\Bigg{\rVert}$ (32)
$\displaystyle=\frac{1}{2}\Bigg{\lVert}\frac{d}{dt}(\beta H_{j,k})\cdot{\rm
tanh}(\beta H_{j,k}){\rm sech}(\beta H_{j,k})\Bigg{\rVert}$
$\displaystyle\leq\frac{1}{2}\lvert\gamma^{\prime}(t)\rvert.$

We also have

$\Bigg{\lVert}\frac{d^{2}}{dt^{2}}(\beta\hat{H}_{0})\Bigg{\rVert}\leq\sum_{k=1}^{M}\sum_{j=1}^{N}\Bigg{\lVert}\gamma^{\prime\prime}(t)\sigma_{j}^{(k)}\sigma_{j}^{(k+1)}\Bigg{\rVert}\leq
MN\lvert\gamma^{\prime\prime}(t)\rvert.$ (33)

These computations applied to Eq. (LABEL:ineq_tilde_H) yield the following
bound:

$\left\lVert\frac{d\mathcal{\hat{H}}(t)}{dt}\right\rVert\leq
MN\left(\frac{3b}{2}\,\lvert\gamma^{\prime}(t)\rvert+\frac{1}{2}\,\lvert\gamma^{\prime\prime}(t)\rvert\right).$
(34)

Finding a lower bound of the energy gap $\Delta(t)$ between the first excited
state and the ground state is a nontrivial step. The coefficient of the
transverse field in the quantum Hamiltonian (11) is
$w_{\sigma\sigma^{\prime}}$. We start from the following inequality for the
coefficient $w_{\sigma\sigma^{\prime}}$:

$w_{\sigma\sigma^{\prime}}=\frac{1}{e^{\beta H_{j,k}}+e^{-\beta
H_{j,k}}}\geq\frac{1}{2\,e^{\lvert\beta H_{j,k}\rvert}}.$ (35)

$\lvert\beta H_{j,k}\rvert$ has the following upper bound owing to the
definition of $H_{j,k}$ in Eq. (II.2):

$\lvert\beta
H_{j,k}\rvert\leq\frac{\beta}{M}\bigg{\lvert}\sum_{j^{\prime}\,({\rm
n.n.}\,j)}J_{jj^{\prime}}\sigma_{j}^{(k)}\sigma_{j^{\prime}}^{(k)}\bigg{\rvert}+2\gamma(t).$
(36)

We adopt the notation

$\displaystyle p(M):={\rm
max}_{j,k}\,\frac{1}{M}\bigg{\lvert}\sum_{j^{\prime}\,({\rm
n.n.}\,j)}J_{jj^{\prime}}\sigma_{j}^{(k)}\sigma_{j^{\prime}}^{(k)}\bigg{\rvert},$
(37)

then $\lvert\beta H_{j,k}\rvert$ has an upper bound

$\lvert\beta H_{j,k}\rvert\leq\beta p(M)+2\gamma(t).$ (38)

From these relations, one learns that the coefficient
$w_{\sigma\sigma^{\prime}}$ has a lower bound as

$w_{\sigma\sigma^{\prime}}\geq\frac{1}{2\,e^{\beta p(M)+2\gamma(t)}}.$ (39)

For a generic transverse-field Ising model, a lower bound of the energy gap
$\Delta(t)$ between the ground state and the first excited stated was deduced
in Refs. [36, 37, 5]. Applying the argument given in those references to the
model under discussion, we obtain the following relation:

$\Delta(t)\geq A(N)\,(w_{\sigma\sigma^{\prime}})^{N},$ (40)

where the $N$-dependence of $A(N)$ is discussed below. Making use of the lower
bound for the coefficient $w_{\sigma\sigma^{\prime}}$ in Eq. (39), we deduce
the lower bound for $\Delta(t)$

$\Delta(t)\geq\frac{A(N)}{2^{N}}e^{-N(\beta p(M)+2\gamma(t))}.$ (41)

The coefficient $A(N)$ does not depend on time $t$ but depends on $N$ for
$N\gg 1$ as:

$A(N)=a\sqrt{N}e^{-cN},$ (42)

where $a$ and $c$ are positive constants independent of $N$ in the asymptotic
limit of large $N$. Thus, we obtain the lower bound of the energy gap
$\Delta(t)$ as follows:

$\Delta(t)\geq\frac{a\sqrt{N}}{2^{N}}e^{-N(\beta p(M)+2\gamma(t)+c)}.$ (43)

As a result of this equation and Eq. (34), we find the following bound:

$\begin{split}&\lim_{t\to\infty}\frac{\left\lVert\frac{d\mathcal{\hat{H}}(t)}{dt}\right\rVert}{\Delta(t)^{2}}\leq\\\
&\lim_{t\to\infty}\frac{2^{2N}M\left(3b\,\lvert\gamma^{\prime}(t)\rvert+\lvert\gamma^{\prime\prime}(t)\rvert\right)}{2a^{2}}\,e^{2N(\beta
p(M)+2\gamma(t)+c)}.\end{split}$ (44)

Dropping constants of order one, we learn from this result that the condition

$\begin{split}&\lim_{t\to\infty}\big{(}3b\,\lvert\gamma^{\prime}(t)\rvert+\lvert\gamma^{\prime\prime}(t)\rvert\big{)}e^{4N\gamma(t)}\\\
&\hskip 28.45274pt\times M\,2^{2N}e^{2N\beta p(M)+2Nc}\ll 1\end{split}$ (45)

suffices to ensure the convergence of SQA for fixed values $N,M$, and $\beta$.
Notice that the time-dependent part has been collected in the first line of
the above equation.

##  IV The result

We study in this section how the condition of Eq. (45) leads to an explicit
form of the coefficient $\gamma(t)$.

###  IV.1 Convergence condition for closed systems

Here, we deduce a condition that ensures convergence of SQA from the bound
(45).

It is natural to assume that $\Gamma(t)$ is a monotonically decreasing
function from a large value at $t=0$ toward zero in the long-time limit. Thus
$\gamma(t)$ is monotonically increasing according to the definition of Eq.
(9). Suppose that the first term in the first line on the left-hand side of
Eq. (45) is fixed to a small constant $c_{1}$. Solving the differential
equation

$\lvert\gamma^{\prime}(t)\rvert e^{4N\gamma(t)}=c_{1},$ (46)

we obtain the solution in terms of $\Gamma(t)$ as follows:

$\Gamma(t)=\frac{M}{\beta}{\rm
tanh}^{-1}\left(\frac{1}{(4N)^{1/2N}(c_{1}t+c_{2})^{1/2N}}\right),$ (47)

where $c_{2}$ is an integral constant. With this form of $\Gamma(t)$, one
finds that $\lvert\gamma^{\prime\prime}(t)\rvert
e^{4N\gamma(t)}=c_{1}^{2}(c_{1}t+c_{2})^{-1}$, which tends to 0 as
$t\to\infty$; therefore the solution (47) satisfies the aymptotic adiabatic
condition for the imaginary-time Schrödinger equation, given that $c_{1}$ is
chosen small enough as required in Eq. (45).

This result inspires us to analyze a more general function of the following
form for the coefficient of the transverse field $\Gamma(t)$:

$\Gamma(t)=\frac{M}{\beta}{\rm
tanh}^{-1}\left(\frac{1}{(c_{1}t+c_{2})^{g(t)}}\right).$ (48)

Here, $g(t)$ denotes a twice-differentiable, strictly positive function,
$g(t)>0$, and $c_{1}$ and $c_{2}$ denote constants with $c_{1}>0$ as we
mentioned previously. For $\Gamma(t)$ of the form (48) to ensure convergence,
conditions are imposed on the functions $g(t)$, $g^{\prime}(t)$, and
$g^{\prime\prime}(t)$. We state this main result as the following proposition:

######  Proposition 1.

Simulated quantum annealing (SQA) for closed systems converges to thermal
equilibrium of the final Ising Hamiltonian in the long-time limit when the
function $g(t)$ in $\Gamma(t)$ of Eq. (48) satisfies the following conditions
for sufficiently large $t$,

$\displaystyle 0<g(t)\leq\frac{1}{2N},$ (49) $\displaystyle\lvert
g^{\prime}(t)\rvert\leq\frac{c^{\prime}}{(c_{1}t+c_{2})\log(c_{1}t+c_{2})},$
(50) $\displaystyle\lvert
g^{\prime\prime}(t)\rvert\leq\frac{c^{\prime\prime}}{(c_{1}t+c_{2})\log(c_{1}t+c_{2})},$
(51)

where $c^{\prime}$ and $c^{\prime\prime}$ denote positive constants, provided
that the constants $c_{1}$, $c^{\prime}$, and $c^{\prime\prime}$ are chosen
small enough satisfying

$\displaystyle\left(\frac{3b\,c_{1}}{4N}+\frac{3b\,c^{\prime}}{2}+\frac{c^{\prime\prime}}{2}\right)M\,2^{2N}e^{2N\beta
p(M)+2Nc}\ll 1.$ (52)

for fixed, possibly large, values of $M,N$, and $\beta$.

###### Proof.

First, we show that the conditions (49) and (50) are necessary for the QA
convergence. When $\Gamma(t)$ takes the form (48), $\gamma(t)$ is given as

$\gamma(t)=\frac{g(t)}{2}\log\,(c_{1}t+c_{2}).$ (53)

Then, $\gamma^{\prime}(t)e^{4N\gamma(t)}$ has the following expression:

$\begin{split}\gamma^{\prime}(t)e^{4N\gamma(t)}&=\frac{g(t)}{2}c_{1}\,(c_{1}t+c_{2})^{2Ng(t)-1}\\\
&+\frac{g^{\prime}(t)}{2}(c_{1}t+c_{2})^{2Ng(t)}\log\,(c_{1}t+c_{2}).\end{split}$
(54)

The first term on the right-hand side of Eq. (54) needs to be bounded from
above by a finite constant as $t\to\infty$, which requires $2Ng(t)-1\leq 0$.
This yields the first stated condition (49). For a similar reason, the second
term on the right-hand side of Eq. (54) needs to be bounded from above by a
finite constant as $t\to\infty$, which yields the second condition (50). When
those conditions of Eqs. (49) and (50) are satisfied,
$\lvert\gamma^{\prime}(t)\rvert e^{4N\gamma(t)}$ has the following bound:

$\displaystyle\lvert\gamma^{\prime}(t)\rvert
e^{4N\gamma(t)}\leq\frac{c_{1}}{4N}+\frac{c^{\prime}}{2}.$ (55)

Thus, we find that the term $\lvert\gamma^{\prime}(t)\rvert e^{4N\gamma(t)}$
can be made arbitrarily small when $c_{1}$ and $c^{\prime}$ are chosen
sufficiently small under the conditions (49) and (50).

Next we explain that the condition (51) is also necessary to keep the term
$\lvert\gamma^{\prime\prime}(t)\rvert e^{4N\gamma(t)}$ arbitrarily small as
$t\to\infty$. With Eq. (53) for $\gamma(t)$, we obtain the following
expression for $\gamma^{\prime\prime}(t)e^{4N\gamma(t)}$:

$\begin{split}\gamma^{\prime\prime}(t)e^{4N\gamma(t)}&=c_{1}g^{\prime}(t)\,(c_{1}t+c_{2})^{2Ng(t)-1}\\\
&-c_{1}^{2}\frac{g(t)}{2}(c_{1}t+c_{2})^{2Ng(t)-2}\\\
&+\frac{g^{\prime\prime}(t)}{2}(c_{1}t+c_{2})^{2Ng(t)}\log\,(c_{1}t+c_{2}).\end{split}$
(56)

For the third term on the right-hand side of Eq. (56) to be bounded from above
by a finite constant, we need the condition (51).

One can confirm that the term $\lvert\gamma^{\prime\prime}(t)\rvert
e^{4N\gamma(t)}$ can be made arbitrarily small as $t\to\infty$ under the
conditions (49), (50), and (51), when $c^{\prime\prime}$ is chosen
sufficiently small. In fact, one has the following bound under the stated
conditions:

$\begin{split}&\lvert\gamma^{\prime\prime}(t)\rvert e^{4N\gamma(t)}\leq
c_{1}\lvert g^{\prime}(t)\rvert\,(c_{1}t+c_{2})^{2Ng(t)-1}\\\
&+c_{1}^{2}\frac{g(t)}{2}(c_{1}t+c_{2})^{2Ng(t)-2}\\\ &+\frac{\lvert
g^{\prime\prime}(t)\rvert}{2}(c_{1}t+c_{2})^{2Ng(t)}\log\,(c_{1}t+c_{2})\\\
&\leq\frac{c_{1}c^{\prime}}{(c_{1}t+c_{2})\log(c_{1}t+c_{2})}+\frac{c_{1}^{2}}{4N}(c_{1}t+c_{2})^{-1}+\frac{c^{\prime\prime}}{2}.\end{split}$
(57)

In the last line of this equation, the first two terms tend to 0 as
$t\to\infty$; the last term becomes arbitrarily small when $c^{\prime\prime}$
is chosen small enough by following Eq. (52). This concludes the proof of the
proposition. ∎

Remark 1.
Notice that $g(t)$ should increase as $t\to\infty$ if we demand $\Gamma(t)$ to
decrease faster than a polynomial of $t$. Therefore, we learn that the
coefficient $\Gamma(t)$ of the form (48) cannot decrease faster than a
polynomial of $t$. This result can be compared with a similar result deduced
in Ref. [38] for the real-time Schrödinger dynamics.

Remark 2.
The expression of Eq. (47) for $\Gamma(t)$ turns out to be best possible
according to Eq. (49).

Remark 3.
By choosing $\beta$ and $M$ sufficiently large, the system would become
sufficiently close to the ground state of the classical Ising model of Eq. (6)
in the long-time limit.

###  IV.2 Convergence condition for open systems

The standard model of environmental effects for open systems is the following
Hamiltonian with an additional term involving bosonic degrees of freedom [39]:

$\displaystyle H(t)$ $\displaystyle=H_{\rm Ising}+H_{\rm TF}(t)$
$\displaystyle+\sum_{j,l}\Big{(}c_{l}(a_{j,l}^{\dagger}+a_{j,l})\sigma_{j}^{z}+\omega_{j,l}a_{j,l}^{\dagger}a_{j,l}\Big{)},$
(58)

where $c_{l}$ is the coupling strength of the $l$th oscillator to the spin
system and $\omega_{j,l}$ is its frequency 333The effect represented by the
bosonic term in (IV.2) is different from the effect of temperature in SQA
introduced by $\beta$ as mentioned in Ref. [24]. We assume that the Ohmic
spectral function, $J(\omega)$, with coupling strength $\alpha$ and a cut-off
frequency $\omega_{c}$ is given as

$\displaystyle
J(\omega)=4\pi\sum_{l}c_{l}^{2}\delta(\omega-\omega_{j,l})=\begin{cases}2\pi\alpha\omega&(\omega<\omega_{c})\\\
0&(\omega\geq\omega_{c})\end{cases}.$ (59)

Then, tracing out the bosonic degrees of freedom in the Suzuki-Trotter
formulation, we obtain the following expression representing environmental
effects to be added to the original Trotterized Ising Hamiltonian $H_{0}$
[39]:

$\displaystyle-\frac{\alpha}{2}\left(\frac{\pi}{M}\right)^{2}\sum_{j=1}^{N}\sum_{k>k^{\prime}}\left({\rm
sin}\frac{\pi\lvert
k-k^{\prime}\rvert}{M}\right)^{-2}\sigma_{j}^{(k)}\sigma_{j}^{(k^{\prime})}.$
(60)

Since this term is independent of time $t$, the theory developed for closed
systems remains almost unchanged. Including the term Eq. (60) modifies
$H_{j,k}$ in Eq. (II.2) and $p(M)$ in Eq. (37) as:

$\displaystyle-\beta H_{j,k}=$
$\displaystyle\frac{\beta}{M}\sum_{j^{\prime}\,({\rm
n.n.}\,j)}J_{jj^{\prime}}\sigma_{j}^{(k)}\sigma_{j^{\prime}}^{(k)}+\gamma(t)\sigma_{j}^{(k)}\left(\sigma_{j}^{(k+1)}+\sigma_{j}^{(k-1)}\right)$
$\displaystyle+\frac{\alpha}{2}\left(\frac{\pi}{M}\right)^{2}\sum_{k^{\prime}(\neq
k)}\left({\rm sin}\frac{\pi\lvert
k-k^{\prime}\rvert}{M}\right)^{-2}\sigma_{j}^{(k)}\sigma_{j}^{(k^{\prime})}$
(61)

and

$\displaystyle p(M)={\rm
max}_{j,k}\,\bigg{\lvert}\frac{1}{M}\sum_{j^{\prime}\,({\rm
n.n.}\,j)}J_{jj^{\prime}}\sigma_{j}^{(k)}\sigma_{j^{\prime}}^{(k)}$
$\displaystyle+\frac{\alpha}{2\beta}\left(\frac{\pi}{M}\right)^{2}\sum_{k^{\prime}(\neq
k)}\left({\rm sin}\frac{\pi\lvert
k-k^{\prime}\rvert}{M}\right)^{-2}\sigma_{j}^{(k)}\sigma_{j}^{(k^{\prime})}\bigg{\rvert},$
(62)

respectively. Proposition 1 applies with those minor amendments. We summarize
this observation as a Corollary.

######  Corollary 1.

Proposition 1 applies to open systems with the parameter $p(M)$ in Eq. (IV.2).

###  IV.3 Bounded coefficients

The Schrödinger dynamics of the following form is often considered

$i\frac{d}{dt}\ket{\psi(t)}=\Big{(}s(t)\,H_{\rm
Ising}-\left(1-s(t)\right)\sum_{j=1}^{N}\sigma^{x}_{j}\Big{)}\ket{\psi(t)},$
(63)

where $s(t)$ is a monotonically increasing function with $0\leq s(t)\leq 1$,
in place of the Hamiltonian (5). We show that slight amendments of discussions
of previous sections make it possible to apply the results, Proposition 1 and
Corollary 1, to this case. Equations are written for real-time Schrödinger
dynamics, which applies to the imaginary-time version as well.

One can rewrite Eq. (63) as

$\frac{i}{s(t)}\frac{d}{dt}\ket{\psi(t)}=\Big{(}H_{\rm
Ising}-\frac{1-s(t)}{s(t)}\sum_{j=1}^{N}\sigma_{j}^{x}\Big{)}\ket{\psi(t)}.$
(64)

We define a function $\tilde{t}$, that is a monotonic function of time $t$, as

$\tilde{t}\equiv\int_{0}^{t}dt\,s(t).$ (65)

Using the introduced function $\tilde{t}$, one can rewrite Eq. (64) as
follows:

$i\frac{d}{d\tilde{t}}\ket{\psi(t)}=\Big{(}H_{\rm
Ising}-\frac{1-s(t)}{s(t)}\sum_{j=1}^{N}\sigma^{x}_{j}\Big{)}\ket{\psi(t)}.$
(66)

Now, we introduce a function $\Gamma(\tilde{t})$ defined as
$\Gamma(\tilde{t})\equiv\left(1-s(t)\right)/s(t)$ to rewrite Eq. (66) as

$i\frac{d}{d\tilde{t}}\ket{\psi(t)}=\Big{(}H_{\rm
Ising}-\Gamma(\tilde{t})\sum_{j=1}^{N}\sigma^{x}_{j}\Big{)}\ket{\psi(t)}.$
(67)

The arguments given in the previous sections applied to Eq. (67) reveal that,
in the limit $\tilde{t}\to\infty$, $\Gamma(\tilde{t})$ proportional to
$c_{1}\tilde{t}^{-\tilde{g}(\tilde{t})}$,

$\Gamma(\tilde{t})=\frac{1-s(t)}{s(t)}\propto(c_{1}\tilde{t})^{-\tilde{g}(\tilde{t})},$
(68)

where $\tilde{g}(\tilde{t})$ is subject to the conditions (49), (50), and
(51), ensures convergence. We used the fact that

$\displaystyle\Gamma(t)=\frac{M}{\beta}{\rm
tanh}^{-1}\left(\frac{1}{(c_{1}t+c_{2})^{g(t)}}\right)\sim\frac{M}{\beta}(c_{1}t+c_{2})^{-g(t)}$
(69)

when $t$ is sufficiently large, and $c_{2}$ is suppressed in the large $t$
limit.

An expression for $s(t)$ is obtained from Eq. (68) as

$s(t)=\frac{1}{1+c_{1}\tilde{t}^{-\tilde{g}(\tilde{t})}}\approx
1-(c_{1}\tilde{t})^{-\tilde{g}(\tilde{t})}~{}~{}~{}(\tilde{t}\gg 1).$ (70)

For large $t$, in some situations, $\tilde{t}$ can be approximated by $t$. For
example, one can choose $s(t)={\rm tanh}\,t$, then $\tilde{t}=\log({\rm
cosh}\,t)\approx t$ for sufficiently large $t$ ($t\gg 1$).

##  V Discussion

We have derived a condition that simulated quantum annealing (SQA) converges
to thermal equilibrium for generic closed and open systems using the
approximate, but asymptotically correct, adiabatic condition for the
imaginary-time Schrödinger equation, to which the classical master equation
governing SQA has been reduced. The result is in qualitative agreement with
the rigorous version of convergence condition for closed systems derived from
the theory of inhomogeneous Markov process [25, 5], where the condition of
convergence has been proved to be:

$\displaystyle\Gamma(t)\geq\frac{M}{\beta}\tanh^{-1}\frac{1}{(t+2)^{2/RL_{1}}}.$
(71)

Here $R$ is a constant of order $N$ and $L_{1}$ is an $N$-independent
constant. Notice that the unit of time is different between those approaches:
discrete steps for the above result in Refs. [25, 5] and continuous time
evolution in the present paper, resulting in the difference of coefficients of
$t$, unity in Eq. (71) and $c_{1}$ in Eq. (48). It is anyway encouraging that
essentially the same conclusion has been reached by two completely different
methods, partly because the present, physics-oriented, approach may be more
flexible in applications to other problems than using the mathematically-
solid, yet hard to generalize, theory of inhomogeneous Markov process.

It is worth attention that there is no essential difference in the convergence
conditions for closed and open systems. The origin of this fact is that the
additional term for environmental effects in Eq. (60) is time independent. We
thus conclude that phase-flip errors caused by the environment as represented
by Eq. (IV.2) does not essentially modify the generic bound on the rate of
change of the time-dependent coefficient.

Another interesting fact is that the time dependence of the coefficient
$\Gamma(t)$ of Eq. (47) is quite similar to the corresponding convergence
condition for real-time QA for closed systems as derived earlier under
rigorous [38] and asymptotic [36, 5, 37] adiabatic conditions. For example,
the asymptotic version of convergence condition under the real-time
Schrd̈inger dynamics is

$\displaystyle\Gamma(t)=a(\delta t+c)^{-1/(2N-1)},$ (72)

where $a,\delta$, and $c$ are time-independent constants. On the side of the
imaginary-time Schrödinger dynamics, when time $t$ is large, Eq. (47) becomes

$\Gamma(t)\sim\frac{M}{\beta(4N)^{1/2N}}(c_{1}t+c_{2})^{-1/2N}.$ (73)

The forms of the two equations, (72) and (73), are quite analogous. It is
difficult to explain intuitively why those two completely different dynamical
processes follow almost identical convergence conditions. This is particularly
so, given that the real-time Schrödinger dynamics operates at zero temperature
whereas the present results, Proposition 1 and Corollary 1, apply at any
temperature, high or low, although one usually chooses very low temperatures
to study the ground-state behavior of the system by SQA. We cannot exclude the
possibility of an accidental coincidence, but also there may lie some deep
physics behind this fact. We leave it to future work to try to answer this
intriguing question.

###### Acknowledgements.

This work is based on a project JPNP16007 commissioned by the New Energy and
Industrial Technology Development Organization (NEDO).

##  Appendix A Matrix element and operator norm

We prove the inequality (25). Given an operator $\mathcal{A}$, the definition
of the operator norm is

$\lVert\mathcal{A}\rVert:={\rm sup}_{\lVert
v\rVert=1}\lVert\mathcal{A}v\rVert,$ (74)

where one should note that $\lVert\cdots\rVert$ on the left-hand side is the
operator norm whereas the one on the right hand side is the norm of a vector.
Therefore, for any vectors $v$ and $w$ of norm 1, $\lVert v\rVert=\lVert
w\rVert=1$,

$\lvert\bra{w}\mathcal{A}\ket{v}\rvert\leq\lVert
w\rVert\cdot\lVert\mathcal{A}v\rVert=\lVert\mathcal{A}v\rVert\leq\lVert\mathcal{A}\rVert.$
(75)

## References

  * Kadowaki and Nishimori [1998] T. Kadowaki and H. Nishimori, Quantum annealing in the transverse Ising model, Phys. Rev. E 58, 5355 (1998).
  * Farhi  _et al._ [2001] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem., Science 292, 472 (2001).
  * Santoro  _et al._ [2002] G. E. Santoro, R. Martoňák, E. Tosatti, and R. Car, Theory of quantum annealing of an Ising spin glass, Science 295, 2427 (2002).
  * Das and Chakrabarti [2008] A. Das and B. K. Chakrabarti, Colloquium: Quantum annealing and analog quantum computation, Rev. Mod. Phys. 80, 1061 (2008).
  * Morita and Nishimori [2008] S. Morita and H. Nishimori, Mathematical foundation of quantum annealing, J, Math. Phys. 49, 125210 (2008).
  * Albash and Lidar [2018] T. Albash and D. A. Lidar, Adiabatic quantum computation, Rev. Mod. Phys. 90, 015002 (2018).
  * Hauke  _et al._ [2019] P. Hauke, H. G. Katzgraber, W. Lechner, H. Nishimori, and W. D. Oliver, Perspectives of quantum annealing: Methods and implementations, Rep. Prog. Phys. 83, 054401 (2019).
  * Crosson and Lidar [2021] E. J. Crosson and D. A. Lidar, Prospects for quantum enhancement with diabatic quantum annealing, Nature Rev. Phys. 3, 466 (2021).
  * Harris  _et al._ [2018] R. Harris, Y. Sato, A. J. Berkley, M. Reis, F. Altomare, M. H. Amin, K. Boothby, P. Bunyk, C. Deng, C. Enderud, S. Huang, E. Hoskinson, M. W. Johnson, E. Ladizinsky, N. Ladizinsky, T. Lanting, R. Li, T. Medina, R. Molavi, R. Neufeld, T. Oh, I. Pavlov, I. Perminov, G. Poulin-Lamarre, C. Rich, A. Smirnov, L. Swenson, N. Tsai, M. Volkmann, J. Whittaker, and J. Yao, Phase transitions in a programmable quantum spin glass simulator, Science 361, 162 (2018).
  * King  _et al._ [2018] A. D. King, J. Carrasquilla, J. Raymond, I. Ozfidan, E. Andriyash, A. J. Berkley, M. Reis, T. Lanting, R. Harris, F. Altomare, K. Boothby, P. I. Bunyk, C. Enderud, A. Fréchette, E. M. Hoskinson, N. Ladizinsky, T. Oh, G. Poulin-Lamarre, C. Rich, Y. Sato, A. Y. Smirnov, L. J. Swenson, M. H. Volkmann, J. Whittaker, J. Yao, E. Ladizinsky, W. Mark, J. P. Hilton, and M. H. Amin, Observation of topological phenomena in a programmable lattice of 1,800 qubits, Nature 560, 456 (2018).
  * Nishimura  _et al._ [2020] K. Nishimura, H. Nishimori, and H. G. Katzgraber, Griffiths-McCoy singularity on the diluted Chimera graph: Monte Carlo simulations and experiments on quantum hardware, Phys. Rev. A 102, 042403 (2020).
  * Gardas  _et al._ [2018] B. Gardas, J. Dziarmaga, W. H. Zurek, and M. Zwolak, Defects in Quantum Computers, Sci. Rep. 8, 4539 (2018), 1707.09463 .
  * Bando  _et al._ [2020] Y. Bando, Y. Susa, H. Oshiyama, N. Shibata, M. Ohzeki, F. J. Gómez-Ruiz, D. A. Lidar, S. Suzuki, A. del Campo, and H. Nishimori, Probing the universality of topological defect formation in a quantum annealer: Kibble-Zurek mechanism and beyond, Phys. Rev. Res. 2, 033369 (2020).
  * Weinberg  _et al._ [2020] P. Weinberg, M. Tylutki, J. M. Rönkkö, J. Westerholm, J. A. Åström, P. Manninen, P. Törmä, and A. W. Sandvik, Scaling and Diabatic Effects in Quantum Annealing with a D-Wave Device, Phys. Rev. Lett. 124, 090502 (2020).
  * King  _et al._ [2022a] A. D. King, S. Suzuki, J. Raymond, A. Zucca, T. Lanting, F. Altomare, A. J. Berkley, S. Ejtemaee, E. Hoskinson, S. Huang, E. Ladizinsky, A. J. R. MacDonald, G. Marsden, T. Oh, G. Poulin-Lamarre, M. Reis, C. Rich, Y. Sato, J. D. Whittaker, J. Yao, R. Harris, D. A. Lidar, H. Nishimori, and M. H. Amin, Coherent quantum annealing in a programmable 2,000 qubit Ising chain, Nature Phys. (2022a).
  * King  _et al._ [2022b] A. D. King, J. Raymond, T. Lanting, R. Harris, A. Zucca, F. Altomare, A. J. Berkley, K. Boothby, S. Ejtemaee, C. Enderud, E. Hoskinson, S. Huang, E. Ladizinsky, A. J. R. MacDonald, G. Marsden, R. Molavi, T. Oh, G. Poulin-Lamarre, M. Reis, C. Rich, Y. Sato, N. Tsai, M. Volkmann, J. D. Whittaker, J. Yao, A. W. Sandvik, and M. H. Amin, Quantum critical dynamics in a 5000-qubit programmable spin glass, arXiv:2207.13800 (2022b).
  * Abel  _et al._ [2021] S. Abel, A. Blance, and M. Spannowsky, Quantum Optimisation of Complex Systems with a Quantum Annealer, arXiv:2105.13945 (2021).
  * Abel and Spannowsky [2021a] S. Abel and M. Spannowsky, Quantum-Field-Theoretic Simulation Platform for Observing the Fate of the False Vacuum, PRX Quantum 2, 010349 (2021a).
  * Abel and Spannowsky [2021b] N. Abel, S.and Chancellor and M. Spannowsky, Quantum computing for quantum tunneling, Phys. Rev. D 103, 16008 (2021b).
  * Koh and Nishimori [2022] Y. W. Koh and H. Nishimori, Quantum and classical annealing in a continuous space with multiple local minima, Phys. Rev. A 105, 062435 (2022).
  * Kadowaki [1999] T. Kadowaki,  _Study of Optimization Problems by Quantum Annealing_ , Ph.D. thesis, Tokyo Institute of Technology (1999).
  * Heim  _et al._ [2015] B. Heim, T. F. Ronnow, S. V. Isakov, and M. Troyer, Quantum versus classical annealing of Ising spin glasses, Science 348, 215 (2015).
  * Suzuki [1971] M. Suzuki, Relationship among Exactly Soluble Models of Critical Phenomena. I: 2D Ising Model, Dimer Problem and the Generalized XY-Model, Prog. Theor. Phys. 46, 1337 (1971).
  * Note [1] As will be discussed later, the term “environment” here does not refer to classical thermal effects used in equilibrium simulations of SQA but means experimentally-relevant quantum-mechanical dissipation coming from interactions with a large number of degrees of freedom outside of qubit systems [41].
  * Morita and Nishimori [2006] S. Morita and H. Nishimori, Convergence theorems for quantum annealing, J. Phys. A 39, 13903 (2006).
  * Albash  _et al._ [2012] T. Albash, S. Boixo, D. A. Lidar, and P. Zanardi, Quantum adiabatic markovian master equations, New Journal of Physics 14, 123016 (2012).
  * Venuti  _et al._ [2017] L. C. Venuti, T. Albash, M. Marvian, D. Lidar, and P. Zanardi, Relaxation versus adiabatic quantum steady-state preparation, Phys. Rev. A 95, 042302 (2017).
  * Crosson and Slezak [2020] E. Crosson and S. Slezak, Classical simulation of high temperature quantum ising models, arXiv preprint arXiv:2002.02232 (2020).
  * Nishimori  _et al._ [2015] H. Nishimori, J. Tsuda, and S. Knysh, Comparative study of the performance of quantum annealing and simulated annealing, Phys. Rev. E 91, 012104 (2015).
  * Henley [2004] C. L. Henley, From classical to quantum dynamics at Rokhsar-Kivelson points, J. Phys. Cond. Matt. 16, S891 (2004).
  * Castelnovo  _et al._ [2005] C. Castelnovo, C. Chamon, C. Mudry, and P. Pujol, From quantum mechanics to classical statistical physics: Generalized Rokhsar–Kivelson Hamiltonians and the “Stochastic Matrix Form” decomposition, Ann. Phys. 318, 316 (2005).
  * Nishimori and Ortiz [2011] H. Nishimori and G. Ortiz,  _Elements of Phase Transitions and Critical Phenomena_ (Oxford Univ. Press, 2011).
  * Bando and Nishimori [2021] Y. Bando and H. Nishimori, Simulated quantum annealing as a simulator of nonequilibrium quantum dynamics, Phys, Rev. A 104, 022607 (2021).
  * S. U. Pillai and Cha [2005] T. S. S. U. Pillai and S. Cha, The Perron-Frobenius theorem: some of its application, IEEE Sig. Proc. 22, 62 (2005).
  * Note [2] Also in the long-time limit $t\to\infty$, the ground state is non-degenerate since, according to Eq. (17), the ground state of $\mathcal{H}(t)$ corresponds to the equilibrium Boltzmann distribution of the original classical system [29], which is naturally unique. This should not be confused with the $Z_{2}$ degeneracy of the ground state of the classical Ising model of Eq. (6).
  * Somma  _et al._ [2007] R. Somma, C. Batista, and G. Ortiz, Quantum Approach to Classical Statistical Mechanics, Phys. Rev. Lett. 99, 030603 (2007).
  * Morita and Nishimori [2007] S. Morita and H. Nishimori, Convergence of Quantum Annealing with Real-Time Schrödinger Dynamics, J. Phys. Soc. Jpn. 76, 064002 (2007).
  * Kimura and Nishimori [2022] Y. Kimura and H. Nishimori, Rigorous convergence condition for quantum annealing, J. Phys. A 55, 435302 (2022).
  * Werner  _et al._ [2005] P. Werner, K. Völker, M. Troyer, and S. Chakravarty, Phase Diagram and Critical Exponents of a Dissipative Ising Spin Chain in a Transverse Magnetic Field, Phys. Rev. Lett. 94, 047201 (2005).
  * Note [3] The effect represented by the bosonic term in (IV.2) is different from the effect of temperature in SQA introduced by $\beta$ as mentioned in Ref. [24].
  * Caldeira and Leggett [1983] A. O. Caldeira and A. J. Leggett, Quantum tunnelling in a dissipative system, Ann. Phys. 149, 374 (1983).