# Introduction to Quantum Annealing¶

This chapter explains what quantum annealing is
and how it works, and introduces the underlying
quantum physics that governs its behavior. For more
detail on quantum annealing in D-Wave systems, see
*Technical Description of the D-Wave Quantum Processing Unit*.

## Applicable Problems¶

Quantum annealing processors naturally return low-energy solutions; some applications require the real minimum energy (optimization problems) and others require good low-energy samples (probabilistic sampling problems).

**Optimization problems.** In an optimization problem,
we search for the best of many possible combinations.
Optimization problems include scheduling challenges, such
as “Should I ship this package on this truck or the next one?”
or “What is the most efficient route a traveling
salesperson should take to visit different cities?”

Physics can help solve these sorts of problems because we can frame them as energy minimization problems. A fundamental rule of physics is that everything tends to seek a minimum energy state. Objects slide down hills; hot things cool down over time. This behavior is also true in the world of quantum physics. Quantum annealing simply uses quantum physics to find low-energy states of a problem and therefore the optimal or near-optimal combination of elements.

**Sampling problems.** Sampling from many low-energy states and
characterizing the shape of the energy landscape is useful for
machine learning problems where we want to build a probabilistic
model of reality. The samples give us information
about the model state for a given set of parameters, which can then be
used to improve the model.

Probabilistic models explicitly handle uncertainty by accounting for gaps in our knowledge and errors in data sources. Probability distributions represent the unobserved quantities in a model (including noise effects) and how they relate to the data. The distribution of the data is approximated based on a finite set of samples. The model infers from the observed data, and learning occurs as it transforms the prior distribution, defined before observing the data, into the posterior distribution, defined afterward. If the training process is successful, the learned distribution resembles the distribution that generated the data, allowing predictions to be made on unobserved data. For example, when training on the famous MNIST dataset of handwritten digits, such a model can generate images resembling handwritten digits that are consistent with the training set.

Sampling from energy-based distributions is a computationally intensive task that is an excellent match for the way that the D-Wave system solves problems; that is, by seeking low-energy states.

## How Quantum Annealing Works in D-Wave Systems¶

The quantum bits—also known as *qubits*—are the lowest energy states of
the superconducting loops that make up the D-Wave QPU. These states have a circulating
current and a corresponding magnetic field.
As with classical bits, a qubit can be in state of 0 or 1;
see Figure 4.
But because the qubit is a quantum object, it can also be in a superposition of the 0 state and
the 1 state at the same time. At the end of the quantum annealing process, each qubit collapses from a
superposition state into either 0 or 1 (a classical state).

The physics of this process can be shown (visualized) with an energy diagram as in Figure 5.
This diagram changes over time, as we can see in (a), (b), and (c). To begin, there is just one valley (a), with a single minimum.
The quantum annealing process runs, the barrier is raised, and this turns the energy diagram into what is
known as a *double-well potential* (b). Here, the low point of the left valley corresponds to the 0 state,
and the low point of the right valley corresponds to the 1 state. The qubit ends up in one of these valleys
at the end of the anneal.

Everything else being equal, the probability of the qubit ending in the 0 or the 1 state is equal (50 percent). We
can, however, control the probability of it falling into the 0 or the 1 state by applying an external magnetic
field to the qubit (c). This field tilts the double-well potential, increasing the probability of the qubit ending up in the
lower well. The programmable quantity that controls the external magnetic field is called a *bias*, and the qubit
minimizes its energy in the presence of the bias.

The bias term alone is not useful, however. The real power of the qubits comes when we link them
together so they can influence each other. This is done with a device called a *coupler*. A coupler
can make two qubits tend to end up in the same state—both 0 or both 1—or it can make them tend to be in
opposite states. Like a qubit bias, the correlation weights between coupled qubits can be programmed by setting
a coupling strength. Together, the programmable biases and weights are the means by which a problem is
defined in the D-Wave system.

When we use a coupler, we are using another phenomenon of quantum physics called entanglement. When two qubits are entangled, they can be thought of as a single object with four possible states. Figure 6 illustrates this idea, showing a potential with four states, each corresponding to a different combination of the two qubits: (0,0), (0,1), (1,1), and (1,0). The relative energy of each state depends on the biases of qubits and the coupling between them. During the anneal, the qubit states are potentially delocalized in this landscape before finally settling into (1,1) at the end of the anneal.

As we have seen, each qubit has a bias and qubits interact via the couplers. When formulating a problem, users choose values for the biases and couplers. The biases and couplings define an energy landscape, and the D-Wave quantum computer finds the minimum energy of that landscape: this is quantum annealing.

As we add qubits, systems get increasingly complex. With two qubits, we have four possible states over which to define an energy landscape. At three qubits, we have eight. For each qubit we add, we double the number of states over which we can define the energy landscape: the number of states goes up exponentially with the number of qubits.

In summary, we start with a set of qubits, each in a superposition state of 0 and 1. They are not yet coupled. When they undergo quantum annealing, the couplers and biases are introduced and the qubits become entangled. At this point, the system is in an entangled state of many possible answers. By the end of the anneal, each qubit is in a classical state that represents the minimum energy state of the problem, or one very close to it. All of this happens in D-Wave systems in a matter of microseconds.

## Underlying Quantum Physics¶

This section discusses some concepts essential to understanding the quantum physics that governs the D-Wave quantum annealing process.

### The Hamiltonian and the Eigenspectrum¶

A classical Hamiltonian is a mathematical description of some physical system in terms of its energies. We can input any particular state of the system, and the Hamiltonian returns the energy for that state. For most non-convex Hamiltonians, finding the minimum energy state is an NP-hard problem that classical computers cannot solve efficiently.

As an example of a classical system, consider an extremely simple system of a table and an apple. This system has two possible states: the apple on the table, and the apple on the floor. The Hamiltonian tells us the energies, from which we can discern that the state with the apple on the table has a higher energy than that when the apple is on the floor.

For a quantum system, a Hamiltonian is a function that maps certain states, called *eigenstates*,
to energies. Only when the system is in an eigenstate of the Hamiltonian is its energy well defined
and called the *eigenenergy*. When the system is in any other state, its energy is uncertain.
The collection of eigenstates with defined eigenenergies make up the *eigenspectrum*.

For the D-Wave system, the Hamiltonian may be represented as

where \({\hat\sigma_{x,z}^{(i)}}\) are Pauli matrices operating on a qubit \(q_i\), and \(h_i\) and \(J_{i,j}\) are the qubit biases and coupling strengths.[1]

[1] | Nonzero values of \(h_i\) and \(J_{i,j}\) are limited to those available in the working graph; see the D-Wave QPU Architecture: Chimera chapter. |

The Hamiltonian is the sum of two terms, the *initial Hamiltonian* and the *final Hamiltonian*:

- Initial Hamiltonian (first term)—The lowest-energy state of the initial Hamiltonian is
when all qubits are in a superposition state of 0 and 1.
This term is also called the
*tunneling Hamiltonian*. - Final Hamiltonian (second term)—The lowest-energy state of the final Hamiltonian is the answer
to the problem that we are trying to solve. The final state is a classical state, and includes the qubit
biases and the couplings between qubits.
This term is also called the
*problem Hamiltonian*.

In quantum annealing, we begin in the lowest-energy eigenstate of the initial Hamiltonian. As we anneal, we introduce the problem Hamiltonian, which contains the biases and couplers, and we reduce the influence of the initial Hamiltonian. At the end of the anneal, we are in an eigenstate of the problem Hamiltonian. Ideally, we have stayed in the minimum energy state throughout the quantum annealing process so that—by the end—we are in the minimum energy state of the problem Hamiltonian and therefore have an answer to the problem we want to solve. By the end of the anneal, each qubit is a classical object.

### Annealing in Low-Energy States¶

A plot of the eigenenergies versus time is a useful way to visualize the quantum annealing process.
The lowest energy state during the
anneal—the *ground state*—is typically shown at the bottom, and any
higher excited states are above it; see Figure 7.

As an anneal begins, the system starts in the lowest energy
state, which is well separated from any other energy
level. As the problem Hamiltonian is introduced,
other energy levels may get closer to the ground state. The
closer they get, the higher the probability that the system
will jump from the lowest energy state into one
of the excited states. There is a point during the anneal
where the first excited state—that with the lowest energy apart
from the ground state—approaches the ground state closely and
then diverges away again. The minimum distance between the ground state
and the first excited state throughout any point in the anneal is called the
*minimum gap*.

Certain factors may cause the system to jump from the ground state into a
higher energy state. One is thermal fluctuations that exist in
any physical system. Another is running the annealing process too quickly.
An annealing process that experiences no interference from outside energy
sources and evolves the Hamiltonian slowly enough is called an *adiabatic*
process, and this is where the name *adiabatic quantum computing* comes from.
Because no real-world computation can run in perfect isolation, quantum annealing
may be thought of as the real-world counterpart to adiabatic quantum computing, a theoretical ideal.
In reality, for some problems, the probability of staying in the ground state can
sometimes be small; however, the low-energy states that are returned are still
very useful.

For every different problem that you specify, there is a different Hamiltonian and a different corresponding eigenspectrum. The most difficult problems, in terms of quantum annealing, are generally those with the smallest minimum gaps.

### Evolution of Energy States¶

Figure 8 shows the evolution of the energy functions
over time while physical temperature remains constant. This chart plots \(\frac{\rm Energy}{h}\)
in GHz, where \(h\) is the Planck constant,[2] against \(s\),
the *normalized anneal fraction*, an abstract parameter ranging from 0 to 1. The
\(A(s)\) curve is the tunneling energy and the \(B(s)\) curve is the problem Hamiltonian energy at \(s\).
A linear anneal sets \(s = t / t_f\), where \(t\) is time and \(t_f\) is the total time
of the anneal. At \(t=0\), \(A(0) \gg B(0)\), which leads to the quantum ground state of the
system where each spin is in a delocalized combination of its classical states. As the system is annealed,
\(A\) decreases and \(B\) increases until \(t_f\), when the final state of the qubits represents
a low-energy solution.

[2] | \(6.6 \times 10^{-34}\) joule-seconds |

At the end of the anneal, the Hamiltonian contains the only \(B(s)\) term. It is a classical Hamiltonian where every possible classical bitstring (that is, list of qubit states that are either 0 or 1) corresponds to an eigenstate and the eigenenergy is the classical energy objective function we have input into the system.

## Annealing Controls¶

We continue to understand more deeply the fine details of quantum annealing and devise better controls for it. The release of the D-Wave 2000Q system includes features that give users programmable control over the annealing schedule, which enable a variety of searches through the energy landscape. These controls can improve both optimization and sampling performance for certain types of problems, and can help investigate what is happening partway through the annealing process.

For more information about the available annealing controls, see *Technical Description of the D-Wave Quantum Processing Unit*.