← Neueste Arbeiten
⚛️ Quantenphysik

Formally verified harness for Shor's order finding algorithm with O(n2+ϵ)O(n^{2+\epsilon}) gate cost

Dieses Paper präsentiert ein formal verifiziertes Harness, das rekursive Schaltungsdesign-Richtlinien aus externen Quellen, wie etwa KI-Agenten, aufnimmt, um automatisch maschinell geprüfte Beweise der mathematischen Korrektheit und einer O(n2+ϵ)O(n^{2+\epsilon}) Gatterkosten-Skalierung für Shors Ordnungssuche-Algorithmus zu generieren und dadurch eine offene Herausforderung für die Entdeckung effizienterer Quantenfaktorisierungsschaltungen mit garantierter Korrektheit ermöglicht.

Ursprünglicher Autor: Anirudh Suresh, Joshua M. Courtney, Runzhou Tao, Yudong Cao

Veröffentlicht 2026-11-17
📖 8 Min. Lesezeit🧠 Tiefgang

Ursprünglicher Autor: Anirudh Suresh, Joshua M. Courtney, Runzhou Tao, Yudong Cao

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 vom Autor verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

In der Landschaft des modernen Computings besteht ein grundlegender Spannungszustand zwischen der Geschwindigkeit der Berechnung und der Sicherheit von Geheimnissen. Seit Jahrzehnten beruht die Sicherheit digitaler Kommunikation auf einem mathematischen Schloss: der Schwierigkeit, eine große Zahl in ihre zwei primen Bausteine zu zerlegen. Während klassische Computer bei dieser Aufgabe Schwierigkeiten haben und tausende von Jahren benötigen, um einen einzigen Code zu knacken, könnte eine theoretische Maschine, die auf den Gesetzen der Quantenphysik aufgebaut ist, dies in einem Bruchteil einer Sekunde lösen. Diese potenzielle Bedrohung hat Wissenschaftler dazu getrieben, den Bauplan für eine solche Maschine zu verfeinern, speziell für einen Algorithmus, der als Shor-Algorithmus bekannt ist. Die Herausforderung bestand nie darin, ob der Algorithmus in der Theorie funktioniert, sondern wie man die physische Maschinerie baut, um ihn effizient auszuführen. Der Engpass liegt in der Arithmetik: den spezifischen Schritten, die zum Multiplizieren und Dividieren von Zahlen innerhalb des Quantensystems erforderlich sind. Jahrelang erforderten die effizientesten bekannten Methoden für diese Schritte eine Anzahl von Operationen, die mit der Größe der Zahl so schnell anstieg, dass selbst die leistungsfähigsten zukünftigen Computer nicht über genügend Ressourcen verfügen könnten, um die Aufgabe auszuführen.

Ein Team von Forschern hat nun ein neues Framework vorgestellt, das darauf ausgelegt ist, diesen komplexen Designraum zu navigieren, und eine Möglichkeit bietet, schnellere, effizientere Schaltkreise zu finden, während gleichzeitig garantiert wird, dass die Mathematik korrekt bleibt. Sie nennen ihre Schöpfung ForShor, ein formal verifiziertes Harness, das sowohl als Schiedsrichter als auch als Baumeister fungiert. Anstatt Wissenschaftler zu bitten, jede mögliche Variation des Quantenschaltkreises manuell zu konstruieren – eine Aufgabe, die anfällig für menschliche Fehler ist und nicht gründlich überprüft werden kann –, haben sie ein System gebaut, in dem Forscher eine Menge von Regeln, oder eine „Policy“, einreichen können, die beschreibt, wie die Multiplikation aufzuteilen ist. Das System prüft diese Regeln dann automatisch gegen einen strengen mathematischen Standard. Wenn die Regeln bestehen, generiert das System ein vollständiges, verifiziertes Quantenprogramm und berechnet exakt, wie viele physische Komponenten, bekannt als Gates, benötigt würden, um es auszuführen. Dieser Ansatz ermöglicht eine offene Suche nach besseren Designs, bei der menschliche Experten und KI-Agenten miteinander konkurrieren können, um den effizientesten Weg zu finden, während das System gleichzeitig sicherstellt, dass der resultierende Schaltkreis mathematisch fundiert und bereit für eine reale Ressourcenabschätzung ist.

Der Kern des Problems liegt darin, wie der Algorithmus die Multiplikation handhabt. Um eine große Zahl zu faktorisieren, muss der Quantencomputer eine massive Serie von Multiplikationen durchführen. Die Forscher konzentrierten sich auf eine spezifische Technik namens rekursive Toom-Cook-Multiplikation, die wie eine hochentwickelte Form der Langdivision funktioniert. Anstatt zwei große Zahlen direkt zu multiplizieren, spaltet die Methode sie in kleinere Stücke, multipliziert diese Stücke und kombiniert die Ergebnisse dann wieder. Die Effizienz dieses Prozesses hängt vollständig davon ab, wie die Stücke unterteilt und wie die Ergebnisse wieder zusammengesetzt werden. Es gibt unzählige Möglichkeiten, diese Schritte anzuordnen, was einen riesigen Designraum schafft. Die Forscher fanden heraus, dass zwar eine exakte mathematische Methode existiert, um die absolut beste Anordnung zu finden, es aber rechnerisch unmöglich ist, diese für die Größen von Zahlen zu berechnen, die in der modernen Kryptographie verwendet werden. Die Anzahl der Möglichkeiten ist so groß, dass selbst mit den schnellsten Supercomputern die Überprüfung jeder einzelnen Option länger dauern würde als das Alter des Universums.

Um dies zu lösen, schuf das Team ein System, das die kreative Arbeit des Entwerfens des Schaltkreises von der mühseligen Arbeit der Verifizierung trennt. Ein Teilnehmer an ihrer Herausforderung reicht eine „Policy“ ein, was im Wesentlichen eine Reihe von Anweisungen ist, die dem Computer sagen, wie die Zahlen zu spalten sind und welche Operationen in jedem Schritt durchzuführen sind. Das System prüft dann, ob diese Anweisungen einer strengen Menge logischer Regeln folgen. Diese Regeln stellen sicher, dass die Schritte umkehrbar sind, dass keine Informationen verloren gehen und dass das Endergebnis mathematisch äquivalent zur beabsichtigten Multiplikation ist. Wenn die Policy diese Prüfung besteht, konstruiert das System automatisch den vollständigen Quantenschaltkreis und berechnet dessen Ressourcenaufwand. Dieser Prozess ist so formalisiert, dass kein Raum für Zweifel bleibt; das System beweist, dass jede gültige Policy ein korrektes Ergebnis liefert, unabhängig davon, wer das Design entworfen hat oder wie komplex das Design ist.

Die Ergebnisse dieses Ansatzes sind signifikant. Indem sie die Suche nach besseren Designs ermöglichen, ohne die Gefahr einzugehen, Fehler einzuführen, haben die Forscher demonstriert, dass es möglich ist, die Anzahl der für den Shor-Algorithmus erforderlichen Operationen zu reduzieren. Ihre Analyse zeigt, dass mit den richtigen Designentscheidungen die Anzahl der Operationen viel langsamer wachsen kann als bisher angenommen, nämlich von einem kubischen Wachstum hin zu etwas, das eher quadratisch ist. Das bedeutet, dass die neue Methode für sehr große Zahlen deutlich weniger Ressourcen benötigen könnte als die Standardansätze. Die Forscher weisen jedoch vorsichtig darauf hin, dass trotz der substanziellen theoretischen Verbesserungen die derzeit besten Designs immer noch eine Anzahl an physischen Komponenten erfordern, die weit über dem liegt, was die heutige Technologie bereitstellen kann. Für eine Zahl so groß wie jene, die in der aktuellen Verschlüsselung verwendet werden, schätzt das System, dass das effizienteste bekannte Design immer noch über eine Billion spezifischer Operationen, bekannt als T-Gates, benötigen würde.

Das Projekt hebt auch eine neue Art des wissenschaftlichen Arbeitens im Zeitalter der künstlichen Intelligenz hervor. Das Framework ist als offene Herausforderung konzipiert, die sowohl menschliche Forscher als auch KI-Agenten dazu einlädt, ihre eigenen Designs einzureichen. Das System fungiert als neutraler Richter, der jede Einreichung akzeptiert, die die mathematischen Kriterien erfüllt, und jene ablehnt, die es nicht erfüllen. Dies schafft ein sicheres Umfeld für Innovationen, in dem das Risiko eines fehlerhaften Designs durch die maschinell geprüfte Verifizierung eliminiert wird. Die Forscher fanden heraus, dass es selbst innerhalb eines eingeschränkten Satzes von Designentscheidungen unglaublich schwierig ist, die optimale Lösung zu finden. Sie testeten ihr System mit einem spezifischen Beispiel, das eine Zahl mit 2048 Bit umfasst, eine Größe, die häufig in der Verschlüsselung verwendet wird. Das System bestätigte, dass zwar theoretisch eine exakte optimale Lösung existiert, das Finden dieser durch Brute-Force jedoch unmöglich ist. Stattdessen ermöglicht das System heuristische Suchen, bei denen intelligente Agenten den Designraum explorieren und bessere Lösungen vorschlagen können, die dann sofort verifiziert werden.

Eine der wichtigsten Erkenntnisse ist, dass die Effizienz des Algorithmus stark von der Größe der zu faktorisierenden Zahl abhängt. Die Forscher entdeckten, dass die beste Art, die Zahlen zu spalten, sich ändert, wenn die Zahlen größer werden. Ein Design, das für eine kleine Zahl gut funktioniert, könnte für eine größere Zahl ineffizient sein. Ihr System kann dies handhaben, indem es unterschiedliche Splitting-Strategien in verschiedenen Stadien der Berechnung zulässt. Diese Flexibilität ist entscheidend, um die Grenzen des Möglichen zu verschieben. Das Team verglich ihre Ergebnisse mit früheren Methoden und stellte fest, dass ihr Ansatz einen klaren Vorteil in Bezug auf die Anzahl der erforderlichen Operationen bietet, allerdings nur für Zahlen, die deutlich größer sind als die derzeit in Gebrauch befindlichen. Für die standardmäßigen 2048-Bit-Zahlen ist die Verbesserung zwar vorhanden, aber noch nicht groß genug, um die Aufgabe mit der Technologie der nahen Zukunft realisierbar zu machen.

Die Arbeit schlägt auch die Brücke zwischen abstrakten mathematischen Beweisen und praktischem Engineering. Das System nimmt die verifizierte mathematische Beschreibung des Schaltkreises und übersetzt sie in ein Format, das von Softwaretools verwendet werden kann, die darauf ausgelegt sind, die benötigten physischen Ressourcen zu schätzen. Diese Übersetzung ist ein kritischer Schritt, da sie es Forschern ermöglicht, genau zu sehen, wie viele Qubits, oder Quantenbits, und wie viele Fehlerkorrekturkomponenten erforderlich wären, um den Algorithmus auf einer realen Maschine auszuführen. Die Forscher nutzten diese Pipeline, um detaillierte Schätzungen für verschiedene Szenarien zu generieren, und bestätigten, dass die theoretischen Verbesserungen Bestand haben, wenn sie in konkrete Ressourcenmengen übersetzt werden. Sie fanden heraus, dass die Anzahl der Operationen auf eine vorhersagbare Weise wächst und den mathematischen Mustern folgt, die sie bewiesen haben.

Trotz des Fortschritts räumen die Forscher ein, dass noch viel zu tun ist. Die aktuellen Schätzungen basieren auf idealisierten Modellen des Quantencomputers, und reale Hardware wird zusätzliche Herausforderungen mit sich bringen, wie etwa Rauschen und die Notwendigkeit der Fehlerkorrektur. Das System berücksichtigt derzeit noch nicht die physische Anordnung der Maschine oder die Zeit, die benötigt wird, um Informationen zwischen verschiedenen Teilen des Prozessors zu bewegen. Dies sind die nächsten Grenzen des Feldes. Die Fähigkeit, die Korrektheit des Algorithmus formal zu verifizieren und gleichzeitig nach dem effizientesten Design zu suchen, ist jedoch ein bedeutender Schritt nach vorn. Sie bietet ein solides Fundament, auf dem zukünftige Verbesserungen aufgebaut werden können, wobei sichergestellt wird, dass jede neue Idee gegen die höchsten Standards mathematischer Strenge geprüft wird.

Das Projekt dient als Proof of Concept für eine neue Ära des Quantum Software Engineering. Durch die Kombination von formaler Verifizierung mit offener, automatisierter Suche haben die Forscher ein Werkzeug geschaffen, das die Komplexität von Quantenalgorithmen auf eine Weise bewältigen kann, die zuvor unmöglich war. Dieser Ansatz beschleunigt nicht nur die Suche nach besseren Algorithmen, sondern schafft auch Vertrauen in die Ergebnisse, da jeder Anspruch durch einen maschinell geprüften Beweis gestützt wird. Während sich das Feld des Quantencomputings weiterentwickelt, werden Werkzeuge wie dieses essenziell sein, um den riesigen Designraum zu navigieren und theoretische Möglichkeiten in praktische Realitäten zu verwandeln. Die Forscher haben ihr Framework der Öffentlichkeit zugänglich gemacht und laden die weltweite Gemeinschaft ein, zur Suche nach dem effizientesten Weg zum Faktorisieren großer Zahlen beizutragen – eine Aufgabe, die weiterhin eine der wichtigsten Herausforderungen in diesem Bereich darstellt.

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.

Digest testen →