Multiobjective Optimization in a Quantum Adiabatic Computer∗
Benjamı́n Barán†

Marcos Villagra‡

arXiv:1605.03152v3 [] 30 Jun 2017

Universidad Nacional de Asunción
Núcleo de Investigación y Desarrollo Tecnológico (NIDTEC)

Abstract
In this work we present a quantum algorithm for multiobjective combinatorial optimization. We
show how to map a convex combination of objective functions onto a Hamiltonian and then use that
Hamiltonian to prove that the quantum adiabatic algorithm of Farhi et al.[FGGS00] can find Paretooptimal solutions in finite time provided certain convex combinations of objectives are used and the
underlying multiobjective problem meets certain restrictions.

Keywords: quantum computation, multiobjective optimization, quantum adiabatic evolution.

1

Introduction

Optimization problems are pervasive in everyday applications like logistics, communication networks, artificial intelligence and many other areas. Consequently, there is a high demand of efficient algorithms for
these problems. Many algorithmic and engineering techniques applied to optimization problems are being
developed to make an efficient use of computational resources in optimization problems. In fact, several engineering applications are multiobjective optimization problems, where several objectives must be optimized
at the same time. For a survey on multiobjective optimization see for example Refs. [EG00, vLBB14]. In
this work, we present what we consider the first algorithm for multiobjective optimization using a quantum
adiabatic computer.
Quantum computation is a promising paradigm for the design of highly efficient algorithms based on the
principles of quantum mechanics. Researchers have studied the computational power of quantum computers
by showing the advantages it presents over classical computers in many applications. Two of the most wellknow applications are in unstructured search and the factoring of composite numbers.
√ In structured search,
Grover’s algorithm can find a single marked element among n elements in time O( n), whereas any other
classical algorithm requires time at least n [Gro96]. Shor’s algorithm can factor composite numbers in polynomial time—any other known classical algorithm can find factors of composite numbers in subexponential
time (it is open whether a classical algorithm can find factors in polynomial time) [Sho94].
Initially, before the year 2000, optimization problems were not easy to construct using quantum computers. This was because most studied models of quantum computers were based on quantum circuits
which presented difficulties for the design of optimization algorithms. The first paper reporting on solving an optimization√problem was in Ref. [DH99]. Their algorithm finds a minimum inside an array of n
numbers in time O( n). More recently, Baritompa et al.[BBW05] presented an improved algorithm based
on Ref. [DH99]; this latter algorithm, however, does not have a proof of convergence in finite time. The
algorithms of Refs. [DH99] and [BBW05] are based on Grover’s search, and hence, in the quantum circuit
model.
Quantum Adiabatic Computing was introduced by Farhi et al.[FGGS00] as a new quantum algorithm and
computation paradigm more friendly to optimization problems. This new paradigm is based on a natural
phenomenon of quantum annealing [DC08]; analogously to classical annealing, optimization problems are
mapped onto a natural optimization phenomenon, and thus, optimal solutions are found by just letting this
phenomenon to take place.
∗ An

extended abstract of this paper appeared in Ref. [BV16]
bbaran@cba.com.py
‡ Email: mvillagra@pol.una.py; corresponding author
† Email:

1

The algorithms of Refs. [DH99] and [BBW05] are difficult to extend to multiobjective optimization and
to prove convergence in finite time. Hence, quantum adiabatic computing presents itself as a more suitable
model to achieve the following two goals: (i) to propose a quantum algorithm for multiobjective optimization
and (ii) prove convergence in finite time of the algorithm.
In this work, as our main contribution, we show that the quantum adiabatic algorithm of Farhi et
al.[FGGS00] can be used to find Pareto-optimal solutions in finite time provided certain restrictions are met.
In Theorem 4.1, we identify two structural features that any multiobjective optimization problem must have
in order to use the abovementioned adiabatic algorithm.
The outline of this paper is the following. In Section 2 we present a brief overview of multiobjective
combinatorial optimization and introduce the notation used throughout this work; in particular, several new
properties of multiobjective combinatorial optimization are also presented that are of independent interest. In
Section 3 we explain the quantum adiabatic theorem, which is the basis of the adiabatic algorithm. In Section
4 we explain the adiabatic algorithm and its application to combinatorial multiobjective optimization. In
Section 5 we prove our main result of Theorem 4.1. In Section 6 we show how to use the adiabatic algorithm
in a concrete problem. Finally, in Section 7 we present a list of challenging open problems.

2

Multiobjective Combinatorial Optimization

In this section we introduce the notation used throughout this paper and the main concepts of multiobjective
optimization. The set of natural numbers (including 0) is denoted N, the set of integers is Z, the set of real
numbers is denoted R and the set of positive real numbers is R+ . For any i, j ∈ N, with i < j, we let [i, j]Z
denote the discrete interval {i, i + 1, . . . , j − 1, j}. The set of binary words of length n is denoted {0, 1}n .
We also let poly(n) = O(nc ) be a polynomial in n.
A multiobjective combinatorial optimization problem (or MCO) is an optimization problem involving
multiple objectives over a finite set of feasible solutions. These objectives typically present trade-offs among
solutions and in general there is no single optimal solution. In this work, we follow the definition of Ref.
[KLP75]. Furthermore, with no loss of generality, all optimization problems considered in this work are
minimization problems.
Let S1 , . . . , Sd be totally ordered sets and let ≤i be an order on set Si for each i ∈ [1, d]Z . We also let ni
be the cardinality of Si . Define the natural partial order relation ≺ over the cartesian product S1 × · · · × Sd
in the following way. For any u = (u1 , . . . , ud ) and v = (v1 , . . . , vd ) in S1 × · · · × Sd , we write u ≺ v if and
only if for any i ∈ [1, d]Z it holds that ui ≤i vi ; otherwise we write u ⊀ v. An element u ∈ S is a minimal
element if there is no v ∈ S such that v ≺ u and v 6= u. Moreover, we say that u is non-comparable with v
if u ⊀ v and v ⊀ u and succinctly write u ∼ v. In the context of multiobjective optimization, the relation ≺
as defined here is often referred to as the Pareto-order relation [KLP75].
Definition 2.1 A multiobjective combinatorial optimization problem (or shortly, MCO) is defined as a tuple
Π = (D, R, d, F , ≺) where D is a finite set called domain, R ⊆ R+ is a set of values, d is a positive integer,
F is a finite collection of functions {fi }i∈[1,d]Z where each fi maps from D to R, and ≺ is the Pareto-order
relation on Rd (here Rd is the d-fold cartesian product on R). Define a function f that maps D to Rd as
f (x) = (f1 (x), . . . , fd (x)) referred as the objective vector of Π. If f (x) is a minimal element of Rd we say
that x is a Pareto-optimal solution of Π. For any two elements x, y ∈ D, if f (x) ≺ f (y) we write x ≺ y;
similarly, if f (x) ∼ f (y) we write x ∼ y. For any x, y ∈ D, if x ≺ y and y ≺ x we say that x and y are
equivalent and write x ≡ y. The set of all Pareto-optimal solutions of Π is denoted P (Π).
A canonical example in multiobjective optimization is the Two-Parabolas problem. In this problem we
have two objective functions defined by two parabolas that intersect in a single point, see Fig.1. In this work,
we will only be concerned with a combinatorial version of the Two-Parabolas problem where each objective
function only takes values on a finite set of numbers.
Considering that the set of Pareto-optimal solutions can be very large, we are mostly concerned on finding
a subset of the Pareto-optimal solutions. Optimal query algorithms to find all Pareto-optimal solutions for
d = 2, 3 and almost tight upper and lower bounds for any d ≥ 4 up to polylogarithmic factors were discovered
by [KLP75]; [PY00] showed how to find an approximation to all Pareto-optimal solutions in polynomial time.
For the remaining of this work, ≺ will always be the Pareto-order relation and will be omitted from the
definition of any MCO. Furthermore, for convenience, we will often write Πd = (D, R, F ) as a short-hand
for Π = (D, R, d, F ). In addition, we will assume for this work that each function fi ∈ F is computable in
polynomial time and each fi (x) is bounded by a polynomial in the number of bits of x.
2

Figure 1: The Two-Parabolas Problem. The first objective function f1 is represented by the bold line and
the second objective function f2 by the dashed line. For MCOs, each objective function takes values only on
the natural numbers. Note that there are no equivalent elements in the domain. In this particular example,
all the solutions between 7 and 15 are Pareto-optimal.
Definition 2.2 An MCO Πd is well-formed if for each fi ∈ F there is a unique x ∈ D such that fi (x) = 0.
An MCO Πd is normal if it is well-formed and fi (x) = 0 and fj (y) = 0, for i 6= j, implies x 6= y.
In a normal MCO, the value of an optimal solution in each fi is 0, and all optimal solutions are different.
In Fig.1, solutions 7 and 15 are optimal solutions of f1 and f2 with value 0, respectively; hence, the TwoParabolas problem of Fig.1 is normal.
Definition 2.3 An MCO Πd is collision-free if given λ = (λ1 , . . . , λd ), with each λi ∈ R+ , for any i ∈ [1, d]Z
and any pair x, y ∈ D it holds that |fi (x) − fi (y)| > λi . If Πd is collision-free we write succinctly as Πλd .
The Two-Parabolas problem of Fig.1 is not collision-free; for example, for solutions 5 and 9 we have that
f1 (5) = f1 (9). In Section 6 we show how to turn the Two-Parabolas problem into a collision-free MCO.
Definition 2.4 A Pareto-optimal solution x is trivial if x is an optimal solution of some fi ∈ F .
In Fig.1, solutions 7 and 15 are trivial Pareto-optimal solutions, whereas any x between 7 and 15 is
non-trivial.
Lemma 2.5 For any normal MCO Πd , if x and y are trivial Pareto-optimal solutions of Πd , then x and y
are not equivalent.
Proof.
Let x, y be two trivial Pareto-optimal solutions of Πd . There exists i, j such that fi (x) and
fj (y) = 0. Since Πd is normal we have that x 6= y and fi (y) > 0 and fj (x) > 0, hence, x ∼ y and they are
not equivalent.
Let Wd be a set of of normalized vectors in [0, 1)d , the continuous interval between 0 and less than 1,
defined as
)
(
d
X
d
wi = 1 .
(1)
Wd = w = (w1 , . . . , wd ) ∈ [0, 1)
i=1

For any w ∈ Wd , define hf (x), wi = hw, f (x)i = w1 f1 (x) + · · · + wd fd (x).

Lemma 2.6 Given Πd = (D, R, F ), any two elements x, y ∈ D are equivalent if and only if for all w ∈ Wd
it holds that hf (x), wi = hf (y), wi.
Proof.

Assume that x ≡ y. Hence f (x) = f (y). If we pick any w ∈ Wd we have that
hf (x), wi = w1 f1 (x) + · · · + wd fd (x) = w1 f1 (y) + · · · + wd fd (y) = hf (y), wi.

Now suppose that for all w ∈ Wd it holds hf (x), wi = hf (y), wi. By contradiction, assume that x 6≡ y.
With no loss of generality, assume further that there is exactly one i ∈ [1, d]Z such that fi (x) 6= fi (y). Hence
X
wi (fi (x) − fi (y)) =
wj (fj (y) − fj (x)).
(2)
j6=i

3

The right hand of Eq.(2) is 0 because for all j 6= i we have that fj (x) = fj (y). The left hand of Eq.(2),
however, is not 0 by our assumption, hence, a contradiction. Therefore, it must be that x and y are equivalent.

Lemma 2.7 Let Πd = (D, R, F ). For any w ∈ Wd there exists x ∈ D such that if hf (x), wi = miny∈D {hf (y), wi},
then x is a Pareto-optimal solution of Πd .
Proof. Fix w ∈ Wd and let x ∈ D be such that hf (x), wi is minimum among all elements of D. For any
y ∈ D, with y 6= x, we need to consider two cases: (1) hf (y), wi = hf (x), wi and (2) hf (y), wi > hf (x), wi.
Case (1). Here we have another two subcases, either fi (y) = fi (x) for all i or there exists at least one pair
i, j ∈ {1, . . . , d} such that wi fi (x) < wi fi (y) and wj fj (y) < wj fj (x). When fi (x) = fi (y) for each i = 1, . . . , d
we have that x and y are equivalent. On the contrary, if wi fi (x) < wi fi (y) and wj fj (y) < wj fj (x), we have
that fi (x) < fi (y) and fj (y) < fj (x), and hence, x ∼ y.
Case (2). In this case, there exists i ∈ {1, . . . , d} such that wi fi (x) < wi fi (y), and hence, fi (x) < fi (y).
Thus, f (y) 6≺ f (x) and y 6≺ x for any y 6= x.
We conclude from Case (1) that x ≡ y or x ∼ y, and from Case (2) that y ⊀ x. Therefore, x is
Pareto-optimal.
In this work, we will concentrate on finding non-trivial Pareto-optimal solutions. Finding trivial elements
can be done by letting wi = 1 for some i ∈ [1, d]Z and then running and optimization algorithm for fi ;
consequently, in Eq.(1) we do not allow for any wi to be 1. The process of mapping several objectives to a
single-objective optimization problem is sometimes referred as a linearization of the MCO [EG00].
From Lemma 2.7, we know that some Pareto-optimal solutions may not be optimal solutions for any
linearization w ∈ Wd . We define the set of non-supported Pareto-optimal solutions as the set N (Π) of all
Pareto-optimal solutions x such that hf (x), wi is not optimal for any w ∈ Wd . We also define the set S(Π)
of supported Pareto-optimal solutions as the set S(Π) = P (Π) \ N (Π) [EG00].
Note that there may be Pareto-optimal solutions x and y that are non-comparable and hf (x), wi =
hf (y), wi for some w ∈ Wd . That is equivalent to say that the objective function obtained from a linearization
of an MCO is not injective.
Definition 2.8 Any two elements x, y ∈ D are weakly-equivalent if and only if there exists w ∈ Wd such
that hf (x), wi = hf (y), wi.
By Lemma 2.6, any two equivalent solutions x, y are also weakly-equivalent, ; the other way, however,
does not hold in general. For example, consider two objective vectors f (x) = (1, 2, 3) and f (y) = (1, 3, 2).
Clearly, x and y are not equivalent; however, if w = (1/3, 1/3, 1/3) we can see that x and y are indeed
weakly-equivalent. In Fig.1, points 10 and 12 are weakly-equivalent.

3

Quantum Adiabatic Computation

Starting from this section we assume basic knowledge of quantum computation. For a thorough treatment
of quantum information science we refer the reader to the book by Nielsen and
P Chuang[NC00].
Let H be a Hilbert
space
with
a
finite
basis
{|u
i}
.
For
any
vector
|vi
=
i
i
i αi |ui i, the ℓ2 -norm of |vi is
pP
2 . For any matrix A acting on H, we define the operator norm of A induced by
defined as kvk =
|α
|
i
i
the ℓ2 -norm as kAk = maxkvk=1 kA|vik.
The Hamiltonian of a quantum system gives a complete description of its time evolution, which is governed
by the well-known Schrödinger’s equation
i~

d
|Ψ(t)i = H(t)|Ψ(t)i,
dt

(3)

where
√ H is a Hamiltonian, |Ψ(t)i is the state of the system at time t, Planck’s constant is denoted by ~ and
i = −1. For simplicity, we will omit ~ and i from now on. If H is time-independent, it is easy to see that a
solution to Eq.(3) is simply |Ψ(t)i = U (t)|Ψ(0)i where U (t) = e−itH using |Ψ(0)i as a given initial condition.
When the Hamiltonian depends on time, however, Eq.(3) is not in general easy to solve and much research
is devoted to it; nevertheless, there are a few known special cases.
4

Say that a closed quantum system is described by a time-dependent Hamiltonian H(t). If |Ψ(t)i is the
minimum energy eigenstate of H(t), adiabatic time evolution keeps the system in its lower energy eigenstate
as long as the change rate of the Hamiltonian is “slow enough.” This natural phenomenon is formalized in
the Adiabatic Theorem, first proved in Ref. [BF26]. Different proofs where given along the years, see for
example Refs. [Kat50, Mes62, SWL04, Rei04, AR04]. In this work we make use of a version of the theorem
presented in Ref. [AR04].
Consider a time-dependent Hamiltonian H(s), for 0 ≤ s ≤ 1, where s = t/T so that T controls the rate
of change of H for t ∈ [0, T ]. We denote by H ′ and H ′′ the first and second derivatives of H.
Theorem 3.1 (Adiabatic Theorem [BF26, Kat50, AR04]) Let H(s) be a nondegenerate Hamiltonian, let |ψ(s)i be one of its eigenvectors and γ(s) the corresponding eigenvalue. For any λ ∈ R+ and
s ∈ [0, 1], assume that for any other eigenvalue γ̂(s) it holds that |γ(s) − γ̂(s)| > λ. Consider the evolution
given by H on initial condition |ψ(0)i for time T and let |φi be the state of the system at T . For any
5
kH ′ k3 kH ′ k·kH ′′ k
nonnegative δ ∈ R, if T ≥ 10
} then kφ − ψ(1)k ≤ δ.
δ 2 . max{ λ4 ,
λ3
The Adiabatic Theorem was used in [FGGS00] to construct a quantum algorithm for optimization problems and introduced a new paradigm in quantum computing known as quantum adiabatic computing. In the
following section, we briefly explain the quantum adiabatic algorithm and use it to solve MCOs.

4

The Quantum Adiabatic Algorithm

Consider a function f : {0, 1}n → R ⊆ R+ whose optimal solution x̄ gives f (x̄) = 0. Let H1 be a Hamiltonian
defined as
X
H1 =
f (x)|xihx|.
(4)
x

Notice that H1 |x̄i = 0, and hence, |x̄i is an eigenvector. Thus, an optimization problem reduces to finding
an eigenstate with minimum eigenvalue [FGGS00]. For any s ∈ [0, 1], let H(s) = (1 − s)H0 + sH1 , where
H0 is an initial Hamiltonian chosen accordingly. If we initialize the system in the lowest energy eigenstate
|ψ(0)i, the adiabatic theorem guarantees that T at least 1/poly(λ) suffices to obtain a quantum state close
to |ψ(1)i, and hence, to our desired optimal solution. We call H1 and H0 the final and initial Hamiltonians,
respectively.
After defining the initial and final Hamiltonians, the adiabatic theorem guarantees that we can find an
optimal solution in finite time using the following procedure known as the Quantum Adiabatic Algorithm.
Let H(s) = (1 − s)H0 + sH1 . Prepare the system in the ground-state |ψ(0)i of H. Then let the system evolve
for time t close to T . Finally, after time t, read-out the result by measuring the system in the computational
basis. The only requirements, in order to make any use of the adiabatic algorithm, is that H0 and H1 must
not commute and the total Hamiltonian H(s) must be nondegenerate in its minimum eigenvalue [FGGS00].
In this section we show how to construct the initial and final Hamiltonians for MCOs. Given any normal
and collision-free MCO Πλd = (D, R, F ) we will assume with no loss of generality that D = {0, 1}n, that is,
D is a set of binary words of length n.
P
For each i ∈ [1, d]Z define a Hamiltonian Hfi = x∈{0,1}n fi (x)|xihx|. The minimum eigenvalue of each
Hfi is nondegenerate and 0 because Πλd is normal and collision-free. For any w ∈ Wd , the final Hamiltonian
Hw is defined as
Hw = w1 Hf1 + · · · + wd Hfd
X

w1 f1 (x) + · · · + wd fd (x) |xihx|
=
x∈{0,1}n

=

X

x∈{0,1}n

hf (x), wi|xihx|.

(5)

Following the work of [FGGS00], we choose
one that does not diagonalizes in
√ as initial Hamiltonian √
the computational basis. Let |0̂i = (|0i + |1i)/ 2 and |1̂i = (|0i − |1i)/ 2. A quantum state |x̂i, for any
x ∈ {0, 1}n, is obtained by applying the n-fold Walsh-Hadamard operation F ⊗n on |xi. The set {|x̂i}x∈{0,1}n
is known as the Hadamard basis. The initial Hamiltonian is thus defined over the Hadamard basis as
X
h(x)|x̂ihx̂|,
(6)
H0 =
x∈{0,1}n

5

where h(0n ) = 0 and h(x) ≥ 1 for all x 6= P
0n . It is easy to see that the minimum eigenvalue is nondegenerate∗
with corresponding eigenstate |0̂n i = √12 x∈{0,1}n |xi.
For any vector w in Euclidian space we define the ℓ1 -norm of w as kwk1 = |w1 | + · · · |wd |.
Theorem 4.1 Let Πλd be any normal and collision-free MCO. If there are no equivalent Pareto-optimal
solutions, then for any w ∈ Wd there exists w′ ∈ Wd , satisfying kw−w′ k1 ≤ 1/poly(n), such that the quantum
adiabatic algorithm, using Hw′ as final Hamiltonian, can find a Pareto-optimal solution x corresponding to
w in finite time.
Note that if a linearization w gives a nondegenerate Hamiltonian H(s), we can directly use the adiabatic
algorithm to find a Pareto-optimal solution. In the case of a degenerate Hamiltonian H(s), Theorem 4.1 tell
us that we can still find a Pareto-optimal solution using the adiabatic algorithm, provided we choose a new
w′ sufficiently close to w.

5

Eigenspectrum of the Final Hamiltonian

In this section we prove Theorem 4.1. Note that if the initial Hamiltonian does not commute with the
final Hamiltonian, it suffices to prove that the final Hamiltonian is nondegenerate in its minimum eigenvalue
[FGGS00]. For the remaining of this work, we let σw and αw be the smallest and second smallest eigenvalues
of Hw corresponding to a normal and collision-free MCO Πλd = (D, R, F ).
Lemma 5.1 Let x be a non-trivial Pareto-optimal solution of Πλd . For any w ∈ Wd it holds that σw >
hw, λi.
Proof.
Let σw = w1 f1 (x) + · · · + wd fd (x) and let x be a non-trivial Pareto-optimal element. For each
wi ∈ N we have that
X
X
wi λi = hw, λi.
wi fi (x) >
σw =
i

i

Lemma 5.2 For any w ∈ Wd , let Hw be a Hamiltonian with a nondegenerate minimum eigenvalue. The
eigenvalue gap between the smallest and second smallest eigenvalues of Hw is at least hλ, wi.
Proof.
Let σw be the unique minimum eigenvalue of Hw . We have that σw = hf (x), wi for some
x ∈ {0, 1}n. Now let αw = hf (y), wi be a second smallest eigenvalue of Hw for some y ∈ {0, 1}n where
y 6= x. Hence,
αw − σw = hf (y), wi − hf (x), wi
= w1 f1 (y) − w1 f1 (x) + w2 f2 (y) − w2 f2 (x)
> w1 λ1 + w2 λ2
= hλ, wi.

Lemma 5.3 If there are no weakly-equivalent Pareto-optimal solutions in Πλd , then the Hamiltonian Hw is
non-degenerate in its minimum eigenvalue.
Proof.
By the contrapositive, suppose Hw is degenerate in its minimum eigenvalue σw . Take any two
degenerate minimal eigenstates |xi and |yi, with x 6= y, such that
w1 f1 (x) + · · · + wd fd (x) = w1 f1 (y) + · · · + wd f2 (d) = σw .
Then it holds that x and y are weakly-equivalent.
We further show that even if Πλd has weakly-equivalent Pareto-optimal solutions, we can find a nondegenerate Hamiltonian. Let m = maxx,i {fi (x)}.
∗ In

quantum physics, a Hamiltonian is degenerate when one of its eigenvalues has multiplicity greater than one.

6

Lemma 5.4 For any Πλd , let x1 , . . . , xℓ ∈ D be Pareto-optimal solutions that are not pairwise equivalent.
If there exists w ∈ Wd and σw ∈ R+ such that hf (x1 ), wi = · · · = hf (xℓ ), wi = σw is minimum among
all y ∈ D, then there exists w′ ∈ Wd and i ∈ [1, ℓ]Z such that for all j ∈ [1, ℓ]Z , with j 6= i, it holds
′
hf (xi ), w′ i < hf (xj ), w′ i. Additionally, if the linearization w′ satisfies kw − w′ k1 ≤ hλ,wi
md , then hf (xi ), w i is
′
unique and minimum among all hf (y), w i for y ∈ D.
Proof.

We prove the lemma by induction on ℓ. Let ℓ = 2, then hf (x1 ), wi = hf (x2 ), wi, and hence,
w1 f1 (x1 ) + · · · + wd fd (x1 ) = σw
w1 f1 (x2 ) + · · · + wd fd (x2 ) = σw .

(7)

for some σw ∈ R+ . From linear algebra we know that there is an infinite number of elements of Wd that
simultaneously satisfy Eq.(7). With no loss of generality, fix w3 , . . . , wd and set b1 = w3 f3 (x1 )+· · ·+wd fd (x1 )
and b2 = w3 f3 (x2 ) + · · · + wd fd (x2 ). We have that
w1 f1 (x1 ) + w2 f2 (x1 ) = σw − b1

w1 f1 (x2 ) + w2 f2 (x2 ) = σw − b2 .

(8)

Again, by linear algebra, we know that Eq.(8) has a unique solution w1 and w2 ; it suffices to note that the
determinant of the coefficient matrix of Eq.(8) is not 0.
Choose any w1′ 6= w1 and w2′ 6= w2 satisfying w1′ +w2′ +w3 +· · ·+wd = 1 and let w′ = (w1′ , w2′ , w3 , . . . , wd ).
Then we have that hf (x1 ), w′ i 6= hf (x2 ), w′ i because w1′ and w2′ are not solutions to Eq.(8). Hence, either
hf (x1 ), w′ i or hf (x2 ), w′ i must be smaller than the other.
Suppose that hf (x1 ), w′ i < hf (x2 ), w′ i. We now claim that hf (x1 ), w′ i is mininum and unique among all
y ∈ D. In addition to the constraint of the preceding paragraph that w′ must satisfy, in order for hf (x1 ), w′ i
to be minimum, we must choose w′ such that kw − w′ k1 ≤ hλ,wi
md .
Assume for the sake of contradiction the existence of y ∈ D such that hf (y), w′ i ≤ hf (x1 ), w′ i. Hence,
hf (y), w′ i ≤ hf (x1 ), wi < hf (y), wi.
From Lemma 5.1, we know that |hf (x1 ), wi − hf (y), wi| > hλ, wi, and thus,
|hf (y), w′ i − hf (y), wi| > hλ, wi.

(9)

Using the Cauchy-Schwarz inequality we have that
|hf (y), w′ i − hf (y), wi| = |hf (y), w′ − wi|
≤ kf (y)k1 · kw′ − wk1
≤ hλ, wi,

where the last line follows from kf (y)k1 ≤ md and kw − w′ k1 ≤ hλ,wi
md ; from Eq.(9), however, we have that
|hf (y), w′ − wi| > hλ, wi, which is a contradiction. Therefore, we conclude that hf (y), w′ i > hf (x1 ), w′ i for
any y ∈ D; the case for hf (x1 ), w′ i > hf (x2 ), w′ i can be proved similarly. The base case of the induction is
thus proved.
Now suppose the statement holds for ℓ. Let x1 , . . . , xℓ , xℓ+1 be Pareto-optimal solutions that are not
pairwise equivalent. Let w ∈ Wd be such that hf (x1 ), wi = · · · = hf (wℓ+1 ), wi holds. By our induction
hypothesis, there exists w′ ∈ Wd and i ∈ [1, ℓ]Z such that hf (xi ), w′ i < hf (y), w′ i for any other y ∈ D.
If hf (xi ), w′ i 6= hf (xℓ+1 ), w′ i then we are done, because either one must be smaller. Suppose, however,
that hf (xℓ+1 ), w′ i = hf (xi ), w′ i = σw′ for some σw′ ∈ R+ . From the base case of the induction we know
there exists w′′ 6= w′ that makes hf (xi ), w′′ i < hf (xℓ+1 ), w′′ i, and hence, hf (xi ), w′′ i < hf (y), w′′ i for any
y ∈ D.
The premise in Lemma 5.4, that each x1 , . . . , xℓ must be Pareto-optimal solutions, is a sufficient condition
because if one solution is not Pareto-optimal, then the statement will contradict Lemma 2.7.
We now apply Lemma 5.4 to find a Hamiltonian with a nondegenerate minimum eigenvalue.
Lemma 5.5 Let Πλd be a MCO with no equivalent Pareto-optimal solutions and let Hw be a degenerate
Hamiltonian in its minimum eigenvalue with corresponding minimum eigenstates |x1 i, . . . , |xℓ i. There exists
′
w′ ∈ Wd , satisfying kw − w′ k1 ≤ hλ,wi
md , and i ∈ [1, ℓ]Z such that Hw is nondegenerate in its smallest
eigenvalue with corresponding eigenvector |xi i.
7

Proof. From Lemma 5.3, we know that if Πλd has no weakly-equivalent Pareto-optimal solutions, then for
any w the Hamiltonian Hw is nondegenerate.
We consider now the case when the minimum eigenvalue of Hw is degenerate with ℓ Pareto-optimal
solutions that are weakly-equivalent. Let x1 , . . . , xℓ be such weakly-equivalent Pareto-optimal solutions that
are non-trivial and xi 6≡ xj for all i 6= j. By Lemma 5.4 there exists w′ ∈ Wd , where w 6= w′ , such that
hf (xi ), w′ i is minimum among all y ∈ D.
If we consider our assumption from Section 2 that m = poly(n), where n is the maximum number of bits
of any element in D, we have that any w′ must satisfy kw − w′ k1 ≤ 1/poly(n). Then Theorem 4.1 follows
immediately from lemmas 2.7 and 5.5.
d
To see that the adiabatic evolution takes finite-time let ∆max = maxs k ds
H(s)k and gmin = mins g(s),
∆max
where g(s) is the eigenvalue gap of H(s). Letting T = O( g2 ) suffices to find a supported solution
min

d
corresponding to w. Since gmin > 0 and k ds
H(s)k = poly(n), we conclude that T is finite.

6

Application of the Adiabatic Algorithm to the Two-Parabolas
Problem

To make use of the adiabatic algorithm of Section 4 in the Two-Parabolas problem we need to consider
a collision-free version of the problem. Let T P2λ = (D, R, F ) be a normal and collision-free MCO where
λ = (λ1 , λ2 ) ∈ R+ × R+ , D = {0, 1}n, R ⊆ R+ and F = {f1 , f2 }. Let x0 and x′0 be the optimal solutions of
f1 and f2 , respectively. We will use xi to indicate the ith solution of f1 and x′i for f2 . Moreover, we assume
that |x0 − x′0 | > 1. This latter assumption will ensure that there is at least one non-trivial Pareto-optimal
solution.
To make T P2λ a Two-Parabolas problem, we impose the following conditions.
1. For each x ∈ [0, x0 ], the functions f1 and f2 are decreasing;
2. for each x ∈ [x′0 , 2n − 1], the functions f1 and f2 are increasing;
3. for each x ∈ [x0 + 1, x′0 − 1] , the function f1 is increasing and the function f2 is decreasing.
The final and initial Hamiltonians are as in Eq.(5) and Eq.(6), respectively. In particular, in Eq.(6), we
define the initial Hamiltonian as
X
|x̂ihx̂|.
(10)
Ĥ0 =
x∈{0,1}n \{0n }

Thus, the Hamiltonian of the entire system for T P2λ is
H(s) = (1 − s)Ĥ0 + sHw .

(11)

From the previous section we know that T = O( ∆g2max ) suffices to find a supported solution corresponding
min
to w [vDMV01]. The quantity ∆max is usually easy to estimate. The eigenvalue gap gmin is, however, very
difficult to compute; indeed, determining for any Hamiltonian if gmin > 0 is undecidable [CPGW15].
We present a concrete example of the Two-Parabolas problem on six qubits and numerically estimate the
eigenvalue gap. In Fig.2 we show a discretized instance of the Two-Parabolas problem—Table 1 presents a
complete specification of all points.
For this particular example we use as initial Hamiltonian 8H0 , that is, Eq.(10) multiplied by 8. Thus,
the minimum eigenvalue of 8H0 is 0, whereas any other eigenvalue is 8.
In Fig.3 we present the eigenvalue gap of T P2λ for w = 0.57 where we let w1 = w and w2 = 1 − w1 ;
for this particular value of w the Hamiltonian HF,w has a unique minimum eigenstate which corresponds
to Pareto-optimal solution 59. The two smallest eigenvalues never touch, and exactly at s = 1 the gap is
|hw, f (x0 )i − hw, f (x1 )i|, where x0 = 59 and x1 = 60 are the smallest and second smallest solutions with
respect to w, which agrees with lemmas 5.1 and 5.2.
Similar results can be observed for different values of w and a different number of qubits. Therefore, the
experimental evidence lead us to conjecture that in the Two-Parabolas problem gmin ≥ |hw, f (x)i−hw, f (y)i|,
where x and y are the smallest and second smallest solutions with respect to w.

8

Figure 2: A discrete Two-Parabolas problem on seven qubits. Each objective function f1 and f2 is represented
by the rounded points and the squared points, respectively. The gap vector λ = (0.2, 0.4). The trivial Paretooptimal points are 40 and 80.

Table 1: Complete definition of the Two-Parabolas example of Fig.2 for seven qubits.
x
1
5
9
13
17
21
25
29
33
37
41
45
49
53
57
61
65
69
73
77
81
85
89
93
97
101
105
109
113
117
121
125

f1 (x)
36.14
28.91
22.816
17.73
13.524
10.07
7.24
4.906
2.94
1.214
0.801
2.455
4.285
6.419
8.985
12.111
15.925
20.555
26.129
32.775
40.621
49.795
60.425
72.639
86.565
102.331
120.065
139.895
161.949
186.355
213.241
242.735

f2 (x)
214.879
188.449
164.435
142.709
123.143
105.609
89.979
76.125
63.919
53.233
43.939
35.909
29.015
23.129
18.123
13.869
10.239
7.105
4.339
1.813
1.2
3.654
6.284
9.218
12.584
16.51
21.124
26.554
32.928
40.374
49.02
58.994

x
2
6
10
14
18
22
26
30
34
38
42
46
50
54
58
62
66
70
74
78
82
86
90
94
98
102
106
110
114
118
122
126

f1 (x)
34.219
27.285
21.455
16.601
12.595
9.309
6.615
4.385
2.491
0.805
1.205
2.891
4.785
7.015
9.709
12.995
17.001
21.855
27.685
34.619
42.785
52.311
63.325
75.955
90.329
106.575
124.821
145.195
167.825
192.839
220.365
250.531

f2 (x)
208.038
182.224
158.794
137.62
118.574
101.528
86.354
72.924
61.11
50.784
41.818
34.084
27.454
21.8
16.994
12.908
9.414
6.384
3.69
1.204
1.804
4.29
6.984
10.014
13.508
17.594
22.4
28.054
34.684
42.418
51.384
61.71

x
3
7
11
15
19
23
27
31
35
39
43
47
51
55
59
63
67
71
75
79
83
87
91
95
99
103
107
111
115
119
123
127

9

f1 (x)
32.375
25.729
20.155
15.525
11.711
8.585
6.019
3.885
2.055
0.401
1.614
3.34
5.306
7.64
10.47
13.924
18.13
23.216
29.31
36.54
45.034
54.92
66.326
79.38
94.21
110.944
129.71
150.636
173.85
199.48
227.654
258.5

f2 (x)
201.354
176.148
153.294
132.664
114.13
97.564
82.838
69.824
58.394
48.42
39.774
32.328
25.954
20.524
15.91
11.984
8.618
5.684
3.054
0.6
2.413
4.939
7.705
10.839
14.469
18.723
23.729
29.615
36.509
44.539
53.833
64.519

x
4
8
12
16
20
24
28
32
36
40
44
48
52
56
60
64
68
72
76
80
84
88
92
96
100
104
108
112
116
120
124
128

f1 (x)
30.606
24.24
18.914
14.5
10.87
7.896
5.45
3.404
1.63
0
2.03
3.804
5.85
8.296
11.27
14.9
19.314
24.64
31.006
38.54
47.37
57.624
69.43
82.916
98.21
115.44
134.734
156.22
180.026
206.28
235.11
266.644

f2 (x)
194.825
170.219
147.933
127.839
109.809
93.715
79.429
66.823
55.769
46.139
37.805
30.639
24.513
19.299
14.869
11.095
7.849
5.003
2.429
0
3.029
5.603
8.449
11.695
15.469
19.899
25.113
31.239
38.405
46.739
56.369
67.423

Figure 3: Eigenvalue gap (in gray) of the Two-Parabolas problem of Fig.2 for w = 0.57. The eigenvalue gap
at s = 1 is exactly |hw, f (x)i − hw, f (y)i|, where x = 59 and y = 60 are the smallest and second smallest
solutions with respect to w.

7

Concluding Remarks and Open Problems

In this work we showed that the quantum adiabatic algorithm of [FGGS00] can be used for multiobjective
combinatorial optimization problems. In particular, a simple linearization of the objective functions suffices
to guarantee convergence to a Pareto-optimal solution provided the linearized single-objective problem has
an unique optimal solution. Nevertheless, even if a linearization of objectives does not give an unique optimal
solution, then it is always possible to choose an appropriate linearization that does.
We end this paper by listing a few promising and challenging open problems.
1. To make any practical use of Theorem 4.1 we need to chose w ∈ Wd in such a way that the optimal
solution of the linearization of an MCO has an unique solution. It is very difficult, however, to know a
priori which w to chose in order to use the adiabatic algorithm. Therefore, more research is necessary
to learn how to select these linearizations. One way could be to constraint the domain of an MCO in
order to minimize the number of weak-equivalent solutions.
2. Another related issue is learn how to solve multiobjective problems in the presence of equivalent
solutions. A technique of mapping an MCO with equivalent solutions to Hamiltonians seems very
difficult owing to the fact that the smallest eigenvalue must be unique in order to apply the adiabatic
theorem.
3. According to Theorem 4.1, we can only find all supported solutions. Other works showed that the
number of non-supported solutions can be much larger than the number of supported solutions [EG00].
Hence, it is interesting to construct a quantum algorithm that could find an approximation to all
Pareto-optimal solutions.
4. Prove our conjecture of Section 6 that the eigenvalue gap of the Hamiltonian of Eq.(11), corresponding
to the Two-Parabolas problem, is at least the difference between the smallest solution and second
smallest solution for any given linearization of the objective functions.

References
[AR04]

Andris Ambainis and Oded Regev. An elementary proof of the quantum adiabatic theorem.
arXiv:quant-ph/0411152, 2004.

[BBW05]

W. P. Baritompa, D. W. Bulger, and G. R. Wood. Grover’s quantum algorithm applied to
global optimization. SIAM Journal on Optimization, 15(4):11701184, 2005.

10

[BF26]

Max Born and Vladimir Fock. Beweis des adiabatensatzes. Zeitschrift für Physik, 51(3–4):165–
180, 1926.

[BV16]

Benjamin Barán and Marcos Villagra. Multiobjective optimization in a quantum adiabatic computer. Electronic Notes in Theoretical Computer Science, 329:27–38, 2016. arXiv:1605.03152.

[CPGW15] Toby S. Cubitt, David Perez-Garcia, and Michael M. Wolf. Undecidability of the spectral gap.
Nature, 528:207–211, 2015.
[DC08]

Arnab Das and Bikas K. Chakrabarti. Quantum annealing and quantum computation. Reviews
of Modern Physics, 80(1061), 2008.

[DH99]

Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum. arXiv:quantph/9607014, 1999.

[EG00]

Matthias Ehrgott and Xavier Gandibleux. A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum, 22(4):425–460, 2000.

[FGGS00]

Edward Farhi, Jeffrey Goldstone, Sam Gutman, and Michael Sipser. Quantum computation by
adiabatic evolution. arXiv:quant-ph/0001106, 2000.

[Gro96]

Lov Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the
28th Annual ACM Symposium on the Theory of Computing (STOC), pages 212–219, 1996.

[Kat50]

Tosio Kato. On the adiabatic theorem of quantum mechanics. Journal of the Physical Society
of Japan, 5(6):435, 1950.

[KLP75]

H. T. Kung, F. Luccio, and F. P. Preparata. On finding the maxima of a set of vectors. Journal
of the ACM, 22(4):469–476, 1975.

[Mes62]

Albert Messiah. Quantum Mechanics, Volume II. North Holland, 1962.

[NC00]

Michael Nielsen and Isaac Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.

[PY00]

Christos Papadimitriou and Mihalis Yannakakis. On the approximability of trade-offs and
optimal access of web sources. In Proceedings of the 41st Annual Symposium on Foundations
of Computer Science (FOCS), pages 86–92, 2000.

[Rei04]

Ben Reichardt. The quantum adiabatic optimization algorithm and local minima. In Proceedings
of the 36th Annual ACM Symposium on Theory of Computing (STOC), pages 502–510, 2004.

[Sho94]

Peter Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), pages
124–134, 1994.

[SWL04]

Marcelo Silva Sarandy, Lian-Ao Wu, and Daniel A. Lidar. Consistency of the adiabatic theorem.
Quantum Information Processing, 3(6):331–349, 2004.

[vDMV01]

Wim van Dam, Michele Mosca, and Umesh Vazirani. How powerful is adiabatic quantum
computation? In Proceedings of the 42nd IEEE Symposium on Foundations of Computer
Science (FOCS), pages 279–287. IEEE, 2001.

[vLBB14]

Christian von Lücken, Benjamin Barán, and Carlos Brizuela. A survey on multi-objective evolutionary algorithms for many-objective problems. Computational Optimization and Applications,
58(3):707–756, 2014.

11

