Frischer Wind fürs Quantencomputing

Forscher der Firma D-Wave Systems haben mit Hilfe eines Quantenalgorithmus eine komplizierte mathematische Aufgabe gelöst. Der Quantenrechner, den sie einsetzten, verwendet 84 Qubits – die höchste Zahl von Qubits, die bislang implementiert wurde.

In Pocket speichern vorlesen Druckansicht 4 Kommentare lesen
Lesezeit: 7 Min.
Von
  • Niels Boeing

Forscher der Firma D-Wave Systems haben mit Hilfe eines Quantenalgorithmus eine komplizierte mathematische Aufgabe gelöst. Der Quantenrechner, den sie einsetzten, verwendet 84 Qubits – die höchste Zahl von Qubits, die bislang implementiert wurde.

Still ist es zuletzt um den Quantencomputer geworden. Noch vor einigen Jahren wurde er als unerhörte Zukunftstechnologie gepriesen, die irgendwann wahnwitzige Berechnungen in Sekundenschnelle anstellen und heutige Rechner alt aussehen lassen würde. So jedenfalls hieß es immer wieder.

Was die ersten einfachen Quantencomputer in Forschungslaboren bisher demonstriert haben, ist jedoch nicht mehr als ein Proof of Principle. So gelang es vor zehn Jahren Physikern, mit Hilfe von sieben „Qubits“ – dem Gegenstück von Bits in einem Quantencomputer – die Zahl „15“ in ihre Faktoren zu zerlegen. Die Aufregung war damals groß – obwohl das im Prinzip jeder Viertklässler kann. 2011 wurde der bisherige Rekord aufgestellt: die Faktorzerlegung der Zahl „143“ mit vier Qubits. Das nötigt schwerlich Bewunderung ab.

Doch nun könnte der schleppende Fortschritt im Quantencomputing vielleicht Fahrt aufnehmen: Zhengbing Bian und seinen Kollegen von der kanadischen Firma D-Wave Systems ist es gelungen, mit 84 Qubits so genannte Ramsey-Zahlen zu berechnen.

Um die Bedeutung dessen zu ermessen, muss man zunächst verstehen, was das Besondere an einem Quantencomputer ist. In einem herkömmlichen Rechner werden Bits – „binary digits“, Binärzahlen – verarbeitet, die entweder den Wert „0“ oder „1“ annehmen können. Quantencomputer hingegen arbeiten mit Qubits, denen eine seltsame Eigenschaft der Quantenmechanik zueigen ist: die Überlagerung von Zuständen. Solange eine Zustandsgröße eines quantenmechanischen Systems, etwa eines Atoms, nicht gemessen wird, kann sie mehrere Werte gleichzeitig annehmen. Stellt ein Atom ein Qubit dar, bedeutet das, dass es sowohl eine „1“ als auch eine „0“ repräsentieren kann – etwa in Form der physikalischen Größe des Spins. Entsprechend können zwei Qubits parallel 4 Bitwerte, vier Qubits schon 16 Bitwerte annehmen.

Die Menge der repräsentierten Bits wächst also nicht nur exponentiell mit der Menge der Qubits, so dass auf relativ kleinem Raum schon riesige Datenmengen verarbeitet werden könnten. Ein Quantencomputer wendet auch auf all diese Daten seine Rechenoperationen gleichzeitig an. Er eignet sich daher insbesondere für Probleme, die nicht exakt lösbar sind, sondern auf einem herkömmlichen Rechner nacheinander mit immer neuen Startwerten durchprobiert werden müssen. Damit kann er im Prinzip auch Aufgaben lösen, die heute nur sündhaft teure Supercomputer bewältigen.Theoretisch jedenfalls: Denn die Kunst ist nun, die Qubits vor jeder Störung durch die Außenwelt abzuschirmen und die richtigen Algorithmen zu finden, die zu einer Messung des Qubit-Systems führen und dabei über die Messgröße das Ergebnis der Berechnung ausspucken.

Eine solche anspruchsvolle Aufgabe ist die Berechnung von Ramsey-Zahlen für zweifach eingefärbte Graphen. Das Problem ist nach dem britischen Mathematiker Frank Plumpton Ramsey benannt, der es 1930 erstmals in einem Aufsatz formuliert. Die Schwierigkeit hat der ungarische Mathematiker Paul Erdös so verdeutlicht: Würden Aliens auf der Erde landen und uns nur am Leben lassen, wenn wir ihnen binnen eines Jahres die Ramsey-Zahl R(5,5) nennen könnten, müsste die Menschheit fix ihre klügsten Köpfe und die besten Rechner versammeln. Dann hätte sie vielleicht eine Chance zu überleben. Würden die Aliens hingegen R(6,6) von uns wissen wollten, sollten wir besser sofort zum Gegenangriff übergehen. Denn R(6,6) wäre schon zu schwierig zu lösen.

Die zu lösende Aufgabe kann man sich am ehesten als Partysituation vorstellen: Von den Gästen sind einige untereinander bekannt, andere nicht. Dies könnte man in einem Graphen darstellen, in dem die Gäste durch die Ecken dargestellt werden, ihre Verbindung zueinander durch Linien – oder mathematisch "Kanten" (siehe Bild). Kennen sich zwei, wird die Linie blau eingefärbt, kennen sie sich nicht, ist sie rot.

Ein Ramsey-Graph mit sechs Ecken, der zwei miteinander verbundene 3er-Gruppen (blaue Linien) enthält. Die roten Linien symbolisieren im Party-Beispiel Paare von Gästen, die sich nicht kennen, die blauen Bekanntschaften.

(Bild: D-Wave Systems)

Wie groß müsste nun die Zahl der Gäste mindestens sein, wenn es unter ihnen eine Gruppe gibt, in der sich drei gegenseitig kennen – eine 3er-Clique bilden –, oder eine Gruppe von drei Gästen, die sich noch nie zuvor gesehen haben? Gesucht ist also die Ramsey-Zahl R(3,3). Die Lösung lautet: 6.

Was zunächst nicht allzu schwierig klingt, wenn man sich den entsprechenden Graphen anschaut, wächst sich schnell zu einer Herkulesaufgabe aus, wenn man die Zahl der Bekanntschaften und Nichtbekanntschaften nur ein wenig erhöht. Schon R(5,5) ist bis heute nicht bekannt. Mathematiker glauben zumindest, dass die Lösung zwischen den Zahlen 43 und 49 liegen muss. Eine Berechnung ist zwar im Prinzip möglich, würde aber mit heutigen Computern 10250 Jahre dauern. Bian und seine Kollegen haben nun die Ramsey-Zahlen R(3,3) und R(m,2) berechnet, bei letzterer setzten sie für m jeweils die Zahlen 4, 5, 6, 7 und 8 ein.

In dem Quantencomputer von D-Wave Systems, den sie hierfür einsetzten, bestehen die Qubits aus supraleitenden Schleifen. In diesen fließt ein eingespeister Strom entweder im oder gegen den Uhrzeigersinn, und das, weil Supraleiter keinen elektrischen Widerstand zeigen, beliebig lange. Da die Schleifen Quantensysteme sind, existieren bis zu einer Messung beide Stromrichtungen überlagert, also gleichzeitig, und repräsentieren so „0“ und „1“. Die Berechnung besteht darin, dass manche der supraleitenden Schleifen magnetisch miteinander gekoppelt werden und man dann wartet, bis das System seine Gesamtenergie minimiert hat. Aus deren Wert lässt sich dann das Ergebnis ablesen.

Für die Berechnung von R(8,2) nutzen die D-Wave-Forscher 84 Qubits eines D-Wave-Quantenprozessors. Davon führten 28 den Algorithmus aus, während die Restlichen der Fehlerkorrektur dienten. Das Ergebnis war in 270 Millisekunden ermittelt und lautet korrekt: 8 (es ist schon seit vielen Jahren bekannt). „Die R(8,2)-Berechnung ist unseres Wissens die bislang größte experimentelle Anordnung eines Quantenalgorithmus“, schreiben Bian und Kollegen.

Für D-Wave Systems könnte es ein wichtiger Meilenstein sein. Die kanadische Firma vermarktet seit 2008 einen 128-Qubit-Rechner für zehn Millionen Dollar. Dabei verwendet sie eine „adiabatische Quantenberechnung“. Das bedeutet, dass sich der Quantenprozessor ganz langsam seinem Ergebniszustand nähert. D-Wave Systems habe jedoch nicht zeigen können, dass diese langsame Variante des Quantencomputings in dem System wirklich stattfinde, kritisieren etliche Physiker. So sei das Unternehmen bislang den Beweis schuldig geblieben, dass sein Quantenrechner wirklich so viel leistungsfähiger als herkömmliche Computer sei.

Andererseits haben sich namhafte Firmen wie Google oder Lockheed Martin zur Zusammenarbeit mit D-Wave Systems entschlossen. Nun bleibt abzuwarten, ob der Ramsey-Zahl-Algorithmus den Kanadiern neue Unterstützer bringt. Die Kritiker werden jedenfalls sehr genau nach einem Knackpunkt in dem Experiment von Bian und seinen Kollegen suchen.


Das Paper:
Bian, Z. et al.: „Experimental Determination Of Ramsey Numbers With Quantum Annealing“, arXiv-Server, 10.1.2012 (nbo)