idw – Informationsdienst Wissenschaft
Nachrichten, Termine, Experten
Nachrichten, Termine, Experten
Der Shor-Algorithmus ist der wohl bekannteste Quantenalgorithmus. Er löst ein jahrtausendealtes Problem, nämlich die Primfaktorzerlegung von Zahlen. Innsbrucker Physiker 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 wird.
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.
Publikation: 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 DOI: 10.1126/science.aad9480
Rückfragehinweis:
Dr. Thomas Monz
Institut für Experimentalphysik
Universität Innsbruck
Tel.: +43 512 507 52452
E-Mail: thomas.monz@uibk.ac.at
Web: http://www.quantumoptics.at
Dr. Christian Flatz
Büro für Öffentlichkeitsarbeit
Universität Innsbruck
Tel.: +43 512 507-32022
Mobil: +43 676 872532022
E-Mail: Christian.Flatz@uibk.ac.at
http://www.quantumoptics.at - Arbeitsgruppe Rainer Blatt
Der Shor-Algorithmus löst ein jahrtausendealtes Problem, nämlich die Primfaktorzerlegung von Zahlen.
Quelle: IQOQI/H. Ritsch
Merkmale dieser Pressemitteilung:
Journalisten, jedermann
Physik / Astronomie
überregional
Forschungsergebnisse, Wissenschaftliche Publikationen
Deutsch
Der Shor-Algorithmus löst ein jahrtausendealtes Problem, nämlich die Primfaktorzerlegung von Zahlen.
Quelle: IQOQI/H. Ritsch
Sie können Suchbegriffe mit und, oder und / oder nicht verknüpfen, z. B. Philo nicht logie.
Verknüpfungen können Sie mit Klammern voneinander trennen, z. B. (Philo nicht logie) oder (Psycho und logie).
Zusammenhängende Worte werden als Wortgruppe gesucht, wenn Sie sie in Anführungsstriche setzen, z. B. „Bundesrepublik Deutschland“.
Die Erweiterte Suche können Sie auch nutzen, ohne Suchbegriffe einzugeben. Sie orientiert sich dann an den Kriterien, die Sie ausgewählt haben (z. B. nach dem Land oder dem Sachgebiet).
Haben Sie in einer Kategorie kein Kriterium ausgewählt, wird die gesamte Kategorie durchsucht (z.B. alle Sachgebiete oder alle Länder).
