Quanten als Codeknacker: Physiker haben eine Methode entwickelt, mit der sich Zahlen einfacher und schneller als bisher von Quantencomputern in Primzahlen zerlegen lassen. Sie modifizierten dafür den sogenannte Shor-Algorithmus und setzten ihn in einem Ionenfallen-Quantencomputer so effizient um, dass er nun auch für größere Zahlen anwendbar wird, wie die Forscher im Fachmagazin „Science“ berichten.
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.
Quanten als Primzahl-Knacker
1994 hat der amerikanische Mathematiker und Informatiker Peter Shor jedoch einen Algorithmus entwickelt, der mithilfe eines Quantencomputers die Primfaktoren sehr viel rascher findet. Weil ein Quantencomputer durch die Überlagerung von Zuständen stärker parallel rechnet als klassische Computer, kann er solche Aufgaben schneller bewältigen. 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 auf der Basis von Photonen und anderen Teilchen verfügen nur über wenige Quantenbits. In den vergangenen 15 Jahren wurde der Shor-Algorithmus im Labor daher zwar schon mit unterschiedlichen Technologien demonstriert – allerdings nicht ohne das Ergebnis schon von vornherein vorauszusetzen und nur für kleine Zahlen.
Zahl der notwendigen Quantenbits reduziert
Thomas Monz von der Universität Innsbruck und seine Kollegen haben den Shor-Algorithmus erstmals so modifiziert und effizient umgesetzt, dass er auch ohne Vorwissen und für größere Zahlen anwendbar wird. Mit Hilfe dieses Ansatzes haben die Physiker in einem Ionenfallen-Quantencomputer mit fünf Quantenbits die Zahl 15 faktorisiert.
„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.“
Vier Bits und ein Zwischenspeicher
Der Quantencomputer startet die Suche nach den Primfaktoren mit einer zufällig gewählten Zahl – im Unterschied zu bisherigen Methoden enthält dies damit keine Vorwegnahme des Ergebnisses. Dann führt er 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.
„Klassische Computer tun sich mit der Primfaktorzerlegung sehr schwer, weil sie alle möglichen Zahlenkombinationen hintereinander durchprobieren müssen“, erklärt Monz. „Im Quantenrechner geschieht dies quasi parallel.“ Ein Vorteil gegenüber bisherigen Quantenverfahren sei zudem die Auslagerung der Zwischenergebnisse durch spektroskopische Verfahren. Das erhöht die Präzision und Zuverlässigkeit der Berechnungen, wie die Forscher erklären. (Science, 2016; doi: 10.1126/science.aad9840)
(Universität Innsbruck, 04.03.2016 – NPO)
