Quantencomputer faktorisiert Zahlen effizienter
Ionenfalle zerlegt die Zahl 15 mit nur fünf Quantenbits in Primzahlen.
Der Shor-Algorithmus ist der wohl bekannteste Quantenalgorithmus. Er löst ein jahrtausendealtes Problem, nämlich die Primfaktorzerlegung von Zahlen. Physiker der Uni Innsbruck um Rainer Blatt haben nun gemeinsam mit Wissenschaftlern am MIT um Isaac Chuang diesen Algorithmus in einem Ionenfallen-Quantencomputer so effizient umgesetzt, dass er auch für größere Zahlen anwendbar ist.
Für kleine Zahlen ist die Primfaktorzerlegung nur eine Denksportaufgabe, bei großen Zahlen erweist sie sich aber als extrem aufwändig. Darauf beruhen heute gängige Verschlüsselungsverfahren wie das RSA-Kryptosystem. Weil klassische Computer an der Primfaktorzerlegung großer Zahlen sehr lange rechnen, galt dieses Verfahren bisher als sehr sicher. Der amerikanische Mathematiker und Informatiker Peter Shor hat jedoch bereits 1994 einen Algorithmus entwickelt, der mithilfe eines Quantencomputers die Primfaktoren sehr viel rascher findet. In den vergangenen fünfzehn Jahren wurde der Shor-Algorithmus im Labor bereits mehrmals mit unterschiedlichen Technologien demonstriert – allerdings nicht, ohne das Ergebnis schon von vornherein vorauszusetzen und nur für kleine Zahlen.
Um die Zahlen speichern und die Primfaktoren berechnen zu können, benötigt ein Quantencomputer entsprechend viele Quantenbits. Das ist heute noch schwierig, denn die im Labor existierenden Quantenrechner verfügen nur über wenige Quantenbits. Das Team der Uni Innsbruck hat nun einen Vorschlag von Alexei Kitaev aufgegriffen, der die Zahl der benötigten Quantenbits reduziert. „Um die Zahl 15 in ihre Primfaktoren zu zerlegen, benötigen wir statt zwölf nur noch fünf Quantenbits“, erklärt Thomas Monz. „Möglich ist das zum einen, weil wir ein Quantenbit im Rahmen der Rechnung recyceln können, zum anderen, weil wir das Ergebnis immer wieder in einem Cache-Bit zwischenspeichern und dann weiterrechnen.“ Mit Hilfe dieses Ansatzes haben die Forscher in einem Ionenfallen-Quantencomputer mit fünf Quantenbits die Zahl 15 faktorisiert.
Der Quantencomputer startet die Suche nach den Primfaktoren mit einer zufällig gewählten Zahl – hier unterscheidet sich die aktuelle Arbeit wesentlich von den bisherigen, weil sie keine Vorwegnahme des Ergebnisses enthält – und führt auf vier Quantenbits eine Reihe von Gatteroperationen durch. Um die Zahl der notwendigen Quantenbits zu begrenzen, wird das Ergebnis immer wieder in einem fünften Quantenbit zwischengespeichert und mit dem Ergebnis weitergerechnet. „Wir mussten dafür eine neue Kühlmethode implementieren, mit der die Ionen zwischen den Rechenschritten immer wieder abgekühlt werden können“, sagt Monz. „Klassische Computer tun sich mit der Primfaktorzerlegung sehr schwer, weil sie alle möglichen Zahlenkombinationen hintereinander durchprobieren müssen. Im Quantenrechner geschieht dies quasi parallel.“
LFU / RK
