JUNIQ Tutorial - Finde das beste Pokemon Team¶
In dieser Übung werden wir lernen, wie der Quantencomputer JUPSI funktioniert und wie wir ihn benutzen können, um optimale Pokemon-Teams zu erstellen.
Dieses Übung ist für Schüler gedacht und wurde durch die Arbeit von [Kuklinski und Gottlieb] (https://www.youtube.com/watch?v=CSLm1HrY6UE) inspiriert.
Um loszulegen, führe zunächst die beiden unteren Zellen aus, um alle nötigen Programme zu laden. Unseren Quantencomputer erreichen wir im Weiteren über die Variable jupsi.
from dwave.system import DWaveSampler, EmbeddingComposite
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
jupsi = EmbeddingComposite(DWaveSampler(region='eu-central-1', token="FUEGE_DEIN_DWAVE_API_TOKEN_HIER_EIN"))
Einführung¶
JUPSI kann Quadratic Unconstrained Binary Optimization (QUBO) Probleme lösen.
Was bedeutet das?
- Optimization: JUPSI findet das Minimum einer Kostenfunktion:
z.B. min( q0 + q1 - q2 - q0*q1 + ... )
^^^^^^^^^^^^^^^^^^^^^^^^^^
Kostenfunktion
- Binary: Die Kostenfuntion besteht aus Qubits q. JUPSI bestimmt binäre Zahlen (
0oder1) für jedes Qubits.
z.B. q0 = 0
q1 = 0
q2 = 1
q3 = 1
q4 = 1
q5 = 0
- Quadratic: Die einzelnen Terme in der Kostenfunktion bestehen nur aus einzelnen Qubits (linearer Term, z.B.
+q1) oder aus zwei Qubits (quadratischer Term, z.B.-q1*q2)
Das ist ein QUBO: min( q0 + q1 - q2 - q0*q1 + ... )
Das ist kein QUBO: min( q0 + q1 - q2 - q0*q1*q2 + ... )
Beispiele¶
Beispiel 1
Was ist das Minimum?
min( q0 + q1 )
Lösung:
q0 = 0
q1 = 0
=> q0 + q1 = 0Beispiel 2
Was ist das Minimum?
min( q0 - q1 + q2 )
Lösung:
q0 = 0
q1 = 1
q2 = 0
=> q0 - q1 + q2 = -1Beispiel 3
Was ist das Minimum?
min( 3*q0 - 2*q1 - 5*q0*q1 )
Lösung:
q0 = 1
q1 = 1
=> 3*q0 - 2*q1 - 5*q0*q1 = -4Solche Probleme können schnell sehr schwierig werden.
Zum Glück haben wir unseren Quantenannealer JUPSI, der entwickelt wurde um genau solche Probleme zu lösen.
Um Beispiel 3 mit JUPSI zu lösen, müssen wir die Gleichung in etwas übersetzen, das der Quantencomputer verstehen kann. Wir verwenden dazu ein dictionary in Python.
Folge einfach diesen Schritten.
- Identifiziere die Zahlen in dem QUBO Problem. Hier haben wir:
3, -2, -5. Schreiben wir diese also in unser dictionary Q:
Q = {
3,
-2,
-5
}
- Dies sagt JUPSI aber nicht, welche Zahl zu welchem Qubit gehört. -5 gehört zu den Qubits
0und1:q0*q1. Wir machen das mit dieser Notation:
(0, 1): -5
- Die Zahlen, die zu einem einzelnen Qubit gehören, müssen die gleiche Form haben. Wir schreiben die Zahlen also zweimal:
(0, 0): 3,
(1, 1): -2
Das Ergebnis steht in der nächsten Zelle. Das ist bereits ein vollständiges Quantencomputerprogramm!
Klicke in die Zelle und anschließend oben auf den Pfeil, um das Program auf JUPSI laufen zu lassen.
Q = {
(0, 0): 3,
(1, 1): -2,
(0, 1): -5,
}
result = jupsi.sample_qubo(Q)
result.to_pandas_dataframe()
| 0 | 1 | chain_break_fraction | energy | num_occurrences | |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 0.0 | -4.0 | 1 |
JUPSI findet das Minimum, bei q0 = 1 und q1 = 1 mit dem Wert 3*q0 - 2*q1 - 5*q0*q1 = -4.
Die Zahl -4 an dem Minimum wird die Energie des QUBO genannt.
Aufgabe 1
Löse das folgende QUBO-Problem auf JUPSI! Verwende dazu einfach das gleiche Verfahren wie oben.
min( - 3*q0 - 2*q1 + 4*q2 + 5*q3 - 4*q0*q1 + 7*q1*q2 - 3*q0*q2 )
Welche Werte haben die Qubits am Minimum?
Welche Energie hat das QUBO am Minimum?
Q = {
# Vervollständige das Quantencomputerprogramm, indem du das QUBO Problem hier einträgst, so wie wir es für Beispiel 3 getan haben
}
result = jupsi.sample_qubo(Q)
result.to_pandas_dataframe()
Ein Quantenannealer sucht nicht nur nach der einen Lösung mit der minimalen Energie, sondern auch nach anderen Lösungen mit etwas höheren Energien.
Wenn es mehr als eine Lösung gibt, können wir diese finden, indem wir das Quantenprogramm mehrmals wiederholen (reads = Anzahl der Quantencomputerdurchläufe):
z.B. num_reads = 1000
Beispiel 4¶
min( - 2*q0*q1 + 2*q0*q2 - 2*q0*q3 + 2*q1*q2 + 2*q1*q3 )
Q = {
(0, 1): -2,
(0, 2): 2,
(0, 3): -2,
(1, 2): 2,
(1, 3): 2,
}
result = jupsi.sample_qubo(Q, num_reads=1000)
result.to_pandas_dataframe()
| 0 | 1 | 2 | 3 | chain_break_fraction | energy | num_occurrences | |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 1 | 0.0 | -2.0 | 413 |
| 1 | 1 | 1 | 0 | 0 | 0.0 | -2.0 | 292 |
| 2 | 1 | 0 | 0 | 1 | 0.0 | -2.0 | 295 |
Aufgabe 2
Löse ein beliebiges QUBO deiner Wahl.
# Schreibe dein Quantencomputerprogramm hier:
Fragen:
Wie viele Lösungen hast du gefunden?
Welche Energien haben diese?
Tipp: JUPSI kann nicht nur die minimale Energie finden, sondern auch nahezu optimale Lösungen mit einer etwas höheren Energie. Je mehr Terme das QUBO hat, desto wahrscheinlicher ist es, dass es nahezu optimale Lösungen findet.
Das Optimieren von Pokemon Teams¶
Um ein gutes Pokemon-Team zu finden, werden wir jeden Pokemon-Typ (PT) durch ein Qubit qType repräsentieren.
Wenn das Qubit
qType = 1ist, werden wir ein Pokemon dieses Typs in unser Team aufnehmen.Wenn das Qubit
qType = 0ist, nehmen wir es nicht auf.
Die Karte unten zeigt, welcher Pokemon-Typ stark (grünes Feld) oder schwach (rotes Feld) gegen einen anderen Pokemon-Typ ist.
Beispiel: Wasser (Zeile 3) ist stark gegen Feuer (Spalte 2), aber schwach gegen Wasser (Spalte 3) und Gras (Spalte 4)
Kostenfunktion¶
Wir wollen zunächst nur Fire, Water, Grass, Electric, Ice und Fighting betrachten.
Um ein optimales Pokemon-Team zu finden, betrachten wir drei Möglichkeiten für die Kostenfunktion:
- Offensiv: Für jeden Angriffstyp
qType(Reihe) zählen wir-1für einen starken Angriff (grünes Feld in einer Reihe) und+1für einen schwachen Angriff (rotes Feld in einer Reihe). Z.B. für qFire rechnen wir(-1) + (-1) + 1 + 1 = 0und erhalten somit0 * qFirein unserem QUBO.
min( 0*qFire + 1*qWater + 1*qGrass + 1*qElectric + 2*qIce - 2*qFighting )
- Defensive: Für jede Verteidigungstyp
qType(Spalte) zählen wir-1für einen schwachen Angriff (rotes Feld in einer Spalte) und+1für einen starken Angriff (grünes Feld in einer Spalte). Z.B. für qFire rechnen wir(-1) + 1 + (-1) + (-1) = -2und erhalten somit-2 * qFirein unserem QUBO.
min( - 2*qFire - 1*qWater - 1*qGrass - 1*qElectric + 1*qIce + 0*qFighting )
- Ausgeglichen: Für jeden Pokemon-Typ
qTypeaddieren wir die offensiven Kosten (1.) und die defensiven Kosten (2.). Z.B. für qFire rechnen wir0 + (-2) = -2und erhalten somit-2 * qFirein unserem QUBO.
min( - 2*qFire + 0*qWater + 0*qGrass + 0*qElectric + 3*qIce - 2*qFighting )
Zuerst optimieren wir für eine offensives Team. Beachte, dass wir die Qubits nicht mit 0, 1, 2, ... bezeichnen müssen, sondern sie auch 'Fire', 'Water', etc. nennen können.
Führe das Quantencomputerprogramm unten aus. Ist die Lösung sinnvoll?
Q = {
('Fire', 'Fire'): 0,
('Water', 'Water'): 1,
('Grass', 'Grass'): 1,
('Electric', 'Electric'): 1,
('Ice', 'Ice'): 2,
('Fighting', 'Fighting'): -2,
}
result = jupsi.sample_qubo(Q, num_reads=100)
result.to_pandas_dataframe()
| Electric | Fighting | Fire | Grass | Ice | Water | chain_break_fraction | energy | num_occurrences | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0.0 | -2.0 | 46 |
| 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0.0 | -2.0 | 54 |
Aufgabe 3
Optimiere ein ausgeglichenes Pokemon team!
# Schreibe dein Quantencomputerprogramm hier:
Aufgabe 4
Optimiere ein defensives Pokemon team!
# Schreibe dein Quantencomputerprogramm hier:
Bonus Aufgabe 4
Berücksichtige dieses Mal nicht nur die 6 Pokemon-Typen, sondern alle 18 und finde ein optimales defensives Team.
Frage: Ein Schadensmultiplikator von 0 (schwarzes Feld in einer Spalte) ist am Besten. Wie sollte dies in der Kostenfunktion berücksichtigt werden?
# Schreibe dein Quantencomputerprogramm hier:
Nebenbedingungen¶
Betrachten wir noch einmal Beispiel 4:
min( - 2*q0*q1 + 2*q0*q2 - 2*q0*q3 + 2*q1*q2 + 2*q1*q3 )
Q = {
(0, 1): -2,
(0, 2): 2,
(0, 3): -2,
(1, 2): 2,
(1, 3): 2,
}
result = jupsi.sample_qubo(Q, num_reads=1000)
result.to_pandas_dataframe()
| 0 | 1 | 2 | 3 | chain_break_fraction | energy | num_occurrences | |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 0 | 0.0 | -2.0 | 341 |
| 1 | 1 | 0 | 0 | 1 | 0.0 | -2.0 | 206 |
| 2 | 1 | 1 | 0 | 1 | 0.0 | -2.0 | 453 |
JUPSI findet drei Lösungen:
1 0 0 1(zwei Qubits sind 1)1 1 0 0(drei Qubits sind 1)1 1 0 1(drei Qubits sind 1)
Wenn wir jedoch nur Lösungen betrachten wollen bei denen z.B. genau zwei Qubits 1 sind, d.h.
q0 + q1 + q2 + q3 == 2,
können wir weitere Nebenbedingungen zu unserem QUBO hinzufügen:
(q0 + q1 + q2 + q3 - 2)²
Diese Nebenbedingung verschwindet (d.h. wird = 0), wenn genau zwei Qubits den Wert 1 haben.
Um diesen Term zu unserem QUBO hinzuzufügen, müssen wir ihn zunächst ausmultiplizieren, da unser QUBO nur aus linearen und quadratischen Termen bestehen darf.
(q0 + q1 + q2 + q3 - 2)² = (q0 + q1 + q2 + q3 - 2)*(q0 + q1 + q2 + q3 - 2)
= q0*q0 + q0*q1 + q0*q2 + q0*q3 - 2*q0
+ q1*q0 + q1*q1 + q1*q2 + q1*q3 - 2*q1
+ q2*q0 + q2*q1 + q2*q2 + q2*q3 - 2*q2
+ q3*q0 + q3*q1 + q3*q2 + q3*q3 - 2*q3
- 2*q0 - 2*q1 - 2*q2 - 2*q3
+ 4
Wir können den oberen Ausdruck vereinfachen, indem wir drei Ticks nutzen:
q0*q0 = q0, weilq0nur0oder1sein kann und0*0 = 0und1*1 = 1q1*q0 = q0*q1- Konstante Zahlen, wie die
4, können wir weglassen, da sie nur den Wert des Minimums verändern, aber nicht die zugehörigen Qubitwerte am Minimum.
Wir erhalten somit:
Nebenbedingung: min( - 3*q0 - 3*q1 - 3*q2 - 3*q3 + 2*q0*q1 + 2*q0*q2 + 2*q0*q3 + 2*q1*q2 + 2*q1*q3 + 2*q2*q3 )
Addieren wir nun diese Nebenbedingung zu unserem ursprünglichen QUBO erhalten wir:
QUBO: min( - 3*q0 - 3*q1 - 3*q2 - 3*q3 + 4*q0*q2 + 4*q1*q2 + 4*q1*q3 + 2*q2*q3 )
Q = {
(0, 0): -3,
(1, 1): -3,
(2, 2): -3,
(3, 3): -3,
(0, 2): 4,
(1, 2): 4,
(1, 3): 4,
(2, 3): 2,
}
result = jupsi.sample_qubo(Q, num_reads=100)
result.to_pandas_dataframe()
Aufgabe 5
Löse das QUBO aus Beispiel 4 min( - 2*q0*q1 + 2*q0*q2 - 2*q0*q3 + 2*q1*q2 + 2*q1*q3 ) unter der Nebenbedingung, dass genau drei Qubits den Wert 1 haben:
q0 + q1 + q2 + q3 = 3
Tipp: Das QUBO sieht sehr ähnlich aus wie oben. Wenn du dir genau ansiehst, was mit der 2 in (q0 + q1 + q2 + q3 - 2)² passiert, kannst du vielleicht erraten, was mit einer 3 dort passieren würde.
# Schreibe dein Quantencomputerprogramm hier:
Hinweis für Fortgeschrittene:
Die allgemeine Formel für ein constraint Term der Form q0 + q1 + q2 + ... == s lautet
CONSTRAINT: min( - (2s-1)*q0 - (2s-1)*q1 - (2s-1)*q2 - ...
+ 2*q0*q1 + 2*q0*q2 + 2*q0*q3 + ...
+ 2*q1*q2 + 2*q1*q3 + ...
+ 2*q2*q3 + ... )
oder in Summenschreibweise:
$$
\sum_{i=0}^{n-1} -(2s-1) q_i + \sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1} 2 q_i q_j
$$
In Python könnten wir die folgenden "for"-Schleifen verwenden, um alle diese Terme zu einem QUBO Q zu addieren:
for i in range(n):
Q[(i, i)] += -(2*s - 1)
for i in range(n):
for j in range(i+1, n):
Q[(i, j)] += 2
Beachte, dass n und s vorhanden sein müssen. Außerdem ist es gut, das QUBO nicht als Q = {}, sondern als Q = defaultdict(float) zu definieren, da so (i, j): 0 automatisch zu Q hinzugefügt wird.
Nebenbedingung: Teamgröße¶
Ein Pokemon-Team sollte nicht beliebig groß sein.
Deshalb fügen wir nun die Bedingung hinzu, dass es genau 3 Pokemon in unserem Team geben soll (Anmerkung: In einem normalen Pokemon-Team gibt es normalerweise 6 Pokemon):
qFeuer + qWasser + qGras + qElektrik + qEis + qKampf = 3
Um das zu erreichen, müssen wir die folgende Nebenbedingung zu unserem QUBO hinzufügen:
(qFeuer + qWasser + qGras + qElektro + qEis + qKampf - 3)²
Mit dem Ergebnis aus Aufgabe 5 erhalten wir die folgenden Terme:
- 5*qFire - 5*qWater - 5*qGrass - 5*qElectric - 5*qIce - 5*qFighting
+ 2*qFire*qWater + 2*qFire*qGrass + 2*qFire*qElectric + ...
+ 2*qWater*qGrass + 2*qWater*qElectric + ...
+ 2*qGrass*qElectric + ...
+ ...
Wir beginnen damit ein ausgeglichenes Team bestehend aus drei Pokemon-Typen zu finden. Führe hierzu die Zelle unten aus.
Frage: Ist das Ergebnis sinnvoll? Betrachte dazu erneut das QUBO:
min( - 2*qFire + 0*qWater + 0*qGrass + 0*qElectric + 3*qIce - 2*qFighting )
Q = {
('Fire', 'Fire'): -2 - 5,
('Water', 'Water'): 0 - 5,
('Grass', 'Grass'): 0 - 5,
('Electric', 'Electric'): 0 - 5,
('Ice', 'Ice'): 3 - 5,
('Fighting', 'Fighting'): -2 - 5,
('Fire', 'Water'): 2,
('Fire', 'Grass'): 2,
('Fire', 'Electric'): 2,
('Fire', 'Ice'): 2,
('Fire', 'Fighting'): 2,
('Water', 'Grass'): 2,
('Water', 'Electric'): 2,
('Water', 'Ice'): 2,
('Water', 'Fighting'): 2,
('Grass', 'Electric'): 2,
('Grass', 'Ice'): 2,
('Grass', 'Fighting'): 2,
('Electric', 'Ice'): 2,
('Electric', 'Fighting'): 2,
('Ice', 'Fighting'): 2,
}
result = jupsi.sample_qubo(Q, num_reads=1000)
result.to_pandas_dataframe()
Aufgabe 6
Finde ein optimales defensives Pokemon Team bestehend aus 4 Pokemon!
# Schreibe dein Quantencomputerprogramm hier:
Bonus Aufgabe 6
Betrachte nun alle 18 Pokemon Typen und finde ein optimales defensives Team bestehend aus 6 Pokemon.
# Schreibe dein Quantencomputerprogramm hier:
Advanced¶
This section contains further code snippets for advanced users.
General QUBO¶
The QUBO Matrix¶
A good way to visualize larger problems is to build and plot the QUBO matrix (also known as "Hamilton matrix").
In the QUBO matrix, every term in the QUBO of the form
(i, j): Qij
will appear in row i and column j (where we always require i<j, otherwise we simply swap i and j)
For example, the QUBO matrix for the QUBO from Exercise 1
min( - 3*q0 - 2*q1 + 4*q2 + 5*q3 - 4*q0*q1 + 7*q1*q2 - 3*q0*q2 )
looks like this:
/ -3 -4 -3 0 \
| 0 -2 7 0 |
| 0 0 4 0 |
\ 0 0 0 5 /
# you can use the following function to plot this matrix
def plot_qubo_matrix(Q, figsize=(6,5)):
seen = set()
keys = [key for key in sum(map(list,Q), start=[]) if not (key in seen or seen.add(key))]
Q = {(keys.index(keyi), keys.index(keyj)): Q[keyi,keyj] for keyi,keyj in Q}
dim = max(max(i,j) for i,j in Q) + 1
Qmatrix = np.zeros((dim,dim))
for (i,j),Qij in Q.items():
if i > j: # aggregate terms in the upper triangle
i,j = j,i
Qmatrix[i,j] += Qij
plt.figure(figsize=figsize)
plt.imshow(Qmatrix, cmap='Spectral')
for i in range(dim):
for j in range(i,dim):
plt.text(j, i, f'{Qmatrix[i,j]:.2f}', ha='center', va='center')
Qmax = np.max(np.abs(Qmatrix))
plt.clim((-Qmax,Qmax))
plt.colorbar()
plt.xticks(range(dim), keys)
plt.yticks(range(dim), keys)
plt.show()
Q = {
(0,0): -3,
(1,1): -2,
(2,2): 4,
(3,3): 5,
(0,1): -4,
(1,2): 7,
(0,2): -3,
}
upload and
plot_qubo_matrix(Q)
Generic Equality Constraints¶
The following code shows how to optimize an offensive Pokemon team with 6 Pokemon over all Pokemon types.
The constraint with 6 Pokemon
qFire + qWater + qGrass + ... == 6
will be added generically using for loops.
types = ['Normal', 'Fire', 'Water', 'Grass', 'Electric', 'Ice', 'Fighting', 'Poison', 'Ground', 'Flying', 'Psychic', 'Bug', 'Rock', 'Ghost', 'Dragon', 'Dark', 'Steel', 'Fairy']
# we define Q as defaultdict(float) instead of simply {}; this will always add `(i, j): 0.0` automatically to `Q` if `(i, j)` it does not yet exist in `Q`.
from collections import defaultdict
Q = defaultdict(float)
# add the terms of the cost function to the QUBO
Q[('Normal', 'Normal')] = 4 # we consider a "0" as "even worse" and add a double penalty of +2
Q[('Fire', 'Fire')] = 0
Q[('Water', 'Water')] = 0
Q[('Grass', 'Grass')] = 4
Q[('Electric', 'Electric')] = 3
Q[('Ice', 'Ice')] = 0
Q[('Fighting', 'Fighting')] = 2
Q[('Poison', 'Poison')] = 4
Q[('Ground', 'Ground')] = -1
Q[('Flying', 'Flying')] = 0
Q[('Psychic', 'Psychic')] = 2
Q[('Bug', 'Bug')] = 4
Q[('Rock', 'Rock')] = -1
Q[('Ghost', 'Ghost')] = 1
Q[('Dragon', 'Dragon')] = 2
Q[('Dark', 'Dark')] = 1
Q[('Steel', 'Steel')] = 1
Q[('Fairy', 'Fairy')] = 0
# add the constraints
for t in types:
Q[(t, t)] += -(2*6 - 1)
for i in range(len(types)):
for j in range(i+1, len(types)):
Q[(types[i], types[j])] += 2
# solve the problem on the quantum annealer
result = jupsi.sample_qubo(Q, num_reads=100)
result.to_pandas_dataframe()[types+['energy','num_occurrences']] # this indexing sorts the columns; furthermore, we do not display the column 'chain break fraction' to show the table in full width
The solution makes sense if all Pokemon with negative cost are on the team, and all with zero cost occur equally likely.
Inequality Constraint: Diversity¶
Against every attacking type, we want fewer than two weak Pokemon on our team.
For example, against Fire, the types Grass, Ice, and Bug are weak. Therefore we want only 0 or 1 Pokemon from the types (Grass, Ice, Bug).
This will add the following inequality constraints to our QUBO:
Fire: qGrass + qIce + qBug + qSteel < 2
Water: qFire + qGround + qRock < 2
Grass: ...
...
We can include such inequality constraints of the form
q0 + q1 + q2 < 2
by adding this term to our QUBO:
(q0 + q1 + q2)*(q0 + q1 + q2 - 1)
This term will be 0 if q0 + q1 + q2 == 0 or q0 + q1 + q2 == 1, but it will add a penalty to the total QUBO energy if q0 + q1 + q2 >= 2.
For an arbitrary number of qubits, the generic form of this term is
(q0 + q1 + q2 + q3 + ...)*(q0 + q1 + q2 + q3 + ... - 1) = q0*q0 + q0*q1 + q0*q2 + q0*q3 + ...
+ q1*q0 + q1*q1 + q1*q2 + q1*q3 + ...
+ q2*q0 + q2*q1 + q2*q2 + q2*q3 + ...
+ q3*q0 + q3*q1 + q3*q2 + q3*q3 + ...
+ ...
- q0 - q1 - q2 - q3 - ...
Using again the tricks from above that q0*q0 = q0 and q0*q1 = q1*q0 etc., we find the following constraint term for "diversity"
2*q0*q1 + 2*q0*q2 + 2*q0*q3 + ...
+ 2*q1*q2 + 2*q1*q3 + ...
+ 2*q2*q3 + ...
+ ...
Final Exercise¶
Try to optimize a balanced Pokemon team with 6 Pokemon from all 18 types that also respects the diversity constraint as best as possible!
# Write your quantum computer program here: