text:
\section{Introduction}

Quantum annealing (QA) is a heuristic optimization method that minimizes classical cost functions using quantum adiabatic evolutions \cite{finnila_quantum_1994,kadowaki_quantum_1998,farhi_quantum_2001,brooke_tunable_2001,Santoro,RevModPhys.80.1061}. For closed systems, adiabaticity guarantees that the time-evolved state is an instantaneous ground state of the time-dependent QA Hamiltonian \cite{Kato:50,Jansen:07,lidar:102106},
which in turn guarantees that the final state is a solution of the optimization problem. A non-adiabatic evolution causes transitions into excited states, which  correspond to computational errors. In open systems, coupling to the environment causes further errors even if the evolution is perfectly adiabatic.
Coupling to a thermal environment results in excitations at any finite temperature \cite{childs_robustness_2001,PhysRevLett.95.250503,TAQC,amin_decoherence_2009,ABLZ:12-SI,Albash:2015nx}.

While QA is believed to be robust against certain types of decoherence \cite{childs_robustness_2001,PhysRevLett.95.250503,TAQC,amin_decoherence_2009,ABLZ:12-SI,Albash:2015nx}, QA remains vulnerable to the aforementioned thermal excitations that depopulate the ground state, so quantum error correction is necessary for scalability.
Currently, despite considerable theoretical progress in the development of quantum error suppression and correction for QA \cite{jordan2006error,PhysRevLett.100.160506,PhysRevA.86.042333,Young:13,Sarovar:2013kx,Ganti:13,Young:2013fk,Bookatz:2014uq,Marvian:2014nr,Jiang:2015kx,Marvian:2016kb,Marvian-Lidar:16}, an adiabatic version of the accuracy-threshold theorem (see, e.g., Ref.~\cite{Aliferis:05}) has not yet been established.
While it is clearly important to address the theoretical fault tolerance challenge \cite{Mizel:2014sp}, there has been a great deal of interest in investigating implementable error correction methods on near-term devices.  One motivation for this is the commercial availability of quantum annealing hardware, the D-Wave processors \cite{Dwave,Harris:2010kx,Bunyk:2014hb}, which are known to be prone to precision and thermal errors \cite{q108,SSSV,Albash:2014if,Crowley:2014qp,Vinci:2014fk,Martin-Mayor:2015dq}. Error correction methods for QA, known as quantum annealing correction (QAC), have been developed and demonstrated on the D-Wave processors \cite{PAL:13,PAL:14,Vinci:2015jt,Mishra:2015,vinci2015nested}.

In QAC, the problem Hamiltonian is encoded using a quantum error detection code. Excitations out of the ground state are suppressed via the introduction of energy penalties that commute with the encoded problem Hamiltonian.
A classical post-processing (decoding) step allows for further recovery of the logical ground state even after such excitations have occurred. We distinguish between two versions of QAC. In one case designated penalty qubits are used to increase the energy of erroneous states \cite{PAL:13,PAL:14,Vinci:2015jt,Mishra:2015}, while in the other case there are no designated penalty qubits but some Ising couplings are used to impose energy penalties \cite{Vinci:2015jt,Mishra:2015,vinci2015nested}.  Here we focus on the former and reserve a study of the latter for a future publication \cite{Matsu2016-part2}.

In a previous paper \cite{MNAL:15}, we investigated how QAC affects the success rate of QA using mean field methods. Focusing mostly on the zero temperature case, we showed that QAC can remove or weaken phase transitions during the
the evolution by increasing the energy gap. As a consequence the success rate for QA is expected to improve when using QAC.  Indeed, this is what was observed experimentally \cite{PAL:13,PAL:14,Vinci:2015jt,Mishra:2015}.

The main goal of this paper is to extend the analysis of QAC to the finite temperature case.
To accomplish this we use analytical methods borrowed from statistical physics, namely
Landau-Ginzburg theory applied to the free energy derived for the quantum model after
the Suzuki-Trotter procedure. In this setting we analyze the phase transitions associated with QAC at finite temperature, since the nature of the phase transition often determines computational complexity: typically first order transitions are associated with exponentially small gaps, while second order transitions feature polynomially small gaps (some exceptions wherein a first order quantum phase transition is associated with a polynomially small gap are known \cite{CabreraJullien-Gap1987,Tsuda:2013br}). We also consider the free energy and study barrier height and width, as these determine the tunneling rate and (as we show) can also be related to the quantum gap; thus they set the inverse time scales for  adiabatic evolution.

In addition to studying QAC at finite temperatures, a novel aspect of the analysis we present here is a study of the effect of a transverse field acting on the penalty qubits. The presence of the transverse field on the penalty qubits is a feature of all the experiments performed so far of QAC \cite{PAL:13,PAL:14,Vinci:2015jt,Mishra:2015}, but it was ignored for simplicity in our earlier study \cite{MNAL:15}.
We provide a theoretical justification for the existence of an optimal penalty strength that maximizes the undecoded ground state probability, a feature that was observed in the experiments \cite{PAL:13}.

This paper is organized as follows. In Section~\ref{penalty QAC section} we briefly review QA and QAC.
In Section~\ref{No transverse field in the penalty} we study the free energy and finite-temperature phase transitions without a transverse field on the penalty qubits. We show that the penalty term in general weakens the phase transitions or splits one ``hard" first-order phase transition into multiple, weaker phase transitions. This corresponds to larger energy gaps, which are expected to improve the performance of  QA. Thermal effects, however, have a competing effect, increasing the potential barriers and thus reducing the gaps.  In Section~\ref{transverse field in the penalty}, we consider phase transition with a transverse field on the penalty qubits. We find that this transverse field also increases the potential barrier at the phase transitions. We therefore conclude that adding a transverse field on the penalty qubits reduces the effectiveness of QAC.
We conclude in Section~\ref{conc}. Additional technical details are presented in the Appendix.

\section{Quantum Annealing and Quantum Annealing Correction}
\label{penalty QAC section}

Quantum annealing is designed to solve combinatorial optimization problems. It is formulated in terms of a classical Ising Hamiltonian of the form
\begin{eqnarray}
H^{Z}=-\sum_{i}h_{i}\sigma^{z}_{i}-\sum_{(i,j)}J_{ij}\sigma^{z}_{i}\sigma^{z}_{j}\ ,
\label{problem Hamil}
\end{eqnarray}
where $i\in [1,N]$ are the spin sites, $\{h_{i}\}$ are the local fields, $\{ J_{ij} \}$ are the Ising couplings, and $\sigma^{z}_{i}$
is the $z$ component of the Pauli matrices acting on site $i$.
The optimization problem is encoded into the parameters $h_{i}$ and $J_{ij}$.
The search space is the set of classical spin configurations, and the optimal solution is the ground state or one of the ground states of the Ising Hamiltonian.
For general $h_i$ and $J_{ij}$, finding a ground state of the Hamiltonian above is NP-hard \cite{Barahona1982}. In physical terms, the Hamiltonian encodes a ``rough" energy landscape so that heuristic search methods such as simulated annealing \cite{kirkpatrick_optimization_1983} tend to become trapped in local minima. QA uses quantum fluctuations to find a ground state of the ``problem Hamiltonian" $H^Z$. Quantum fluctuations are induced by a simple ``driver Hamiltonian" $H^X$ whose ground state is easy to prepare since it involves no interactions. We consider the standard transverse-field driver Hamiltonian
\begin{eqnarray}
H^{X}=-\sum_{i=1}^N\sigma^{x}_{i}\ .
\label{driver Hamil}
\end{eqnarray}
The time-dependent QA Hamiltonian is given by
\begin{eqnarray}
H(t)=A(t)H^{X}+B(t)H^{Z},~~~~t\in[0,t_f]\ .
\label{driver functs}
\end{eqnarray}
The driver term dominates the Hamiltonian at the initial time $t=0$: $A(0)\gg B(0)$.
Then $A(t)$ decreases while $B(t)$ increases, and at the end of the
evolution
$t=t_f$, the problem Hamiltonian dominates: $A(t_f)\ll B(t_f)$. In the absence of any coupling to an external environment and provided the evolution is slow (adiabatic) compared to the timescale set by the minimum inverse gap of $H(t)$, the final state is a ground state of $H(t_f)$ with high probability and gives the solution to the optimization problem.

In the open system case the steady state is no longer the ground state, and the spectral gap of the Liouvillian sets the inverse timescale for adiabatic evolution \cite{joye_general_2007,oreshkov_adiabatic_2010,Avron:2012tv,Venuti:2015kq}.
Coupling to the environment (typically modeled as a thermal bath) introduces computational errors in the form of thermally induced excitations \cite{childs_robustness_2001,PhysRevLett.95.250503,TAQC,amin_decoherence_2009,ABLZ:12-SI,Albash:2015nx}. Error correction is thus necessary in any physical implementation of QA. In the QAC approach,  the quantum state is protected in three steps.
First, a classical repetition code is used, whereby a logical qubit is encoded into $C$ physical qubits. The problem Hamiltonian is correspondingly ``encoded", e.g., every Pauli operator is replaced by the corresponding encoded Pauli operator.
In the second step we deform the Hamiltonian by adding penalty terms that (i) commute with the problem Hamiltonian and (ii) anticommute with bit-flip errors. Step (i) ensures that the encoded problem Hamiltonian and the penalty terms share the same set of eigenstates, and step (ii) ensures that it costs more energy for the environment to generate any errors that anti-commute with $\sigma^z$.
In the third step the logical qubits are decoded at the end of the
evolution, either by majority vote \cite{PAL:13,PAL:14,Vinci:2015jt,Mishra:2015} or energy minimization \cite{Vinci:2015jt,Mishra:2015}.

The encoded Hamiltonian for QAC that we consider is of the form
\begin{eqnarray} \label{eqt:QACHamiltonian}
H=\sum_{c=1}^{C}(H^{Z}_{c}+\Gamma H_{c}^{X}+\gamma H^{P}_{c})\ ,
\end{eqnarray}
where $H^{Z,X}_{c}$ are $C$ identical copies of the same $H^{Z,X}$  defined in Eqs.~\eqref{problem Hamil} and \eqref{driver Hamil}.
The third term $H^{P}_{c}$ is the penalty term, with $\gamma$ its strength. $\Gamma$ is the strength of the quantum term which sweeps from $\infty$ to zero
during the quantum annealing evolution.

As in our earlier work \cite{MNAL:15}, we choose the penalty as the sum over the stabilizer elements of the  repetition code, anticommuting with all single-qubit bit-flip errors, as required for error detection and suppression of such errors  \cite{Gottesman:1996fk}:
\begin{eqnarray}
H^{P}_{c}=-\sum_{i=1}^N\sigma_{ic}^{z}\sigma_{i0}^{z}\ .
\end{eqnarray}
The penalty term includes an independent penalty qubit $\sigma_{i0}^{z}$ for each logical qubit $i$.
It couples ferromagnetically to all $C$ physical qubits corresponding to logical qubit $i$, thus creating an energy penalty for misalignment with the penalty qubit.
Note that the degenerate ground states of the penalty term are $|\bar{0}  \rangle_{i} |0\rangle_{P}$
and $|\bar{1}  \rangle_{i} |1\rangle_{P}$ where $|0\rangle_{P}$ and $|1\rangle_{P}$ are the states of the penalty qubit, and the code space of the $i^\textrm{th}$ logical qubit is spanned by the two states with all the ``problem spins" pointing in the same direction: $\ket{\bar{0} }_i=\ket{00 \cdots 0}_{i} $ and $\ket{\bar{1} }_i=\ket{11 \cdots 1}_{i}$, where $\ket{0}$ and $\ket{1}$ are the eigenstates of $\sigma^{z}$.
Therefore, the ground state of the QAC Hamiltonian $H$ at the end of evolution
($\Gamma =0$) is the ground state of
the problem Hamiltonian $H^{Z}$.
However, the ground state of $H^{Z}+\Gamma H^{X}$ is not an eigenstate of $H^{P}=\sum_c H_c^P$.
Thus, although the above form of the penalty term is natural from the problem Hamiltonian point of view, it is not \textit{a priori} clear that it helps the performance of QA.
To ensure an increase in the ground state gap of $H^{Z}+\Gamma H^{X}$
one needs to have a time- and problem-dependent penalty term, or encode the driver Hamiltonian as well \cite{jordan2006error}.

We shall consider a modification of the QAC Hamiltonian in Eq.~\eqref{eqt:QACHamiltonian} by the inclusion of a transverse field on the penalty qubit.  This addition takes the form
\begin{equation}
V=-\epsilon C \Gamma\sum_{i=1}^N\sigma_{i0}^{x}\ ,
\label{eq:V}
\end{equation}
where $\epsilon$ is the strength of transverse field on the penalty qubit relative to the problem qubits.
All QAC experiments to date \cite{PAL:13,PAL:14,Vinci:2015jt,Mishra:2015,Vinci:2015jt,Mishra:2015} were performed in the presence of this term, and one needs to account for this feature in order to have a more complete understanding of the experimental results.

\section{QAC without a transverse field on the penalty qubits}
\label{No transverse field in the penalty}

Let us first consider QAC at finite temperature in the absence of a penalty transverse field, i.e., with $\epsilon=0$ in Eq.~\eqref{eq:V}.
Our problem Hamiltonian is a fully connected $p$-body ferromagnet, i.e.,
\begin{equation}
H^{Z}_{c} = -N \left({1\over N}  \sum_{i=1}^{N}\sigma_{ic}^{z}   \right)^{p}\ ,
\end{equation}
where $i$ is the logical qubit index and $c$ is the copy index. The encoded QAC Hamiltonian~\eqref{eqt:QACHamiltonian} is therefore:
\begin{align}
H&=
-{N}\sum_{c=1}^{C}\left({1\over N}  \sum_{i=1}^{N}\sigma_{ic}^{z}   \right)^{p}
-\Gamma \sum_{c=1}^{C} \sum_{i=1}^{N} \sigma_{ic}^{x}\notag \\
& \quad -\gamma \sum_{c=1}^{C} \sum_{i=1}^{N} \sigma_{ic}^{z}\sigma_{i0}^{z} \ .
\label{hamil-QAC}
\end{align}
It is clear that the ground state of the problem Hamiltonian $H^{Z}_{c}$ is the state with all the spins pointing in the $+z$ direction for odd $p$, and is degenerate with all the spins pointing either in the $+z$ or $-z$ direction for even $p$.
This fact does not change after we turn on the penalty $\gamma$.
The sign of $\gamma$ is not important since the penalty spin $\sigma_{i0}^{z}$ couples only to
the problem qubits $\sigma_{ic}^{z}$, and in the ground state either the penalty and the problem qubits are
parallel ($\gamma>0$) or anti-parallel ($\gamma<0$).
Without loss of generality we choose $\gamma$ to be non-negative.

Phase transitions occurring during the evolution are the main bottlenecks hindering the performance of the algorithm.  Therefore, to obtain useful insights for the mechanisms that help QAC in improving the performance of QA, we analyze the phase transitions associated with the QAC encoding defined in Eq.~\eqref{hamil-QAC}. In particular, we study how such phase transitions are affected by both the presence of a finite temperature and a transverse field on the penalty qubits.

The free energy of this system can be computed using the Suzuki-Trotter decomposition.
In this decomposition, one can transform a quantum problem in $d$ dimensions
into a classical problem in $(d+1)$ dimensions by introducing a Trotter direction \cite{Suzuki:1976rt}.
For our model, one can write the partition function $Z=\mathop{\mathrm{Tr}} e^{-\beta H}$ as a
path integral of an order parameter $m_c={1\over N}\langle \sum_{i} \sigma_{ic}^z\rangle$ along the Trotter direction.  In the large $N$ limit, one can use a static approximation in which $m_c$ does not change along the Trotter direction.

As shown in Appendix \ref{sec:TransverseFieldExtra}, the saddle point equation for $m_c$ is
\begin{align}
m_c=
\frac{\sum_{s\in\{-,+\}} \frac{v_{s,c}}{Q_{s,c}} \sinh(\beta{Q_{s,c}})
\prod_{c' \neq c} \cosh(\beta{Q_{s,c'}}) }
{\prod_{c'=1}^C \cosh\beta{Q_{-,c'}}
+
\prod_{c'=1}^C \cosh\beta{Q_{+,c'}}
} \ .
\label{saddle point eq0}
\end{align}
where
\begin{subequations}
\begin{eqnarray}
\label{eq:Q}
Q_{s,c} &=& \sqrt{v_{s,c}^2+\Gamma^2}\ , \\
v_{s,c}(m) &=& p m_c^{p-1}+s \gamma \ .
\end{eqnarray}
\end{subequations}
The minimum free energy solution is given by taking all order parameters equal, $m_c = m, \forall c$, with $m$ satisfying
\begin{align}
m=
{\sum_{s\in\{-,+\}}\sinh(\beta{Q_s})
\cosh^{C-1}(\beta{Q_s}) {v_{s}\over{Q_s}}
\over
(\cosh\beta{Q_-})^C
+
(\cosh\beta{Q_+})^C
} \ ,
\label{saddle point eq1}
\end{align}
where we dropped the $c$ subscript on $Q_{\pm,c}$ and $v_{\pm,c}$. Considering only this solution, the resultant free energy $F$, defined by $Z=\exp(-\beta N F)$, is
\begin{align}
\label{free energy mean field}
F/C=(p-1)m^p- {1\over C\beta}
\ln
\sum_{s\in\{-,+\}}
\left[ 2\cosh(\beta Q_s) \right]^C\ .
\end{align}
Details of this calculation can be found in the Supplemental Material of Ref.~\cite{MNAL:15} [in particular Eq.~(19) there becomes Eq.~\eqref{free energy mean field}].

\subsection{The zero temperature limit}
Note that when $p$ is even, $Q_\pm$ and hence both $F$ and the RHS of Eq.~\eqref{saddle point eq1} are invariant under the reflections $m \leftrightarrow -m$
and $\gamma \leftrightarrow -\gamma$.
At zero temperature ($\beta\to\infty$), only the largest term in the exponents in Eq.~\eqref{free energy mean field} survives.
By denoting $v^2=\max\{v^2_{+},v^2_{-}\}$, the free energy simplifies to
\begin{eqnarray}
F/C=(p-1)m^{p}-\sqrt{v^2+\Gamma^2}\ ,
\label{zero T free energy}
\end{eqnarray}
and the saddle point equation simplifies to
\begin{eqnarray}
m={v \over \sqrt{v^2+\Gamma^2 }}\ .
\end{eqnarray}
For $|m| \approx 0$ we have, using $v= p |m|^{p-1}+ \gamma$, and keeping only the leading order term in $|m|$,
\begin{eqnarray}
\sqrt{v^2+\Gamma^2} &\approx &\sqrt{\gamma^2+\Gamma^2} \left[1+2\gamma p |m|^{p-1}/(\gamma^2+\Gamma^2)\right]^{1/2} \notag \\
&\approx& \sqrt{\gamma^2+\Gamma^2}+\frac{\gamma p |m|^{p-1}}{\sqrt{\gamma^2+\Gamma^2}} \notag \ .
\end{eqnarray}
Therefore, when $|m| \approx 0$:
\begin{equation}
\left(F/C \right)_{\beta \to \infty}=-\sqrt{\gamma^2+\Gamma^2}-{p\gamma \over \sqrt{\gamma^2+\Gamma^2}}|m|^{p-1}+\mathcal{O}(m^{p})\ .
\label{eq:F/C-m-small}
\end{equation}

\subsection{Second order phase transition: $p=2$}

Let us first study the $p=2$ case at finite temperature.
If there is no penalty term ($\gamma=0$), the phase diagram is simply that of the transverse field Ising model.
At zero temperature [Eq.~\eqref{zero T free energy}],
the ground state is determined by the dominance of either the ferromagnetic coupling or the quantum fluctuations ($\Gamma$).
If the ferromagnetic coupling dominates (small $\Gamma$), the state is in the symmetry-broken (ferromagnetic) phase ($m\neq0$).
On the other hand, if the quantum fluctuations dominate (large $\Gamma$), the state is in the symmetric (paramagnetic) phase ($m=0$).
These two phases are separated by a second order phase transition at a critical value $\Gamma_c$.

The penalty term induces symmetry breaking. As mentioned above, the ground state configuration for the
penalty term has both the problem spins and the penalty spin parallel along the $z$ direction.
The symmetric configuration in which the problem spins point in the $x$ direction costs more energy.
In Ref.~\cite{MNAL:15}, it was shown that the symmetry is always broken in the zero temperature limit in the presence of the penalty term.
Indeed, one can easily see this by considering the free energy around $m=0$, given in Eq.~\eqref{eq:F/C-m-small}.  The presence of the linear term shows that for any finite value of $\gamma>0$, the origin $m=0$ is unstable and the ground state is realized at $|m|>0$.

At finite temperature, thermal fluctuations can change the situation qualitatively.
From Eq.~\eqref{saddle point eq1},
one can see that $m=0$ is always a solution of the saddle point equation.
The left and the right hand sides of Eq.~\eqref{saddle point eq1} are plotted in
Fig.~\ref{mM plot}.
If the slope of the RHS of Eq.~\eqref{saddle point eq1} at $m=0$ is less than 1, then $m=0$
is the unique solution which suggests that the system is in the symmetric phase with $m=0$.
If the slope is larger than 1, then there are two additional solutions with $m\neq0$. In this case
the system is in the symmetry-broken phase.
At finite temperature, one can see that the critical value of $\Gamma$ is finite.
The Taylor expansion of the right hand side of
Eq.~\eqref{saddle point eq1} around $m=0$ is
\begin{eqnarray}
&\left({2\beta\gamma^2 \over \gamma^2+\Gamma^2}
+{2\Gamma^2 \tanh(\beta\sqrt{\gamma^2+\Gamma^2})\over (\gamma^2+\Gamma^2)^{3/2}}  \right. \nonumber \\
& \left. +{4\beta \gamma^2\tanh^2(\beta\sqrt{\gamma^2+\Gamma^2})\over \gamma^2+\Gamma^2}
\right)m+\mathcal{O}(m^2) \ .
\label{saddle Taylor}
\end{eqnarray}
At sufficiently low temperatures such that $\beta\gamma\gg1$, the coefficient of $m$ is greater than 1 for small $\Gamma$,
while it goes to zero as $\Gamma\to\infty$.
Therefore, the large $\Gamma$ and the small $\Gamma$ regions are separated by a phase transition, and the critical
value is finite: $0<\Gamma_c<\infty$.

\begin{figure}[t]
\includegraphics[scale=0.75]{mag.pdf}
\caption{Plot of Eq.~\eqref{saddle point eq1} for
$C=3,p=2,\gamma=0.1,\beta=100$ and $\Gamma=0.5$, $\Gamma=4$. Since $\beta < \infty$,
$m=0$ is always a solution. The number of solutions is determined by the slope of the curves at $m=0$: if the slope is greater than 1, there are three solutions ($m_1 < 0, m_2 = 0, m_3 > 0$), and the state is in the symmetry-broken  phase. If the slope is less than 1, there is only one solution at $m=0$, and the system is in the symmetric phase.}
\label{mM plot}
\end{figure}

To illustrate these considerations, Fig.~\ref{gammaGamma p=2} shows the phase transition line in the $(\Gamma,\gamma)$ plane for various temperatures.
The region above each fixed temperature line (larger $\gamma$) is the symmetry-broken phase while that below (smaller $\gamma$) is the symmetric phase. The symmetry-broken phase is where the system solves the (trivial) computational problem of finding the ground state with high probability, while the symmetric phase is where it does not. Therefore, from the point of view of successful QAC, we would like the system to end up in the symmetry-broken phase.

There are several interesting and noteworthy features; in particular, we observe the existence of two critical temperatures, $T_1 = 1$ and $T_2 = 2$. For temperatures below $T_1$, the phase transition lines converge to $\Gamma_c=2$ as $\gamma\to 0$.  In the zero temperature limit, the slope of the phase transition line goes to zero, corresponding to the disappearance of the symmetric phase, i.e., an arbitrarily small penalty $\gamma$ suffices to push the system into the symmetry-broken phase.  Conversely, for a fixed $\gamma$, the phase transition happens at larger $\Gamma$ (earlier in the anneal) as the temperature decreases.

For temperatures between $T_1$ and $T_2$, the $\Gamma_c(\gamma\to 0)$ point moves to values lower than 2. At $T_2$, the phase transition line intersects the origin, i.e., $\Gamma_c(\gamma\to 0)=0$. For temperatures higher than $T_2$, the phase transition lines do not reach $\gamma=0$.  Therefore, there is no phase transition for $\gamma$ below a certain value, and the system is always in the symmetric phase (and fails to solve the computational problem) due to thermal fluctuations.  An example of such a case ($T=2.22$) is shown in Fig.~\ref{gammaGamma p=2}, where there is no phase transition for $\gamma<0.53$.

\begin{figure}[h]
      \includegraphics[scale=0.75]{gamGamp2.pdf}
\caption{Phase diagram $(\Gamma,\gamma)$ at $p=2$ for various values of temperature $T$, and for $C=3$.
Each second order phase transition line separates the symmetry-broken phase $m\neq0$ (above the lines)
from the symmetric phase $m=0$ (below the lines).
For $T< T_1 =1$, the phase transition lines merge at $\Gamma=2$ as $\gamma\to0$.
The $\Gamma(\gamma\to 0)$ point takes smaller values for $T_1 < T < T_2$,
and at $T = T_2=2$ it is zero.
Above $T_2$, the phase transition lines merge on finite $\gamma$ in $\Gamma\to0$ limit.
This means that even in the absence of quantum fluctuations, the spin fluctuations due to the temperature are large enough to have $m=0$ always be the global minimum if $\gamma$ is not too large.
     }
  \label{gammaGamma p=2}
\end{figure}
\subsection{First order phase transitions: $p\ge3$}
\label{sec:1PTp>2}

For $p\ge3$, the phase transition becomes first order, characterized by a discrete jump in the value of $m$ that minimizes the free energy.

\subsubsection{$T=0$}
Let us first review the zero temperature case  \cite{MNAL:15}. The first order phase transition persists as long as $\gamma$ is less than some critical value $\gamma_c(p)$.
At the critical point, the free energy barrier between different ground states becomes smaller for larger values of $\gamma$.  We interpret this as a softening of the phase transition as the penalty coupling increases. The reason for this, as we show in Appendix~\ref{app:Instanton}, is that the gap $\Delta$ of the QAC Hamiltonian can be estimated as
\begin{equation}
\Delta \gtrsim e^{-\Delta m \Delta F N} \ .
\label{eq:gap-F}
\end{equation}
where $\Delta m$ is the width and $\Delta F$ is the height of the free energy barrier at the phase transition. Thus, a smaller free energy barrier translates into a larger quantum gap $\Delta$.

The Taylor expansion of the free energy around $m=0$, Eq.~\eqref{eq:F/C-m-small}, shows that the symmetric phase $m=0$ is always unstable and will not be realized as the ground state.
The phase transition at finite $\gamma$ is therefore a transition between finite values of $m$, which we denote by $m_{\text{small}}$  and $m_{\text{large}}$ ($m_{\text{small}} < m_{\text{large}}$). Both values are continuous in $\gamma$.
In particular, $m_{\text{small}}$ goes to zero continuously as $\gamma\to0$. As $\gamma$ increases, $m_{\text{small}}$ becomes larger and eventually it merges with $m_{\text{large}}$ at the critical value $\gamma=\gamma_c$. For $\gamma>\gamma_c$, the phase transition disappears \cite{MNAL:15}.

\subsubsection{$T>0$}
At finite temperature, the symmetric point $m=0$ becomes locally stable, as can be seen by computing the Taylor expansion of the free energy [Eq.~\eqref{free energy mean field}] at $m=0$:
\begin{eqnarray}
F(m)/C=F(0)/C+(p-1)m^{p}+\mathcal{O}(m^{p+1})\ .
\end{eqnarray}
Therefore, phase transitions can happen not only between $m_{\text{small}}$ and $m_{\text{large}}$ but also between $m=0$ and $m_{\text{small}}$, and between $m=0$ and $m_{\text{large}}$.  Furthermore, unlike the zero temperature case, at finite temperature the point $\Gamma=0$ is always separated from $\Gamma=\infty$ by first order phase transitions, similarly to what happens for $p=2$.  However, the penalty $\gamma$ does soften the phase transition, in that it shrinks the free energy barrier separating degenerate minima of the free energy [recall Eq.~\eqref{eq:gap-F}].

\begin{figure*}[t]
\begin{tabular}{ccc}
\subfigure[]{\includegraphics[scale=0.6]{PLpmulRedup4r.pdf} \label{PLpmulRedup4} }&
\subfigure[]{\includegraphics[scale=0.6]{PLpmulRedup4rZoom.pdf} \label{PLpmulRedup4Zoom} }&
\subfigure[]{\includegraphics[scale=0.6]{PLpmulRedu.pdf}  \label{PLpmulRedu-a} }
\end{tabular}
\caption{$(\Gamma,T)$ phase diagrams for $p=4,5$ and different penalty values.  The space to the right of the curves corresponds to the paramagnetic or symmetric phase, labeled by `PM', while the space to the left of the curves corresponds to the ferromagnetic or symmetry-broken phase, labeled by `FM'.  (a) For $p=4$ and $\gamma=0.5$, $0.7$  and $1.5$. At zero temperature, there is a first order phase transition. The lower branch ($\Gamma=2.1, T<0.07$) of the phase boundary connects to the phase transition at zero temperature. This line separates the state characterized by $m_{\text{large}}$ from $m_{\text{small}}$.  Another line ($\Gamma>2.1, T<0.07$) is for the phase transition between $m_{\text{small}}$ and $m=0$. There is no corresponding phase transition at $T=0$ and this transition effectively disappears ($m_{\text{small}}$ goes to zero)  as $T$ approaches zero. For $\gamma=1.5$, there is no corresponding phase transition at $T=0$. Therefore there is no branch that reaches $T=0$.  (b) A close-up around the branching point in (a). The branching temperature increases as $\gamma$ increases. (c) The phase diagram for $p=4,\gamma=0.5$ and for $p=5,\gamma=0.8$.}
\label{PLpmulRedu}
\end{figure*}

\begin{figure*}[t]
\begin{tabular}{ccc}
\subfigure[]{     \includegraphics[scale=0.6]{p4T0025g0a.pdf} \label{lowT-highG}  }  &
\subfigure[]{     \includegraphics[scale=0.6]{p4T0025g0b.pdf}   \label{p4T0025g0a} }     &
\subfigure[]{     \includegraphics[scale=0.6]{highTbranch.pdf}   \label{highTbranch}} \\
\end{tabular}
\caption{
Free energy as a function of the order parameter $m$ along the phase transition lines, for $p=4$,  $\gamma=0.7$. (a) Transition between $m=0$ and $m=m_{\text{small}}$ $(T<T_{\text{branch}},\Gamma>\Gamma_{\text{branch}})$.  (b) Transition between $m=m_{\text{small}}$ and $m=m_{\text{large}}$ $(T<T_{\text{branch}},\Gamma=\Gamma_{\text{branch}})$. (c) Transition between $m=0$ and $m=m_{\text{large}}$ $(T>T_{\text{branch}},\Gamma<\Gamma_{\text{branch}})$.}
  \label{on the transition line}
\end{figure*}

The $(\Gamma,T)$ phase diagram is shown in Fig.~\ref{PLpmulRedu}.
In Fig.~\ref{PLpmulRedup4}, we plot the phase transition lines for $p=4$ and $\gamma=0.5,0.7,1.5$  ($\gamma_c \simeq 0.8)$.  The point $(\Gamma,T)=(0,0)$, which encodes the solution to the optimization problem, is separated from the large $\Gamma$ and/or the large $T$ region by first order phase transition lines.  When quantum fluctuations are very large $(\Gamma\gg 1)$, the free energy minimum is in the symmetric phase $m=0$.  As quantum fluctuations decrease $(\Gamma\to0)$, the free energy minimum shifts to the ordered phase $m=m_{\text{large}}$ due to the ferromagnetic coupling.  The same thing happens for thermal fluctuations: when the temperature is large, the system is in the symmetric phase $m=0$ and as temperature decreases it crosses into the ordered phase $m\neq0$.  The details of the first order phase transitions are sensitive to the value of the penalty strength $\gamma$, which we we analyze next.

For $\gamma < \gamma_c$, there is a branch point and three phase transition lines are connected there.  For example, in Fig.~\ref{PLpmulRedup4}, such a branch point can be observed for $\gamma = 0.5$ at $(T,\Gamma) = (0.02, 1.8)$ and for $\gamma = 0.7$ at $(T, \Gamma) = (0.078,2.096)$ [at these points, $F(m=0)$, $F(m_{\text{small}})$, and $F(m_{\text{large}})$ all take the same value at the critical point $\Gamma=\Gamma_c$. See Fig.~\ref{branchfreeg07}];
let us denote such ($\gamma$-dependent) branching points by $(T_{\text{branch}},\Gamma_{\text{branch}})$.  The phase transition line $(T<T_{\text{branch}},\Gamma>\Gamma_{\text{branch}})$ indicates the transition between $m=0$ and $m=m_{\text{small}}$. Likewise,
the phase transition line $(T<T_{\text{branch}},\Gamma=\Gamma_{\text{branch}})$ indicates the transition between $m_{\text{small}}$ and $m=m_{\text{large}}$, and the phase transition line $(T>T_{\text{branch}},\Gamma<\Gamma_{\text{branch}})$ indicates the transition between $m=0$ and $m=m_{\text{large}}$.  This branching behavior is a generic feature for $p\geq 3$, and we show in Fig.~\ref{PLpmulRedu-a} an example for $p = 5$ with $\gamma \leq \gamma_c$.

\begin{figure}[t]
\includegraphics[scale=0.75]{branchfreeg07.pdf}
\caption{ Free energy at the branching point for $\gamma=0.7$. At $T=0.078$ and $\Gamma=2.096$, the free energy possesses three minima
at $m=0$, $m=m_{\text{small}}$, and  $m=m_{\text{large}}$.
 }
\label{branchfreeg07}
\end{figure}

\subsubsection{Free energies along each phase transition line}

In Fig.~\ref{on the transition line}, we plot the free energies \emph{along} each phase transition line.
Figure~\ref{lowT-highG} shows the free energy for $(T<T_{\text{branch}},\Gamma >\Gamma_{\text{branch}})$.  As the temperature decreases the critical value of $\Gamma$ becomes larger, and the free energy barrier becomes smaller.  The phase transition effectively disappears at very low temperatures, which is consistent with the fact that there is no corresponding phase
transition at $T=0$.

Figure~\ref{p4T0025g0a}  shows the free energy for $(T<T_{\text{branch}},\Gamma_{\text{branch}}=\Gamma)$.  This transition exists at $T=0$, and the phase transition line at $T>0$ continuously connects to the transition line at $T=0$.  The critical value of $\Gamma$ does not change within numerical precision.

Figure~\ref{highTbranch} shows the free energy for $(T>T_{\text{branch}},\Gamma<\Gamma_{\text{branch}})$.  The critical value of $\Gamma$ becomes smaller as the temperature increases. Above a $\gamma$-dependent critical temperature, the global minimum of the free energy is at $m = 0$, so the state is in the symmetric phase even when there are no quantum fluctuations ($\Gamma=0$).  This state can therefore not recover the solution to the optimization problem.   As can be observed in Fig.~\ref{PLpmulRedup4}, the value of this critical temperature increases with increasing $\gamma$.  We provide additional analysis of the free energy in Appendix \ref{sec:extraF}.

\ignore{
This means that above this temperature the quantum annealing process results in the wrong answer. \red{Can we fix this by increasing $\gamma$? i.e., does a higher $\gamma$ lead to a higher $T_{\text{branch}}$? Or does the $T=0$ result that a penalty larger than $\gamma=0.8$ doesn't help tell us that, at any $T$, increasing $\gamma$ beyond 0.8 doesn't help?}
\green{The value of $T$-intercept in Fig.~\ref{PLpmulRedup4} increases as $\gamma$ becomes large. Namely  the phase transition  exists even at a large value of $T$ as long as $\gamma$ is taken to be large enough. Therefore, the quantum state can be in the correct phase at the end of the evolution ($\Gamma=0$).  The same feature appears in the $p=2$ case (Fig.~\ref{gammaGamma p=2}).
When $\gamma\ge0.8$ there is only one phase transition.
yes the $T$-intercept increases as $\gamma$ increases. when $\gamma$ is bigger than 0.8, the branch structure disappears and therefore
we cannot get a benefit of it. however, we still have a possibility to get the correct answer by increasing $\gamma$ since it prevents the thermal fluctuation, in some sense.}
}

\section{QAC with a transverse field on the penalty qubits}
\label{transverse field in the penalty}

Recall that all the experiments conducted to date on QAC \cite{PAL:13,PAL:14,Vinci:2015jt,Mishra:2015} involve a transverse field on the penalty qubits. In this section we analyze this scenario, defined by the total Hamiltonian that includes the ``penalty transverse field", namely the sum of Eqs.~\eqref{eq:V} and \eqref{hamil-QAC}:
\begin{align}
H =&-{N}\sum_{c=1}^{C}\left({1\over N}  \sum_{i=1}^{N}\sigma^{z}_{ic}   \right)^{p}
-\Gamma\sum_{c=1}^{C}\sum_{i=1}^{N} \sigma^{z}_{ic}
-\epsilon {C} \Gamma \sum_{i=1}^{N} \sigma^{x}_{i0} \notag \\
&-\gamma \sum_{c=1}^{C}\sum_{i=1}^{N} \sigma^{z}_{ic}\sigma^{z}_{i0}\ .
\label{full trans penalty hamil}
\end{align}

Beyond the direct connection to experiments, the addition of the transverse field should make the penalty qubits, and as a consequence the problem qubits, fluctuate more easily, and it is interesting to study whether this helps the QA process cross phase transitions more efficiently.

When a transverse field on the penalty qubits is included, the $C$ copies of the problem qubits and the penalty qubit are no longer effectively decoupled. This means that to understand the effect of the penalty qubits we need to study a $2^{C+1}$-dimensional Hilbert space instead of a $2$-dimensional one.

\subsection{Second order phase transition: $p=2$}

We show in Appendix~\ref{sec:TransverseFieldExtra} that after the Suzuki-Trotter procedure, the free energy at low temperature ($\beta \gg 1$) can be written as
\begin{eqnarray}
F/C=(p-1)m^p-{1\over C\beta}\ln\left[ \mathop{\mathrm{Tr}}\exp(\beta H_\mathrm{eff})  \right] \ ,
\label{trans penalty partition func}
\end{eqnarray}
where $H_{\mathrm{eff}}$ is an effective Hamiltonian given by
\begin{equation}
H_{\mathrm{eff}} = -(p m^{p}\sigma^{z}_{c}+\gamma
\sigma^{z}_{c}\sigma^{z}_{0}
+ { \Gamma}  \sigma^{x}_{c}+{\epsilon \Gamma } \sigma^{x}_{0}) \ .
\label{eq:Heff}
\end{equation}
The term $\mathop{\mathrm{Tr}}\exp(\beta H_{\mathrm{eff}})$ can be evaluated by numerically diagonalizing the  $2^{C+1}\times 2^{C+1}$ matrix.

The phase diagram in the $(\Gamma,T)$ plane is shown for $p=2$ in Fig.~\ref{transp2-a} for various values of $\gamma$ and $\epsilon$.
The phase transition line separates the symmetry-broken phase $m\neq0$ (below the lines)
from the symmetric phase $m=0$ (above the lines).
As in the case without a penalty transverse field studied in the previous section, there exists a critical temperature above which the state is in the symmetric phase for all values of $\Gamma$ even for finite $\epsilon$.
However, unlike the $\epsilon = 0$ case, we find that $\Gamma_c$ approaches a finite value in the low temperature limit for finite $\epsilon$.  The phase transition lines at finite $\gamma$ approach that of $\gamma=\epsilon=0$ as $\epsilon$ increases. Thus, the penalty transverse field counterbalances the effect of the penalty term $\gamma$, as it enlarges the phase space of the symmetric phase with $m=0$, where the system fails to solve the optimization problem.

The location of the phase transition depends on the value of $C$. In Fig.~\ref{diffCp2g05}, we compare the phase transition lines for $C=2$ and $3$. While the qualitative features
for the two $C$ values are the same, the symmetry-broken phase is enlarged as $C$ increases for both the $\epsilon=0$ and $\epsilon=1$ cases. Thus, increasing $C$ acts productively and enhances the phase where the system solves the optimization problem.

\begin{figure*}[t]
\subfigure[]{ \includegraphics[scale=0.75]{transp2.pdf}  \label{transp2-a}}\quad \quad \quad \quad \quad \quad
\subfigure[]{ \includegraphics[scale=0.75]{diffCp2g05.pdf} \label{diffCp2g05}}
\caption{(a) Phase diagram in the presence of a penalty transverse field. Shown are the
$p=2$ phase transition lines with $C=3$ for different values of $\gamma$ and $\epsilon$.
(b) Comparison of $p=2$ phase transition lines with $C=2$ and $C=3$
for $\gamma=0.5$ and $\epsilon=0$ and $1$.  The space to the right of the curves corresponds to the paramagnetic or symmetric phase, while the space to the left of the curves corresponds to the ferromagnetic or symmetry-broken phase.}
 \label{transp2}
\end{figure*}

\begin{figure}[t]
\includegraphics[scale=0.75]{transg05p4.pdf}
\caption{Phase diagram for $p=4$ in the presence of a penalty transverse field.  The space to the right of the curves corresponds to the paramagnetic or symmetric phase, while the space to the left of the curves corresponds to the ferromagnetic or symmetry-broken phase.  The penalty coupling is chosen to be $\gamma=0.5$ for all curves.}
 \label{transg05p4}
\end{figure}

\begin{figure}[t]
\includegraphics[scale=0.75]{compF.pdf}
\caption{Free energies $F$ with and without the penalty transverse field at the critical points. Parameters are chosen to be $p=4,\gamma=0.5,T=0.03$. The blue line is for  $\epsilon=0,\Gamma=1.85$, and the red line is for $\epsilon=0.1,\Gamma=1.76$. }
\label{compF}
\end{figure}

\begin{figure*}[t]
\subfigure[]{     \includegraphics[scale=0.6]{Plotoptb40e1gG.pdf}    \label{Plotoptb40e1gG} }
\subfigure[]{     \includegraphics[scale=0.6]{Plotoptb40e1gm.pdf}   \label{Plotoptb40e1gm} }
\subfigure[]{     \includegraphics[scale=0.6]{Plotoptb40e1gF.pdf}   \label{Plotoptb40e1gF} }
\caption{ (a) Critical value of $\Gamma$ as a function of the penalty coupling $\gamma$.
(b) $m_{\text{large}}$ as a function of $\gamma$.
(c) the barrier height $\Delta F$  as a function of $\gamma$.
In all panels $p=4$,
$T=0.025$, and $\epsilon=1$.}
\end{figure*}

\subsection{First order phase transitions: $p\ge3$}

The phase diagram in the $(\Gamma,T)$ plane for various values of $\epsilon$ is shown in Fig.~\ref{transg05p4}, for $\gamma=0.5$.
For sufficiently small $\epsilon$, the phase diagram is similar to that of $\epsilon=0$: $m_{\text{small}}$ still exists and can be the lowest free energy state for sufficiently low temperatures. Therefore there are two phase transitions, one from $m=0$ to $m_{\text{small}}$ and the other from $m_{\text{small}}$ to $m_{\text{large}}$.
As the temperature increases, $m_{\text{small}}$ goes to $0$ and above a certain branching point temperature there is only one phase transition from $m=0$ to $m_{\text{large}}$.
At $\epsilon=0.014$ (not shown), this branching point disappears, and there is only one phase transition from $m=0$ to $m_{\text{large}}$.

In order to understand the disappearance of the phase transition as $\epsilon$ is increased, we show a comparison of the free energies for $\epsilon = 0$ and $\epsilon \neq 0$ at their respective  critical $\Gamma$'s in Fig.~\ref{compF}.
For the choice of parameters shown, there are three local minima for $\epsilon=0$.  As we noted in the previous section, there are correspondingly two phase transitions, one between $m = 0$ and $m_{\text{small}}$ followed by a transition between $m_{\text{small}}$ and $m_{\text{large}}$.
By increasing $\epsilon$, the free energy barrier between $m = 0$ and $m_{\text{large}}$ is raised, and as a consequence the local minimum $m_{\text{small}}$ disappears for sufficiently large $\epsilon$, as shown in Fig.~\ref{compF} for $\epsilon=0.1$.

Recall that as we discussed in Sec.~\ref{sec:1PTp>2}, the splitting of a first order phase transition into multiple smaller phase transitions is beneficial from the QA point of view.
Further recall that the energy gap between the ground state and the excited state decreases when the potential barrier becomes larger [Eq.~\eqref{eq:gap-F}]. This means that the transverse field decreases the energy gap at the phase transition. Both effects thus adversely affect the success rate of QAC in comparison to having no transverse penalty.

In Appendix~\ref{app:pert-th} we supplement the analysis presented here with perturbation theory in $\epsilon$, which allows us to show analytically how introducing the penalty transverse field removes the local minimum at $m_{\text{small}}$.

\subsection{Optimal value of $\gamma$}

The experimental results reported in Refs.~\cite{PAL:13,PAL:14,Vinci:2015jt,Mishra:2015,vinci2015nested} all included a penalty transverse field and showed a marked improvement in performance relative to the unencoded case. These results required the optimization of the penalty strength in order to maximize the success probability of QAC after decoding, although an optimal penalty strength was also observed when maximizing the physical (i.e., encoded, but undecoded) ground state probability.  Here we do not include a decoding step and instead study the phase transition as a function of $\gamma$ for a fixed value of $\epsilon$ in order to study whether any features of the free energy may indicate the presence of an optimal $\gamma$ value for QAC.

We display the critical value of $\Gamma$, denoted $\Gamma_c$, as a function of $\gamma$ for $\epsilon=1$ in Fig.~\ref{Plotoptb40e1gG}.  $\Gamma_c$ increases monotonically with $\gamma$, so the phase transition happens earlier in the evolution.  (Note that for the value of $\epsilon$ relevant to the experiments, there is only a single phase transition.)
On the other hand, both the free energy height and $m_{\text{large}}$ (which characterizes the free energy barrier width) are non-monotonic functions of $\gamma$ at the critical point, as shown in Figs.~\ref{Plotoptb40e1gm} and \ref{Plotoptb40e1gF}.  The free energy barrier height decreases for $\gamma\le 5$ and increases for $\gamma > 5$.  The barrier width decreases monotonically for $\gamma<6$ but increases monotonically for $\gamma\ge 6$.
Since the barrier height and width control the behavior of the instanton connecting the two free energy minima and hence the tunneling rate at the phase transition point (more details are provided in Appendix \ref{app:Instanton}), the presence of a minimum as a function of $\gamma$ that takes a value smaller than that at $\gamma = 0$ is strong evidence in favor of an optimal $\gamma$ for QAC.
While the position of the minima of the barrier height and width do not coincide precisely, they are broad minima, and it is possible that their combined effect is responsible for the appearance of the optimal $\gamma$ observed for the undecoded ground state in experiments.

\section{Conclusions}
\label{conc}

Building on the methods and results of Ref.~\cite{MNAL:15}, we have extended the mean-field analysis of quantum annealing correction to include the effects of temperature and of a transverse field on the penalty qubits. We find that the effects of a finite temperature $T$ on QA manifests themselves in two different but connected ways, both of which are detrimental. First, the symmetric phase, where quantum annealing fails to find the ground state, is enlarged in the $(\gamma,T)$ phase space, where $\gamma$ is the penalty strength. Second,  the free-energy landscape is modified in such a way that the barrier between the two minima at the phase transition is increased.  This implies that for sufficiently large temperatures the two first-order phase transitions present for the $p>2$ case are replaced by one first-order phase transition with a larger free energy barrier. For first order phase transitions, larger barriers imply smaller tunneling rates between the two minima, which means that the probability of finding the ground state is lowered at fixed annealing time. In fact, the energy gap between the ground state and excited states is a function of the potential barrier, which appears in the exponent for a model with a first order transition [see Eq.~\eqref{eq:gap-F}]. Thus the gap size shrinks exponentially in the free energy barrier height and width.
Clearly, multiple phase transitions with small barriers are preferable to a single transition with a large barrier: in the former case the total annealing time is $t_a^{\text{small}} \sim \max_i 1/\Delta_i  \sim \max_i \exp(\Delta m \Delta F_i^{\text{small}} N)$, while in the latter
$t_a^{\text{large}} \sim 1/\Delta \sim  \exp(\Delta m \Delta F^{\text{large}}N)$, and $t_a^{\text{small}} \ll t_a^{\text{large}}$ provided $\max_i \Delta F_i^{\text{small}} \ll \Delta F^{\text{large}}$.

We have shown that the introduction of a transverse field on the penalty qubit, for a fixed value of $\gamma$, makes the critical value of the annealing parameter $\Gamma$ smaller for $p=2$, and enlarges the potential barrier for $p\ge2$. In this sense one might say that the penalty transverse field favors the symmetric phase with $m=0$.

Both the temperature and the additional transverse field favor fluctuations (either of thermal or quantum nature)  that facilitate the appearance of the symmetric phase, so part of our results have an intuitive explanation. On the other hand, intuitively, the transverse field should facilitate the annealing process by inducing quantum fluctuations of the penalty qubit. However, we find that the transverse field tends to reduce the tunneling rate at the phase transitions, a counter-intuitive results. A possible resolution of this puzzle may be that the free energy includes entropy considerations that may not be relevant in the dynamics. Preliminary analysis of dynamics suggest that the transverse field on the penalty qubits accelerates relaxation to equilibrium, possibly by providing quantum transition paths that do not exist in classical dynamics.  It is an important future problem to clarify the balance (or trade-off) between this dynamics and the equilibrium effects associated with the transverse field on the penalty qubit.

Finally, our analysis of the free energy as a function of $\gamma$ revealed a minimum for both the free energy width and barrier height separating minima at the phase transition.  This provides a possible explanation for the observed experimental results reported in Ref.~\cite{PAL:13} of an optimal $\gamma$ for the undecoded (``physical") ground state.
We postpone the inclusion of decoding to future work \cite{Matsu2016-part2}, which will also include disordered spin models, such as the quantum Hopfield model analyzed for $T=0$ in Ref.~\cite{MNAL:15}.

\begin{acknowledgments}
The work of H.N. was funded by the ImPACT Program of Council for Science, Technology and Innovation, Cabinet Office, Government of Japan, and by the JPSJ KAKENHI Grant No. 26287086. The work of W.V., T.A., and D.L. was supported under ARO Grant No. W911NF- 12-1-0523, ARO MURI Grants No. W911NF-11-1-0268 and No. W911NF-15-1-0582, and NSF Grant No. INSPIRE-1551064.
\end{acknowledgments}

redpajama_set_name: RedPajamaArXiv