Zur Verschlüsselung von Daten ist oft Primfaktorzerlegung angesagt. Dabei wird eine natürliche Zahl dargestellt als die Multiplikation von zwei Primzahlen – welche per Definition nur zwei Teiler haben, sich also nur durch 1 und sich selbst teilen lassen. Weil das Finden von Primfaktoren für große Zahlen sehr aufwendig ist, beruhen Verschlüsselungsverfahren auf dieser Primfaktorzerlegung.
Schon früh erkannte man das große Potenzial von Quantencomputern für die Faktorisierung, genutzt werden konnte es bisher aber nicht. Innsbrucker Physiker stellen nun ein neues Konzept für einen Quantencomputer vor, der im Rückwärtsgang Zahlen zerlegen kann.
Exponentiell steigender Aufwand
Klassische Computer plagen sich mit der Primfaktorzerlegung, "weil sie auf irreversiblen Prozessen beruhen. Algorithmen haben dort immer eine Richtung und können nicht einfach rückwärts ablaufen", erklärt Wolfgang Lechner vom Institut für Theoretische Physik der Universität Innsbruck und Gründer des Quanten-Spin-offs Parity QC. Daher ist eine Multiplikation von zwei Zahlen, selbst wenn sie groß sind, für einen klassischen Computer einfach, die Zerlegung großer Zahlen aber nicht.
So kann man etwa die simple Multiplikation 2 x 2 = 4 nicht einfach umgekehrt ablaufen lassen. Denn 4 könnte das Produkt von 2 x 2 sein, aber ebenso von 1 x 4 oder 4 x 1. "Klassisch müsste ich für die Faktorisierung alle diese Möglichkeiten durchgehen – und der Aufwand dafür steigt exponentiell, je größer die Zahl ist", sagt Lechner.
Probleme des Shor-Algorithmus
1994 hat der amerikanische Mathematiker Peter Shor einen Algorithmus entwickelt, der mithilfe eines – damals noch gar nicht existierenden – Quantencomputers die Primfaktoren deutlich schneller findet als ein klassischer Rechner. Doch dieser Shor-Algorithmus braucht für große Zahlen entsprechend viele Quantenbits (Qubits). Solche Qubits, die grundlegende Informationseinheit eines Quantencomputers, können mit verschiedenen Quantensystemen realisiert werden, etwa mit Ionen, Atomen, Photonen oder supraleitenden Schaltkreisen.
Bisher ist es allerdings noch schwierig, viele Qubits zuverlässig zu kontrollieren und mittels des quantenphysikalischen Phänomens der Verschränkung zu einer Einheit zusammenzuschließen. Daher verfügen Quantenrechner bisher nur über wenige Quantenbits und schaffen es selbst mit dem Shor-Algorithmus noch nicht, auf großen Zahlen beruhende Verschlüsselungsverfahren zu knacken.
Superposition hilft bei Lösung
Lechner schlägt nun mit seinem Team im Fachjournal "Nature Communications Physics" eine Alternative zum Shor-Algorithmus vor. "Die Idee dabei ist, dass man eine Multiplikation umdreht", betonte der Physiker. Basis dafür ist das mit der Alltagserfahrung nicht nachvollziehbare quantenphysikalische Phänomen der Superposition.
Während ein Bit im klassischen Computer nur zwei Zustände einnehmen kann (0 oder 1), kann ein Qubit mehrere Zustände gleichzeitig annehmen. "Konkret bedeutet das, dass ich eine Quantenmultiplikation baue und diese dann umdrehe. Wenn ich dann 4 eingebe, bekomme ich eine Superposition von allen Möglichkeiten, die zu 4 führen, also 2 x 2, 1 x 4 und 4 x 1", sagt Lechner.
Skalierbare Architektur
Mit einem solchen Quantencomputer, der auf der an der Uni Innsbruck entwickelten und von Parity QC mittlerweile kommerziell angebotenen Parity-Architektur basiert, braucht man dem Physiker zufolge "viel weniger Qubits als für den fehlerkorrigierten Shor-Algorithmus". Um einen gängigen RSA-Schlüssel mit 2.048 Bits Länge zu knacken, würde der Shor-Algorithmus Milliarden Qubits und vor allem eine unglaublich hohe Zahl (10 hoch 21) Quanten-Gatter benötigen. "Ein nach unserem Bauplan konzipierter Quantencomputer benötigt dagegen nur 14 Millionen Qubits und keine Quanten-Gatter, sondern läuft analog", sagt Lechner. Die neue Architektur sei gut skalierbar, denn die dafür notwendigen Grundbausteine schauen alle gleich aus und könnten einfach parallel betrieben werden.
Das Konzept der Innsbrucker Physiker bietet ihren Angaben zufolge weitere Vorteile: Die Architektur kann mit allen Quantensystemen, beispielsweise Atomen oder supraleitenden Schaltkreisen, realisiert werden. "Zudem brauchen wir kein Pre- und kein Postprocessing – bei unserem Computer sind sowohl der Input als auch der Output klassische Daten", sagt Lechner. Dagegen seien beim herkömmlichen Quantencomputer die notwendige Aufbereitung der klassischen Daten und das Auslesen der Ergebnisse sehr aufwendig. (APA, red, 5.5.2023)