Residual Energies after Slow Quantum Annealing
Features of the residual energy after the quantum annealing are investigated. The quantum annealing method exploits quantum fluctuations to search the ground state of classical disordered Hamiltonian. If the quantum fluctuation is reduced sufficiently slowly and linearly by the time, the residual energy after the quantum annealing falls as the inverse square of the annealing time. We show this feature of the residual energy by numerical calculations for small-sized systems and derive it on the basis of the quantum adiabatic theorem.
letter.tex
%% ****** Start of file template.aps ****** %
%%
%%
%%   This file is part of the APS files in the REVTeX 4 distribution.
%%   Version 4.0 of REVTeX, August 2001
%%
%%
%%   Copyright (c) 2001 The American Physical Society.
%%
%%   See the REVTeX 4 README file for restrictions and more information.
%%
%
% This is a template for producing manuscripts for use with REVTEX 4.0
% Copy this file to another name and then work on that file.
% That way, you always have this original template file to use.
%
% Group addresses by affiliation; use superscriptaddress for long
% author lists, or if there are many overlapping affiliations.
% For Phys. Rev. appearance, change preprint to twocolumn.
% Choose pra, prb, prc, prd, pre, prl, prstab, or rmp for journal
%  Add 'draft' option to mark overfull boxes with black boxes
%  Add 'showpacs' option to make PACS codes appear
%  Add 'showkeys' option to make keywords appear
\documentclass[aps,prl,twocolumn,showpacs]{revtex4}
%\documentclass[aps,prl,preprint,groupedaddress]{revtex4}
%\documentclass[aps,prl,preprint,superscriptaddress]{revtex4}
%\documentclass[aps,prl,twocolumn,groupedaddress]{revtex4}

\usepackage{graphicx}

% You should use BibTeX and apsrev.bst for references
% Choosing a journal automatically selects the correct APS
% BibTeX style file (bst file), so only uncomment the line
% below if necessary.
%\bibliographystyle{apsrev}

\begin{document}

% Use the \preprint command to place your local institutional report
% number in the upper righthand corner of the title page in preprint mode.
% Multiple \preprint commands are allowed.
% Use the 'preprintnumbers' class option to override journal defaults
% to display numbers if necessary
%\preprint{}

%Title of paper
\title{Residual Energies after Slow Quantum Annealing}

% repeat the \author .. \affiliation  etc. as needed
% \email, \thanks, \homepage, \altaffiliation all apply to the current
% author. Explanatory text should go in the []'s, actual e-mail
% address or url should go in the {}'s for \email and \homepage.
% Please use the appropriate macro foreach each type of information

% \affiliation command applies to all authors since the last
% \affiliation command. The \affiliation command should follow the
% other information
% \affiliation can be followed by \email, \homepage, \thanks as well.
\author{Sei Suzuki$^{1,2}$}
\email[]{sei@mns.k.u-tokyo.ac.jp}
\author{Masato Okada$^{1,2}$}
%\homepage[]{Your web page}
%\thanks{}
%\altaffiliation{}
\affiliation{
$^1$Graduate School of Frontier Sciences, The University of Tokyo, 
Kashiwa 277-8561 \\
$^2$Brain Science Institute, RIKEN, Wako 351-0198
}

%Collaboration name if desired (requires use of superscriptaddress
%option in \documentclass). \noaffiliation is required (may also be
%used with the \author command).
%\collaboration can be followed by \email, \homepage, \thanks as well.
%\collaboration{}
%\noaffiliation

\date{\today}

\begin{abstract}
Features of the residual energy after the quantum annealing are 
investigated.
The quantum annealing method exploits quantum fluctuations
to search the ground state of classical disordered Hamiltonian.
If the quantum fluctuation
is reduced sufficiently slowly and linearly by the time,
the residual energy after the quantum 
annealing falls as the inverse square of the annealing time. 
We show this feature of
the residual energy by numerical calculations for small-sized
systems and derive it on the basis of the quantum adiabatic 
theorem.
\end{abstract}

% insert suggested PACS numbers in braces on next line
\pacs{02.60.Cb, 03.65.Xp, 03.67.Lx, 75.10.Nr}
% insert suggested keywords - APS authors don't need to do this
%\keywords{}

%\maketitle must follow title, authors, abstract, \pacs, and \keywords
\maketitle

% body of paper here - Use proper section commands
% References should be done using the \cite, \ref, and \label commands
%\section{Introduction}
Combinatorial optimization problems have presented a 
variety of challenges in vast area of sciences. 
Since the number of combination usually explodes exponentially 
with the number of elements,
they becomes unsolvable for large elements
by means of checking all of the combinations.
In particular, no algorithm suitable for conventional computers
has been discovered to solve the 
nondeterministic polynomial-time (NP) problem in a time of 
the polynomial order of elements.
The quantum annealing method has been proposed for such an
intractable problem\cite{bib:Kadowaki}.



The combinatorial optimization problem is often represented
in terms of a classical Hamiltonian, such as a random
Ising model. What we do for the problem is 
to find the ground state of the classical Hamiltonian.
In the quantum annealing method, a quantum Hamiltonian is
introduced for a classical problem.
Namely quantum fluctuations are exploited to search the solution.
The principle of the quantum annealing method 
provides us a novel algorithm for quantum computation
\cite{bib:Farhi,bib:Hogg}. In fact, fundamental experiments of quantum
computation have been carried out\cite{bib:Steffen}.
Another importance of this method lies in implementation
by conventional classical computers. 
The thermal (simulated) annealing is an well-known
method for classical computers\cite{bib:Geman}.
It has been shown experimentally that the quantum annealing
surpasses the thermal annealing\cite{bib:brookeS}.
Hence the algorithm of quantum annealing in classical computers
is expected to reduce the complexity of the problem.
However it has been in question 
whether the exponential scaling law of the complexity
regarding the problem size 
is replaced by the power law in the quantum algorithm.
It is a great issue whether this algorithm can transform
NP problems to polynomial-time solvable problems.

In this letter, we investigate the asymptotic behavior of the
residual energy for long annealing time. The residual energy
is defined by the energy difference between the 
solution by means of an algorithm and the true one.
%The computation of the residual energy enables us to estimate
%accuracy of the obtained solution. 
If the scaling law of the asymptotic behavior with respect to
the process time is unveiled, it becomes clear how efficiently 
the method leads us to the true solution.
For instance, the residual energy after the thermal 
annealing decreases with the annealing (process) time as
$\Delta E \sim 1/(\ln\tau)^{\zeta}$ with $1\le\zeta \le
2$\cite{bib:Huse,bib:Shinomoto}, 
and thus extraordinarily long time is needed to obtain a closely
approximate solution.
The logarithmic scaling law of the residual energy
reminds us of the exponential law of the complexity.
For the quantum annealing method, an earlier work has estimated 
that the residual energy falls as $\Delta E\sim 1/(\ln\tau)^{\zeta}$
with $\zeta\sim 6$\cite{bib:Santoro}.
However no one has confirmed numerically this scaling law of
the residual energy after the quantum annealing.

We examine the scaling law numerically in the present work.
The result shows that the residual energy obeys power law,
$\Delta E\sim 1/\tau^{\zeta}$ with $\zeta \sim 2$ in the
long $\tau$ limit, %which is 
in contrast to the earlier prediction.
This asymptotic behavior is derived from the adiabatic theorem of
the quantum mechanics.
%One can ask here whether the Landau-Zener theory gives rise to
%incorrect results. We mention that the Landau-Zener theory is
%validated when the annealing time is not long, where the adiabatic
%theorem is not applicable. We discuss the behavior of the
%residual energy in this regime in association with the
%earlier work.



%We organize the present letter as follows.
%First, we present results of numerical calculation
%and show evidences of the power law of the residual energy.
%After that we derive this asymptotic behavior analytically 
%on the basis of the adiabatic theorem in the quantum mechanics.
%At last we discuss the origin of the confliction 
%between our result and the earlier one.




%\section{Procedure and mechanism of quantum annealing}
Let us consider a time-dependent Hamiltonian
$\mathcal{H}(t)$
which consists of the classical Hamiltonian 
$\mathcal{H}_0$ and the tunneling Hamiltonian $\mathcal{H}_T$.
The classical Hamiltonian denotes the energy function
representing a combinatorial optimization problem,
while the tunneling Hamiltonian is responsible for 
quantum effects.
Detailed forms of these Hamiltonians are written later.
We assume the time dependence of the Hamiltonian as follows.
The tunneling term dominates the Hamiltonian at the initial time,
and it vanishes at the final time. 
The Hamiltonian changes
continuously in between the initial and final times.
There is no symmetry at any time which brings about degenerate
ground states of the Hamiltonian.
The quantum state vector stands for a solution of the combinatorial
optimization problem in the quantum annealing method.
The evolution of the state vector denoted by $|\Psi(t)\rangle$ 
with the time $t$
is determined by the Schr\"{o}dinger equation,
\begin{equation}
 i\frac{d}{dt} |\Psi(t)\rangle = \mathcal{H}(t) |\Psi(t)\rangle .
  \label{eq:Schrodinger}
\end{equation}
We assume that the initial state is adjusted to the ground state
of the initial Hamiltonian.
It follows that the approximate solution is obtained as the state vector
after an evolution with the time when the Hamiltonian coincides with the
classical Hamiltonian.
This is the process of the quantum annealing method.




The validity of the quantum annealing method originates in the
adiabatic evolution of quantum mechanical states.
The state evolving from the eigen state of the Hamiltonian
almost retains being the eigen state.
This dynamical process goes on when
the change in the Hamiltonian with the time is sufficiently slow
and the associated state is non-degenerate at any time.
Hence the state starting from the ground state of the 
initial Hamiltonian arrives at
an approximate ground state of the Hamiltonian at the final time.
In the quantum annealing method, the final Hamiltonian is
set to the classical Hamiltonian. Thus the state vector 
at the final time becomes an approximate ground state of the
classical Hamiltonian, namely the solution of the
combinatorial optimization problem.





%\section{Time-dependent Hamiltonian}
Although we have imposed assumptions on the time dependence of
the Hamiltonian, there are some degrees of freedom on that.
We settle it as follows.
First we denote an annealing time by $\tau$
and consider the time period $[0, \tau]$.
Taking into account the assumptions in the above,
it is favored that the Hamiltonian at the initial time is identical to
the tunneling Hamiltonian. This is because it is usually easy to
make the exact ground eigen state of the tunneling Hamiltonian 
as will be seen later.
Moreover it is natural to let the Hamiltonian 
depend on the time linearly, 
since the adiabatic theorem is proven for a
Hamiltonian linear in the time. There is no strict insurance that
the adiabatic theorem works correctly for the 
Hamiltonian with other time dependences.
Thus we employ the following form of the Hamiltonian,
\begin{equation}
 \mathcal{H}_{\tau}(t) = \frac{t}{\tau}\mathcal{H}_0 + 
  \left(1 - \frac{t}{\tau}\right) \mathcal{H}_T.
  \label{eq:Htotal}
\end{equation}
Since the derivative of this Hamiltonian by the time is proportional to
$1/\tau$, the change of Hamiltonian involved by the time advance
is infinitely slow in the infinite limit of $\tau$. 
Using this Hamiltonian, the adiabatic theorem ensures
that the final state converges to the ground
eigen state of $\mathcal{H}_0$ in infinite limit of $\tau$.

We note here that the Hamiltonian (\ref{eq:Htotal}) is artificial.
Although we are interested in the classical Hamiltonian $\mathcal{H}_0$,
the Hamiltonian does not include the contribution from $\mathcal{H}_0$
initially. We emphasize here that the important thing is not
how the intermediate state is but how the final state is after
the evolution. Hence it does not matter that the Hamiltonian
at the initial time differs entirely from $\mathcal{H}_0$.




%It is the classical Hamiltonian $H_0$ that we are interested in.
%The important thing is not how the intermediate state is
%but how the final state after the annealing is.
%Hence we demand no naturalness on the Hamiltonian in the way.



%\section{Numerics}
For the sake of implementation of 
the quantum annealing, we consider two simple models as pilot cases.
The first is a single-particle problem of the tight-binding model.
Let us consider a one-dimensional lattice. We assume that 
there is one energy eigen-state at each site and the states
in different sites are orthogonal each other.
The classical Hamiltonian is given by
\begin{equation}
 \mathcal{H}_0 = \sum_{i=1}^N V_i |i\rangle\langle i| ,
  \label{eq:TB1}
\end{equation}
where $|i\rangle$ denotes the single-particle state of the site $i$.
$N$ denotes the number of sites.
$V_i$ indicates the energy of the state at the site $i$. We assume
$V_i$s are randomly distributed between $0$ and $1$.
The tunneling Hamiltonian of the present system is brought by
hopping between nearest neighbor sites. It is written as
\begin{equation}
 \mathcal{H}_T = - \alpha \sum_{i=1}^{N-1} 
 \left(|i\rangle\langle i+1| + |i+1\rangle\langle i| \right) .
  \label{eq:TB2}
\end{equation}
A positive parameter $\alpha$ denotes the strength of tunneling.
The ground state of $\mathcal{H}_T$ as the initial state is
given by 
$|\Psi_0\rangle = \frac{1}{\sqrt{N}}\sum_{i=1}^N |i\rangle$.

\begin{figure}[tbp]
 \begin{center}
  \includegraphics[width=8cm,clip]{figure1.eps}
%  \vspace{5cm}
 \end{center}
 \caption{Results on the tight-binding model. 
 Calculations were performed for the system with twenty sites, $N=20$. 
 Figure (a) shows the potential energy of each site.
 Figure (b) shows the annealing time dependence of residual energies. 
 Results for several tunneling energies are plotted. 
 A straight line, $\Delta E\propto 1/\tau^2$, is shown for
 comparison.
 Note that both axes are logarithmic.
 For large $\tau$, the residual energy obeys the power law for
 the annealing time. The exponent is estimated to be approximately two.
}
 \label{fig:TB}
\end{figure}




The next model is the random Ising spin model. The classical
Hamiltonian is written as
\begin{equation}
 \mathcal{H}_0 = - \sum_{<i,j>} J_{ij} S_i^z S_j^z - h \sum_i S_i^z ,
  \label{eq:SG1}
\end{equation}
where $S_i^z$ is the $z$ component of the spin operator at the site $i$.
The coupling constant $J_{ij}$ takes the value $+1$ or $-1$ randomly.
The Zeemann term with $h=0.1$ is included so as to avoid that 
the ground state becomes doubly degenerated.
The tunneling Hamiltonian is introduced by the transverse field.
Supposing $\alpha$ to be the transverse field, the Zeemann energy
yields the tunneling Hamiltonian,
\begin{equation}
 \mathcal{H}_T = -\alpha \sum_{i} S_i^x ,
  \label{eq:SG2}
\end{equation}
where $S_i^x$ is the $x$ component of the spin operator at the site $i$.
All spins are fully polarized along the $x$ axis in the ground state
of $\mathcal{H}_T$. It follows from this that the initial state 
is written as
$|\Psi_0\rangle = \prod_i[\frac{1}{\sqrt{2}}
\left(|\uparrow\rangle_i + |\downarrow\rangle_i\right)]$, where
$|\uparrow\rangle_i$ and $|\downarrow\rangle_i$
are the eigen states of $S_i^z$ with the eigen values $\frac{1}{2}$
and $-\frac{1}{2}$ respectively.

\begin{figure}[tbp]
 \begin{center}
  \includegraphics[width=8cm,clip]{figure2.eps}
%  \vspace{5cm}
 \end{center}
 \caption{Annealing time dependence of residual energies 
 for the random Ising spin model. Two-dimensional lattice with nine
 spins are considered. 
 Results are shown for several values of the transverse field.
 A line representing $\Delta E\propto 1/\tau^2$ is drawn for
 comparison.
 It is clear that the residual energy is fitted well by 
 the line of $\Delta E\propto 1/\tau^2$.
 The inset depicts bonds of the interaction
 and values of the coupling constant.
 }
 \label{fig:SG}
\end{figure}

For each model we solved the Schr\"{o}dinger equation 
(\ref{eq:Schrodinger}) numerically 
using the Runge-Kutta algorithm of fourth order and
obtained the time dependence of the state vector.
The residual energy is defined by the energy difference
between the energy expectation value with respect to the
final state and the ground eigen energy of
the classical Hamiltonian,
\begin{equation}
 \Delta E = \langle\Psi (\tau)|\mathcal{H}_0|\Psi(\tau)\rangle - 
 E_0,
 \label{eq:DeltaE}
\end{equation}
where $E_0$ denotes the ground eigen energy of $H_0$.
In our calculation, $E_0$ is known because the system
is small enough.

We show results on the tight-binding model represented by
eqs. (\ref{eq:TB1}) and (\ref{eq:TB2}) in Fig.\ref{fig:TB}.
The potential 
energy at each site is randomly generated and is shown in 
Fig\ref{fig:TB}(a). Calculations ware performed for 
several tunneling energies. Large value of $\alpha$
gives rise to the large energy gap at the initial time.
Since the adiabatic theorem works better for larger energy gap,
large $\alpha$ is preferable to lower the residual energy.
However large $\alpha$ yields large derivative by the time of the
Hamiltonian. Since large derivative disturbs
the adiabatic evolution, large $\alpha$ is not preferable.
Therefore there is an optimum $\alpha$.
In the present case, it seems around $\alpha = 0.6$.

It is seen in Fig.\ref{fig:TB}(b) that
the logarithm of residual energy decreases almost linearly with 
increasing the logarithm of annealing time for long annealing time. 
Therefore the residual energy roughly obeys 
the power law with respect to the annealing time, 
\begin{equation}
 \Delta E \propto \frac{1}{\tau^{\zeta}}.
\label{eq:SquareInv}
\end{equation}
By comparison with the line 
$\Delta E \propto\tau^{-2}$ drawn in the same figure,
the exponent is estimated as $\zeta\sim 2$.

Results on the random Ising model given by eqs.(\ref{eq:SG1}) and 
(\ref{eq:SG2}) are shown in Fig.\ref{fig:SG}. The system consists of
nine spins in the two-dimensional square lattice with nearest neighbor
interactions. The values of coupling constants are indicated by the
inset in the figure. 
Similar to the case in Fig.\ref{fig:TB}(b), the residual energy
is smallest at a certain optimum $\alpha$ for a fixed $\tau$. 
%Comparing the results for several $\alpha$, 
%the optimum value is roughly estimated as $\alpha\sim 0.3$.
It is clearly seen that the logarithm of residual energy is
linear in $\ln\tau$ for long $\tau$.
Hence the power law of the residual energy, eq.(\ref{eq:SquareInv})
\begin{equation}
 \Delta E \sim \frac{1}{\tau^{\zeta}},
\end{equation}
holds also in the present case. 
Furthermore we can estimate $\zeta\sim 2$ by comparison with 
the straight line
of $\Delta E\propto 1/\tau^2$ in the figure.
This result is the same as that of the tight-binding model.



%\section{Analytic consideration}
From results of numerical calculations, we naturally infer
that the power law with the exponent $\zeta\sim 2$ is 
the universal feature in the quantum annealing method.
In fact, one can derive from the adiabatic theorem that this is true.
According to a rigorous theory on the adiabatic 
theorem,
the probability to find out the excited states of $\mathcal{H}_0$ in
the final state is given by\cite{bib:Messiah}
\begin{equation}
 \sum_{n\neq 0} |\langle n|\Psi(\tau)\rangle|^2 
  \sim O\left(\frac{1}{\left(\epsilon\tau\right)^2}\right)
  \label{eq:error}
\end{equation}
where $|n\rangle$ denotes the eigen 
state of $\mathcal{H}_0$ and $n=0$ indicates the ground state
in particular. 
$\epsilon$ has the dimension of energy and defined by
$\epsilon = \varepsilon_{\rm min}^2/\varepsilon'$
where $\varepsilon_{\rm min}$ is the minimum of energy gap
above the instantaneous ground state of $\mathcal{H}_{\tau}(t)$
and $\varepsilon'$ is the maximum of matrix element of 
$\mathcal{H}_T - \mathcal{H}_0$ among instantaneous ground state
and the lowest excited state of $\mathcal{H}_{\tau}(t)$.
The value of $\varepsilon'$ is of the order of the energy unit.
Equation (\ref{eq:error}) holds for $\epsilon\tau\gg 1$. 
Formulas for each eigen state are derived, that is, 
$|\langle n|\Psi(\tau)\rangle|^2 
\sim O(1/\left(\epsilon\tau\right)^2)$ for
$n\neq 0$ and $|\langle 0|\Psi(\tau)\rangle|^2 
\sim 1 - O(1/\left(\epsilon\tau\right)^2)$.
%We remark here 
%$\sum_n |\langle n|\Psi(\tau)\rangle|^2 = 
%\langle\Psi(\tau)|\Psi(\tau)\rangle = 1$.
Hence, arranging the eq.(\ref{eq:DeltaE}), 
we obtain that the residual energy 
is of the order of $1/\left(\epsilon\tau\right)^2$.
\begin{eqnarray}
 \Delta E &=& \sum_{n\neq 0} E_n |\langle n|\Psi(\tau)\rangle|^2 - 
  E_0 \left(1- |\langle 0|\Psi(\tau)\rangle|^2\right) \nonumber \\
 %&\sim& \sum_{n\neq} E_n O(\frac{1}{\tau^2}) + E_0 O(\frac{1}{\tau^2})
  &\sim& O(\frac{1}{\left(\epsilon\tau\right)^2}) ,
  \label{eq:DeltaE1}
\label{eq:powerlaw}
\end{eqnarray}
where $E_n$ is the eigen energy of $\mathcal{H}_0$.
Thus it is shown that the term proportional to $1/\tau^2$ dominates the
residual energy in the infinite limit of $\tau$.

We note that eq.(\ref{eq:powerlaw}) may contain higher order terms
of $1/\left(\epsilon\tau\right)$ than $1/\left(\epsilon\tau\right)^2$.
We attribute fluctuations around the line of
$\Delta E\propto 1/\tau^2$ in Fig.\ref{fig:TB}(b) to these 
additional terms.



%\section{Discussion}
The existence of the energy gap above the instantaneous ground
state of $\mathcal{H}_{\tau}(t)$ is crucial
for the quantum annealing method. 
The argument on the basis of the eq.(\ref{eq:error}) is
incorrect when the ground state is degenerate at
a time during the evolution.
This is obvious because of $\epsilon=0$.
However the Hamiltonian of disordered systems 
does not usually possess any symmetry 
which brings about degenerate ground state.



We assume that the instantaneous energy gap is always finite.
The value of $\varepsilon_{\rm min}$ depends on the problem. 
For problems with small $\varepsilon_{\rm min}$, 
a large $\tau$ is required in order to validate the power 
law of the residual energy.
In other words, 
the quantum annealing method is more efficient for problems
with larger $\varepsilon_{\rm min}$.



For $\epsilon\tau\sim 1$, 
the adiabatic theorem does not work.
Instead the Landau-Zener theory should account for 
the transition between two states with close energies.
Consider that the energy levels of instantaneous ground and 
first excited states come close together at a time.
The excitation energy is locally minimized at this time.
According to the Landau-Zener theory\cite{bib:LandauQM,bib:Zener}, 
the transition probability
from the ground state to the first excited state is given
by $p\sim \exp(-c \epsilon\tau)$, 
where $c$ is a constant of the order of unity.
If such a possible transition occurs just once,
the residual energy is proportional to $\exp(-c \epsilon\tau)$.
However it is not obvious whether this exponential behavior
is true for large systems, since the transition events
may take place many times.

Santoro \textit{et al.} have predicted the logarithmic scaling
law of the residual energy
on the basis of the Landau-Zener theory\cite{bib:Santoro}.
We remark that our result of power law is valid for 
$\tau\gg 1/\epsilon$ where the quantum adiabatic theorem
is guaranteed. Since the Landau-Zener theory is intended for
$\tau\sim 1/\epsilon$, these two scaling laws may not conflict
with each other.
Nevertheless it should be noted that the definition of the
residual energy in ref.\cite{bib:Santoro} is given 
by the expectation value of the excitation energy
among the quantum annealing process. 
It is natural that the residual energy
is defined by the energy expectation value of the final state 
measured from the true ground energy, eq.(\ref{eq:DeltaE}).
Furthermore no one has confirmed numerically the scaling behavior 
for $\tau\sim 1/\epsilon$.
In order to unveil the feature in this regime,
numerical calculations for huge sized systems are desired.


%If we neglect multiple transitions between the ground and first
%excited states and those between higher excited states,
%the total transition probability from the ground state at
%the initial time to the first excited state at final time
%is given by 
%$P = n p (1-p)^{n-1} \sim n p \sim n 
%\exp(-c\tau\epsilon)$.
%Here we denoted the times of energy-level approaching
%by $n$ and assumed $p<1/n\ll 1$.
%Although it is not clear how many the number $n$ is,
%it increases with the size of the problem.
%In the approximation which neglects higher excited states,
%the residual energy is roughly estimated as 
%$\Delta E = (E_1 - E_0) P$.
%This expression means that the residual energy falls exponentially
%with annealing time. 

%Santoro \textit{et al.} also estimated the residual energy
%on the basis of the Landau-Zener theory\cite{bib:Santoro}.
%They predict logarithmic scaling of the residual energy
%by the annealing time. It should be noted here that 
%there are following two large differences between their theory and
%ours above. The first is on the definition of the residual energy.
%In ref\cite{bib:Santoro}, the residual energy is defined by
%by the expectation value
%of the excitation energy among the quantum annealing.
%However it is natural 
%to see the energy of final state after the quantum annealing.
%Hence we have defined the residual energy by 
%the energy expectation value of the final state 
%measured from the true ground energy.
%The second difference is in the model studied.
%The classical Hamiltonian in ref\cite{bib:Santoro} has
%doubly degenerate ground states. Then the energy gap above
%the ground state closes at the final time. 
%In our definition, the excitation to the first excited state
%has no contribution to the residual energy.
%
%
%
%
%The result is in contrast to ours. This conflict comes from
%the definition of the residual energy.
%Their have defined the residual energy by the expectation value
%of the excitation energy among the quantum annealing, while
%our definition is the energy expectation value of the final state measured
%from the true ground energy.
%Since their model has no energy gap in the classical limit,
%the residual energy vanishes in our definition.




We remark on the implementation of the quantum annealing
for combinatorial optimization problems with large elements.
In order to carry out the quantum annealing, we must 
compute the real-time dynamics according to the Schr\"{o}dinger
equation. Methods of numerical calculation for the real-time
quantum dynamics have not 
been developed enough except for cases of one-dimensional models. 
Construction of a general method is a big issue.
One possibility exists in the quantum Monte-Carlo
method. Even though direct computations of the real-time
dynamics are impossible in the quantum Monte-Carlo method,
one can regard an evolution by Monte-Carlo step 
as a fictitious-time evolution.
some of earlier works have 
reported that
the quantum annealing with the quantum Monte-Carlo
is more efficient than the 
thermal annealing\cite{bib:Kadowaki,bib:Martonak}.
However it is not clear that the adiabatic theorem works 
in the Monte-Carlo evolution, 
the residual energy may show annealing time dependence different from
real-time quantum annealing.
A rigorous theory on the residual energy after the 
Monte-Carlo evolution is left as a future work.



%\section{Summary}
%In conclusion, we revealed behavior of
%the residual energy after the quantum annealing.
%If the evolution of the quantum state is sufficiently slow,
%the residual energy falls as inverse square of
%the annealing time.
%This result is independent of the model.
%We also discussed applicability of our result.




%\section{Acknowledgements}

The present work is supported by Grant-in-Aid 
for Scientific Research (Grant No.14084212) 
by the Ministry of Education, Culture, Sports, Science and 
Technology of Japan.











% If in two-column mode, this environment will change to single-column
% format so that long equations can be displayed. Use
% sparingly.
%\begin{widetext}
% put long equation here
%\end{widetext}

% figures should be put into the text as floats.
% Use the graphics or graphicx packages (distributed with LaTeX2e)
% and the \includegraphics macro defined in those packages.
% See the LaTeX Graphics Companion by Michel Goosens, Sebastian Rahtz,
% and Frank Mittelbach for instance.
%
% Here is an example of the general form of a figure:
% Fill in the caption in the braces of the \caption{} command. Put the label
% that you will use with \ref{} command in the braces of the \label{} command.
% Use the figure* environment if the figure should span across the
% entire page. There is no need to do explicit centering.

% \begin{figure}
% \includegraphics{}%
% \caption{\label{}}
% \end{figure}

% Surround figure environment with turnpage environment for landscape
% figure
% \begin{turnpage}
% \begin{figure}
% \includegraphics{}%
% \caption{\label{}}
% \end{figure}
% \end{turnpage}

% tables should appear as floats within the text
%
% Here is an example of the general form of a table:
% Fill in the caption in the braces of the \caption{} command. Put the label
% that you will use with \ref{} command in the braces of the \label{} command.
% Insert the column specifiers (l, r, c, d, etc.) in the empty braces of the
% \begin{tabular}{} command.
% The ruledtabular enviroment adds doubled rules to table and sets a
% reasonable default table settings.
% Use the table* environment to get a full-width table in two-column
% Add \usepackage{longtable} and the longtable (or longtable*}
% environment for nicely formatted long tables. Or use the the [H]
% placement option to break a long table (with less control than 
% in longtable).
% \begin{table}%[H] add [H] placement to break table across pages
% \caption{\label{}}
% \begin{ruledtabular}
% \begin{tabular}{}
% Lines of table here ending with \\
% \end{tabular}
% \end{ruledtabular}
% \end{table}

% Surround table environment with turnpage environment for landscape
% table
% \begin{turnpage}
% \begin{table}
% \caption{\label{}}
% \begin{ruledtabular}
% \begin{tabular}{}
% \end{tabular}
% \end{ruledtabular}
% \end{table}
% \end{turnpage}

% Specify following sections are appendices. Use \appendix* if there
% only one appendix.
%\appendix
%\section{}

% If you have acknowledgments, this puts in the proper section head.
%\begin{acknowledgments}
% put your acknowledgments here.
%\end{acknowledgments}

% Create the reference section using BibTeX:
\bibliography{letter}

\end{document}
%
% ****** End of file template.aps ******


letter.bbl
\begin{thebibliography}{13}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi
\expandafter\ifx\csname bibnamefont\endcsname\relax
  \def\bibnamefont#1{#1}\fi
\expandafter\ifx\csname bibfnamefont\endcsname\relax
  \def\bibfnamefont#1{#1}\fi
\expandafter\ifx\csname citenamefont\endcsname\relax
  \def\citenamefont#1{#1}\fi
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{\texttt{#1}}\fi
\expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{URL }\fi
\providecommand{\bibinfo}[2]{#2}
\providecommand{\eprint}[2][]{\url{#2}}

\bibitem[{\citenamefont{Kadowaki and Nishimori}(1998)}]{bib:Kadowaki}
\bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Kadowaki}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{H.}~\bibnamefont{Nishimori}},
  \bibinfo{journal}{Phys.\ Rev.\ E} \textbf{\bibinfo{volume}{58}},
  \bibinfo{pages}{5355} (\bibinfo{year}{1998}).

\bibitem[{\citenamefont{Farhi et~al.}(2001)\citenamefont{Farhi, Goldstone,
  Gutmann, Lapan, Lundgren, and Preda}}]{bib:Farhi}
\bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Farhi}},
  \bibinfo{author}{\bibfnamefont{J.}~\bibnamefont{Goldstone}},
  \bibinfo{author}{\bibfnamefont{S.}~\bibnamefont{Gutmann}},
  \bibinfo{author}{\bibfnamefont{J.}~\bibnamefont{Lapan}},
  \bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Lundgren}}, \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Preda}},
  \bibinfo{journal}{Science} \textbf{\bibinfo{volume}{292}},
  \bibinfo{pages}{472} (\bibinfo{year}{2001}).

\bibitem[{\citenamefont{Hogg}(2003)}]{bib:Hogg}
\bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Hogg}},
  \bibinfo{journal}{Phys.\ Rev.\ A} \textbf{\bibinfo{volume}{67}},
  \bibinfo{pages}{22314} (\bibinfo{year}{2003}).

\bibitem[{\citenamefont{Steffen et~al.}(2003)\citenamefont{Steffen, van Dam,
  Hogg, Breyta, and Chuang}}]{bib:Steffen}
\bibinfo{author}{\bibfnamefont{M.}~\bibnamefont{Steffen}},
  \bibinfo{author}{\bibfnamefont{W.}~\bibnamefont{van Dam}},
  \bibinfo{author}{\bibfnamefont{T.}~\bibnamefont{Hogg}},
  \bibinfo{author}{\bibfnamefont{G.}~\bibnamefont{Breyta}}, \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{I.}~\bibnamefont{Chuang}},
  \bibinfo{journal}{Phys.\ Rev.\ Lett.} \textbf{\bibinfo{volume}{90}},
  \bibinfo{pages}{67903} (\bibinfo{year}{2003}).

\bibitem[{\citenamefont{Geman and Geman}(1984)}]{bib:Geman}
\bibinfo{author}{\bibfnamefont{S.}~\bibnamefont{Geman}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Geman}},
  \bibinfo{journal}{IEEE\ Trans.\ Pattern.\ Anal.\ Mach.\ Intell.}
  \textbf{\bibinfo{volume}{6}}, \bibinfo{pages}{721} (\bibinfo{year}{1984}).

\bibitem[{\citenamefont{Brooke et~al.}(1999)\citenamefont{Brooke, Bittro,
  Rosenbaum, and Aeppli}}]{bib:brookeS}
\bibinfo{author}{\bibfnamefont{J.}~\bibnamefont{Brooke}},
  \bibinfo{author}{\bibfnamefont{D.}~\bibnamefont{Bittro}},
  \bibinfo{author}{\bibfnamefont{T.~F.} \bibnamefont{Rosenbaum}},
  \bibnamefont{and} \bibinfo{author}{\bibfnamefont{G.}~\bibnamefont{Aeppli}},
  \bibinfo{journal}{Science} \textbf{\bibinfo{volume}{284}},
  \bibinfo{pages}{779} (\bibinfo{year}{1999}).

\bibitem[{\citenamefont{Huse and Fisher}(1986)}]{bib:Huse}
\bibinfo{author}{\bibfnamefont{D.~A.} \bibnamefont{Huse}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{D.~S.} \bibnamefont{Fisher}},
  \bibinfo{journal}{Phys.\ Rev.\ Lett.} \textbf{\bibinfo{volume}{57}},
  \bibinfo{pages}{2203} (\bibinfo{year}{1986}).

\bibitem[{\citenamefont{Shinomoto and Kabashima}(1991)}]{bib:Shinomoto}
\bibinfo{author}{\bibfnamefont{S.}~\bibnamefont{Shinomoto}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{Y.}~\bibnamefont{Kabashima}},
  \bibinfo{journal}{J. Phys.} \textbf{\bibinfo{volume}{A 24}},
  \bibinfo{pages}{L141} (\bibinfo{year}{1991}).

\bibitem[{\citenamefont{Santoro et~al.}(2002)\citenamefont{Santoro,
  Marto{\v{n}}{\'{a}}k, Tosatti, and Car}}]{bib:Santoro}
\bibinfo{author}{\bibfnamefont{G.~E.} \bibnamefont{Santoro}},
  \bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Marto{\v{n}}{\'{a}}k}},
  \bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Tosatti}}, \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Car}},
  \bibinfo{journal}{Science} \textbf{\bibinfo{volume}{295}},
  \bibinfo{pages}{2427} (\bibinfo{year}{2002}).

\bibitem[{\citenamefont{Messiah}(1962)}]{bib:Messiah}
\bibinfo{author}{\bibfnamefont{A.}~\bibnamefont{Messiah}},
  \emph{\bibinfo{title}{Quantum Mechanics}}, Vol. 2
  (\bibinfo{publisher}{North-Holland}, \bibinfo{address}{Amsterdam},
  \bibinfo{year}{1962}).

\bibitem[{\citenamefont{Landau and Lifshitz}(1965)}]{bib:LandauQM}
\bibinfo{author}{\bibfnamefont{L.~D.} \bibnamefont{Landau}} \bibnamefont{and}
  \bibinfo{author}{\bibfnamefont{E.~M.} \bibnamefont{Lifshitz}},
  \emph{\bibinfo{title}{Quantum Mechanics : non-relativistic theory}}, 2nd ed.
  (\bibinfo{publisher}{Pergamon Press}, \bibinfo{address}{Oxford},
  \bibinfo{year}{1965}).

\bibitem[{\citenamefont{Zener}(1932)}]{bib:Zener}
\bibinfo{author}{\bibfnamefont{C.}~\bibnamefont{Zener}},
  \bibinfo{journal}{Proc.\ Roy.\ Soc.\ London\ Ser.\ A}
  \textbf{\bibinfo{volume}{137}}, \bibinfo{pages}{696} (\bibinfo{year}{1932}).

\bibitem[{\citenamefont{Marto{\v{n}}{\'{a}}k
  et~al.}(2002)\citenamefont{Marto{\v{n}}{\'{a}}k, Santoro, and
  Tosatti}}]{bib:Martonak}
\bibinfo{author}{\bibfnamefont{R.}~\bibnamefont{Marto{\v{n}}{\'{a}}k}},
  \bibinfo{author}{\bibfnamefont{G.~E.} \bibnamefont{Santoro}},
  \bibnamefont{and} \bibinfo{author}{\bibfnamefont{E.}~\bibnamefont{Tosatti}},
  \bibinfo{journal}{Phys.\ Rev.\ B} \textbf{\bibinfo{volume}{66}},
  \bibinfo{pages}{94203} (\bibinfo{year}{2002}).

\end{thebibliography}
