Warum Quantencomputer 21 noch immer nicht faktorisieren konnten

• Erläuterung, warum es seit der Faktorisierung von 15 mit einem Quantencomputer im Jahr 2001 so wirkt, als habe es keinen Fortschritt gegeben
• Eine Schaltung zur Faktorisierung von 21 benötigt 100-mal mehr verschränkende Gates als die Faktorisierung von 15
• Dieser Unterschied beruht auf der Komplexität der bedingten modularen Multiplikation und auf speziellen Optimierungen, die nur für 15 gelten
• Quantenfehlerkorrektur und Hardwaregrenzen erhöhen die Hürde zur Faktorisierung von 21 zusätzlich
• Die bisher gemeldeten Faktorisierungen von 21 beruhen meist auf Tricks, ohne eine echte Multiplikation im eigentlichen Sinn auszuführen

---

Warum Quantencomputer 21 noch immer nicht faktorisieren konnten

Warum nach der Faktorisierung von 15 keine Faktorisierung von 21 folgte

• 2001 gab es ein Experiment, bei dem 15 mit einem Quantencomputer faktorisiert wurde
• Doch selbst im Jahr 2025 gibt es noch keinen erfolgreichen Nachweis der Faktorisierung von 21
• Daraus hat sich die Wahrnehmung verbreitet, dass Quantencomputer überhaupt keine Fortschritte gemacht hätten
• Tatsächlich gibt es jedoch einen wesentlich erstaunlicheren Grund, wenn man die Schaltungen zur Faktorisierung von 15 und 21 vergleicht

Strukturelle Unterschiede zwischen den Schaltungen zur Faktorisierung von 15 und 21

• Die Schaltung zur Faktorisierung von 15 lässt sich mit nur 21 Quantengattern (21 verschränkenden Gates) realisieren
  • sie besteht aus 6 Zwei-Qubit-Verschränkungsgattern (CNOT- und CPHASE-Gates) und
  • 2 Toffoli-Gates (jeweils in 6 verschränkende Gates zerlegt), insgesamt also 21 verschränkenden Gates
• Die Schaltung zur Faktorisierung von 21 benötigt 191 CNOTs, 369 Toffoli-Gates und insgesamt 2405 verschränkende Gates
  • damit entsteht gegenüber der Faktorisierung von 15 ein 115-fach höherer Aufwand an verschränkenden Gates
  • die Schaltungsgröße steigt also nicht einfach um 25 % oder auf das Doppelte, sondern wird mehr als 100-mal teurer
• Selbst unter Berücksichtigung des Optimierungsniveaus der Schaltungen erscheint in der Praxis auch ein 500-facher Unterschied realistisch

Warum entsteht ein so großer Unterschied

• In Quanten-Faktorisierungsschaltungen (Shors Algorithmus) wird der Aufwand von der bedingten modularen Multiplikation dominiert
  • für eine n-Bit-Zahl N muss mehrfach bedingt eine modulare Multiplikation auf einem Akkumulator ausgeführt werden
  • im Fall von 15 können von 8 bedingten Multiplikationen 6 als Multiplikation mit 1 (also ohne eigentliche Operation) behandelt werden
    • die erste Multiplikation lässt sich, weil die Eingabe 1 ist, nahezu kostenlos realisieren
    • die zweite (die verbleibende weitere) lässt sich ebenfalls günstig mit zwei CSWAPs umsetzen
    • dadurch muss man effektiv nur für 2 Multiplikationen wirklich Kosten zahlen
    • diese Struktur ist eine besondere Eigenschaft von 15; weil viele Multiplikationen nahe bei 1 liegen, ist die Last deutlich geringer
• Bei 21 hingegen ist keine dieser Multiplikationen einfach 1, und die Werte sind vielfältiger, sodass jede Multiplikation Kosten verursacht
  • alle 8 Multiplikationen schlagen zu Buche; der Aufwand steigt daher nicht nur um das 4- bis 5-Fache, sondern um das 20- bis 100-Fache
  • Multiplikationen wie mit 4 oder 16 lassen sich nicht in einer Struktur per CSWAP (bedingtem Swap) realisieren
  • die Komplexität unterscheidet sich von Multiplikation zu Multiplikation, und Optimierungen sind nicht einfach

Realistische Grenzen von Hardware und Fehlerkorrektur

• Die frühere Faktorisierung von 15 (2001) wurde auf einem NMR-Quantencomputer umgesetzt, der viele Grenzen bei der Skalierung hatte
• Hinzu kommt die wachsende Notwendigkeit von Quantenfehlerkorrektur
  • wenn die Zahl der Gates um den Faktor 100 steigt, muss die Fehlerrate um den Faktor 100 niedriger sein
  • in der Praxis kann sogar die Zahl der Qubits um den Faktor 100 steigen müssen, wodurch die Gesamtkosten auf das 10.000-Fache anwachsen können

Kontroversen um Faktorisierungsversuche und fehlerhafte Ergebnisse

• In einigen neueren Arbeiten wird behauptet, dass 21 mit einem Quantencomputer faktorisiert worden sei, aber
  • tatsächlich wurde oft die Multiplikation des Algorithmus weggelassen oder die Schaltung vereinfacht, weil das Ergebnis bereits bekannt war
  • ohne echte Multiplikationsoperation kann man dies nicht als Faktorisierung bezeichnen
  • solche Ergebnisse ignorieren den grundlegenden Unterschied zwischen bloßer „Periodensuche“ und echter Faktorisierung
• Manche Arbeiten greifen dabei ganz offen zu Tricks; teils erschienen dazu sogar satirische Papers
  • darunter mehrere satirische Arbeiten wie Replikationsexperimente von Rekorden im Faktorisierungs-Championat
  • auch Benchmarks wie Variational factoring tauchen immer wieder auf, obwohl ihnen eine belastbare Grundlage für Skalierung fehlt

Was ist ein sinnvoller Indikator für echten Fortschritt bei Quantencomputern

• Zum jetzigen Zeitpunkt ist die Faktorisierung kein zentraler Benchmark für Fortschritte bei Quantencomputern
  • jenseits von 15 explodieren die Kosten so stark, dass eine praktische Verifikation schwierig wird
• Wichtiger zu beobachten sind stattdessen die Einführung von Quantenfehlerkorrektur (z. B. Verbesserungen beim surface code) oder
  • Änderungen in der Hardwarearchitektur, die Skalierungsprobleme lösen (z. B. der kontinuierliche Austausch neutraler Atome)
  • das sind die wichtigeren Punkte, an denen sich echter Fortschritt erkennen lässt

[GN⁺]

Hacker-News-Kommentare

• Das liegt daran, dass bisher noch nie tatsächlich kleinere Zahlen faktorisiert wurden. Wenn ein Programm nur dann läuft, wenn der Kompilierungsprozess die Antwort bereits kennt, dann ist das keine echte Faktorisierung, sondern nur „Gib 3 aus“

• Ich frage mich, wie viele Quantum Gates man tatsächlich braucht, um eine kryptografisch relevante Zahl zu faktorisieren. Ich würde auch gern wissen, ob es überhaupt einen realistischen Weg gibt, noch in diesem Jahrhundert einen brauchbaren Quantencomputer zu bekommen

  • Als Beispiel kann man die Schätzung aus Tabelle 5 eines Papers nennen, wonach für die Faktorisierung von 2048-Bit-RSA etwa 7 Milliarden Toffoli-Gates nötig sind (Paper-Link). Der Weg zu mehreren Milliarden Operationen ist genau die Quantenfehlerkorrektur; laut dem Paper genügt ein Surface Code mit Distance 25. Damit skaliert man von 1.400 logischen Qubits auf etwa 1 Million reale, verrauschte Qubits. Sehenswert ist auch ein Vortrag von Samuel Jacques auf der PQCrypto (YouTube). Ich bin der Autor dieses Blogs und des zugehörigen Papers
  • Diese Frage ist aus zwei Gründen schwierig. Erstens lässt sich keine klare Grenze dafür ziehen, was „kryptografisch relevant“ ist. Zweitens ist noch nicht klar bekannt, wie die Architektur eines QC aussehen wird, das diese Operation tatsächlich ausführen kann. Das ist ein bisschen so, als würde man 1985 abschätzen wollen, wie viele klassische Logikgatter nötig sind, um neuronale Netze zu bauen. Trotzdem scheint sicher, dass mehr als Millionen Gates nötig sein werden. Drittens gibt es in der Quantenfehlerkorrektur einen Trade-off zwischen niedrigeren Fehlerquoten der physischen Qubits und der Zahl der Gates, die nötig ist, um verlässliche fehlerkorrigierte virtuelle Qubits aufzubauen. Wie weit sich die Fehlerquoten physischer Qubits künftig noch senken lassen, wissen wir derzeit nicht. Wenn sich Quantencomputer ähnlich entwickeln wie Computer in den letzten 75 Jahren, dann wären bestehende kryptografische Verfahren bis etwa 2100 vollständig entwertet. Bis es eine einzelne Innovation wie den Transistor gibt, bleibt Vorhersage schwierig. Technologischer Fortschritt wirkt immer unmöglich, bis jemand den ersten Weg findet. (UNIVAC I-Beschreibung)
  • Siehe auch einen aktuellen Tweet dazu (Tweet-Link). Aus Sicht der Allgemeinheit scheint dieser Pfad hinter mehreren gewaltigen materialwissenschaftlichen Durchbrüchen verborgen zu sein
  • Für RSA 4096 braucht man grob 10^7 Qubits bei einer Fehlerrate von 10^-4. Schon mit gut 100 Qubits sind nützliche quantenchemische Berechnungen möglich, und da sich Post-Quantum-Algorithmen allmählich verbreiten, sinkt auch die Motivation, Quantencomputer zum Brechen von Kryptografie zu entwickeln. Ich denke, Quantencomputing wird sich in Richtungen ohne Bezug zu Kryptografie schneller weiterentwickeln
  • Die aktuellsten Zahlen sagen, dass man bei einer Fehlerrate von 1e-4 etwa 1 Million Qubits braucht (Paper-Link). Die Zahl der Gates wird auf Code-Ebene je nach konkreter Operation unterschiedlich gemessen, und bei einem 1-MHz-„Takt“ (Code-Zykluszeit) dauert die gesamte Berechnung etwa eine Woche. Diese Laufzeit ist ein schwierigerer Messwert als die reine Qubit-Zahl. Dank des fast magischen Effekts der Quantenfehlerkorrektur — die benötigte Qubit-Zahl sinkt drastisch, wenn die Fehlerrate weiter fällt — führt schon eine Stufe besserer Qubit-Qualität zu einem starken Rückgang der nötigen Qubits. Wenn man die Operationen dagegen auf mehrere Systeme verteilen muss, verschlechtert sich die Lage massiv

• Das Paper 'Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog' ist interessant (Paper lesen)

• Mich interessieren Schaltungsgröße und Umsetzbarkeit für die Faktorisierung kryptografisch relevanter Zahlen wie RSA1024

  • Die Kostenschätzungen für RSA1024 werden nicht durch schlichtes Hochskalieren kleiner Zahlen (etwa 4 Bit) gewonnen, sondern anhand tatsächlicher Schaltungsentwürfe für realistische Größen. Das heißt, das in diesem Beitrag erwähnte Diskontinuitätsproblem ist darin bereits implizit berücksichtigt. Dieser Post hat daher keinen Einfluss auf bestehende Kostenschätzungen
  • (Nebenbei: Die Optimierung der Schaltung zur Faktorisierung von 21 wird sich bei großen Zahlen kaum anwenden lassen. Im Vergleich zur Schaltung für die Faktorisierung von 15 könnte ein 500-facher Kostenfaktor realistischer sein. Natürlich reicht auch ein 100-facher Overhead aus, um den Punkt zu illustrieren. Besonderer Dank an Noah Shutty, der für diese Schaltungsoptimierung eine teure Computersuche durchgeführt hat)
  • Das geht leicht am Thema vorbei, aber mich würde interessieren, ob Kryptografen wirklich sicher sind, dass selbst riesige moderne Rechenzentren RSA1024 praktisch nicht faktorisieren können. Nach aktuellem Stand kann selbst der schnellste Algorithmus das nicht in realistischer Zeit. Mich würde aber interessieren, ob Konsens darüber besteht, dass es in naher Zukunft keine revolutionäre Verbesserung dieses Algorithmus geben wird

• Ich frage mich, ob Quantencomputer irgendwann auf Post-Quantum RSA zielen könnten (relevantes Paper). Da gewöhnliche RSA-Operationen (Schlüsselerzeugung, Verschlüsselung, Entschlüsselung) gegenüber dem Shor-Algorithmus asymmetrisch im Vorteil sind, gibt es auch die Ansicht, dass einfach nur ausreichend große Schlüssel nötig seien. Das hätte einen ähnlichen Effekt wie Merkle-Puzzles, nur mit der zusätzlichen Bedingung, dass der Angreifer zwingend mit einem Quantencomputer angreifen muss. Ich habe früher einmal einen Gigabit-RSA-Public-Key erstellt (Schlüsseldatei). Das Format ist: 4 Byte Little-Endian für die Byte-Zahl des Schlüssels, dann der Schlüssel selbst und danach sein Inverses (mod 256^bytes). Der öffentliche Exponent ist 3

  • Post-Quantum RSA ist ein Witz von djb als Antwort auf die Frage „Ist es nicht sicher, wenn man einfach große Schlüssel benutzt?“. Es ist so gebaut, dass eine einzelne Verschlüsselung mit einem 1-TB-Schlüssel 100 Stunden dauert. Auch mit einem Quantencomputer ist das nicht zu knacken

• Ich fand den Tippfehler „error corection“ ziemlich lustig

• Ich finde die Stelle „500-fache Schaltungskosten im Vergleich zu factor-15“ schwer nachzuvollziehen. Der Autor hat doch schon ein Beispiel mit dem Faktor 115 gezeigt; ich frage mich, wie zusätzliche Optimierung zu einem schlechteren Ergebnis führen kann

  • Das bedeutet, dass der enorme Optimierungsaufwand, der in Schaltungen zur Faktorisierung kleiner Zahlen gesteckt wurde, bei großen Zahlen praktisch nicht mehr möglich ist. Intuitiv heißt das: Im Allgemeinen braucht man beim Übergang zu größeren zu faktorisierenden Zahlen eher eine etwa 500-fache Erhöhung der Gate-Zahl und nicht nur etwas wie das 115-Fache
  • In wirklich großem Maßstab wird der Optimierungseffekt kleiner sein, und die Vorteile einer Schaltung wie für N=21 werden nicht so groß ausfallen
  • Eine Minimalimplementierung ist instabil und schwer zuverlässig zu machen. Für die Entwicklung praktischer Schaltungen ist viel Forschung nötig, um stabile Qubits zu erhalten; dabei fallen auch Begriffe wie „Dekohärenzzeit“. Daher muss die Zahl der Qubits zwangsläufig explodieren
  • Das 115-Fache ist das Ergebnis von viel (unrealistischer) Optimierung

• Ich frage mich, ob der Kern dieses Beitrags andeuten soll, dass der Big-O-Schaltungsbedarf für Schorrs Faktorisierung superpolynomiell ist

  • Dem Inhalt nach entstehen die Gate-Kosten hauptsächlich durch O(n) modulare Multiplikationen, und jede dieser Operationen kann mit O(n^2) Gates implementiert werden. Insgesamt scheint das also selbst im schlechtesten Fall ungefähr kubische Komplexität zu sein

• Der Grund für die Einführung von PQ-Post-Quantum-Kryptografie ist nicht unbedingt die feste Überzeugung, dass QC unmittelbar bevorsteht. Wann QC kommt, ist je nach Entwicklungsgeschwindigkeit der Technik ungewiss. Das Ziel der Kryptografie ist es, Verfahren zu finden, die selbst theoretisch kaum brechbar sind; wenn ein Angriff theoretisch möglich ist, dann ist er prinzipiell auch physikalisch möglich, und deshalb bereitet man sich darauf vor. Für ECC und RSA ist ein theoretischer Angriffsweg bereits bekannt, deshalb gelten sie als angreifbar, auch wenn die real existierende Hardware dafür noch fehlt. Es ist daher völlig vernünftig, sich schon vor dem Vorhandensein von QC darauf vorzubereiten. Bei SHA2, AES, ChaCha usw. gibt es dagegen keinen realistischen Angriffsweg, deshalb gibt es aktuell keinen unmittelbaren Ersatzplan. Kryptografie ist nicht die einzige oder wichtigste mögliche Anwendung von QC. Man hofft, dass in Bereichen wie physikalischen Systemen, Proteinfaltung oder Machine Learning noch unbekannte Durchbrüche möglich sind

  • Ich frage mich, ob es in Bereichen wie Proteinfaltung künftig noch mehr Fortschrittspotenzial gibt (auch nach AlphaFold). (Referenzartikel)

  • Bei symmetrischer Kryptografie (AES, ChaCha, SHA-2) bedeutet ein Quantenangriff praktisch eine Halbierung der effektiven Schlüssellänge, ähnlich wie bei 3DES und 2DES. In der Praxis kann man nicht einfach von einer exakten Halbierung ausgehen, weil reale Quantencomputer nicht unbedingt in Leistung vergleichbar oder identisch sind, aber ein Wechsel zu AES-256 löst das Problem. Der eigentliche Fokus sollte aber auf Key Exchange liegen. Der Grund ist, dass Key Exchange dazu dient, einen geheimen Schlüssel zu vereinbaren, ohne dass beide Seiten ihn direkt offenlegen. Mit einem Quantum Computer lassen sich dann auch in der Vergangenheit aufgezeichnete Gespräche nachträglich lesen. Wenn man nur ein Signaturalgorithmus bricht, kann man nicht in die Vergangenheit reisen und nachträglich signieren; wenn aber Key Exchange einmal fällt, werden auch vergangene Unterhaltungen offengelegt. Deshalb ist ein sicherer Ersatz für Key Exchange dringend nötig