# A note on Adiabatic Evolution in Quantum Annealing

In a lot of introductory literature about Quantum Annealing, Adiabatic Quantum Computing (AQC) and Quantum Annealing (QA) are explained very well, but one crucial connection seem to always be amiss.. What exactly is evolution, or adiabatic evolution?

First, the Hamiltonian of a system gives us the total energy of that system. It basically explains the whole system (what kind of kinetic or potential energy exists, etc). The ground state of a given Hamiltonian is the state associated with the lowest possible total energy in the system. Note that finding the ground state of a system is extremely tough. A problem such as the Traveling Salesman Problem (TSP) is then converted into a formulation (QUBO or Ising) for which a Hamiltonian is set up easily.

Quantum Annealing works as per AQC as follows:

• Set up the problem Hamiltonian for our problem, s.t. the ground state of the Hamiltonian corresponds to the solution of our problem.
• Set up an initial Hamiltonian for which the ground state is easily known and make sure the system is in the ground state.
• Adiabatically evolve the Hamiltonian to the problem Hamiltonian.

Adiabatic evolution follows the adiabatic theorem in that the evolution should not be too fast, else the system could jump into the next excited state above the ground state, which would result in a sub-optimal solution in the end. The general formula is as follows:

$\mathcal{H}_t = s(t) \mathcal{H}_i + (1 - s(t)) \mathcal{H}_f$,

where $\mathcal{H}_i$ is the initial Hamiltonian and $\mathcal{H}_f$ is the problem Hamiltonian. The paramater $s(t)$ is modified over time. In the beginning, the system (or time-dependent) Hamiltonian consists solely of the initial Hamiltonian. In the end, it consists solely of the problem Hamiltonian (and is hopefully still in the ground state, if the adiabatic theorem was followed).

Setting up Hamiltonians consists of translating the TSP instance to an Ising spin glass problem instance. The Hamiltonian of that problem is very well known, and by translating to an Ising problem, one automatically encodes the problem in a way s.t. minimizing the Hamiltonian (i.e. minimizing the total energy and thus getting into the ground state) automatically minimizes the Ising spin glass instance and thus the TSP instance.

With the Hamiltonians out of the way, a huge question marks sits with the adiabatic evolution part. What is going on here? The figure below shall help build an intuition.

One can see different system Hamiltonians over time and the corresponding ground state (black dot) of all possible states. The experiment would now start with the light blue Hamiltonian and over time slowly change to the problem Hamiltonian (dark purple). Thus, we are modifying the energy landscape over time! Looking back at the time-dependent Hamiltonian equation further above, this suddenly makes sense. The time-dependent Hamiltonian changes over time in that it consists of both the initial Hamiltonian and problem Hamiltonian with different fractions. Thus, the energy landscape changes over time in that it first consists solely of the initial Hamiltonian and later more and more of the problem Hamiltonian. So the literature is not missing a description of adiabatic evolution after all. Hopefully though, this visualization helps people out there understand easier the intuition behind it.

There are quite a few more topics to cover, but this post ends here to keep things short and concise. More will likely follow.

A project this was related to is QUBO-NN.

References:

• McGeoch, Catherine C. "Adiabatic quantum computation and quantum annealing: Theory and practice."
• Lucas, Andrew. "Ising formulations of many NP problems.", 2014