Bestimmte natürliche Zahlen kann man als Produkt zweier Primzahlen darstellen. Weil das Finden solcher 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, gehoben 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.
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ärte Wolfgang Lechner vom Institut für Theoretische Physik der Universität Innsbruck und Gründer des Quanten-Spin-off ParityQC. 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.
Vom Produkt zurückrechnen ist nicht einfach
So kann man etwa die simple Multiplikation 2x2=4 nicht einfach umgekehrt ablaufen lassen. Denn 4 könnte das Produkt von 2x2 sein, aber ebenso von 1x4 oder 4x1. "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", so Lechner.
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.
Alternative zum Shor-Algorithmus
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 2x2, 1x4 und 4x1", so Lechner.
Mit einem solchen Quantencomputer, der auf der an der Uni Innsbruck entwickelten und von ParityQC 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 2048 Bit 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", sagte 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, also Atomen, supraleitenden Schaltkreisen, etc. realisiert werden. "Zudem brauchen wir kein Pre- und kein Postprocessing - bei unserem Computer sind sowohl der Input als auch der Output klassische Daten", so Lechner. Dagegen sei beim herkömmlichen Quantencomputer die notwendige Aufbereitung der klassischen Daten und das Auslesen der Ergebnisse sehr aufwendig. (apa)
