Quantencomputer

[Enas Yorl]

Einen leicht verständlichen Artikel zur Arbeitsweise eines Quantencomputer findet ihr hier. Mit einer Umsetzung des Quantencomputers im heimischen PC, wäre ich nicht ganz so Optimistisch. Gerade die Abschirmung nach Außen, um die empfindlichen Quantenzustände nicht ungewollt zu zerstören. Könnte für die Heimanwendung etwas zu aufwendig sein. Nebenbei bringt ein QC nur bei der Lösung einer ganz bestimmten Art von Algorithmen einen recht beachtlichen Geschwindigkeitsvorteil. Bei ganz normalen Additionen oder den Abarbeiten von Befehlssätzen (die Mehrzahl der an PC ausgeführten Rechenoperationen) bringt seine Funktionsweise keine Vorteile.
Außerdem glaube ich, wenn die ersten komplexen QC in zehn bis zwanzig Jahren verfügbar sind. Dürften konventionelle Prozessoren genügend Rechenpower mitbringen, um den Heimanwender ausreichend zufrieden zu stellen.

[McWire]

Jetzt nehmen wir einfach mal an, ich hätte zwei sehr große Primzahlen. Und die multiplizier ich jetzt. Und geb dir das Produkt (einfaches Beispiel: 8458523). Wie machst du jetzt eine Primfaktorzerlegung?

Und jetzt sag nicht: "Durchprobieren."

Das Problem momentan ist halt, dass viele gängige Verschlüsslungsverfahren darauf aufbauen, dass es "schwer" ist, so eine Primfaktorzerlegung zu machen.
Wenn das auf einmal "einfach" wird, durch Quantencomputer, dann muss man sich etwas neues ausdenken. Ich schwör ja auf One-Time-Pads, die sind auf Dauer aber unpraktisch.

Durchprobieren ist im Prinzip nur einmalig nötig, da man ja für später jede Primfaktorzerlegung in eine Datenbank speichern könnte und im Wiederholungsfalle sie dann einfach hervorzaubern kann.

Ausserdem muss man nichtmal alle Primzahlen ausprobieren sondern nur Quadratwurzel(Primzahlprodukt)-viele.
Ist das Produkt also 100-stellig würden es reichen ~ 10^50 Primzahlen durchzuprobieren.

[Pyromancer]

Durchprobieren ist im Prinzip nur einmalig nötig, da man ja für später jede Primfaktorzerlegung in eine Datenbank speichern könnte und im Wiederholungsfalle sie dann einfach hervorzaubern kann.

Eine Datenbank mit den Primfaktorzerlegungen von allen Zahlen zwischen 1 und 10^1000. Das ist so einfach, warum ist da noch niemand draufgekommen? Damit sind ja sämtliche gängigen asymmetrischen Verschlüsselungsverfahren kompromitiert!

[TheJoker]

Eine Datenbank mit den Primfaktorzerlegungen von allen Zahlen zwischen 1 und 10^1000. Das ist so einfach, warum ist da noch niemand draufgekommen? Damit sind ja sämtliche gängigen asymmetrischen Verschlüsselungsverfahren kompromitiert!

aus Zeitmangel nur kurz: google mal nach Rainbow-Tables und Salt.

[McWire]

aus Zeitmangel nur kurz: google mal nach Rainbow-Tables und Salt.

So eine Datenbank anzulegen geht genauso schnell wie die systematische Suche nach der Primfaktorzerlegung einer einzelnen 1000-stelligen Zahl!

Im Prinzip braucht man nur anzufangen Primzahlen zu ermitteln und diese miteinander zu Multiplizieren und das Ergebnis samt Ausgangsprimzahlen zu notieren.
Da man um eine bestimmte Primzzahl herauszufinden, eh beim ersten mal alle anderen Primzahlen durchprobieren muss, wäre es äußerst klug sich die Zwischenergebnisse einfach zu notieren.
Eine Datenbank nach passenden Zahlen zu durchsuchen ist dann eine Sache von paar Sekunden.

[Taschenmogul]

Zum konkreten Nutzen von Quantenrechnern:
Ich denke schon, daß sich da einiges finden ließe.
Ohne mich jetzt mit Mathe auszukennen (nur das Nötigste...), würde ich spontan schätzen, daß sich u.A. Datenbank-Applikationen ebenso beschleunigen ließen, wie Mustererkennung oder eben auch Grafikberechnung.
Das hieße dann vielleicht sowas wie Durchsuchen von Datenbanken in Null komma Nix, aber auch zuverlässige Stimm- und Gesichtserkennung und Echtzeit-Raytracing/-Radiosityrendering.


Zur Verfügbarkeit:
Natürlich werden die kommen.
Niemand wird sich diese große Chance entgehen lassen, auch wenn die Implikationen problematisch sein könnten; waren sie bei der Atombombe ja auch.
Vor allem bringt es aber auch die Computer-/Datensicherheit nicht voran, zu versuchen, Quantenrechner zu verbieten.
Notfalls würden halt Geheimorganisationen (Militär, Geheimdienste, etc.) im Verborgenen daran forschen, nur daß dann ein Ungleichgewicht der Kräfte herrschen würde.
Das einzig Sinnvolle wäre also, Quantenrechner allgemein verfügbar zu machen, und sich eben neue Verschlüsselungstechnologien auszudenken; woran dann ja auch alle interessiert wären.
Sicherheit durch Geheimhaltung spielt, wie z.B. der CCC oder diverse Computersicherheitsfachleute immer wieder gerne zeigen, letztlich nur denen in die Hände, die gewitzt, skrupellos und vermögend genug sind, um die Geheimnisse doch herauszufinden.
Während der große Rest dann zur leichten Beute wird.

[Enas Yorl]

Zum konkreten Nutzen von Quantenrechnern:
Ich denke schon, daß sich da einiges finden ließe.
Ohne mich jetzt mit Mathe auszukennen (nur das Nötigste...), würde ich spontan schätzen, daß sich u.A. Datenbank-Applikationen ebenso beschleunigen ließen, wie Mustererkennung oder eben auch Grafikberechnung.
Das hieße dann vielleicht sowas wie Durchsuchen von Datenbanken in Null komma Nix, aber auch zuverlässige Stimm- und Gesichtserkennung und Echtzeit-Raytracing/-Radiosityrendering.

Sag mal, hast du dich mit der Funktionsweise von Quantencomputern überhaupt beschäftigt? Oder spekulierst du nur ins Blaue hinein?

[blueflash]

hmm.. und woher kommt diese Annahme?

Nun, es gibt mittlerweile eine ganze Reihe von Algorithmen, die bestimmte Aufgaben in geringerer Laufzeit lösen können. Wenn nun mehr dieser Algorithmen erforscht werden (was mit Sicherheit passieren wird) und Quantencomputer tatsächlich gebaut werden, dann liegt es nahe, davon auszugehen, dass eine Kombination dieser Algorithmen eine universale Turingmaschine simulieren kann und dies dann eventuell in O(log(n)) oder so.

[Taschenmogul]

@Yorl: So halb/ halb. ;-)
Kann aber wie gesagt auch sein, daß ich´s net richtig verstanden habe; Mathe ist nicht so meine größte Stärke.
Anstatt mit einer zwei Satz Antwort abzukanzeln... könntest du vielleicht einfach schreiben, was deiner Meinung nach denn an meiner Spekulation so falsch bzw. undenkbar ist?

[Phoenow]

Nun, es gibt mittlerweile eine ganze Reihe von Algorithmen, die bestimmte Aufgaben in geringerer Laufzeit lösen können. Wenn nun mehr dieser Algorithmen erforscht werden (was mit Sicherheit passieren wird) und Quantencomputer tatsächlich gebaut werden, dann liegt es nahe, davon auszugehen, dass eine Kombination dieser Algorithmen eine universale Turingmaschine simulieren kann und dies dann eventuell in O(log(n)) oder so.

Aha, nun sind diese Algorithmen spweit ich das mitbekommen habe doch auf sehr spezielle Aufgaben beschränkt, während die Turingmachine ja ein universelles Konzept ist. Ich weiß nicht ob sich das so einfach übertragen lässt.

[Pyromancer]

In Japan haben sie einen Quantencomputer gebaut, der braucht für die Endlos-Schleife weniger als 4 Sekunden.

[The Guardian]

Also Quantencomputer sind mir wahrscheinlich zu hoch. Die versteh ick nich.

[BongoMercury]

In Japan haben sie einen Quantencomputer gebaut, der braucht für die Endlos-Schleife weniger als 4 Sekunden.

Vielleicht ist mir das jetzt ebenfalls zu hoch. Was hat ein Video mit Rick Astley damit zu tun?

[Harmakhis]

Vielleicht ist mir das jetzt ebenfalls zu hoch. Was hat ein Video mit Rick Astley damit zu tun?

Such mal "Rickroll'd" oder "Rickrolling" bei Google bzw. Wikipedia - dann sollte sich die Sache aufklären.

Rick Astley hat gar nichts damit zu tun. Das ist der Punkt.

[Enas Yorl]

@Yorl: So halb/ halb. ;-)
Kann aber wie gesagt auch sein, daß ich´s net richtig verstanden habe; Mathe ist nicht so meine größte Stärke.
Anstatt mit einer zwei Satz Antwort abzukanzeln... könntest du vielleicht einfach schreiben, was deiner Meinung nach denn an meiner Spekulation so falsch bzw. undenkbar ist?

Nun eigentlich müsstest du erst mal deine Spekulationen begründen, aber ich will mal nicht so sein. Als erstes ein Quantencomputer rechnet nicht schneller als konventionelle Computer. Er kann allerdings alle Lösungsmöglichkeiten einer ganz bestimmten Art von Algorithmus gleichzeitig ausprobieren, das war es dann aber schon auch. Bei einfachen Rechenaufgaben, wo der Lösungsweg bekannt ist bringt dies keine Vorteile.
Nun zu den von dir angesprochenen Anwendungsgebieten:

1. Das durchsuchen von Datenbanken in Null komma Nix.

Der eigentliche Flaschenhals einer Datenbanksuche ist die Durchsatzrate der Speichermedien, nicht der Prozessor. Da hilft in der Regel ein guter Index weiter. Wie schon erwähnt verarbeitet ein QC Daten nicht schneller, was soll der also bringen.

2. zuverlässige Stimm- und Gesichtserkennung

Auch da liegen die Probleme nicht beim Prozessor, unter Laborbedingungen funktionieren solche Systeme heutzutage recht zuverlässig. Und genau da liegt auch der Hund begraben, in "freier Wildbahn" haben es diese Systeme mit widrigen Bedingungen zu tun. Wie: schlecht platzierte oder ungenügende Sensoren, Störfaktoren (Lärm, schlechte Beleuchtung oder Blendlicht) oder gar einem Zielobjekt das nicht kooperiert.

3. Echtzeit-Raytracing/-Radiosityrendering

Weißt du eigentlich was das ist? Raytraycing ist ein auf der Aussendung von Strahlen basierender Algorithmus zur Verdeckungsberechnung, also zur Ermittlung der Sichtbarkeit von dreidimensionalen Objekten von einem bestimmten Punkt im Raum aus. Da kannst du nicht einfach einen Algorithmus in den QC eingeben und schon rechnet der das komplette Bild aus. Nein!!! Ein QC müsste genauso alle Rechenschritte durcharbeiten wie ein konventioneller Prozessor. Für jedes einzelne Pixel sind andere Parameter vorhanden, welche auch eine eigene Berechnung notwendig macht.

Hey, ich bin keineswegs gegen den Einsatz von Quantencomputern. Aber man sollte sich schon klar darüber sein, das sie keine alleskönnenden Wundermaschinen sind.