Die Basis heutiger Computer sind Mikroprozessoren, die sogenannte Gatter ausführen. Ein Gatter kann zum Beispiel eine Und-Operation sein, also eine Operation die zwei Bits addiert. Diese Gatter und damit Computer als Ganzes sind irreversibel. Das heißt, Algorithmen können nicht einfach rückwärts ablaufen. „Nimmt man die Multiplikation 2 x 2 = 4, so kann man diese Operation nicht einfach umgekehrt ablaufen lassen, weil 4 könnte 2 x 2 sein, aber genauso 1 x 4 oder 4 x 1“, erklärt Wolfgang Lechner, Professor für Theoretische Physik an der Universität Innsbruck. Gelänge dies aber, könnte man große Zahlen faktorisieren, sie also in ihre Faktoren zerlegen, was ein wichtiger Pfeiler der Kryptographie ist.
Genau diese Umkehrung von Algorithmen haben Martin Lanthaler, Ben Niehoff und Lechner vom Institut für Theoretische Physik der Universität Innsbruck und dem Quanten-Spin-off ParityQC mit Hilfe von Quantencomputern nun entwickelt. Startpunkt ist ein klassischer logischer Schaltkreis, welcher zwei Zahlen miteinander multipliziert. Werden als Ausgangswert zwei ganze Zahlen eingegeben, liefert der Schaltkreis deren Produkt. Ein solcher Schaltkreis ist aus irreversiblen (nicht umkehrbaren) Operationen aufgebaut. „Jedoch kann die Logik des Schaltkreises innerhalb von Grundzuständen eines Quantensystems kodiert werden“, erklärt Lanthaler aus dem Team von Lechner. „Damit kann sowohl Multiplikation als auch Faktorisierung als Grundzustandsproblem verstanden und mit Methoden der Quantenoptimierung gelöst werden.“
Superposition aus allen Möglichkeiten
„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“, so Lanthaler. Die Codierung erlaubt es, den ganzen Schaltkreis aus sich wiederholenden Subsystemen aufzubauen, die auf einem zweidimensionalen Raster angeordnet werden können. Indem mehrere dieser Subsysteme aneinandergereiht werden, können größere Problem-Instanzen realisiert werden.
Anstelle der klassischen Brute-Force-Methode, wo alle möglichen Faktoren ausprobiert werden, können Quantenverfahren den Suchprozess beschleunigen: Um den Grundzustand zu finden, und damit ein Optimierungsproblem zu lösen, muss nicht die ganze Energielandschaft abgesucht werden, sondern tieferliegende Täler können durch „tunneln“ erreicht werden.
