Zahlen mit dem Quantencomputer in Primfaktoren zerlegen

3. März 2016, 23:10
40 Postings

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)

Share if you care.