Forschung

Knobeln auf dem Quanten-Schachbrett

10.07.2019 - Neues Modell könnte Überlegenheit von Quantencomputern bei der Lösung von Optimierungsaufgaben zeigen.

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 zwei 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. Unlängst 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 von der Uni Innsbruck. Gemeinsam mit Kollegen entwickelte Lechner ein Quanten-Schachbrett, auf dem das Damenproblem mit Hilfe der Quantenphysik experimentell gelöst werden könnte.

„Als Schachbrett kann ein optisches Gitter aus Laserstrahlen genutzt werden, in das einzelne Atome geladen werden“, erklärt Helmut Ritsch von der Uni Innsbruck. „Ü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 Bewegungs­richtungen 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 Wechsel­wirkung 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 Quanten­eigen­schaften 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.

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 Atom­mikroskopie ermittelt werden, ein Verfahren, das an vergleichbaren Aufbauten bereits erfolgreich demonstriert wurde.

Simulationen auf klassischen Computern deuten stark darauf hin, dass das von Lechner und seinen Kollegen entworfene Experiment aufgrund der Quanten­eigen­schaften 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 Quanten­computern für die Berechnung von bestimmten Optimierungs­problemen mit diesem Experiment erstmals eindeutig nachweisen“, resümiert 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.“

U. Innsbruck / RK

Weitere Infos

 

Produkte des Monats

4 Methoden, um Niederdruck-Gasströmungen zu modellieren

Vakuum- und Niederdrucksysteme werden für unterschiedliche Zwecke, wie Elektronenmikroskope oder in der Halbleiterherstellung, eingesetzt. Forscher und Entwickler, die mit Vakuumsystemen arbeiten, nutzen verstärkt Simulation für eine effizientere Entwicklung und zur Reduktion kostspieliger Prototypen.

 

Zur Registrierung

Neues aus der Welt der Multiphysik-Simulation

Die COMSOL News 2019 enthält spannende Berichte aus den verschiedensten Bereichen der Forschung und Entwicklung. Erfahren Sie, wie Multiphysik-Simulation Smart City-Technologien verbessert, den gezielteren Einsatz von Krebs-Medikamenten ermöglicht und für eisfreie Straßen im Winter sorgen kann!

Laden Sie die COMSOL News 2019 ohne Anmeldung und kostenfrei herunter:

HIER

Produkte des Monats

4 Methoden, um Niederdruck-Gasströmungen zu modellieren

Vakuum- und Niederdrucksysteme werden für unterschiedliche Zwecke, wie Elektronenmikroskope oder in der Halbleiterherstellung, eingesetzt. Forscher und Entwickler, die mit Vakuumsystemen arbeiten, nutzen verstärkt Simulation für eine effizientere Entwicklung und zur Reduktion kostspieliger Prototypen.

 

Zur Registrierung

Neues aus der Welt der Multiphysik-Simulation

Die COMSOL News 2019 enthält spannende Berichte aus den verschiedensten Bereichen der Forschung und Entwicklung. Erfahren Sie, wie Multiphysik-Simulation Smart City-Technologien verbessert, den gezielteren Einsatz von Krebs-Medikamenten ermöglicht und für eisfreie Straßen im Winter sorgen kann!

Laden Sie die COMSOL News 2019 ohne Anmeldung und kostenfrei herunter:

HIER