Wie genau funktioniert die Primfaktorzerlegung bei Quantencomputern?

[Brotbüchse aus Blech]

Überall wird immer behauptet, daß Quantencomputer das Ende klassischer Verschlüsselungsverfahren bringen. Nur wie.

Ein Quantencomputer stellt quasi alle möglichen Ergebnisse gleichzeitig dar (Katze tot _und_ Katze lebt). Will ich ein Ergebnis ablesen, muß ein Filter angewendet werden, der für jede Quante ;-) festlegt, was ich erwarte zu sehen. Damit müßte ich doch aber schon die zwei gesuchten Primzahlen vorgeben, die dann als Ergebnis rausfallen sollen? Oder läßt sich bei jeder einzelnen Messung feststellen, ob mein Filter falsch oder richtig war?

[cyblord]

Brotbüchse aus Blech schrieb:
--------------------------------------------------------------------------------
> Überall wird immer behauptet, daß Quantencomputer das Ende klassischer
> Verschlüsselungsverfahren bringen. Nur wie.
>
> Ein Quantencomputer stellt quasi alle möglichen Ergebnisse gleichzeitig dar
> (Katze tot _und_ Katze lebt). Will ich ein Ergebnis ablesen, muß ein Filter
> angewendet werden, der für jede Quante ;-) festlegt, was ich erwarte zu
> sehen. Damit müßte ich doch aber schon die zwei gesuchten Primzahlen
> vorgeben, die dann als Ergebnis rausfallen sollen? Oder läßt sich bei jeder
> einzelnen Messung feststellen, ob mein Filter falsch oder richtig war?

Es funktioniert aktuell gar nicht. man ist froh wenn man ein paar QuBits überhaupt gebändigt bekommt. Von irgendeiner sinnvollen Nutzung spricht nur, wer keine Ahnung hat oder Aufmerksamkeit heischen, oder einen Artikel bei Golem schreiben will.

Quatencomputer sind heute vor allem ein tolles Buzzword. Damit kann man theoretisch so viel machen wie auf eine PowerPoint Folie geht und die eigene Phantasie zu lässt.

[oll72]

Wie der Autor im Artikel schon erwähnte beruht die Primfaktorzerlegung auf dem Quantencomputer auf Shors-Algorithmus. Er funktioniert tatsächlich, man hat ihn immerhin schon mit einem 4 Bit Quantencomputer erfolgreich testen können. (Siehe https://de.wikipedia.org/wiki/Shor-Algorithmus) Aber um ehrlich zu sein, man muss schon verdammt fit in Mathe sein, um den wirklich zu verstehen.

Da wird einiges klassisch berechnet ehe die Quanten-Fourier-Transformation zum Einsatz kommt, welche einem dann auch nur mit einer gewissen Wahrscheinlichkeit eine Antwort liefert, so dass das Verfahren mehrfach angewendet werden muss und am Ende muss man den Faktor dann noch klassisch verifizieren, aber trotz allem bleibt der Rechenaufwand eben VIEL kleiner wie für klassische Algorithmen...

Der Quantencomputer benötigt für das Zerlegen einer Zahl n in seine Primfaktoren mindestens log(n) Quantenbits. Da die Größe des Schlüssels heutzutage aber meist per Bit-Länge des Schlüssels angegeben wird, also etwa RSA 2048, hat man somit die Mindestzahl an QBits eines Rechners, der dies knacken will, gleich mitgeliefert - eben rund 2048 QBits. Aktuell klappt aber selbst im Labor kaum das Verschränken von mehr als 20 QBits, das dauert also noch ein wenig...