Sind Quantencomputer überflüssig?

Faszinierend ist die Idee eines Quantencomputers und vermutlich steht in jedem Forschungsantrag die Anwendung des Shor-Algorithmus. Da wichtige Verschlüsselungsverfahren auf dem exponentiellen Aufwand bei der Primfaktorenzerlegung (im Bezug auf die Länge der Primzahl) beruhen, hätte der Shor- Algorithmus, der nur auf einem Quantencomputer funktioniert, weitreichende Konsequenzen. Er beschleunigt das Verfahren enorm, da der Aufwand „nur“ noch mit der Länge der Primzahl hoch drei steigen würde.

Ein neuer Beweis von Vladimir Romanov zeigt jetzt aber,  dass man auch ohne Quantencomputer den Aufwand deutlich reduzieren kann (mindestens bis auf Länge der Primzahl hoch zehn). Der Beweis ist noch nicht in einem Journal mit Peer-Review erschienen, aber man sollte schon mal drüber nachdenken, die Forschungsanträge umzuformulieren! Der Beweis zeigt sogar noch mehr: es gibt keine Probleme, die einen exponentiellen Aufwand erfordern. Er löst nämlich das 3-SAT Problem in polynomialer Zeit.

Glücklicherweise ist der Beweis physikerfreundlich! Es wird eine Implementierung des Verfahrens angeboten, so dass man ohne den Beweis auch nur angeschaut zu haben, Messungen zum Aufwand durchführen kann.

Hierzu erzeugt man aus der Primzahl zunächst ein Problem, das die Implementierung versteht, dann misst man die Zeit, die zur Lösung benötigt wird.

b: Länge der zu zerlegenden Zahl in Bits

In Klammern: die Zahl

n (im Original Artikel definiert) m (im Original Artikel definiert) m*n4, der Aufwand der im Beweis bewiesen wurde Rechenzeit in ms Aufwand / Rechenzeit
4 (15) 12 36 746496 2111 354
5 (21) 22 73 17100688 2569 6657
7 (35) 52 187 1367272192 21618 63247
8 (63) 68 248 5302581248 45642 116178
10 (91) 116 434 78581748224 3300730 23807
11 (143) 138 519 188227772784 8688040 21665
13 (299) 204 777 1345679661312 73877183 18215
14 (899) 232 888 2566762356736 111720846 22795

Bei den größeren Zahlen bleibt die letzte Spalte bei ungefähr 20000 konstant. Das Verhalten des Aufwands wird also durch die im Artikel angegebene Formel m*n4 beschrieben. Da sowohl n als auch m bei der Problemerzeugung  quadratisch mit der Länge der zu zerlegenden Zahl wachsen, ist der gesamte Aufwand b10

Der Vergleich des general number field sieve (GNFS) Algorithmus mit diesem Aufwand zeigt,
dass er erst bei sehr großen Zahlen konkurrenzfähig wird:Vergleich mit GNFS Algorithmus