|
Innsrbuck (lk) - Physiker der Universität Innsbruck schlagen ein neues Modell vor, mit dem die Überlegenheit
von Quantencomputern gegenüber klassischen Supercomputern bei der Lösung von Optimierungsaufgaben gezeigt
werden könnte. Sie demonstrieren in einer aktuellen Arbeit, dass schon wenige Quantenteilchen genügen
würden, um das mathematisch schwierige Damenproblem im Schach auch für größere Schachbretter
zu lösen.
Das Damenproblem ist eine schachmathematische Aufgabe, die schon den großen Mathematiker Carl Friedrich Gauß
beschäftigt hat, für die er aber erstaunlicher Weise nicht die richtige Lösung fand. Es geht dabei
um die Frage, wie acht Damen so auf einem klassischen Schachbrett mit 8 x 8 Feldern angeordnet werden können,
dass sich keine davon gegenseitig schlagen können. Mathematisch kann noch relativ einfach ermittelt werden,
dass es 92 verschiedene Möglichkeiten gibt, die Damen aufzustellen. Auf einem Schachbrett mit 25 x 25 Feldern
sind es schon über 2 Billiarden Möglichkeiten. Allein die Berechnung dieser Zahl verschlang insgesamt
53 Jahre an CPU-Zeit.
Noch schwieriger wird die Aufgabe, wenn einige Damen bereits auf dem Feld stehen und bestimmte Diagonalen nicht
besetzt werden dürfen. Vor kurzem wurde gezeigt, dass mit diesen zusätzlichen Einschränkungen das
Problem mit 21 Damen durch klassische mathematische Algorithmen nicht mehr in angemessener Zeit gelöst werden
kann. „Ich bin zufällig auf dieses Thema gestoßen und dachte mir, hier könnte die Quantenphysik
ihre Vorteile ausspielen“, erzählt Wolfgang Lechner vom Institut für Theoretische Physik der Universität
Innsbruck und dem Institut für Quantenoptik und Quanteninformation der Österreichischen Akademie der
Wissenschaften. Gemeinsam mit Helmut Ritsch und den Doktoranten Valentin Torggler und Philipp Aumann entwickelte
Lechner ein Quanten-Schachbrett, auf dem das Damenproblem mit Hilfe der Quantenphysik experimentell gelöst
werden könnte.
Aus Atomen werden Schachdamen
„Als Schachbrett kann ein optisches Gitter aus Laserstrahlen genutzt werden, in das einzelne Atome geladen
werden“, erklärt Helmut Ritsch, der ebenfalls am Innsbrucker Institut für Theoretische Physik forscht.
„Ü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.“ Diese Abstoßung der Teilchen wird mit Hilfe von Lasern erzeugt, die in den Bewegungsrichtungen eingestrahlt
werden. Über einen optischen Resonator - zwei Spiegel oberhalb und unterhalb des optischen Gitters - wird
diese Wechselwirkung noch einmal deutlich verstärkt und ist damit über deutlich größere Distanzen
wirksam.
„Man könnte dieses Spiel auch mit sich entsprechend abstoßenden Billardkugeln spielen“, sagt Ritsch.
„Weil es aber so viele Möglichkeiten gibt, würde das sehr, sehr lange dauern. Es ist deshalb entscheidend,
dass die Atome sehr stark abgekühlt werden und deren Quanteneigenschaften zum Tragen kommen. Weil sie dann
wie Wellen funktionieren, können die Teilchen viele Möglichkeiten gleichzeitig austesten und es zeigt
sich sehr rasch, ob es eine nach Schachregeln gültige Lösung für die vorgegebenen Bedingungen gibt.
Quantenüberlegenheit nachweisen
Die Antwort auf die Frage, ob es unter den jeweils vorgegebenen Einschränkungen eine Lösung gibt,
kann aus dem von den Atomen abgestrahlten Licht sehr leicht abgelesen werden. Die konkrete Anordnung der Atom-Damen
könnte im Prinzip mittels Atommikroskopie ermittelt werden, ein Verfahren, das an vergleichbaren Aufbauten
bereits erfolgreich demonstriert wurde.
Simulationen auf klassischen Computern deuten stark darauf hin, dass das von den Innsbrucker Theoretikern entworfene
Experiment aufgrund der Quanteneigenschaften der Teilchen sehr viel rascher zu einem Ergebnis führen würde,
als jeder mathematische Algorithmus auf einem klassischen Computer das schaffen könnte. „Damit ließe
sich die Überlegenheit von Quantencomputern für die Berechnung von bestimmten Optimierungsproblemen mit
diesem Experiment erstmals eindeutig nachweisen“, resümiert Wolfgang Lechner. „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.“
Die Arbeit ist im Fachmagazin Quantum erschienen und wurde vom österreichischen Wissenschaftsfonds FWF, der
Hauser-Raspe-Stiftung und der Europäischen Union finanziell unterstützt.
Publikation: A Quantum N-Queens Solver.
Valentin Torggler, Philipp Aumann, Helmut Ritsch, and Wolfgang Lechner. Quantum 3, 149 (2019) https://doi.org/10.22331/q-2019-06-03-149
|
