Letztes Update am Mi, 10.07.2019 12:11

TT / Tiroler Tageszeitung Onlineausgabe


Innsbruck

Innsbrucker Forscher verlagern das Schach-“Damenproblem“ in den Quantencomputer

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.

Auf dem „Quanten-Schachbrett“ lässt sich das Damenproblem vergleichsweise einfach lösen.

© Uni InnsbruckAuf dem „Quanten-Schachbrett“ lässt sich das Damenproblem vergleichsweise einfach lösen.



Innsbruck – Wie können acht Damen auf einem Schachbrett so angeordnet werden, dass sie einander nicht schlagen können? Dieses „Damenproblem“ lässt sich auf dem klassischen Schachbrett mit überschaubarem Aufwand lösen, wird das Feld aber größer, nimmt der Rechenaufwand massiv zu. Mit dem Quantencomputer könnte das Problem künftig leichter gelöst werden, berichten Innsbrucker Physiker im Fachjournal Quantum.

Auf dem Schachbrett mit seinen acht mal acht Feldern gehen sich genau 92 Anordnungen aus, bei denen sich die acht Damen in ihrem durch die Schachregeln definierten Aktionsradius nicht in die Haare kriegen. Wird der Raum jedoch erweitert, werden die Anzahl der Möglichkeiten und der rechnerische Aufwand explosionsartig größer: Zählt das Brett 25 mal 25 Felder sind es schon zwei Billiarden Möglichkeiten.

Stehen bereits einige Damen auf dem Feld und stellen damit Wege zu, wird es noch komplizierter. In einem populärwissenschaftlichen Artikel ist Wolfgang Lechner vom Institut für Theoretische Physik der Universität Innsbruck und dem Institut für Quantenoptik und Quanteninformation (IQOQI) der Österreichischen Akademie der Wissenschaften (ÖAW) über eine Arbeit britischer Wissenschafter gestolpert: Sie haben gezeigt, dass dem Problem unter diesen Voraussetzungen mit 21 Damen durch klassische mathematische Algorithmen nicht mehr in angemessener Zeit beizukommen ist.

Lechner, der sich mit allgemeineren Optimierungsproblemen beschäftigt, wurde klar, dass es sich hier um eine Aufgabe handelt, wo quantenphysikalische Herangehensweisen zu besseren Resultaten führen könnten, wie er im Gespräch mit der APA erklärte. Anders als die herkömmlichen Bits eines Computers, die nur exakt zwei Zustände (0 und 1) einnehmen können, können die Qubits genannten Informationseinheiten des Quantencomputers mehrere Zustände gleichzeitig darstellen und miteinander wechselwirken. „Ob es überhaupt möglich ist, für so ein numerisches Problem die Überlegenheit von Quantencomputern zu zeigen“, sei momentan eine zentrale Frage in der Quantenphysik.

Aus Atomen werden Schachdamen

In Kooperation mit Helmut Ritsch, Valentin Torggler und Philipp Aumann ging Lechner daran, eine Art Quanten-Schachbrett zur Lösung des Damenproblems zu konstruieren. Als Spielfiguren fungieren hier einzelne Atome, das Brett wird mittels eines optischen Gitters aus Laserstrahlen aufgebaut.

„Ü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“, so Ritsch in einer Aussendung der Uni Innsbruck. Da die Teilchen in der ultrakalten Umgebung ihre Quanteneigenschaften herauskehren und wie Wellen funktionieren, können diese „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“, so der Physiker.

Lösung abmessen oder auslesen

Wie die Lösung aussieht, könnte dann entweder ausgelesen werden, „indem man einfach die Position der Atome misst“. Aber auch das von dem System abgestrahlte Lichtfeld trage die Information über die Positionen in sich, erklärte Lechner. Obwohl ein solcher Aufbau noch Schwierigkeiten in der Umsetzung bereit halte, „spricht überhaupt nichts dagegen, dass man es sofort probiert“. Außerdem bestehe die Hoffnung, „dass man relativ schnell diese 21 Atome erreicht“, sagte der Wissenschafter. (APA)