Ein spielerischer Einstieg in Quantum Computing

bei

 / 6. March. 2020

1. Quantencomputer und Spiele – wie passt das zusammen?

Die Funktionsweise von Quantencomputern beruht auf quantenmechanischen Effekten wie Superposition und Verschränkung (engl. „Entanglement“), die wenig anschaulich sind, ja teilweise sogar unserer Anschauung und alltäglichen Erfahrung widersprechen. Aktuelle Forschungsergebnisse lassen erwarten, dass Quantencomputer – sobald sie mit genügend vielen, qualitativ hochwertigen „Qbits“ gebaut werden können – für bestimmte Fragestellungen klassischen Computern weit überlegen sein werden. Die Algorithmen für Quantencomputer beruhen allerdings auf ganz anders Prinzipien als klassische Algorithmen. Es ist eine andere Welt, in der klassisches Denken – d.h. unser Verständnis aus der klassischen Newtonschen Physik – nur sehr begrenzt weiterhilft.

Bildquelle: https://filecache.mediaroom.com/mr5mr_ibmnews/179023/500CEOForum_IBM50Qsystem%20%282%29.jpeg

Dieser Artikel gibt einen ersten Einblick in die seltsam anmutende Welt des Quantum Computing, indem Spiele (sog. „Quantum Games“) betrachtet werden, die Quanteneffekte ausnutzen und anschaulich – teilweise sogar unterhaltsam – darstellen. Eines dieser Spiele, ein Münzspiel, wird eingehend beschrieben – inkl. Regeln, (Quanten-)Theorie und einer online zugänglichen Implementierung basierend auf dem Quantum Computing Framework „Qiskit“.

 

2. Quantum Games

Bildquelle: https://www.ted.com/talks/shohini_ghose_quantum_computing_explained_in_10_minutes

Das Spektrum an Quantum Games ist groß. Es reicht von Smartphone Apps wie „Hello Quantum“ [1] über Brettspiele wie „Entanglion“ (https://entanglion.github.io) bis hin zu wissenschaftlichen Artikeln wie dem von Vassili N. Kolokoltsov [2] mit einer mathematischen Betrachtung mehrerer Quantum Games. Dieser Artikel geht u.a. auf „Meyer’s quantum penny-flip game“ ein, das auch die Basis für einen TED Vortrag von Shohini Ghose („A beginner’s guide to quantum computing“) (https://www.ted.com/talks/shohini_ghose_quantum_computing_explained_in_10_minute s) ist. Dieses „Quantum Münzspiel“ wurde erstmals im Jahr 1998 von David A. Meyer in seinem Artikel „Quantum Strategies“ [3] als „PQ Penny Flip“ betrachtet. Die Namensgebung ist angelehnt an die Charaktere Picard und Q aus der Serie „Star Trek: The Next Generation“.

3. Das Quantum Münzspiel

Die Regeln des Spiels sind einfach: Eine Münze wird verdeckt in eine Box gelegt mit der Seite „Kopf“ nach oben. Zwei Spieler – wir nennen sie Alice und Bob – sind abwechselnd am Zug und dürfen die Münze entweder unverändert lassen oder umdrehen. Es werden insgesamt drei Züge gemacht, also zwei von Alice und dazwischen einer von Bob. Die Münze wird erst am Ende wieder aufgedeckt. Zeigt sie „Kopf“, so gewinnt Alice, zeigt sie dagegen „Zahl“, so gewinnt Bob.

Das Spiel scheint zunächst wenig spannend, und man überlegt sich schnell, dass es weder für Alice noch für Bob eine Spielstrategie gibt, so dass sie mit mehr als 50% Chance gewinnen. Vereinfacht gesagt kann Alice nicht wissen, ob die Münze vor ihrem letzten Zug mit Kopf oder Zahl oben liegt. Sie kann im letzten Zug also nur raten und hat damit eine Chance von 50/50 zu gewinnen.

Interessant wird das Spiel, wenn wir Quanteneffekte einführen. Aber zunächst wollen wir das Spiel in mathematische Formeln fassen. Für die klassische Version des Spiels erscheinen die Formeln zu komplex. Die Darstellung wird aber später – bei Berücksichtigung von Quanteneffekten – sehr hilfreich sein.

Wir beschreiben den Zustand der Münze in einem zweidimensionalen Vektorraum. K steht für den Zustand Kopf, Z für Zahl. (Die notwendigen Mathematischen Grundlagen sind im folgenden Abschnitt kurz zusammengefasst.)

$$K=\left(\begin{array}{l}{1} \\ {0}\end{array}\right), \quad Z=\left(\begin{array}{l}{0} \\ {1}\end{array}\right)$$

Die Züge, d.h Umdrehen der Münze oder Liegenlassen, können nun durch Matrizen dargestellt werden. L für Liegenlassen und U für Umdrehen:

$$
L=\left(\begin{array}{ll}{1} & {0} \\ {0} & {1}\end{array}\right), \quad U=\left(\begin{array}{ll}{0} & {1} \\ {1} & {0}\end{array}\right)
$$

Das Ergebnis eines Zuges ergibt sich durch Multiplikation der entsprechenden Matrix mit dem Zustand vor dem Zug. Es gilt wie erwartet:

$$
\begin{array}{l}{L K=\left(\begin{array}{cc}{1} & {0} \\ {0} & {1}\end{array}\right)\left(\begin{array}{l}{1} \\ {0}\end{array}\right)=\left(\begin{array}{c}{1} \\ {0}\end{array}\right)=K, \quad U K=\left(\begin{array}{cc}{0} & {1} \\ {1} & {0}\end{array}\right)\left(\begin{array}{l}{1} \\ {0}\end{array}\right)=\left(\begin{array}{c}{0} \\ {1}\end{array}\right)=Z} \\ {L Z=\left(\begin{array}{cc}{1} & {0} \\ {0} & {1}\end{array}\right)\left(\begin{array}{l}{0} \\ {1}\end{array}\right)=\left(\begin{array}{c}{0} \\ {1}\end{array}\right)=Z, \quad U Z=\left(\begin{array}{cc}{0} & {1} \\ {1} & {0}\end{array}\right)\left(\begin{array}{l}{0} \\ {1}\end{array}\right)=\left(\begin{array}{c}{1} \\ {0}\end{array}\right)=K}\end{array}
$$

D.h. U („Umdrehen“) ändert den Zustand, L („Liegenlassen“) dagegen nicht.

Spielverlauf für die Zugfolge U(mdrehen) U(mdrehen) L(iegenlassen) Bildquelle: J. Lahmann

Ein konkreter Spielverlauf kann nun folgendermaßen aussehen: Die Münze liegt zunächst mit Kopf oben. Alice dreht sie um, Bob ebenfalls, im letzten Zug lässt Alice die Münze liegen. Wegen der Reihenfolge der Matrix-Multiplikationen (von rechts nach links) kann dies geschrieben werden als

$$
L U U K=L U Z=L K=K
$$

D.h. auch die Formeln zeigen, dass die Münze nach dem dritten Zug mit Kopf oben liegt und Alice gewinnt.

Neue Möglichkeiten ergeben sich, wenn wir vom klassischen Ziel zu einem Quantum Game übergehen und Alice erlauben, auch Quantenzustände der Münze zu erzeugen. Wir werden später versuchen, diese neuen Zustände (es handelt sich um eine Superposition der Zustände Kopf und Zahl) zu veranschaulichen. Wir führen sie aber zunächst mit Hilfe mathematischer Formeln ein, bzw. einer weiteren Matrix H, die einen neuen Zug – einen Quanten-Zug – ermöglicht.

Wir definieren die Matrix H als

$$
H=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}{1} & {1} \\ {1} & {-1}\end{array}\right)
$$

Wenn Alice den neuen Zug „H“ in ihrem ersten Zug anwendet (die Münze liegt davor mit Kopf oben), so ist die Münze danach in folgendem Zustand:

$$
H K=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}{1} & {1} \\ {1} & {-1}\end{array}\right)\left(\begin{array}{l}{1} \\ {0}\end{array}\right)=\frac{1}{\sqrt{2}}\left(\begin{array}{l}{1} \\ {1}\end{array}\right)
$$

Dieser Zustand ist eine Linearkombination der Zustände Kopf und Zahl, mit der Gewichtung von jeweils 1/√2 :

$$
H K=\frac{1}{\sqrt{2}}\left(\begin{array}{l}{1} \\ {1}\end{array}\right)=\frac{1}{\sqrt{2}}\left(\left(\begin{array}{l}{1} \\ {0}\end{array}\right)+\left(\begin{array}{l}{0} \\ {1}\end{array}\right)\right)=\frac{1}{\sqrt{2}}(K+Z)
$$

Diesen Zustand können wir uns nicht anschaulich vorstellen; in der Quantenmechanik ist dies jedoch ein eindeutig definierter Zustand – eine Superposition von Kopf und Zahl. Viele populärwissenschaftliche Artikel versuchen dies zu veranschaulichen, indem sie davon sprechen, die Münze sei „gleichzeitig im Zustand K als auch im Zustand Z“.

Für Anwendung von H auf den Zustand Z (Zahl) ergibt sich analog:

$$
H Z=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}{1} & {1} \\ {1} & {-1}\end{array}\right)\left(\begin{array}{l}{0} \\ {1}\end{array}\right)=\frac{1}{\sqrt{2}}\left(\begin{array}{c}{1} \\ {-1}\end{array}\right)=\frac{1}{\sqrt{2}}(K-Z)
$$

Nach etwas Überlegung bemerkt Alice, dass ihr der neue Zug einen großen Vorteil verschafft. Wenn sie ihn zweimal verwendet gewinnt sie das Spiel immer, egal ob Bob in seinem Zug zwischendrin die Münze umdreht oder liegenlässt! Denn es gilt:

$$
\begin{aligned} H L H K=H L\left(\frac{1}{\sqrt{2}}(K+Z)\right)=& \frac{1}{\sqrt{2}} H(L(K+Z))=\frac{1}{\sqrt{2}} H(L K+L Z) \\=& \frac{1}{\sqrt{2}} H(K+Z)=\frac{1}{\sqrt{2}}(H K+H Z) \\=& \frac{1}{\sqrt{2}}\left(\frac{1}{\sqrt{2}}(K+Z)+\frac{1}{\sqrt{2}}(K-Z)\right) \\ &=\frac{1}{2}((K+Z)+(K-Z))=K \end{aligned}
$$

Und ebenso (da Z+K = K+Z):

$$
\begin{aligned} H U H K=H U &\left(\frac{1}{\sqrt{2}}(K+Z)\right)=\frac{1}{\sqrt{2}} H(U(K+Z))=\frac{1}{\sqrt{2}} H(U K+U Z) \\=& \frac{1}{\sqrt{2}} H(Z+K)=\frac{1}{\sqrt{2}} H(K+Z)=\cdots=K \end{aligned}
$$

Alice hat in dem Spiel einen enormen Vorteil erzielen können, da sie Superposition genutzt hat, also den Zustand \(\frac{1}{\sqrt{2}}\left(\begin{array}{l}{1} \\ {1}\end{array}\right)=\frac{1}{\sqrt{2}}(K+Z)\), sowie einen weiteren Effekt der
Quantenmechanik, die Interferenz, bei der sich Zustände „aufheben“ können. In der letzten Zeile der Rechnung zur ersten Zugfolge heben sich nämlich die Zustände 𝑍 und −𝑍 auf:

$$
\frac{1}{2}((K+Z)+(K-Z))=\frac{1}{2}(K+Z+K-Z)=\frac{1}{2}(K+K+Z-Z)=K
$$

 

4. Exkurs: Mathematische Grundlagen

Die hier gewählte mathematische Darstellung des Münzspiels benötigt lediglich elementare Lineare Algebra. Als Erinnerung die grundlegende Vorgehensweise der Matrix-VektorMultiplikation für reelle oder komplexe Zahlen a, b, c, d, x, y:

$$
\left(\begin{array}{ll}{a} & {b} \\ {c} & {d}\end{array}\right)\left(\begin{array}{l}{x} \\ {y}\end{array}\right)=\left(\begin{array}{l}{a x+b y} \\ {c x+d y}\end{array}\right)
$$

Dies wird oftmals in folgender Form dargestellt, bekannt als „Falksches Schema“:

$$
\left(\begin{array}{ll}{a} & {b} \\ {c} & {d}\end{array}\right)\left(\begin{array}{l}{\left(\begin{array}{l}{x} \\ {y}\end{array}\right)} \\ {c \quad d}\end{array}\right)\left(\begin{array}{l}{a x+b y} \\ {c x+d y}\end{array}\right)
$$

Und analog für die Multiplikation von Matrizen:

$$
\left(\begin{array}{ll}{a} & {b} \\ {c} & {d}\end{array}\right)\left(\begin{array}{ll}{x} & {u} \\ {y} & {v}\end{array}\right)=\left(\begin{array}{ll}{a x+b y} & {a u+b v} \\ {c x+d y} & {c u+d v}\end{array}\right)
$$

 

5. Versuch einer anschaulichen Deutung

Die Quantenmechanik verschließt sich an vielen Stellen einer anschaulichen Deutung. Wir wollen dennoch eine anschauliche Darstellung des Münzspiels versuchen, die jedoch zwangsläufig Lücken hat. Die Münze liege zunächst flach vor uns – natürlich verdeckt und mit Kopf nach oben. Das normale Umdrehen wird durch eine Drehung um 180° um die Achse, die von uns wegzeigt, realisiert. Der „Quantenzug“ von Alice ist dann eine Drehung um 90° um die „Querachse“ der Münze, die dann sozusagen „auf der Kante steht“. Egal ob Bob die Münze in seinem Zug liegenlässt oder dreht (um die Achse, die von vorne durch die Münze hindurch zeigt), die Münze bleibt auf der Kante. Der letzte Zug von Alice legt die Münze von der Kante wieder flach hin – und zwar mit Kopf nach oben. Hier versagt die Anschauung leider etwas, denn der Zug H ist selbstinvers und kippt die Münze bei der zweiten Anwendung nicht um weitere 90° nach vorne, sondern wieder um 90° nach hinten. Es gilt 𝐻𝐻=𝐿.

Veranschaulichung des Spielverlaufs für die Zugfolge „H L H“ Bildquelle: J.Lahmann
Veranschaulichung des Spielverlaufs für die Zugfolge „H U H“ Bildquelle: J.Lahmann

 

6. Das Quantum Münzspiel als Online-Spiel

Nach den sicher sehr interessanten, aber doch eher theoretischen Betrachtungen des Quantum Münzspiels wollen wir eine Möglichkeit vorstellen, dieses Spiel online zu spielen. Auch dabei steht das Kennenlernen verschiedener Aspekte des Quantum Computing im Vordergrund. Das Münzspiel ist nunmal kein MMOG (Massive Multiplayer Online Game).

Eine Implementierung des Quantum Münzspiels ist verfügbar auf [4] . Es wurde vom Autor auf Basis des IBM Quantum Computing Frameworks „Qiskit“ implementiert [5]. Qiskit basiert auf Python und Jupyter Notebooks und ermöglicht neben der Nutzung von Quantencomputer Simulatoren auch die (kostenfreie) Nutzung von realen Quantencomputern über die Cloud. Die Bezeichnungen im QiskitCoinGame unterscheiden sich etwas von denen in diesem Artikel und sind eher an die im Quantum Computing üblichen Begriffe angelehnt. Neben Qiskit wird mybinder verwendet [6], ein ebenfalls kostenfreier online Service, in dem Jupyter Notebooks ausgeführt werden können, sowie RISE, eine Erweiterung von Jupyter Notebooks um Slideshow/Screenshow Funktionen. Alle Elemente und deren Bedienung werden auf [4] erklärt. Der Start dauert bis zu einer Minute, danach ist die Umgebung recht agil und lädt dazu ein, selber Änderungen am Python Code vorzunehmen und so erste Erfahrungen mit einem eigenen Quanten-Programm zu machen. Für weitere Schritte ist die Literatur am Ende dieses Artikels sehr zu empfehlen.

Quanten-Algorithmus in Qiskit für den Spielverlauf „U U L“ Bildquelle: screenshot http://ibm.biz/QiskitCoinGame
Ergebnis für den Spielverlauf „U U L“ Bildquelle: screenshot http://ibm.biz/QiskitCoinGame
Quanten-Algorithmus in Qiskit für den Spielverlauf „H U H“ Bildquelle: screenshot http://ibm.biz/QiskitCoinGame
Ergebnis für den Spielverlauf „H U H“ Bildquelle: screenshot http://ibm.biz/QiskitCoinGame

7. Die Brücke zur Quantenmechanik

Die Darstellung in diesem Artikel ist bewusst einfach gewählt. Um „echte“ Quantenalgorithmen zu verstehen oder sogar selber erstellen zu können, ist eine ausführlichere Beschäftigung mit den Grundlagen der Quantenmechanik und der „Quantum Information Science“ erforderlich.

An dieser Stelle wollen wir nur einen kurzen Einblick zu Zuständen von Quantensystemen und deren Messung geben. Wir betrachten nur Quantensysteme, die aus einem einzelnen Qubit bestehen und aus nicht mehreren (wir hatten im Münzspiel ja auch nur eine einzelne Münze).

Wir haben bereits einige mögliche Zustände kennengelernt, nämlich Kopf, Zahl und einen Superpositionszustand:

$$
K=\left(\begin{array}{l}{1} \\ {0}\end{array}\right), \quad Z=\left(\begin{array}{l}{0} \\ {1}\end{array}\right), \quad \frac{1}{\sqrt{2}}\left(\begin{array}{l}{1} \\ {1}\end{array}\right)
$$

Ein allgemeiner Quantenzustand 𝜓 hat die Form \(\psi=\left(\begin{array}{l}{\alpha} \\ {\beta}\end{array}\right)\) oder gleichbedeutend  \(\psi=\alpha K+\beta Z\) mit komplexen Zahlen \alpha, \beta , die folgende Bedingung erfüllen (eine Art Normierung auf die „Länge eins“):

$$
|\alpha|^{2}+|\beta|^{2}=1
$$

Die Quantenmechanik besagt, dass es nicht möglich ist, den Zustand eines solchen Quantensystems 𝜓 exakt zu bestimmen, d.h. die exakten Werte von 𝛼 und 𝛽 zu messen. Bei einer Messung des Zustands von 𝜓 kann als Ergebnis immer nur der Zustand 𝐾oder 𝑍 festgestellt werden. Der Ausgang der Messung erscheint dabei zunächst zufällig.

Präpariert man das Qubit jedoch mehrfach in denselben Zustand 𝜓 und führt dann jeweils eine Messung des Zustands durch, so ergibt sich ein Zusammenhang zwischen der Häufigkeit der Ergebnisse 𝐾 und 𝑍 mit den Koeffizienten 𝛼 und 𝛽. Es gilt: die Häufigkeit des Ergebnisses 𝐾 ist gleich \(|\alpha|^{2}\), und die Häufigkeit des Ergebnisses 𝑍 ist gleich \(|\beta|^{2} \cdot \alpha\) und 𝛽 sind verallgemeinerte Wahrscheinlichkeiten, sogenannte „Wahrscheinlichkeitsamplituden“ (man beachte: 𝛼 und 𝛽 sind komplexe Zahlen).

Der Zustand 𝜓 ist also wohldefiniert und beinhaltet selber keine Unsicherheit oder Wahrscheinlichkeit. Erst im Rahmen der Messung treten verschiedene Ergebnisse mit gewissen Wahrscheinlichkeiten auf.

Als Beispiel sei \(\psi=\alpha K+\beta Z\) mit \(\alpha=\beta=1 / \sqrt{2}\)  , also \(\psi=\frac{1}{\sqrt{2}} K+\frac{1}{\sqrt{2}} Z\), und damit der bereits zuvor betrachtete Superpositionszustand von K und Z. Die Wahrscheinlichkeit, bei einer Messung den Zustand K festzustellen, ist nun \(|\alpha|^{2}=1 / 2=50 \%\) , und analog für den Zustand Z ebenfalls 50%.

Eine Superposition muss jedoch nicht gleiche Wahrscheinlichkeitsamplituden für 𝛼 und 𝛽 besitzen, sondern es ist z.B. auch folgender Zustand möglich (und unendlich viele weitere): \(\psi=\alpha K+\beta Z \text { mit } \alpha=1 / 2 \text { und } \beta=\sqrt{3} / 2, \text { also } \psi=\frac{1}{2} K+\frac{\sqrt{3}}{2} Z\) . Die Wahrscheinlichkeit, bei einer Messung den Zustand K festzustellen, ist nun (|\alpha|^{2}=1 / 4=25 \%\), und für den Zustand \(Z:|\beta|^{2}=3 / 4=75 \%\).

Eine ausführlichere Darstellung der Grundlagen der Quantenmechanik, des Quanten Computing und auch eine Darstellung des bekannten Quanten-Algorithmen von Grover mitsamt seiner Implementierung findet sich in dem Buch von Andrew Thomas „Hidden In Plain Sight 10: How To Program A Quantum Computer“.

8. Ist das Spiel fair?

Zum Abschluss wollen wir diskutieren, ob das Spiel fair ist – und falls nicht, wie dies zu deuten ist. Da Alice andere Züge verwenden darf als Bob, ist das Spiel nicht fair. Man kann dies jedoch auch anders betrachten: und zwar nicht als Spiel, sondern als Algorithmen. Bob wendet einen klassischen Algorithmus an; Alice jedoch einen Quantenalgorithmus unter Verwendung von Superposition und Interferenz. Wie wir gesehen haben, ist der Algorithmus von Alice mächtiger als der von Bob. Das bestätigt uns in der Erwartung, dass Quantenalgorithmen Aufgaben lösen können, die mit klassischen Algorithmen und klassischen Computern unerreichbar sind. Es sind bereits etliche Quantenalgorithmen bekannt, die Superposition, Interferenz und Verschränkung geschickt ausnutzen. Man geht jedoch davon aus, dass es hier noch viel zu erforschen und zu entdecken gibt. Es lohnt sich daher, sich mit den Grundlagen und dem Potential des Quantencomputing zu beschäftigen!

Jan-Rainer Lahmann. Studium der Technomathematik an der TU Clausthal, Promotion am KIT Karlsruhe über Angewandte Mathematik und Strömungsmechanik. Seit 1999 bei IBM in der technischen Vertriebsunterstützung (Hardware, Analytics/BigData, Cloud). Mitglied der IBM Academy of Technology und Qiskit Contributor.

Thomas Haag. Studium der Informatik an der Fachhochschule Frankfurt am Main. Seit 2002 bei der deutschen Lufthansa, verantwortlich für Datamanagement, BI und Analytics in der LH Group.

Quellen und Referenzen:

[1] https://helloquantum.mybluemix.net/

[2] https://arxiv.org/abs/1909.04466v1

[3] https://arxiv.org/abs/quant-ph/9804010v1

[4] http://ibm.biz/QiskitCoinGame

[5] https://qiskit.org/ 

[6] https://mybinder.org/

[7] https://www.ted.com/talks/shohini_ghose_quantum_computing_explained_in_10_ minutes

[8] Andrew Thomas, Hidden In Plain Sight 10: How To Program A Quantum Computer, ASIN: B07GPRBYVC

[9] https://github.com/Qiskit/qiskit-communitytutorials/tree/master/games

[10] https://github.com/Qiskit/qiskit-iqx-tutorials

[11] https://www.ibm.com/quantum-computing/

[12] Anton Zeilinger, Einsteins Spuk: Teleportation und weitere Mysterien der Quantenphysik, ISBN-13: 978-3442154357

[13]  J. von Neumann, „Zur Theorie der Gesellschaftsspiele“, Math. Ann. 100 (1928) 295- 320.