# Quantum Computation by Cooling

Jaeyoon Cho<EMAIL_ADDRESS>Department of Physics and Research Institute of
Natural Science, Gyeongsang National University, Jinju 52828, Korea

###### Abstract

Adiabatic quantum computation is a paradigmatic model aiming to solve a
computational problem by finding the many-body ground state encapsulating the
solution. However, its use of an adiabatic evolution depending on the spectral
gap of an intricate many-body Hamiltonian makes its analysis daunting. While
it is plausible to directly cool the final gapped system of the adiabatic
evolution instead, the analysis of such a scheme on a general ground is
missing. Here, we propose a specific Hamiltonian model for this purpose. The
scheme is inspired by cavity cooling, involving the emulation of a zero-
temperature reservoir. Repeated discarding of ancilla reservoir qubits
extracts the entropy of the system, driving the system toward its ground
state. At the same time, the measurement of the discarded qubits hints at the
energy level structure of the system as a return. We show that quantum
computation based on this cooling procedure is equivalent in its computational
power to the one based on quantum circuits. We then exemplify the scheme with
a few illustrative use cases for combinatorial optimization problems. In the
first example, the cooling is free from any local energy minima, reducing the
scheme to Grover’s search algorithm with a few improvements. In the second
example, the cooling suffers from abundant local energy minima. To circumvent
this, we implant a mechanism in the Hamiltonian so that the population trapped
in the local minima can tunnel out by high-order transitions. We support this
idea with a numerical simulation for a particular combinatorial optimization
problem. We also discuss its application to preparing quantum many-body ground
states, arguing that the spectral gap is a crucial factor in determining the
time scale of the cooling.

##  I Introduction

Identifying the ground states of quantum many-body Hamiltonians and
understanding their characteristics are fundamental in physics. The ground
states encode the spectral properties of the Hamiltonian [1, 2, 3, 4, 5, 6, 7]
and represent the essential quantumness of the system. The latter becomes
particularly evident in gapped systems, in which the ground state
predominantly determines the entire properties at sufficiently low
temperature. This lays the foundation for various exotic quantum phenomena,
such as quantum Hall effects and superconductivity [8].

Computing many-body ground states is extremely hard in general: for classical
Hamiltonians, it falls into the NP-hard complexity class, and for quantum
Hamiltonians, it is classified as QMA-hard [9, 10, 11]. The difficulty arises
mainly from the geometric frustration, i.e., the stark mismatch between local
and global energy minima. The problem is combinatorial in nature: one needs to
find the optimal configurations of data among exponentially many, mutually
conflicting ones. This is indeed the core challenge of combinatorial
optimization problems [12]. It is well-established that combinatorial
optimization problems can be reduced to the task of finding the ground states
of Ising-like spin models [13, 14, 15].

It is widely believed that quantum computers are not universally efficient in
solving general ground-state problems, even for classical Hamiltonians.
Nonetheless, we still need to find out specific classes of such problems that
benefit from quantum computation and are yet practically useful. Also, there’s
a need to devise diverse quantum algorithms for them, each having its unique
advantages. We have a number of tools available for such purposes [16, 17, 18,
19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29] (Ref. [29] contains a nice summary
of earlier schemes). The most prominent is adiabatic quantum computation (AQC)
[18, 19, 20]. The AQC exploits the adiabatic evolution of the instantaneous
ground state when the Hamiltonian is varied. The time scale of the operation
is thus governed by the minimal spectral gap during the evolution. However,
analyzing the spectral gap is extremely difficult, leaving the performance of
AQC largely unknown. There are also hybrid approaches, such as quantum
approximate optimization algorithms (QAOA) [22, 23, 21] and variational
quantum eigensolvers (VQE) [24, 25, 26], aided by classical optimization
subroutines.

As mentioned, the difficulty in analyzing AQC arises as the initial and final
Hamiltonians intermingle. On the other hand, the properties of the final
Hamiltonian alone can be largely unveiled, even though its ground state
remains unknown. Given this, it is natural to consider schemes to directly
cool the final Hamiltonian system to its ground state. While earlier schemes
based on dissipative engineering [27, 28, 29] seem to achieve this goal, a
closer inspection reveals that they actually lack desirable properties as a
cooling method. To clarify this, it is instructive to discuss classical and
quantum Hamiltonians separately. By the former, we mean those Hamiltonians
diagonalized in the computational basis.

For classical Hamiltonians, the earlier dissipative schemes are reduced to a
classical random search. There are a few fundamental reasons. They implement a
completely-positive trace-preserving (CPTP) map that transforms the state
$\rho$ to $\sum_{k}E_{k}\rho E_{k}^{\dagger}$ [30]. Here, each Kraus operator
$E_{k}$ directly accesses the associated local part of the system, driving it
into a certain direction. However, as the energy of the whole system is a
global quantity, determining the optimal direction based solely on a small
part is not possible (note that this was the very origin of the geometric
frustration, rendering the problem intractable). For this reason, the state is
randomized when the measurement projects the state into an undesired subspace.
Note, however, that this entire process is essentially equivalent to a mere
random guess. Furthermore, for classical Hamiltonians, they do not involve any
operations in non-computational bases. This means that they are, in fact,
identical to classical probabilistic models. In the case of quantum
Hamiltonians, the problem is more involving: one needs to find an appropriate
basis containing the ground state. This is the place where the above CPTP map
comes into play. Apart from the role of fixing the basis, however, the above-
mentioned limitations persist.

Simply put, both cooling and heating coexist in the above-mentioned schemes. A
genuine cooling scheme should rely on quantum transitions that take place
exclusively in the direction of lowering energy. It is important to understand
that a heating-prevention mechanism requires an external agent, which globally
accesses the system, gathers its energy, and relaxes it into a Markovian
reservoir. This process is exactly provided by cavity cooling methods [31].
This paper aims at materializing this concept as a general quantum computation
model and discuss its efficiency in some illustrative scenarios. Our model can
be paralleled with AQC for their similarity in motivation. On the other hand,
unlike AQC, our model exploits a non-unitary process. For brevity, we will
refer to our model as cooling-based quantum computation (CQC) hereafter. A
recent work [32] shares a similar motivation with ours. However, their scheme
is far from being general, focusing only on a particular spin model for a
single problem, and uses a unitary evolution throughout, lacking some
important ingredients and favorable features of cooling.

Being a dissipative process, CQC inherits the intrinsic advantages of the
earlier dissipative schemes, alleviating the demand of precise system controls
to some extent. On top of this, CQC takes true quantum advantages. In fact, we
show that CQC is equivalent to quantum circuit models in terms of
computational power. This argument is similar to the established one regarding
the computational equivalence between AQC and quantum circuit models [19]. All
three frameworks are thus computationally equivalent. However, this assertion
needs to be interpreted with care. For instance, the equivalence of AQC to CQC
is established by translating the unitary evolution of AQC into a quantum
circuit, which is then converted into a Hamiltonian for CQC. However, this
resulting Hamiltonian differs from the original problem Hamiltonian of the
AQC. It is an open question whether the feasibility of ground-state
preparation by AQC implies that of the same Hamiltonian by CQC, and vice
versa.

Any ground-state preparation scheme, including AQC, inevitably suffers from
the issue of local energy minima [14, 33, 34]. In CQC, one can design
tunneling transitions out of local minima if the information is given on their
nature. This flexibility also constitutes the advantage of CQC. In practice,
one could try various transition terms in the Hamiltonian, while observing the
occurrence of the transition by monitoring cavity photons. This, in turn,
provides a method to inspect the energy-level structure of the Hamiltonian.
For example, the presence or absence of a finite spectral gap above the ground
state could be inspected for unsolvable Hamiltonians.

In this work, much of our focus will be placed on CQC for combinatorial
optimization problems, which have favorable features for CQC and allow for the
analytical treatment. We consider two extreme cases. The first case is free
from local energy minima, but the transition rate is superpolynomially small
in the system size. This case turns out to be equivalent to Grover’s quantum
search algorithm, aside from some advantages that CQC brings. The second case
is an opposite limit, wherein the transition rate is maximized, but local
energy minima begin to pose challenges. The local minima can be overcome by
introducing high-order tunnel-out transitions. We perform the numerical
simulation for a particular combinatorial optimization problem to support this
idea. Finally, we briefly discuss the case of quantum Hamiltonians. This case
is heavily system-dependent and more complicated to analyze. We argue that the
spectral gap above the ground state is a crucial factor in determining the
time scale of the cooling. This is a natural consequence of the energy-time
uncertainty principle.

##  II Notation and working principles

Consider an $N$-qubit system described by Hamiltonian

$H_{P}=\sum_{z=0}^{2^{N}-1}E(z)|z\rangle_{P}\langle z|,$ (1)

where $E(z)\leq E(z^{\prime})$ for $z<z^{\prime}$. Let us call $H_{P}$ a
problem Hamiltonian. We aim to find the ground state $|0\rangle_{P}$.
Transitions among the energy levels $|z\rangle_{P}$ are allowed by introducing
in the Hamiltonian what we call a transition term $H_{T}$, which does not
commute with $H_{P}$. $H_{T}$ should be designed to suit the needs of the
given problem. We will consider two simple examples below. Here, we assume the
energy level spacings of $H_{P}$ are characterized by an energy scale
$\Delta>0$, and so is the norm $\|H_{T}\|$. Our aim is to introduce a
parameter $0<\lambda\ll\Delta$ to treat $\lambda H_{T}$ as a perturbation to
$H_{P}$.

If we consider the transition problem described by Hamiltonian $H_{P}+\lambda
H_{T}$, the transition from $|z\rangle$ to $|z^{\prime}\rangle$ is allowed
only when $|E(z)-E(z^{\prime})|\lesssim|\langle z^{\prime}|\lambda
H_{T}|z\rangle|$, where the influence of the degeneracy is ignored. In order
to ensure $E(z^{\prime})<E(z)$, we introduce cavity field $c_{m}$ with
resonant frequency $\omega_{m}\gg|\langle z^{\prime}|\lambda H_{T}|z\rangle|$
and couple it to the transition. Here, the subscript $m$ is the index for
different cavities. Let us denote by $|\cdot\rangle_{m}$ the photon number
state of the cavity. If the cavity is initially empty, the transition from
$|z\rangle_{P}|0\rangle_{m}$ to $|z^{\prime}\rangle_{P}|1\rangle_{m}$ is
allowed only when $E(z^{\prime})\simeq E(z)-\omega_{m}$, providing a mechanism
to prevent heating.

Introducing $M$ different cavity modes, our final Hamiltonian reads

$\begin{split}H&=H_{P}+\sum_{m=1}^{M}\omega_{m}c_{m}^{\dagger}c_{m}\\\
&\quad+\lambda
H_{T}\otimes\left[a_{0}I+\sum_{m=1}^{M}(c_{m}+c_{m}^{\dagger})\right].\end{split}$
(2)

Here, $a_{0}\in\\{0,1\\}$ determines whether the transitions preserving the
cavity photon numbers are allowed. This term helps the state escape from local
minima through high-order transitions. In practice, it is generally enough to
restrict the maximum number of photons in each cavity to one. In this case,
$M$ cavity modes can be simulated with $M$ qubits.

Initially, the system is prepared in state
$2^{-N/2}\sum_{z=0}^{2^{N}-1}|z\rangle_{P}\bigotimes_{m=1}^{M}|0\rangle_{m}$.
A single cycle of cooling is performed by unitarily evolving the system
according to Hamiltonian (2) for an appropriate duration of time, measuring
the cavity states, and resetting every cavity to the vacuum state. Here, the
measurement of the cavity photon is not mandatory, but it would reveal some
information on the current state and the internal transition structure of the
problem Hamiltonian.

The computation is done by repeating this cycle. The required number of cycles
depends on the problem and strategy. One possible strategy is to repeat until
the cavity photon is not detected for an enough number of cycles. This signals
with high probability that the system has reached either the ground state or
local minima. For NP problems that are guaranteed to have at least one
solution, deciding which is the case is straightforward. Otherwise, one may
repeat the same computation to increase the confidence. Given that the unknown
ground state is not verifiable in general, the decision is probabilistic after
all.

We will implicitly assume that the evolution by the Hamiltonian (2) is
simulated on a universal quantum computer, which is reasonable given the
complexity of the Hamiltonian. In our analysis below, the polynomial overhead
associated with this implementation is not taken into account.

##  III Equivalence to circuit models

Figure 1: The transition diagram into which a quantum circuit is converted for
CQC. $|\phi_{t}\rangle_{P}$, $|t\rangle_{C}$, and $|\cdot\rangle_{1}$ denotes,
respectively, the state of the quantum circuit at the $t$-th time step, the
clock state to label the time step, and the number state of the cavity.
$\Delta$ is the energy difference between the adjacent levels and $\lambda$ is
the Rabi frequency of the designated transition. The wavy lines represent the
transition after detecting and clearing the cavity photon.

Ref. [19] shows that AQC is equivalent to the quantum circuit model in
computational power up to polynomial overhead. The forward direction of the
equivalence is straightforward because the entire procedure of AQC is a
unitary transformation, which can be simulated efficiently in quantum
circuits. Showing the other direction relies on the clock state
$|t\rangle_{C}$ tagged to the state at the $t$-th time step of the quantum-
circuit computation.

A similar equivalence relation can be shown for CQC. Again, showing that CQC
can be simulated efficiently in a quantum circuit is straightforward. We thus
focus on the other direction. Suppose a quantum algorithm is run on a quantum
circuit in $T$ time steps, where $U_{t}^{P}$ is applied to the qubits at the
$t$-th time step. Let $|\phi_{t}\rangle_{P}\equiv U_{t}^{P}U_{t-1}^{P}\cdots
U_{1}^{P}|\phi_{0}\rangle_{P}$ be the state right after applying $U_{t}^{P}$,
and tag this state with the clock state as
$|\phi_{t}\rangle_{P}|t\rangle_{C}$. The idea is to get
$|\phi_{t}\rangle_{P}|t\rangle_{C}$ transformed into
$|\phi_{t+1}\rangle_{P}|t+1\rangle_{C}$ in the course of an energy-lowering
transition. This is enabled by choosing the terms in Hamiltonian (2) as

$\displaystyle H_{P}$
$\displaystyle=-\sum_{t=0}^{T}t\Delta|t\rangle_{C}\langle t|,$ (3)
$\displaystyle H_{T}$
$\displaystyle=\sum_{t=0}^{T-1}(U_{t+1}^{P}\otimes|t+1\rangle_{C}\langle
t|+\text{H.c.}),$ (4)

where the parameter $\Delta>0$ is an arbitrary energy scale, and the other
parmeters are chosen as $M=1$, $\omega_{1}=\Delta$, and $\alpha_{0}=0$. If the
initial state is chosen to be
$|\phi_{0}\rangle_{P}|0\rangle_{C}|0\rangle_{1}$, the entire transition
dynamics is restricted to a subspace spanned by
$\\{|\phi_{t}\rangle_{P}|t\rangle_{C},0\leq t\leq T\\}$, as depicted in Fig.
1. It can be seen that the average time needed to reach the ground state,
which is the final state of the quantum circuit, is polynomial in $T$. As the
transition rate $\lambda$ is restricted by the energy gap $\Delta$, the
computation time is $\mathcal{O}(T/\Delta)$.

##  IV Combinatorial optimization by cooling-based quantum computation

###  IV.1 Notation

Consider combinatorial optimization problems that aim to find the optimal
solutions from a set of $2^{N}$ possible configurations represented by $N$-bit
string $z\equiv z_{1}z_{2}\cdots z_{N}$. The optimality of each configuration
is evaluated by a non-negative cost function $E(z)$. The objective is to
identify configurations $z$ that minimize $E(z)$. This problem is
straightforwardly translated into the ground-state finding problem, where the
cost function $E(z)$ is identified with the energy eigenvalue in Hamiltonian
(1). Here, we set $E(z)$ as integer multiples of a parameter $\Delta>0$. For
example, for boolean satisfiability (SAT) problems, $E(z)$ is the number of
unsatisfied clauses by the configuration $z$ [12]. The cavity frequencies in
Hamiltonian (2) can then be chosen as integer multiples of $\Delta$. By
choosing $M$ to be the maximum of $E(z)$, all possible transitions in the
problem Hamiltonian can be coupled to a cavity transition.

###  IV.2 Reproduction of Grover’s search algorithm

Grover’s quantum search algorithm is paradigmatic in quantum information
theory [35, 30]. It can be recast as an algorithm to find the zeros of a
binary function $f(z)\in\\{0,1\\}$ from the set of $2^{N}$ configurations $z$.
Provided that $f(z)$ is computed only by an external agent, called the oracle,
Grover’s algorithm requires $\mathcal{O}(2^{N/2})$ oracle calls to find the
solution, while the number becomes $\mathcal{O}(2^{N})$ for the best classical
algorithm. The quadratic speedup of Grover’s algorithm is proven to be optimal
unless the structure of the function $f(z)$ is exploited somehow [36, 37, 38].

To perform an analogous task in CQC, we adjust the Hamiltonian (2) as

$\begin{split}H&=\sum_{z=0}^{2^{N}-1}\Delta f(z)|z\rangle_{P}\langle z|+\Delta
c_{1}^{\dagger}c_{1}\\\
&\quad+\lambda\bigotimes_{i=1}^{N}\frac{I_{i}+X_{i}}{2}\otimes(c_{1}+c_{1}^{\dagger}),\end{split}$
(5)

where $I_{i}$ and $X_{i}$ denote the identity and Pauli $X$ operators acting
on qubit $i$, respectively. Let $n_{0}$ be the number of zeros of $f(z)$. For
the initial state $2^{-N/2}\sum_{z}|z\rangle_{P}|0\rangle_{1}$, the problem
Hamiltonian $H_{P}$ effectively becomes two-dimensional, where the Hilbert
space is spanned by

$|\phi_{0}\rangle_{P}=\frac{1}{\sqrt{n_{0}}}\sum_{f(z)=0}|z\rangle_{P}$ (6)

and

$|\phi_{1}\rangle_{P}=\frac{1}{\sqrt{2^{N}-n_{0}}}\sum_{f(z)\not=0}|z\rangle_{P}.$
(7)

In this basis, the off-diagonal element becomes
${}_{P}\langle\phi_{0}|\lambda\bigotimes_{i}\frac{I_{i}+X_{i}}{2}|\phi_{1}\rangle_{P}\simeq\lambda
n_{0}^{1/2}2^{-N/2}$. The computation time is thus
$\mathcal{O}(\sqrt{2^{N}/n_{0}})$, identical to that of Grover’s algorithm.
One advantage of CQC implementation is that the end of computation is signaled
by a detection of the cavity photon. This is especially beneficial when the
number of solutions $n_{0}$ is unknown.

In this example, the problem Hamiltonian has only two energy levels
corresponding to the solution states and the rest. A naturally following
question is if the performance can be improved when the problem Hamiltonian
has more than two energy levels. It can be seen that with the transition term
chosen above, more energy levels just make the computation slower. To see
this, note that the quadratic speedup comes from the collective transition,
the rate of which increases with the degeneracy of the energy level. The
increase in the number of energy levels leads to a decrease in the degeneracy
of each level, which diminishes the collective effect. Moreover, it results in
an increased number of transitions required to reach the ground state.

###  IV.3 Alternative approach

In the previous example reproducing Grover’s search algorithm, the transition
term generates an all-to-all interaction with the identical transition
strength. This makes the problem Hamiltonian utterly featureless except for
each energy level having a different degeneracy. While the absence of any
local energy minimum is advantageous, the transition strength decreases
superpolynomially with the number of qubits.

In this subsection, we consider an opposite limit, where the transition term
is given by

$H_{T}=\sum_{i=1}^{N}X_{i}.$ (8)

The off-diagonal element ${}_{P}\langle z|H_{T}|z^{\prime}\rangle_{P}$ is then
non-vanishing and equals one, independently of $N$, only when the Hamming
distance between $z$ and $z^{\prime}$ is one. While the transition strength is
maximum, local energy minima now become an issue. As the distance between two
configurations is at most $N$, any state $|z\rangle_{P}$ can reach the ground
state in at most $N$ transitions in principle. However, we do not know a
general rule for every state to take the right path. For this reason, we take
the direction of lowering the energy, even though it does not necessarily
coincide with the direction of approaching the ground state. This mismatch is
the origin of local energy minima.

Note that every state $|z\rangle_{P}$ is linked to $N$ different states by
transition. It is instructive to envisage this as an $N$-regular graph with
$2^{N}$ vertices. Each vertex is endowed with a potential determined by the
problem Hamiltonian, and the transition occurs along the edges toward the
direction of not increasing the potential. Once the population is trapped in a
local potential minimum, a high-order transition is needed to get out of it.

To elucidate this mechanism, consider an $n$-th order transition through the
sequence
$|z_{0}\rangle_{P}\rightarrow|z_{1}\rangle_{P}\rightarrow\cdots|z_{n}\rangle_{P}$.
For the moment, suppose that $\alpha_{0}=1$ in Hamiltonian (2) and there is no
cavity mode involved. For such a transition to occur, the first requirement is
$E(z_{0})=E(z_{n})$. The perturbation theory yields the effective transition
rate $\mathcal{O}[\lambda(\lambda/\Delta)^{n-1}]$. However, if the Stark
shifts of $|z_{0}\rangle_{P}$ and $|z_{n}\rangle_{P}$ are different, the
effective detuning breaks the condition $E(z_{0})=E(z_{n})$, suppressing the
transition. Consequently, the most prominent transitions come from the cases
wherein the energy differences satisfy the condition
$E(z_{i+1})-E(z_{i})=E(z_{n-(i+1)})-E(z_{n-i})$ for all $i$ (simply put, the
transition diagram has a mirror symmetry). This rule is easily verifiable with
simple numerical simulations, which we do not present here.

Now taking the cavity modes into account, the condition can also be met when
an intermediate transition $|z_{i}\rangle_{P}\rightarrow|z_{i+1}\rangle_{P}$
is replaced by
$|z_{i}\rangle_{P}|0\rangle_{m}\rightarrow|z_{i+1}^{\prime}\rangle_{P}|1\rangle_{m}$
with $E(z_{i+1})=E(z_{i+1}^{\prime})+\omega_{m}$. This is always possible
provided $E(z_{i+1}^{\prime})<E(z_{i+1})$ and the appropriate cavity mode
exists. By incorporating multiple cavity modes, various tunnelling-out
transition channels can appear. For instance, the lambda-type-like transitions
characterized by $E(z_{1})-E(z_{0})=E(z_{n-1})-E(z_{n})+\omega_{m}$ with
$n\geq 2$ are expected to play an important role in overcoming local minima.

To illustrate the above idea, we consider a particular integer factoring
algorithm (not to be confused with Shor’s algorithm [39, 30]). Specifically,
we follow the integer multiplication procedure as in the elementary arithmetic
and turn it into a combinatorial optimization problem. The problem Hamiltonian
is constructed as follows. Consider a multiplication of two 3-bit integers
$\bar{x}\equiv(x_{2}x_{1}x_{0})_{2}$ and $\bar{y}\equiv(y_{2}y_{1}y_{0})_{2}$
resulting in a 6-bit integer $\bar{z}\equiv(z_{5}z_{4}\cdots z_{0})_{2}$,
incorporating additional four carry bits
$\bar{c}\equiv(c_{3}c_{2}c_{1}c_{0})_{2}$. For a given value of $\bar{z}$, we
turn each calculation step into an energy term in the problem Hamiltonian.
Here, 10 qubits are needed to encode $\bar{x}$, $\bar{y}$, and $\bar{c}$,
while $\bar{z}$ is hard-coded in the problem Hamiltonian. For example, the
first energy term has a value zero if $x_{0}y_{0}=z_{0}$ and $\Delta$
otherwise, the second has a value zero if
$x_{1}y_{0}+x_{0}y_{1}=(c_{0}z_{1})_{2}$ and $\Delta$ otherwise, and so on.
The ground state, representing the solution of the factoring, has energy zero
as it satisfies all the conditions, and has a two-fold degeneracy as $\bar{x}$
and $\bar{y}$ are interchangeable.

Figure 2: Numerical simulation of CQC for integer factoring of 35. Dotted
curves represent the energy with respect to the number of cooling cycles,
averaged over $10^{3}$ samples, for (a) $\alpha_{0}=1$ and (b) $\alpha_{0}=0$.
Gray curves represent typical individual trajectories.

Fig. 2 shows the results of our numerical simulation for $\bar{z}=35$. We take
the transition term as in Eq. (8) and set the parameters in Hamiltonian (2) as
$M=3$, $\omega_{m}=m\Delta$, $\lambda=\Delta/10$, and $a_{0}=1$. The duration
of a single cooling cycle is chosen to be $\pi/2\lambda$. The simulation is
performed by exact diagonalization. Fig. 2(a) shows that the energy of the
system vanishes in time, indicating that the system evolves into the ground
state. As a comparison, we have changed $a_{0}$ to zero for Fig. 2(b) to test
the effectiveness of the mechanism for tunneling out from local minima.
Without such a mechanism, the system almost always evolves into local minima,
which appear to be present at the first excited level.

A remark is in order. Our choice of the parameter $\lambda=\Delta/10$, chosen
to fulfill the requirement that the transition rate is much smaller than the
energy difference, appears effective, as demonstrated in Fig. 2(a). However,
it should be noted that the optimal choice of $\lambda$ depends on the
characteristics and size of the problem. In general, smaller $\lambda$ is
preferable as the collective effect enhances the transition rate. This effect
is particularly important for combinatorial optimization problems, which are
characterized by large degeneracies in the problem Hamiltonian. As the
degeneracies are generally very large in the middle of the energy spectrum,
the collective effect is also stronger in that region. Consequently, there
exists a parametric regime of $\lambda$ where the heating is sufficiently
avoided for the ground state, but not for higher energy states. On the other
hand, by choosing smaller $\lambda$, leading to slower transitions, one could
reach the regime where heating is avoided throughout the entire energy
spectrum. While the cooling is feasible in both cases, it is not clear which
case is more efficient.

##  V Discussion

In this work, we have introduced the notion of cooling-based quantum
computation along with a few illustrative examples. An important part is to
choose an appropriate transition term, which generates off-diagonal elements
in the diagonal basis of the problem Hamiltonian. There exists a trade-off
between the connectivity and strength of the transition. We have discussed two
opposite limits when the ground state is the solution of a combinatorial
optimization problem. In both cases, the running time generally increases
superpolynomially with the system size. It is an open question whether the
performance can be substantially improved by interpolating between the two
opposites.

In fact, the idea of CQC can be used to prepare the ground states of general
quantum Hamiltonians, although we focused on the analyzable cases. The most
essential requirement is that the ground state should not be heated to make it
a steady state. This is ensured when the ground state has a finite spectral
gap to the excited state and this spectral gap is resolved. Consequently, the
inverse of the spectral gap determines the basic time scale of the cooling,
which is a natural consequence of the energy-time uncertainty principle. For
gapped Hamiltonians, as the transition strength can be determined finitely
without the risk of heating the ground state, a finite number of cavity modes
can cover the transitions across the entire spectrum in principle, where the
number is roughly given by the ratio of the whole energy range to the
characteristic transition rate. This means that the number of cavity modes
increases only polynomially with the system size for gapped Hamiltonians.
However, choosing an appropriate transition term is heavily dependent on the
Hamiltonian, hence analytically challenging.

An interesting open question is the precise relationship between CQC and AQC.
In particular, the abundance and depth of local energy minima in CQC might be
strongly correlated with the spectral gap during AQC [14, 33, 34]. If not, the
two methods can differ in efficiency for particular ground-state findings. In
fact, the transition terms $H_{T}$ in Eqs. (5) and (8) are the two
conventional initial Hamiltonians in AQC. Consequently, when Trotter-
decomposed, the infinitesimal unitary evolutions of CQC with Eqs. (5) and (8)
are identical to those of AQC, although their arrangements and the inclusion
or exclusion of cavities make differences. This might be a clue to
understanding one of the two more deeply from inspecting the other.

###### Acknowledgements.

This work was supported by the National Research Foundation (NRF) of Korea
under Grant No. NRF-2022R1A4A1030660.

## References

  * Hastings and Koma [2006] M. B. Hastings and T. Koma, Communications in Mathematical Physics 265, 781 (2006).
  * Nachtergaele and Sims [2006] B. Nachtergaele and R. Sims, Communications in Mathematical Physics 265, 119 (2006).
  * Hastings [2007] M. B. Hastings, Journal of Statistical Mechanics: Theory and Experiment 2007, P08024 (2007).
  * [4] I. Arad, A. Kitaev, Z. Landau, and U. Vazirani, An area law and sub-exponential algorithm for 1D systems, arXiv:1301.1162.
  * Brandão and Horodecki [2013] F. G. S. L. Brandão and M. Horodecki, Nature Physics 9, 721 (2013).
  * Cho [2014] J. Cho, Physical Review Letters 113, 197204 (2014).
  * Cho [2018] J. Cho, Physical Review X 8, 031009 (2018).
  * Wen [2007] X.-G. Wen,  _Quantum Field Theory of Many-body Systems: From the Origin of Sound to an Origin of Light and Electrons_ (Oxford University Press, Oxford, 2007).
  * Kitaev  _et al._ [2002] A. Y. Kitaev, A. Shen, and M. N. Vyalyi,  _Classical and Quantum Computation_ (American Mathematical Soc., 2002).
  * Kempe and Regev [2003] J. Kempe and O. Regev, Quantum Information & Computation 3, 258 (2003).
  * Kempe  _et al._ [2006] J. Kempe, A. Kitaev, and O. Regev, SIAM Journal on Computing 35, 1070 (2006).
  * Korte and Vygen [2018] B. Korte and J. Vygen,  _Combinatorial Optimization: Theory and Algorithms_, Algorithms and Combinatorics, Vol. 21 (Springer Berlin Heidelberg, Berlin, Heidelberg, 2018).
  * Barahona [1982] F. Barahona, Journal of Physics A: Mathematical and General 15, 3241 (1982).
  * Mézard and Zecchina [2002] M. Mézard and R. Zecchina, Physical Review E 66, 056126 (2002).
  * Lucas [2014] A. Lucas, Frontiers in Physics 2, 5 (2014).
  * Kadowaki and Nishimori [1998] T. Kadowaki and H. Nishimori, Physical Review E 58, 5355 (1998).
  * Bharti  _et al._ [2022] K. Bharti, A. Cervera-Lierta, T. H. Kyaw, T. Haug, S. Alperin-Lea, A. Anand, M. Degroote, H. Heimonen, J. S. Kottmann, T. Menke, W.-K. Mok, S. Sim, L.-C. Kwek, and A. Aspuru-Guzik, Reviews of Modern Physics 94, 015004 (2022).
  * Farhi  _et al._ [2001] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, Science 292, 472 (2001).
  * Aharonov  _et al._ [2008] D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, SIAM Review 50, 755 (2008).
  * Albash and Lidar [2018] T. Albash and D. A. Lidar, Reviews of Modern Physics 90, 015002 (2018).
  * Zhou  _et al._ [2020] L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Physical Review X 10, 021067 (2020).
  * [22] E. Farhi, J. Goldstone, and S. Gutmann, A Quantum Approximate Optimization Algorithm, arXiv:1411.4028.
  * Hadfield  _et al._ [2019] S. Hadfield, Z. Wang, B. O’Gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, Algorithms 12, 34 (2019).
  * Kandala  _et al._ [2017] A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta, Nature 549, 242 (2017).
  * Cerezo  _et al._ [2021] M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, Nature Reviews Physics 3, 625 (2021).
  * Tilly  _et al._ [2022] J. Tilly, H. Chen, S. Cao, D. Picozzi, K. Setia, Y. Li, E. Grant, L. Wossnig, I. Rungger, G. H. Booth, and J. Tennyson, Physics Reports 986, 1 (2022).
  * Verstraete  _et al._ [2009] F. Verstraete, M. M. Wolf, and J. Ignacio Cirac, Nature Physics 5, 633 (2009).
  * Cho  _et al._ [2011] J. Cho, S. Bose, and M. S. Kim, Physical Review Letters 106, 020504 (2011).
  * Cubitt [2023] T. S. Cubitt, Dissipative ground state preparation and the Dissipative Quantum Eigensolver (2023), arXiv:2303.11962.
  * Nielsen and Chuang [2011] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information: 10th Anniversary Edition_ (Cambridge University Press, Cambridge; New York, 2011).
  * Cho  _et al._ [2015] J. Cho, S. Bose, and M. S. Kim, Optics Communications 337, 66 (2015).
  * Feng  _et al._ [2022] J.-J. Feng, B. Wu, and F. Wilczek, Physical Review A 105, 052601 (2022).
  * Amin [2008] M. H. S. Amin, Physical Review Letters 100, 130503 (2008).
  * Werner  _et al._ [2023] M. Werner, A. García-Sáez, and M. P. Estarellas, Physical Review Research 5, 043236 (2023).
  * Grover [1996] L. K. Grover, in  _Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing_, STOC ’96 (Association for Computing Machinery, New York, NY, USA, 1996) pp. 212–219.
  * Bennett  _et al._ [1997] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, SIAM Journal on Computing 26, 1510 (1997).
  * Boyer  _et al._ [1998] M. Boyer, G. Brassard, P. Høyer, and A. Tapp, Fortschritte der Physik 46, 493 (1998).
  * Zalka [1999] C. Zalka, Physical Review A 60, 2746 (1999).
  * Shor [1994] P. Shor, in  _Proceedings 35th Annual Symposium on Foundations of Computer Science_ (1994) pp. 124–134.