29

C H A P T E R 3

Quantum Annealing

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. [3], Ray et al. [87], Tirumalai

et al. [104], Finnila et al. [38], and Kadowaki and Nishimori [56].

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

design process.

Many authors now use the terms AQC and QA interchangeably. Here, however, we observe

a distinction suggested by Rose and Macready [92] 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

F

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

worst-case time.

• An approximation algorithm runs in polynomial time and has a guaranteed

bound on solution quality, typically expressed as a bound on the ratio Approx-

Solution/OptimalSolution.

• 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.

Get *Adiabatic Quantum Computation and Quantum Annealing* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.