Innsbrucker Physiker lassen Quantencomputer rückwärts rechnen
Die Faktorierung großer Zahlen stellt herkömmliche Computer vor größere Problemen. Physiker der Universität Innsbruck scheinen hierfür eine Lösung gefunden zu haben, die sich mit Hilfe von Quantencomputern realisieren lässt.
Innsbrucker Physiker entwickeln umkehrbare Computer-Gatter für die Faktorisierung großer Zahlen.
Foto: Panthermedia.net/welcomia
Die Faktorisierung großer Zahlen erfordert erhebliche Rechenarbeit, um ihre Bestandteile zu identifizieren. Ein Team von Physikern der Universität Innsbruck unter der Leitung von Professor Wolfgang Lechner hat einen Plan für den Bau eines neuartigen Quantencomputers entwickelt, der das Faktorisierungsproblem lösen kann. Dieses Problem bildet eine Grundlage für moderne Verschlüsselungsmethoden in der Kryptographie. Vereinfacht gesagt kann der Quantencomputer rückwärts rechnen.
Das Problem mit der Zerlegung von Primfaktoren
Die Darstellung bestimmter natürlicher Zahlen als Produkt zweier Primzahlen spielt eine entscheidende Rolle in der Kryptographie. Da das Finden dieser Primfaktoren bei großen Zahlen sehr zeitaufwendig ist, basieren viele Verschlüsselungsverfahren auf dem Prinzip der Primfaktorzerlegung. Schon früh erkannte man das enorme Potenzial von Quantencomputern für die Faktorisierung, doch bisher war es nicht möglich, dieses Potenzial vollständig auszuschöpfen. Nun präsentieren Physiker der Universität Innsbruck ein neues Konzept für einen Quantencomputer, der in der Lage ist, Zahlen durch den Einsatz von Rückwärtsoperationen zu zerlegen.
Die Primfaktorzerlegung stellt für klassische Computer eine Herausforderung dar, da sie auf irreversiblen Prozessen beruhen. Algorithmen haben in klassischen Computern eine feste Richtung und können nicht einfach rückwärts ablaufen, erklärte Wolfgang Lechner. Daher ist die Multiplikation zweier Zahlen, selbst wenn sie groß sind, für einen klassischen Computer einfach durchzuführen, während die Zerlegung großer Zahlen eine deutlich größere Herausforderung darstellt.
Selbst einfache Rechenaufgaben lassen sich nicht rückwärts rechnen
Nimmt man die Multiplikation 2*2=4, so kann man diese Operation nicht einfach umgekehrt ablaufen lassen, weil 4 könnte 2*2 sein, aber genauso 1*4 oder 4*1“, erklärt Wolfgang Lechner, Professor für Theoretische Physik an der Universität Innsbruck. Wenn es jedoch möglich wäre, dies zu erreichen, hätte man die Möglichkeit, große Zahlen zu faktorisieren und somit in ihre Primfaktoren zu zerlegen. Dies stellt einen entscheidenden Grundpfeiler in der Kryptographie dar.
Im Jahr 1994 entwickelte der amerikanische Mathematiker Peter Shor einen Algorithmus, der mithilfe eines hypothetischen Quantencomputers die Primfaktoren von Zahlen wesentlich schneller finden könnte als ein herkömmlicher Computer. Zu dieser Zeit existierte jedoch noch kein funktionsfähiger Quantencomputer. Der sogenannte Shor-Algorithmus erfordert allerdings eine beträchtliche Anzahl von Quantenbits (Qubits), insbesondere bei großen Zahlen. Qubits sind die grundlegenden Informationseinheiten eines Quantencomputers und können mit verschiedenen physikalischen Systemen realisiert werden, darunter Ionen, Atome, Photonen oder supraleitende Schaltkreise.
Nach wie vor ist es jedoch schwierig, eine zuverlässige Kontrolle über eine große Anzahl von Qubits zu erreichen und sie mithilfe des quantenphysikalischen Phänomens der Verschränkung zu einer kohärenten Einheit zusammenzuführen. Aus diesem Grund verfügen aktuelle Quantencomputer nur über eine begrenzte Anzahl von Quantenbits und sind selbst mit dem Shor-Algorithmus noch nicht in der Lage, Verschlüsselungsverfahren auf der Basis großer Zahlen zu entschlüsseln.
Martin Lanthaler (li.) und Wolfgang Lechner (re.) vom Institut für Theoretische Physik der Universität Innsbruck.
Foto: ParityQC
Physiker entwickeln neue Methode
Martin Lanthaler, Ben Niehoff und Wolfgang Lechner vom Institut für Theoretische Physik der Universität Innsbruck haben nun eine Alternative zum Shor-Algorithmus entwickelt. Ihre Idee haben Sie im Fachjournal „Natur Communications Physics“ veröffentlicht. Wolfgang Lechner erläutert dazu, dass die Idee dahinter besteht, die Multiplikation umzukehren. Dies basiert auf dem quantenphysikalischen Phänomen der „Superposition“, das in der alltäglichen Erfahrung nicht nachvollziehbar ist. Während ein klassisches Bit im herkömmlichen Computer nur zwei Zustände (0 oder 1) haben kann, 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×2, 1×4 und 4×1“, so Lechner.
Basierend auf der an der Universität Innsbruck entwickelten Parity-Architektur, die mittlerweile von ParityQC kommerziell angeboten wird, benötigt ein solcher Quantencomputer laut dem Physiker „viel weniger Qubits als für den fehlerkorrigierten Shor-Algorithmus“. Um beispielsweise einen gängigen RSA-Schlüssel mit einer Länge von 2048 Bit zu knacken, würde der Shor-Algorithmus Milliarden von Qubits und eine unglaublich große Anzahl von Quanten-Gattern (10 hoch 21) erfordern. „Ein nach unserem Bauplan konzipierter Quantencomputer benötigt dagegen nur 14 Millionen Qubits und keine Quanten-Gatter, sondern läuft analog“, erklärte Lechner. Die neue Architektur sei gut skalierbar, da alle benötigten Grundbausteine gleich aussehen und parallel betrieben werden können.
Quantenverfahren beschleunigen den Suchprozess
„Kern unserer Arbeit ist die Codierung der Grundbausteine des Multiplizier-Schaltkreises, konkret von UND-Gatter, Halb-und Volladdierer mit der Parity-Architektur als Grundzustandsproblem auf einem Ensemble von wechselwirkenden Spins“, erklärt Martin Lanthaler. Durch die Codierung ist es möglich, den gesamten Schaltkreis aus wiederholenden Subsystemen aufzubauen, die auf einem zweidimensionalen Raster angeordnet werden können. Zusätzlich können durch die Reihung mehrerer solcher Subsysteme größere Probleminstanzen realisiert werden.
Im Gegensatz zur klassischen Brute-Force-Methode, bei der alle möglichen Faktoren ausprobiert werden, können Quantenverfahren den Suchprozess beschleunigen. Um den Grundzustand zu finden und ein Optimierungsproblem zu lösen, ist es nicht erforderlich, die gesamte Energielandschaft zu durchsuchen. Stattdessen können tieferliegende Täler durch das Phänomen des „Tunnelns“ erreicht werden.
Das Konzept hat nach Ansicht der Innsbrucker Physiker noch weitere Vorteile, so lasse sich zum Beispiel die Architektur mit allen Quantensystemen realisieren. Dazu gehören beispielsweise Atome oder supraleitende Schaltkreise. „Zudem brauchen wir kein Pre- und kein Postprocessing – bei unserem Computer sind sowohl der Input als auch der Output klassische Daten“, so Lechner. Beim herkömmlichen Quantencomputer sei die Aufbereitung der Daten und das Auslesen der Ergebnisse hingegen sehr aufwendig.
Ein Beitrag von:
