=Paper=
{{Paper
|id=Vol-2454/paper_22
|storemode=property
|title=Max-Sum Dispersion via Quantum Annealing
|pdfUrl=https://ceur-ws.org/Vol-2454/paper_22.pdf
|volume=Vol-2454
|authors=Christian Bauckhage,Rafet Sifa,Dirk Hecker,Stefan Wrobel
|dblpUrl=https://dblp.org/rec/conf/lwa/BauckhageSHW19
}}
==Max-Sum Dispersion via Quantum Annealing==
https://ceur-ws.org/Vol-2454/paper_22.pdf
Max-Sum Dispersion via Quantum Annealing
Christian Bauckhage123 , Rafet Sifa12 , Dirk Hecker12 , and Stefan Wobel123
1
Fraunhofer Center for Machine Learning, Sankt Augustin, Germany
2
Fraunhofer IAIS, Sankt Augustin, Germany
3
B-IT, University of Bonn, Bonn, Germany
Abstract. We devise an Ising model for the max-sum dispersion prob-
lem which occurs in contexts such as Web search or text summarization.
Given this Ising model, max-sum dispersion can be solved on adiabatic
quantum computers; in proof of concept simulations, we solve the corre-
sponding Schrödinger equations and observe our approach to work well.
1 Introduction
Quantum computing exploits quantum mechanical phenomena for information
processing and is about to become a technical reality [7]. This will likely impact
machine learning and data mining because quantum computing promises efficient
solutions to certain optimization problems encountered there [2, 4, 12]. Here, we
explore quantum computing for unsupervised learning and discuss how to solve
the max-sum dispersion problem via adiabatic quantum computing (AQC).
Adiabatic quantum computers determine minimum energy states of Ising
models, that is they solve combinatorial optimization problems of the form
s∗ = argmin s| Q s + s| q. (1)
s∈{−1,+1}n
The 2n vectors s over which to minimize represent possible global states of a
system of n entities each of which can be in one of two local states; Q ∈ Rn×n
and q ∈ Rn model internal and external dependencies, respectively. Ising models
as in (1) occur in various data science settings [5, 6] which thus stand to benefit
from quantum computing because it promises an efficiency unreachable by digital
computers.
2 An Ising Model for the Max-Sum Dispersion Problem
The max-sum dispersion problem occurs in where data mining practitioners are
interested in identifying diverse or mutually far apart elements of a set of objects
or observations [1, 8, 10, 11]. Given a finite data set X = {x1 , . . . , xn } and a
distance measure d(·, ·), the problem is to determine a subset of size k < n of
Copyright c 2019 for this paper by its authors. Use permitted under Creative Com-
mons License Attribution 4.0 International (CC BY 4.0).
maximum dispersion. In other words, the max-sum dispersion problem consists
in solving the following constrained optimization problem
X X
S ∗ = argmax
d xi , xj s.t. |S| = k. (2)
S⊂X
xi ∈S xj ∈S
Introducing a distance matrix D ∈ Rn×n where Dij = d xi , xj and a binary
indicator vector z ∈ {0, 1}n where zi = 1 if xi ∈ S, (2) can be written as
z ∗ = argmax z | D z s.t. z | 1 = k. (3)
z∈{0,1}n
Equation (3) reveals max-sum dispersion to be an integer programming prob-
lem and thus to be NP-hard. State of the art solutions involve greedy approx-
imations which achieve O(nk) efficiency but lack optimality guarantees. More
sophisticated algorithms provide optimality guarantees of O(1 − 1/k) and re-
quire O(nk 2 log k) runtime or achieve O(1 − 1/) at O(n/ log k) runtime where
the constant 1. Interestingly, however, problem (3) resembles the Ising en-
ergy minimization problem in (1). This suggests that it might be amenable to
quantum computing.
2
Using the equivalence z | 1 = k ⇔ z | 1 − k = 0, the problem in (3) can
also be written as an unconstrained maximization problem
2
z ∗ = argmax z | D z − λ z | 1 − k (4)
z∈{0,1}n
where λ ∈ R is a Lagrange multiplier. Treating this multiplier as a constant and
expanding the expression on the right hand side, we find
z ∗ = argmin −z | D − λ 11| z − λ 2 k z | 1 + const
(5)
z∈{0,1}n
where we used that (4) is quadratic form in z so that the maximization problem
can equivalently be cast in terms of a minimization problem.
Written like this, max-sum dispersion is recognizable as a problem similar to
the one in (1). However, while (5) minimizes over binary vectors z ∈ {0, 1}n , Ising
models as in (1) involve bipolar vectors s ∈ {−1, +1}n . Yet, since s = 2 · z − 1
is a bipolar vector so that we can write binary vectors as z = s + 1 /2. Hence,
using the substitutions Q = − 41 (D − λ 11| ) and q = − 12 (D − λ 11| )1 − λk1,
the problem in (5) can also be written as
s∗ = argmin s| Q s + s| q (6)
s∈{−1,+1}n
which constitutes an appropriate Ising model for max-sum dispersion. Once the
solution s∗ is available, entries s∗i = +1 indicate which xi ∈ X to select into S ∗ .
3 Max-Sum dispersion via AQC
When using adiabatic quantum computing in order to identify k diverse elements
among a set of n elements, we consider a time dependent system of n qubits
n
2X −1
ψ(t) = ai (t) ψ i . (7)
i=0
The key idea is to understand each basis state |ψ i i as an indicator vector that
represents one of the 2n subsets of our data. The task is then to manipulate the
system such that, when measured afterwards, it will likely collapse to a state
which encodes the sought after solution.
Manipulations that obey the laws of quantum mechanics are modeled in
terms of Hamiltonian operators, and, if a qubit system as in (7) evolves under
the influence of a time-dependent Hamiltonian H(t), its behavior is governed by
d
the Schrödinger equation i ~ dt ψ(t) = H(t) ψ(t) . To use this for computing,
one prepares a qubit register in the ground state of a problem independent
beginning Hamiltonian HB and evolves it towards a problem Hamiltonian HP
whose ground state represents a solution to the problem at hand.
If the sought after solution is known to correspond to a minimum energy
configuration of an Ising model, a seminal paper by Farhi et al. [6] proposed a
simple recipe for how to set up appropriate problem Hamiltonians. To set up HP
for the Ising model in (6), we therefore follow standard suggestions and define
n X
X n n
X
HP = Qij σzi σzj + qi σzi (8)
i=1 j=1 i=1
where σzi denotes the Pauli spin matrix σz acting on the i-th qubit. Likewise
and again following standard suggestions, we choose
n
X
HB = − σxi (9)
i=1
where σxi denotes the Pauli spin matrix σx acting on the i-th qubit. Considering
an evolution from t = 0 to t = T , the Hamiltonian of the system
H t = 1 − Tt · HB + Tt · HP
(10)
can be used to let |ψ(t)i evolve from the ground state |ψ(0)i of HB to a final
state |ψ(T )i where |ψ(0)i. Upon termination of this evolution, a measurement
of the qubit system causes it to collapse to one of its 2n basis states and the
probability for this state to be |ψ i i is given by the amplitude |ai (T )|2 . However,
since the adiabatic evolution was steered towards the problem Hamiltonian HP ,
states |ψ i i that correspond to ground states of HP are more likely to be found.
The computational efficiency of adiabatic quantum computing will depend
on the choice of T in (10) which is known to depend on the minimum energy gap
between the ground state and the first excited state of H(t). This gap is inversely
proportional to the square root of the number of basis states that have energies
close to global minimum [3]. For problems such as max-sum √ dispersion
where
the number of potential solutions is typically small, T ∈ O 2n is the smallest
possible runtime Hence, AQC can perform exhaustive searchers for max-sum
dispersion solutions quadratically faster than classically possible.
4 Proof of Concept Simulations
Next, we present didactic simulation experiments to illustrate the feasibility of
AQC for max-sum dispersion. In each case, we numerically solve the governing
Schrödinger equations using the Python toolbox QuTip [9].
Figure 1 shows n = 12 monthly weather
measurements in Hamburg. We normalize
30
them to unit variance so that far points are
25
O(2) apart. Setting λ = 2 n will then cause Aug
Jul
temperature [◦ C]
Jun
20
neither of the terms in (6) to dominate. We May Sep
15
consider Euclidean distances and try to ex- Apr Oct
10
tract k ∈ {4, 5, 6} diverse elements. In each Mar Nov
5 Feb Jan Dec
setting, we work with 12 qubit systems in a su-
perposition of 212 = 4096 basis states. Using 0
40 50 60 70 80
Hamiltonians as discussed √ above, we evolve precipitation [mm]
them over T = 100 ∈ O 212 steps.
Fig. 1: Data of monthly climatic
The top row of Fig. 2 shows the results conditions in Hamburg.
for each setting. The middle row visualizes
how each qubit system evolves over time. At
t = 0, all basis states are equally likely but
over time their amplitudes begin to diverge; amplitudes of basis states that cor-
respond to low energy states of our Ising model increase while amplitudes of
basis states that could hardly be considered a solution to our problem decrease.
At t = T , certain basis states are therefore more likely to be measured and
the tables in the bottom row of Fig. 2 rank the 5 most likely ones. Looking
at these tables, the most likely final states for the qubit systems to be found
in are |010010100001i, |010101010001i, and |110100110001i for k ∈ {4, 5, 6},
respectively. Understood as indicator vectors, these qubit configurations repre-
sent the sets {February, May, July, December}, {February, April, June, August,
December}, and {January, February, April, July, August, December}.
Our experiments thus suggest that AQC can solve max-sum dispersion. Clas-
sical algorithms typically resort to greedy heuristics. AQC, on the other hand,
(implicitly) performs exhaustive√ searches
over all 2n subsets of the n given data
points. Our choice of T ∈ O 2n suggests that it can accomplish this quadrat-
ically faster than classically possible. Finally, in contrast to classical algorithms,
the runtime of the AQC approach does not depend on the size k of the subset
to be selected.
result for k = 4 result for k = 5 result for k = 6
30 30 30
25 25 25
Aug
Jul Aug
Jul Aug
Jul
temperature [◦ C]
temperature [◦ C]
temperature [◦ C]
Jun Jun Jun
20 May Sep 20 May Sep 20 May Sep
15 Oct 15 Oct 15 Oct
Apr Apr Apr
10 Mar Nov
10 Mar Nov
10 Mar Nov
5 Feb Jan Dec 5 Feb Jan Dec 5 Feb Jan Dec
0 0 0
40 50 60 70 80 40 50 60 70 80 40 50 60 70 80
precipitation [mm] precipitation [mm] precipitation [mm]
ψi |ai |2 ψi |ai |2 ψi |ai |2
|010010100001i 0.002463 |010101010001i 0.002161 |110100110001i 0.001763
|010100100001i 0.002404 |010101100001i 0.002159 |110101100001i 0.001719
|010010010001i 0.002388 |010100110001i 0.002092 |110101010001i 0.001711
|010011000001i 0.002357 |010100101001i 0.001935 |010100110011i 0.001617
|010100010001i 0.002324 |010100011001i 0.001850 |011100110001i 0.001593
Fig. 2: AQC for max-sum dispersion (see the explanation in the text).
References
1. Abassi, Z., Mirrokni, V.S., Thakur, M.: Diversity Maximization under Matroid
Constraints. In: KDD (2013)
2. Aı̈meur, E., Brassard, G., Gambs, S.: Quantum Clustering Algorithms. In: ICML
(2007)
3. Amin, M.H.S.: Effect of Local Minima on Adiabatic Quantum Optimization. Phys-
ical Review Letters 100(13), 130503 (2008)
4. Bauckhage, C., Brito, E., Cvejoski, K., Ojeda, C., Sifa, R., Wrobel, S.: Ising Models
for Binary Clustering via Adiabatic Quantum Computing. In: EMMCVPR (2017)
5. Bauckhage, C., Ojeda, C., Sifa, R., Wrobel, S.: Adiabatic Quantum Computing for
Kernel k=2 Means Clustering. In: KDML-LWDA (2018)
6. Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum Computation by Adi-
abatic Evolution. arXiv:quant-ph/0001106 (2000)
7. Gibney, E.: Quantum Computer Gets Design Upgrade. Nature 541(7638) (2017)
8. Gollapudi, S., Sharma, A.: An Axiomatic Approach for Result Diversification. In:
WWW (2009)
9. Johansson, J., Nation, P., Nori, F.: QuTiP 2: A Python Framework for the Dynam-
ics of Open Quantum Systems. Computer Physics Communications 184(4) (2013)
10. Santos Rodrygo, L.T., Macdonald, C., Ounis, I.: Intent-aware Result Diversifica-
tion. In: SIGIR (2011)
11. Sifa, R., Bauckhage, C.: Online k-Maxoids Clustering. In: DSAA (2017)
12. Wiebe, N., Kapoor, A., Svore, K.M.: Quantum Algorithms for Nearest-Neighbor
Methods for Supervised and Unsupervised Learning. Quantum Information &
Computation 15(3–4) (2015)