idw – Informationsdienst Wissenschaft

Nachrichten, Termine, Experten

Grafik: idw-Logo
Grafik: idw-Logo

idw - Informationsdienst
Wissenschaft

Science Video Project
idw-Abo

idw-News App:

AppStore

Google Play Store



Instance:
Share on: 
05/04/2023 09:05

Quantencomputer kann rückwärts rechnen: Umkehrbare Computer-Gatter für die Faktorisierung großer Zahlen entwickelt

Dr. Christian Flatz Büro für Öffentlichkeitsarbeit
Universität Innsbruck

    Große Zahlen lassen sich nur mit sehr viel Rechenarbeit in ihre Faktoren zerlegen. Physiker der Universität Innsbruck um Wolfgang Lechner liefern nun einen Bauplan für eine neue Art von Quantencomputer zum Lösen des Faktorisierungsproblems, das ein Eckpfeiler der modernen Kryptographie ist.

    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*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. 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 Wolfgang 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 Martin Lanthaler aus dem Team von Wolfgang 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 Martin 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.

    Die aktuelle Forschungsarbeit liefert einen Bauplan für eine neue Art von Quantencomputer zum Lösen des Faktorisierungsproblems, das ein Eckpfeiler der modernen Kryptographie ist. Dieser Bauplan basiert auf der an der Universität Innsbruck entwickelten Parity-Architektur und kann auf allen gängigen Quantencomputerplattformen umgesetzt werden.

    Veröffentlicht wurden die Ergebnisse vor kurzem in der Fachzeitschrift Nature Communications Physics. Finanziell unterstützt haben die Forschungen unter anderem der Österreichische Wissenschaftsfonds FWF, die Europäische Union und die Österreichische Forschungsförderungsgesellschaft FFG.


    Contact for scientific information:

    Wolfgang Lechner
    Institut für Theoretische Physik
    Universität Innsbruck
    +43 512 507 52232
    Wolfgang.Lechner@uibk.ac.at
    https://www.uibk.ac.at/th-physik/quantum-optimization/


    Original publication:

    Scalable set of reversible parity gates for integer factorization. Martin Lanthaler, Benjamin E. Niehoff & Wolfgang Lechner. Nature Communications Physics 6, 73 (2023) DOI: https://doi.org/10.1038/s42005-023-01191-3


    More information:

    https://www.uibk.ac.at/de/newsroom/2022/neue-art-von-universellen-quantencompute... - Neue Art von uni­ver­sel­len Quan­ten­com­pu­tern


    Images

    Martin Lanthaler (li.) und Wolfgang Lechner (re.) vom Institut für Theoretische Physik der Universität Innsbruck.
    Martin Lanthaler (li.) und Wolfgang Lechner (re.) vom Institut für Theoretische Physik der Universit ...

    ParityQC


    Criteria of this press release:
    Journalists, all interested persons
    Information technology, Physics / astronomy
    transregional, national
    Research results, Scientific Publications
    German


     

    Help

    Search / advanced search of the idw archives
    Combination of search terms

    You can combine search terms with and, or and/or not, e.g. Philo not logy.

    Brackets

    You can use brackets to separate combinations from each other, e.g. (Philo not logy) or (Psycho and logy).

    Phrases

    Coherent groups of words will be located as complete phrases if you put them into quotation marks, e.g. “Federal Republic of Germany”.

    Selection criteria

    You can also use the advanced search without entering search terms. It will then follow the criteria you have selected (e.g. country or subject area).

    If you have not selected any criteria in a given category, the entire category will be searched (e.g. all subject areas or all countries).