nicht angemeldet
Hallo Sven,
Und mit der Simulation eines Quantencomputers geht's eben auch nicht in polynomialer Zeit, sondern nur in exponentieller.
Ja, aber der exponentielle Aufwand entsteht gerade bei der Simulation, weil Du zur Darstellung eines Q-Bits exponentiell viele Bits benötigst. (Exponentiell in der Anzahl der darauf ausgeführten Operationen).
Wie gesagt kann man mit Quantenkomputern nichts neues berechnen, daher kann man sie auch simulieren. Die Simulation aber ist extrem aufwendig.
Sagen Dir Nicht-Deterministische Maschinen etwas? Mit denen kann man z.B. alle NP-Vollständingen Probleme in Polynomialzeit lösen. Man kann diese Maschinen auch simulieren, aber diese Simulation benötigt dann wieder exponentiellen Aufwand. (Jedenfalls wie bei all diesen Dingen nach bisherigem Kenntnisstand, es ist ja durchaus möglich, dass es schnelle deterministische Algorithmen gibt.)
Quantencomputer stellen so eine Art abgeschwächten Nichtdeterminismus zur Verfügung.
Der Wikipedia-Artikel schreibt, dass man beispielsweise ein 8-Qubit-System mit allen 256 8-Bitkombinationen aufladen und damit dann eine Rechenoperation durchführen kann, die am Ende alle 256 Ergebnisse enthält.
Das ist wohl eine sehr vereinfachende Vorstellung. In der Praxis ist es wohl sehr schwierig, aus diesen Ergebnissen dann eines herauszubekommen, dass man haben will.
Wenn man einen Quantenzustand misst, bekommt man ja prinzipiell erst mal einen der möglichen Zustände zufällig. Wenn nun eines der exponentiell vielen Ergebnisse die Lösung ist, die man haben will, bekommt man die da so ohne weiteres nicht raus.
Natürlich muß man das erstmal quantenkompatibel bauen, aber der Beschleunigungseffekt wird doch recht deutlich. Und ich glaube kaum, dass soetwas nicht irgendwann Wahrheit werden kann.
Nun, das ist eben nicht so sicher. Quantencomputer sind ein weiterer Ansatz um solche Probleme zu lösen. Ob und für welche Probleme das Funktionieren wird ist aber meines Wissens kaum absehbar.
Und wenn es tatsächlich gelingt, Quantencomputer zu bauen und einen entsprechenden Algorithmus für ein Verschlüsselungsverfahren zu finden, dann kann man das Verfahren wegwerfen. Dann ist Knacken nämlich vergleichbar schnell wie Verschlüsseln. Es ist also nicht wie bei schnelleren Rechnern, dass man einfach die Schlüssellänge verdoppeln kann oder so.
Grüße
Daniel