C H A P T E R 3
Quantumannealing (QA) is a heuristic approach to solving problems in combinatorial optimiza-
tion, originally developed for implementation on classical machines. It may be seen as a variation
on the more familiar simulated annealing (SA) metaheuristic. (See Figure 3.1 for a deﬁnition of
this term.) e idea of incorporating a model of quantum rather than thermal annealing into a
heuristic optimization framework appears to have been independently suggested by several re-
searchers. Early work may be found, for example, in Apolloni et al. , Ray et al. , Tirumalai
et al. , Finnila et al. , and Kadowaki and Nishimori .
It is now understood that quantum annealing algorithms can be developed using the “basic
instruction set” of AQC as well as that of classical computers. us QA provides a conceptual
bridge between adiabatic quantum computation and classical optimization, which (judging from
the number of algorithms proposed in the last few years) has served to catalyze the algorithm
Many authors now use the terms AQC and QA interchangeably. Here, however, we observe
a distinction suggested by Rose and Macready  that applies not so much to the algorithm as
to how it is analyzed:
• e term AQC algorithm refers to an algorithm in the universal AQC model. AQC algo-
rithms can be designed to solve any Turing-computable problem; they can simulate quan-
tum algorithms in the gate model with at most polynomial increase in computation time.
• A QA algorithm is designed to solve a (typically NP-hard) combinatorial optimization prob-
lem. is implies a restriction on the ﬁnal Hamiltonian H
so that it represents a classical
objective function, as described in Section 2.4. On the other hand certain properties of the
AQC model are relaxed: for example, we do not assume that the entire computation take
place in ground state.
is chapter considers algorithms designed in the QA framework, focusing on applications
in combinatorial optimization. e analysis of any algorithm depends on the platform on which
it runs; in the case of QA, we have three options:
• e algorithm may run on a theoretically ideal AQC platform (analogous to a Turing ma-
chine) in an adiabatically closed system, which means that it experiences no interference from
the environment. With this assumption, the algorithm is probabilistic and the Adiabatic
eorem may be used to bound the tradeoﬀ between computation time and the probability
that the system ﬁnishes in ground state.
30 3. QUANTUM ANNEALING
• A complete or exact algorithm guarantees to return a minimum-cost solution to
a given minimization problem. (Respectively, a maximum-cost solution to a given
maximization problem.) Assuming P ¤NP, such an algorithm runs in exponential
• An approximation algorithm runs in polynomial time and has a guaranteed
bound on solution quality, typically expressed as a bound on the ratio Approx-
• A probabilistic algorithm uses an internal random source to perform its com-
putations. ere may be a known probabilistic bound on the tradeoﬀ between
computation time and solution quality.
• A heuristic is an algorithm that has weak or nonexistent theoretical guarantees
on runtime and/or solution quality.
• A metaheuristic is a problem-generic solution strategy for solving NP-hard prob-
lems, on par with an algorithm paradigm like dynamic programming.
• Heuristic search is a type of metaheuristic. Quantum annealing and simulated
annealing (also metaheuristics) are variations on heuristic search.
• In optimization, Monte Carlo refers to a category of metaheuristic. is use of
the term is distinct from its meaning in complexity theory.
• A hybrid metaheuristic combines distinct metaheuristics, for example using one
to control the “long range” and another for the “local” search strategies.
Figure 3.1: Categories of classical optimization algorithms.
• e algorithm may be implemented to run on a physically realized quantum platform. It
is a matter of natural law that a real quantum computer must work in an open system: that
is, it cannot be perfectly isolated from its environment. Energy from the environment—of
all types, including thermal, magnetic, and radiation—creates noise that interferes with the
computation and reduces the probability of ﬁnishing in ground state. us the theoretical
guarantees of AQC do not necessarily apply. When no suitable performance bounds are
known, we consider the QA algorithm to be a heuristic.
• e algorithm can be implemented to run on an everyday classical platform. A classical
computer is not vulnerable to the so-called energy bath of an open system; on the other
hand it does not have support for quantum features like superposition and entanglement.