Quantenfußball: Wie Qubits die Euro 2020 vorhersagen können
Wie Millionen Menschen rund um den Globus haben auch wir von Classiq in den letzten Wochen viele Spiele der UEFA-Fußball-Europameisterschaft verfolgt. Das hat uns zum Nachdenken gebracht: Wie können wir unsere Leidenschaft für Fußball mit unserer Leidenschaft für Quantencomputing verbinden?
Also legten wir unsere Turnierklammern für eine Weile beiseite und griffen zu unseren Quantenbremsen, um zu erforschen, wie man einen Quantenschaltkreis erstellen kann, der das Ergebnis vorhersagt.
Erste Überlegungen
Wir möchten einen Quantenschaltkreis bauen, der die Ergebnisse des gesamten Turniers mit einer einzigen Messung vorhersagt. Das Messergebnis muss ein gültiges Turnierresultat sein - zum Beispiel kann in der K.O.-Phase nur eine Mannschaft ein beliebiges Spiel gewinnen, und daher muss der Messraum Ergebnisse mit zwei Gewinnern oder ohne Gewinner ausschließen. Wir möchten außerdem, dass der Kreislauf parametrisch ist, damit wir die Wahrscheinlichkeiten für den Sieg jeder Mannschaft in einem Spiel gegen jede andere Mannschaft definieren können.
Es gibt mehrere Möglichkeiten, eine solche Quantenschaltung zu bauen. Eine Möglichkeit besteht darin, einfach eine Münzwurfschaltung mit einem Qubit und einem Rx-Gatter zu konstruieren und dann das Ergebnis für jedes Spiel unabhängig zu messen - aber das ist wirklich nicht besonders interessant, und unser Ziel ist es, nur eine einzige Messung zu verwenden. Eine andere Möglichkeit ist die Verwendung von Zustandsvorbereitungsalgorithmen, die effizient eine vorbestimmte Wahrscheinlichkeitsverteilung aufbauen, aber dann müssten wir mit einer klassischen Berechnung der Wahrscheinlichkeit jedes möglichen Ergebnisses beginnen. Auch dies ist für uns weniger interessant.
Stattdessen demonstrieren wir hier zwei Ansätze, die Quantenlogik verwenden, um den Schaltkreis von Grund auf aufzubauen. Für den Aufbau und die Visualisierung der Schaltkreise werden wir Qiskit verwenden - das IBM-Paket für Quantenberechnungen.
Grundlegende Annahmen
Bei der Entwicklung der Schaltungen sind wir von einer wichtigen Annahme ausgegangen: Die Gewinnwahrscheinlichkeit für jedes Spiel zwischen zwei bestimmten Mannschaften ist vorgegeben und bekannt. Im wirklichen Leben könnte dies eine fragwürdige Annahme sein - Spieler verletzen sich oder sitzen wegen gelber Karten aus, Mannschaften haben eine Eigendynamik usw., aber lassen Sie uns für den Moment annehmen, dass diese Wahrscheinlichkeiten im Voraus bekannt sind. Eine einfache Möglichkeit, diese Wahrscheinlichkeiten in einem Quantenzustand zu kodieren, besteht darin, ein einzelnes Qubit zu verwenden, um ein einzelnes Spiel zwischen zwei Mannschaften zu beschreiben. Es gäbe eine Wahrscheinlichkeit p für den Sieg der ersten Mannschaft und somit die Wahrscheinlichkeit 1-p für den Sieg der zweiten Mannschaft. Natürlich ist 0 ≤ p ≤ 1.
Wir bezeichnen den Basiszustand |0> als den Sieg der ersten Mannschaft und |1> als den Sieg der zweiten Mannschaft. Ein einzelnes Rotationstor in der Y-Achse (Ry-Tor) wird auf das Qubit mit dem Winkel θ angewendet. Der Quantenzustand ist nun |psi> = cos(θ/2)*|0> +sin(θ/2)*|1>. Wenn wir θ = 2*arccos(√p) wählen, kann der Quantenzustand geschrieben werden als |psi> = √p*|0> + √(1-p)*|1>. Somit ist die Wahrscheinlichkeit, das Qubit im Zustand |0> zu messen, gleich p, was dem entspricht, was wir wollten.
In diesem Beitrag zeigen wir die explizite Konstruktion für ein Turnier, das mit dem aktuellen Stand des Viertelfinales in der K.O.-Phase beginnt. Sie kann jedoch leicht für größere Turniere skaliert und auf physikalischen Computern modelliert werden, wenn die Anzahl der Qubits und ihre Kohärenzzeit ausreichend groß ist.
Rundenbasierter Ansatz
Bei unserem ersten Ansatz beschreibt jedes Qubit das Ergebnis eines einzigen Spiels. Der Zustand der Qubits, die die ersten Spiele beschreiben, wird in die entsprechende wahrscheinlichkeitsgewichtete Überlagerung gedreht. Die Ergebnisse nachfolgender Spiele hängen von den Identitäten der Gewinner der vorangegangenen Spiele ab, wobei kontrollierte Rotationsgatter verwendet werden. Der resultierende Quantenschaltkreis sieht wie folgt aus:
Die Qubits, die das Viertelfinale darstellen (Qubits 1, 2, 4 und 5), werden von einem einfachen Ry-Gatter begleitet, das jeweils die bekannten Wahrscheinlichkeiten für die Viertelfinalphase kodiert. Jedes Halbfinale wird ebenfalls durch ein einzelnes Gubit (Qubits 3 und 6) und vier aufeinanderfolgende kontrollierte Ry-Gatter mit zwei Kontroll-Qubits kodiert. Diese Gatter unterscheiden sich dadurch, dass jedes kontrollierte Gatter ein mögliches Match zwischen den Gewinnern der Viertelfinale darstellt. Das Endspiel schließlich wird mit einem einzigen Qubit (Qubit 7) und 16 aufeinanderfolgenden kontrollierten Gattern mit vier Kontrollqubits kodiert.
Wie würde diese Schaltung aussehen, wenn wir mehr Teams und mehr Runden hätten? Wenn wir mit dem Achtelfinale beginnen würden, bräuchten wir 15 Qubits (eines für jedes Spiel) und das Endspiel hätte 64 Ry-Gatter (für jede mögliche Kombination des Endspiels), die jeweils von 6 Qubits der entsprechenden vorherigen Spiele gesteuert werden. Für N Mannschaften würden wir N-1 Qubits benötigen. Das Qubit, das das Endspiel repräsentiert, wäre das Ziel von O(N²) mehrfach kontrollierten Ry-Gattern, jedes kontrolliert von O(log₂N) Qubits.
Matchup-basierter Ansatz
Wir bei Classiq wissen, wie wichtig es ist, den Quantenalgorithmus an die physikalische Implementierung des Quantencomputers anzupassen. Derselbe Quantenalgorithmus kann in vielen verschiedenen Schaltkreisen mit unterschiedlichen Eigenschaften implementiert werden. Daher konzentrieren wir uns auf die Bereitstellung von Spitzentechnologie, um alternative Implementierungen zu bauen, die unseren Kunden helfen, ihre Bedürfnisse und verfügbaren Ressourcen zu erfüllen. Ein möglicher alternativer Ansatz wäre in diesem Fall einer, der zu einem breiteren, aber flacheren Schaltkreis führt - d. h. mehr Qubits, weniger Gatter. Je nach den verfügbaren Ressourcen kann ein Wechsel zwischen diesen Alternativen dazu führen, dass die gleichen Berechnungen auf verschiedenen Quantencomputern mit unterschiedlichen Ressourcen durchgeführt werden.
Beim matchup-basierten Ansatz ordnen wir jedem möglichen Match zwei Qubits zu - ein Qubit kodiert wie bisher das Ergebnis des Matches (|0> : das erste Team hat gewonnen, |1> : das zweite Team hat gewonnen), und ein zweites Qubit kodiert, ob dieses Match stattgefunden hat - wie durch die Ergebnisse früherer Spiele bestimmt. Wenn eine Mannschaft ein Spiel in einer früheren Runde verloren hat, wird sie in diesem Turnier nicht mehr antreten.
Betrachten wir ein Beispiel mit nur vier Mannschaften - Schweiz, Spanien, Belgien und Italien. Die Halbfinalspiele in diesem Beispiel sind Schweiz-Spanien und Belgien-Italien. So sieht diese Runde aus:
Die Wahrscheinlichkeit, dass jede Mannschaft jedes Spiel gewinnt, kann durch die Ry-Gates angepasst werden, ist aber nur dann sinnvoll, wenn sich das zweite Qubit des Spiels im Zustand |1> befindet - was bedeutet, dass das Spiel tatsächlich stattgefunden hat. Da das Halbfinale stattgefunden haben muss, wird das zweite Qubit für Schweiz-Spanien (Qubit 2) und Belgien-Italien (Qubit 4) umgedreht. Die nächste Runde der Spiele (die vier möglichen Finalspiele) hängen von den Ergebnissen der vorherigen Runde ab und davon, ob sie überhaupt stattgefunden haben - daher die mehrfach gesteuerten NOT-Gatter. Wenn die Schaltung schließlich vermessen wird, müssen wir nur noch die Ergebnisse der Spiele mit einem zweiten Qubit im Zustand |1> überprüfen.
Schauen wir uns eine Beispielmessung an: |110100001111> (das oberste Qubit im Diagramm ist das ganz rechte in der Messung). Das erste und das dritte Qubit sind im Zustand |1>, also haben in diesem Beispiel Spanien und Italien das Halbfinale gewonnen. Wir können sehen, dass das letzte Qubit - das ein Spiel zwischen Spanien und Italien anzeigt - tatsächlich im Zustand |1> ist, während die Qubits 6, 8 und 10 wie erwartet |0> sind. Da in diesem Szenario das 11. Qubit als |1> gemessen wird, hat Italien gewonnen!
Wie ist diese Schaltung im Vergleich zur ersten Option? Wenn wir ein K.O.-Turnier mit N Mannschaften konstruieren, benötigen wir N-(N-1) Qubits - die doppelte Anzahl möglicher Spiele. Wir bräuchten auch die gleiche Anzahl von Ry- und mehrfach gesteuerten X-Gattern - eines für jedes mögliche Match. Die Anzahl der Kontroll-Qubits für jedes mehrfach kontrollierte X-Gatter bleibt jedoch konstant - 4 Kontroll-Qubits, da jede Übereinstimmung nur von zwei vorherigen Übereinstimmungen abhängt. Wenn N groß ist, skaliert zwar die Anzahl der Qubits mit O(N²), aber die Komplexität der Gatter bleibt konstant. Dies kann im Vergleich zur ersten Schaltung sehr viel gattereffizienter sein, wenn N groß ist.
Ergebnisse
Können wir diese Schaltkreise auf einem physikalischen Quantencomputer betreiben? Leider nicht mit den heutigen Geräten. Die auf Runden basierende Schaltung benötigt nur sieben Qubits, aber wenn sie kompiliert wird, um die nativen Gatter der verfügbaren Quantencomputer zu verwenden, steigt die Schaltungstiefe auf etwa 1000! Das ist viel mehr, als derzeit möglich ist, bevor das Rauschen die Oberhand gewinnt. Die matchup-basierte Schaltung würde 52 Qubits und die gleiche Anzahl von mehrfach gesteuerten X-Gattern benötigen, was heute ebenfalls nicht machbar ist.
Aber hier bei Classiq lassen wir uns nicht von physikalischen Beschränkungen davon abhalten, nach der Wahrheit zu suchen. Wir können den rundenbasierten Kreislauf mit geräuschlosen Simulatoren laufen lassen, um den Sieger zu ermitteln. Indem wir die Gewinnwahrscheinlichkeit jedes Spiels anhand der Wettquoten (zum Zeitpunkt der Berechnung) geschätzt haben, haben wir die Quantenvorhersage für die Ergebnisse simuliert.
Classiq ist stolz darauf, die weltweit erste Quantenvorhersage für das Siegerteam der EURO 2020 zu präsentieren: