Primfaktoren zerlegen mit dem Quantencomputer
3. März 2016, 23:10
Einem Physikerteam mit Innsbrucker Beteiligung
gelang die bisher effizienteste Umsetzung des "Shor-Algorithmus"
Innsbruck/Cambridge – Große Zahlen in
Primfaktoren zu zerlegen, sie also als Produkt aus Primzahlen
darzustellen, ist eine Herausforderung. Seit 1994 gibt es ein Programm,
das auf derzeit verfügbaren Quantencomputern bei kleinen Zahlen bereits
funktioniert. Quantenphysiker um Rainer Blatt (Uni Innsbruck) berichten
nun in "Science", dass es ihnen gelungen ist, den erforderlichen
Algorithmus in einem Quantencomputer so effizient umzusetzen, dass er
auch für größere Zahlen anwendbar ist.
Die Primfaktorenzerlegung sehr großer Zahlen
ist etwa für Verschlüsselungsverfahren interessant – aber selbst mit
leistungsfähigen Computern extrem aufwendig. Hier könnten künftig
Quantencomputer abhilfe schaffen.
Der US-Mathematiker Peter Shor hat 1994 den
sogenannten "Shor-Algorithmus" zur raschen Primfaktorenzerlegung
entwickelt. In den vergangenen 15 Jahren wurde der Shor-Algorithmus im
Labor bereits mehrmals mit unterschiedlichen Technologien demonstriert,
allerdings nur an kleineren Zahlen, für die man das Ergebnis vorher
kennen musste.
Zwischenspeicherung
Die Innsbrucker Physiker haben nun gemeinsam
mit US-Kollegen vom Massachusetts Institute of Technology (MIT) eine
Lösung gefunden, "die sich auch für größere Zahlen eignet, die nicht
mehr die Kenntnis des Ergebnisses voraussetzt und auf manuellen
Optimierungen aufbaut", wie Erstautor Thomas Monz erklärte. "Bisher
benötigte man für die Zerlegung der Zahl 15 in ihre Primfaktoren noch
zwölf Qubits, wir schaffen es nun mit nur noch fünf Qubits", so Monz.
Möglich wurde dies, weil es den
Wissenschaftern gelang, Zwischenergebnisse in einem Qubit – quasi als
Cache – zu speichern, auszulesen und dann weiterzurechnen. Dieses
Zwischenspeichern wurde erst möglich, als die Physiker das Speicher-Qubit
durch neue Kühlmethoden recyceln konnten. Bisher war dieses Ion nach dem
Auslesen des Ergebnisses nicht mehr zu verwenden. Ohne Vorwegnahme des
Ergebnisses wird also für die Zerlegung der Zahl 15 auf vier Qubits eine
Reihe von Rechenoperationen durchgeführt und das jeweilige
Zwischenergebnis immer wieder am fünften Qubit ausgelesen.
Grundsätzlich reicht auch bei mehr als vier
Qubits, die für Rechenoperationen zur Verfügung stehen, ein Speicher-Qubit.
Im Innsbrucker Quantencomputer könnten also bereits 13 Qubits rechnen
und Ergebnisse im 14. Qubit ausgelesen werden. Allerdings sind aufgrund
der bisherigen Qualität der Verschränkung zwischen den Ionen noch sehr
aufwendige Fehlerkorrekturen notwendig. "Wir arbeiten sowohl an noch
besseren Rechenoperationen und Fehlerkorrektur-Verfahren als auch an
immer besseren Algorithmen", so Monz. (APA, red, 3.3.2016)
Abstract
Science: "Realization of a scalable Shor algorithm"
http://derstandard.at/2000032226375/Primfaktoren-zerlegen-mit-dem-Quantencomputer