We devise an Ising model for the max-sum dispersion problem 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 corresponding Schrodinger equations and observe our approach to work well. 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 e cient 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 argmin s|Q s + s|q: s2f 1;+1gn 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 2 Rn n and q 2 Rn model internal and external dependencies, respectively. Ising models as in (1) occur in various data science settings [5, 6] which thus stand to bene t from quantum computing because it promises an e ciency unreachable by digital computers.
Introduction
(
S = argmax X X d xi; xj
S X xi2S xj2S s:t: jSj = k:
Introducing a distance matrix D 2 Rn n where Dij = d xi; xj and a binary
indicator vector z 2 f0; 1gn where zi = 1 if xi 2 S, (
Equation (
Using the equivalence z|1 = k , z|1 k 2 = 0, the problem in (
Written like this, max-sum dispersion is recognizable as a problem similar to
the one in (
argmin s|Q s + s|q s2f 1;+1gn which constitutes an appropriate Ising model for max-sum dispersion. Once the solution s is available, entries si = +1 indicate which xi 2 X to select into S .
2n 1 (t) = X ai(t) i=0 i : The key idea is to understand each basis state j ii 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 (
If the sought after solution is known to correspond to a minimum energy
con guration 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 (
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 where zi denotes the Pauli spin matrix z acting on the i-th qubit. Likewise and again following standard suggestions, we choose
n n HP = X X Qij zi zj + n
X qi zi can be used to let j (t)i evolve from the ground state j (0)i of HB to a nal state j (T )i where j (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 j ii is given by the amplitude jai(T )j2. However, since the adiabatic evolution was steered towards the problem Hamiltonian HP , states j ii that correspond to ground states of HP are more likely to be found.
The computational e ciency of adiabatic quantum computing will depend
on the choice of T in (
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 Schrodinger equations using the Python toolbox QuTip [9].
Figure 1 shows n = 12 monthly weather measurements in Hamburg. We normalize them to unit variance so that far points are 30 nOe(i2th)earpoafrtt.hSeettetirnmgs in=(62) ntowdilolmthineantec.aWusee ◦ []reC2205 May Sep AuJguJlun tscreoatntcsitnidgke,rw2Eeufw4col;ir5dk;e6wagnithddi1ivs2etraqsnuecbeeisltesmaynsedtnetmtsr.syIinntoaeaescuxh-- rtteeapum11055 FebApr MOJacartn Nov Dec 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 2 O p212 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 correspond 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 nal states for the qubit systems to be found in are j010010100001i, j010101010001i, and j110100110001i for k 2 f4; 5; 6g, respectively. Understood as indicator vectors, these qubit con gurations represent the sets fFebruary, May, July, Decemberg, fFebruary, April, June, August, Decemberg, and fJanuary, February, April, July, August, Decemberg.
Our experiments thus suggest that AQC can solve max-sum dispersion. Classical 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 2 O p2n suggests that it can accomplish this quadratically 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 = 6 40