Quantencomputer faktorisiert Zahlen effizienter

Jede natürliche Zahl lässt sich als Produkt von Primzahlen darstellen. Für kleine Zahlen ist diese Primfaktorzerlegung einfach, bei großen Zahlen erweist sie sich aber als extrem aufwendig. Darauf beruhen heute gängige Verschlüsselungsverfahren. 1994 wurde der sogenannte Shor-Algorithmus entwickelt, der mithilfe eines Quantencomputers die Primfaktoren deutlich schneller findet. Physiker aus Österreich und den USA haben diesen Quantenalgorithmus nun erstmals so effizient umgesetzt, dass er auch für größere Zahlen anwendbar wird, wie sie in der Fachzeitschrift „Science“ berichten.

Damit ein Quantencomputer große Zahlen speichern und die Primfaktoren berechnen kann, benötigt er entsprechend viele Quantenbits. Dies erweist sich heute noch als schwierig, denn die im Labor existierenden Quantenrechner verfügen nur über wenige Quantenbits. Das Forscherteam um Thomas Monz von der Universität Innsbruck griff nun einen Vorschlag des Physikers Alexei Kitaev auf, 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 Monz. „Möglich ist dies 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.“ Mithilfe dieses Ansatzes haben die Physiker 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“, berichtet Monz.

Klassische Computer geraten bei der Primfaktorzerlegung großer Zahlen schnell an ihre Grenzen, denn der Rechenaufwand nimmt exponentiell mit der Länge der Zahl zu. „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“, erläutert Monz. In den vergangenen 15 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.