Can PCE solve the factorisation problem via optimisation?
Diese Arbeit untersucht die Durchführbarkeit der Anpassung des Pauli Correlation Encoding (PCE)-Algorithmus auf das Problem der Ganzzahlfaktorisierung als eine Methode zur drastischen Reduzierung des Qubit-Bedarfs, wobei sie eine vorläufige Analyse seines Potenzials und seiner Einschränkungen für Quantenhardware der nächsten Generation bietet, ohne einen Rechenvorteil zu beanspruchen.
Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen
Stellen Sie sich vor, Sie versuchen, einen geheimen Code zu knacken, der Ihr Bankkonto, Ihre E-Mails und fast alles, was Sie online tun, schützt. Dieser Code beruht auf einem einfachen, aber kniffligen mathematischen Spiel: Nehmen Sie zwei riesige Primzahlen (Zahlen, die nur durch 1 und sich selbst teilbar sind), multiplizieren Sie diese miteinander und geben Sie das Ergebnis an die Welt weiter. Es ist einfach, sie zu multiplizieren, aber wenn man nur die riesige Endzahl hat, ist es, die zwei Primzahlen zu finden, die sie erzeugt haben, so, als würde man versuchen, einen Kuchen „rückwärts zu backen“, um genau herauszufinden, wie viele Eier und wie viel Mehl verwendet wurden. Für unsere heutigen Computer ist dies bei sehr großen Zahlen nahezu unmöglich. Dies ist das Problem der „Primfaktorzerlegung“ und es bildet das Rückgrat der modernen digitalen Sicherheit.
Stellen Sie sich nun einen neuen Typ von Computer vor, der nicht nur berechnet, sondern gleichzeitig viele Möglichkeiten erforscht, indem er die seltsamen Regeln der Quantenphysik nutzt. Wissenschaftler versuchen, diese Quantenmaschinen beizubringen, dieses „Rückwärts-Back-Problem“ zu lösen. Eine berühmte Methode, die Peter Shor erfand, ist theoretisch perfekt, erfordert aber einen Quantencomputer, der so leistungsstark und ruhig ist, dass wir noch nicht die Technologie besitzen, um ihn zu bauen. Daher suchen Forscher nach „quanteninspirierten“ Abkürzungen – Methoden, die ein wenig Quantenmagie nutzen, aber auf den verrauschten, unvollkommenen Maschinen laufen können, die wir heute haben. Die große Frage ist: Können wir dieses massive mathematische Problem in ein winziges, handhabbares Rätsel pressen, das diese frühen Quantencomputer tatsächlich lösen können?
Diese Arbeit untersucht genau diese Frage unter Verwendung eines cleveren neuen Tricks namens Pauli Correlation Encoding (PCE). Betrachten Sie PCE als einen supereffizienten Kompressionsalgorithmus. Normalerweise benötigt man eine riesige Anzahl von Quantenbits (Qubits), um ein komplexes Problem mit vielen Variablen (wie die Bits einer riesigen Zahl) darzustellen. PCE wirkt wie ein magischer Reißverschluss, der es den Forschern ermöglicht, tausende von Variablen in eine viel kleinere Anzahl von Qubits zu packen. Die Autoren, Fernando Alonso und sein Team vom Galicia Supercomputing Center, fragten sich: „Wenn wir diesen Reißverschluss verwenden, um das Faktorisierungsproblem zu komprimieren, können wir dann Optimierungstechniken nutzen, um die Antwort zu finden?“
Sie haben nicht einfach nur geraten; sie haben zwei verschiedene „Landkarten“ erstellt, um die Suche zu leiten. Die erste Karte, der sogenannte Basic Approach, war wie der Versuch, die Faktoren durch direktes Erraten des Binärcodes der beiden Primzahlen zu finden. Sie testeten dies an Zahlen von bis zu 25 Bit Länge. Die Ergebnisse waren etwas gemischt: Bei kleineren Zahlen funktionierte es ganz gut, aber als die Zahlen größer wurden, sank die Erfolgsquote, und der Computer blieb oft in „trivialen“ Lösungen stecken (wie etwa zu sagen, dass eine Zahl einfach sich selbst mal eins ist).
Die zweite Karte, DoTS (Difference of Two Squares), war eine intelligentere Strategie. Anstatt direkt nach den Faktoren zu suchen, suchte sie nach zwei Zahlen, deren Quadrate sich um ein Vielfaches der Zielzahl unterscheiden. Es ist wie die Suche nach zwei Personen, die, wenn sie auf einer Waage stehen, eine Gewichtsdifferenz aufweisen, die exakt einem bestimmten Muster entspricht. Dieser Ansatz war viel erfolgreicher. In ihren Simulationen gelang es der DoTS-Methode, Zahlen von bis zu 36 Bit Länge erfolgreich zu faktorisieren.
Das Team verwendete drei verschiedene „Suchmaschinen“ (Optimizer), um sich auf diesen Landkarten zu bewegen: Differential Evolution (DE), Particle Swarm Optimization (PSO) und eine quanteninspirierte Version namens QDPSO. Die Ergebnisse zeigten, dass der DE-Optimizer der klare Gewinner war, da er konsistent die richtigen Antworten fand, während die anderen Schwierigkeiten hatten.
Die Autoren sind jedoch sehr vorsichtig damit, zu behaupten, sie hätten den Code „geknackt“. Sie betonen, dass ihre Methode zwar weit weniger Qubits verwendet als andere Quantenansätze (was sie für die heutige Hardware machbar macht), es sich aber dennoch um eine Simulation handelt, die auf klassischen Computern läuft. Sie stellten fest, dass ihr Verfahren für Zahlen größer als 36 Bit zu scheitern beginnt, was darauf hindeutet, dass die „Kostenfunktion“ (die Regel, die sie für den Computer geschrieben haben) neu geschrieben werden muss, um die Mathematik effektiver zu erfassen. Sie merkten auch an, dass, falls sie dies auf echter Quantenhardware ausführen würden, das Rauschen dem Computer entweder helfen könnte, Sackgassen zu verlassen, oder die Berechnung komplett ruinieren könnte.
Kurz gesagt deutet diese Arbeit darauf hin, dass PCE ein vielversprechendes Werkzeug sein kann, das Faktorisierungsprobleme viel kleiner und handhabbarer für Quantencomputer machen kann. Es löst das Problem für die massiven Zahlen, die in der realen Verschlüsselung verwendet werden, noch nicht, aber es öffnet eine neue Tür. Es zeigt, dass wir mit der richtigen Kompression und der richtigen Suchstrategie Quantencomputer vielleicht schon früher zu ernsthafter Zahlenarbeit bringen können, auch wenn wir noch einen weiten Weg vor uns haben, bevor wir die größten Kuchen der Welt „rückwärts backen“ können.
Ertrinken Sie in Arbeiten in Ihrem Fachgebiet?
Erhalten Sie tägliche Digests der neuesten Arbeiten passend zu Ihren Forschungsbegriffen — mit technischen Zusammenfassungen, in Ihrer Sprache.