Das schachmathematische Damenproblem zeigt Überlegenheit des Quantencomputers

Schachbrett Modell Quantencomputer(c) Universität Innsbruck

Schachbrett (c) Universität Innsbruck

By Hildegard Suntinger

Theoretische Physiker von der Universität Innsbruck demonstrierten die Überlegenheit von Quantencomputern gegenüber klassischen Supercomputern bei der Lösung von Optimierungsaufgaben. Das Experiment, das sie entwarfen, basiert auf der schachmathematischen Aufgabe des Damenproblems.

Das Damenproblem ist eine schachmathematische Aufgabe, die erstmals 1848 in der Berliner Schachzeitung gestellt wurde. Dabei sollen acht Damen so aufgestellt werden, dass keine zwei Damen einander schlagen können – es gelten die in den Schachregeln definierten Zugmöglichkeiten. Allerdings wird angenommen, dass jede Dame durch jede andere angegriffen werden könne, das heißt, die Farbe wird ignoriert. Die Aufgabe besteht darin, die Zahl der möglichen Lösungen herauszufinden. Das Schachbrett hat acht mal acht Felder und die korrekte Zahl beträgt zweiundneunzig. Die richtige Lösung wurde erstmals 1850 in der Leipziger Illustrirte Zeitung veröffentlicht, aber erst 1874 vom englischen Mathematiker James Whitbread Lee Glaisher bewiesen.

Die schachmathematische Aufgabe

Vergrößert man das Schachbrett, so erhöht sich die Zahl der Möglichkeiten enorm: bei fünfundzwanzig mal fünfundzwanzig Feldern sind es schon über zwei Billiarden. Die mathematische Berechnung dieser Zahl benötigte insgesamt dreiundfünfzig Jahre an Zentraler Verarbeitungs Einheits (ZVE)-Zeit. Wenn einige Damen bereits auf dem Feld stehen und bestimmte Diagonalen nicht besetzt werden dürfen, wird die Aufgabe noch anspruchsvoller. Eine Variante, die unlängst mit einundzwanzig Damen versucht wurde. Wie sich zeigte, war eine Lösung durch mathematische Algorithmen in angemessener Zeit nicht mehr möglich.

Quanten-Schachbrett

Wolfgang Lechner vom Institut für Theoretische Physik an der Universität Innsbruck und dem Institut für Quantenoptik und Quanteninformation der Österreichischen Akademie der Wissenschaften stieß durch Zufall auf das Damenproblem und erkannte darin eine mathematische Aufgabe, die sich eignet, die Vorteile der Quantenphysik zu zeigen. Er entwarf mit einem Team am Institut für Theoretische Physik an der Universität Innsbruck ein Experiment, das zeigte, dass diese Aufgabe für einen Quantencomputer ungleich leichter sein könnte.

Mit Helmut Ritsch und den Doktoranden Valentin Torggler und Philipp Aumann entwickelte Lechner ein Quanten-Schachbrett, auf dem das Damenproblem mit Hilfe der Quantenphysik gelöst werden könnte.

„Als Schachbrett kann ein optisches Gitter aus Laserstrahlen genutzt werden, in das einzelne Atome geladen werden. Über die Einstellung der Wechselwirkung zwischen den Teilchen, können wir aus den Atomen Schachdamen machen, die sich nach den Schachregeln verhalten, sich also in allen Bewegungsrichtungen des Spiels aus dem Weg gehen.“ Helmut Ritsch

Quanteneigenschaften nutzen

Die sich abstoßenden Damen werden mit Laser erzeugt, die in den Bewegungsrichtungen eingestrahlt werden. Ein optischer Resonator verstärkt diese Wirkung noch deutlich und ist über weit größere Distanzen wirksam. Gebildet wird dieser von je einem Spiegel ober- und unterhalb des optischen Gitters.

Laut Ritsch könnte man dieses Spiel auch mit Billardkugeln spielen, die sich gegenseitig abstoßen. Aufgrund der vielen Möglichkeiten würde das Experiment allerdings sehr lang dauern. Deshalb sei es entscheidend, die Atome stark abzukühlen, um deren Quanteneigenschaften nutzen zu können. Die abgekühlten Atome funktionieren wie Wellen und können viele Möglichkeiten gleichzeitig austesten. Es zeigt sich sehr rasch, ob es eine den Schachregeln entsprechende Lösung für die gegebene Aufgabe gibt. Die Lösung kann aus dem von den Atomen abgestrahlten Licht abgelesen werden.

Ein alternatives Verfahren wäre jenes der Atommikroskopie. Wie Ritsch anmerkt, seien damit bereits ähnliche Aufbauten erfolgreich demonstriert worden.

Überlegene Quantencomputer

Bisweilen kann das Experiment nur auf klassischen Computern simuliert werden. Aber die Simulationen lassen annehmen, dass die Quanteneigenschaften der Teilchen sehr viel rascher zu einem Ergebnis führen würden, als jeder mathematische Algorithmus auf einem klassischen Computer.

„Damit ließe sich die Überlegenheit von Quantencomputern für die Berechnung von bestimmten Optimierungsproblemen mit diesem Experiment erstmals eindeutig nachweisen. Die Kontrolle weniger Dutzend Atome gehört heute im Labor schon zum Standard, weshalb die Umsetzung dieser Idee vielleicht schon bald Realität werden könnte“, resümiert Wolfgang Lechner.

Ermöglicht wurde das Experiment durch die finanzielle Unterstützung des Österreichischen Wissenschaftsfonds FWF, der Hauser-Raspe-Stiftung und der Europäischen Union.

Das Paper zum Experiment erschien im Fachmagazin Quantum. Den Link finden Sie hier:

Aumann, P./Lechner, W./Ritsch, H./Torggler, V. (2019): A Quantum N-Queens Solver. In: Quantum 3, 149.