Hallo LeKuchen,
Das ist imho nicht viel. Dann wird die Leistung der Computer bald stagnieren?
Nein, ich denke nicht. Die Rechner werden ja nicht in erster Linie durch fundamentale Entdeckungen schneller, sondern dadurch, dass man immer kleinere Schaltelemente und damit immer komplexere Schaltungen bauen kann. In diesem Bereich tut sich ja immer wieder etwas.
Die Leistungsverbesserungen durch einen Quantencomputer wären allerdings ganz anderer Art. Die ersten Quantencomputer wenn es sie denn gibt werden vermutlich viel langsamer addieren oder multiplizieren können, als ein herkömmlicher Rechner.
Der Unterschied ist, dass herkömmliche Rechner deterministisch Rechnen. Es gibt also in jedem Zustand genau einen Folgezustand. Bei nicht-deterministischem Rechnen kann es mehrere mögliche Folgezustände geben. Dadurch kann man Lösung quasi raten und braucht dann nur noch nachzuprüfen, ob es eine Lösung ist.
Bei einer Verbesserung herkömmlicher Rechner braucht man hinterher z.B. nur noch 1/100 der Zeit, weil man eben 100 mal so viele Operationen pro Sekunde ausführen kann.
Bei einem Quantenrechner kann man aber manche Probleme z.B. in nur in log(s) Schritten lösen.
Der besagte Algorithmus zur Faktorisierung einer Zahl arbeitet z.b. in O((log z)^3) wobei n die zu faktorisierende Zahl ist. also in O(n^3) wenn n die Anzahl der Stellen ist.
Alle bekannten Algorithmen für herkömmliche Rechner arbeiten dagegen in O(2^n). Einige sind etwas besser, für große Zahlen ist das Problem aber trozdem unlösbar.
O(f(x)) heißt, dass k * f(x) + c Schritte benötigt werden, wobei k und c beliebige Konstanten sind.
Grüße
Daniel