Quantencomputing wird in Diskussionen immer herangezogen, wenn Public-Key-Systeme wie RSA zu brechen sind. Die laufen klassischen Computern zeitlich exponentiell davon, Quantencomputern aber nur polynomial (Shor-Algorithmus). Ergo, so die Schlussfolgerung, seien heutige Public-Key-Systeme überholt, sobald es Quantencomputer gibt. Ich schätze, das stimmt nicht. Enfaches Rechenbeispiel: RSA läuft heute mit 2.048 - 4.192 Bit. Nehmen wir die letzte Größe, so benötigt ein Rechenregister 8.192 Bit zum Berechnen aller Größen. Ein Quantencomputer benötigt davon drei Stück, um den Shor-Algorithmus auszuführen, macht ca. 24.000 Qbit. Ohne Korrektur kommt man vermutlich nicht weiter, ergibt für Bit- und Phasenflips den Faktor 9 und somit ca. 220.000 Qbit. Das wäre dann die erste Hürde, die zu nehmen wäre (heute beglaubigte Breite ca. 8-10 Qbit), und RSA könnte man problemlos auf 32 kBit oder höher aufsatteln. Sodann läuft eine modulare Exponentiation auf Quantenrechnern etwa proportional n⁴ (vielleicht lässt sich da noch was drehen im Austausch gegen mehr Quantenbits), bezogen auf den RSA-Modul. Die Obergrenze der Operationenanzahl liegt aufgrund der Dekohärenz aber bei ca. 10¹³. Damit kämen die Quantencomputer aber noch nicht einmal mit den heutigen RSA-Moduln klar. Selbst wenn sich hier in der Zukunft noch einiges ändert, spricht doch derzeit eine ganze Menge dafür, dass Quantenrechner ebenfalls nicht skalierbar sind. RSA läuft Quantencomputern zwar nicht zeitlich, aber bezüglich der Operationenanzahl davon. -- Gbrands 09:12, 15. Jan. 2011 (CET)