Jede natürliche Zahl lässt sich als Produkt von Primzahlen darstellen. 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 auch als sehr sicher. 1994 hat der amerikanische Mathematiker und Informatiker Peter Shor aber einen Algorithmus entwickelt, der mithilfe eines Quantencomputers die Primfaktoren sehr viel rascher findet. 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. Physiker am Institut für Experimentalphysik der Universität Innsbruck und am Institut für Quantenoptik und Quanteninformation der Österreichischen Akademie der Wissenschaften haben nun gemeinsam mit Physikern am Massachusetts Institute of Technology, USA, den Shor-Algorithmus erstmals ohne Vorwissen und so effizient umgesetzt, dass er auch für größere Zahlen anwendbar wird.
Zahl der notwendigen Quantenbits reduziert
Mit Hilfe des Shor-Algorithmus kann ein Quantencomputer große Zahlen sehr viel rascher in Primfaktoren zerlegen als klassische Computer. Um die Zahlen speichern und die Primfaktoren berechnen zu können, benötigt er allerdings entsprechend viele Quantenbits. Dies erweist sich heute noch als schwierig, denn die im Labor existierenden Quantenrechner verfügen nur über wenige Quantenbits. In Innsbruck haben Physiker 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 Experimentalphysiker Thomas 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.“ Mit Hilfe dieses Ansatzes haben die Physiker in einem Ionenfallen-Quantencomputer mit fünf Quantenbits die Zahl 15 faktorisiert.
Parallelsuche führt schneller zum Ergebnis
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 Thomas Monz, der den Vorteil des Shor-Algorithmus noch einmal unterstreicht: „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.“
Finanziell unterstützt wurde die Arbeit unter anderem vom österreichischen Wissenschaftsfonds FWF und der Europäischen Union.
Links
- Realization of a scalable Shor algorithm. Thomas Monz, Daniel Nigg, Esteban A. Martinez, Matthias F. Brandl, Philipp Schindler, Richard Rines, Shannon X. Wang, Isaac L. Chuang, Rainer Blatt. Science 2016
- Forschungsgruppe "Quantenoptik und Spektroskopie"
- Institut für Experimentalphysik
- Institut für Quantenoptik und Quanteninformation (IQOQI)