Verschlüsselung im Quantenrechnerzeitalter

[Mark]

Man könnte auch sagen : ein Quantencomputer ist begrenzt durch die Geschwindigkeit mit der Informationen übertragen werden können ?
Damit wird die Übertragung der Daten zur eigentlichen Aufgabe, denn Berechnungen sind im dem Moment schon beendet in dem die Daten als Quantenzustände in den Speicher eines "Quantenprogrammes" angekommen sind.

Komplexitätstheorie hatte ich leider nie, haben wohl nur die theoretischen Informatiker

[Klaus]

Man könnte auch sagen : ein Quantencomputer ist begrenzt durch die Geschwindigkeit mit der Informationen übertragen werden können ?

Nein. Bei verschränkten Quantenteilchen ist die Information sofort da. Sind die Teilchen verschränkt und der Spin-Zustand eines Teilchens wird verändert, ist beim anderen Teilchen die Zustandsänderung sofort da. Das Problem ist die Messung der Zustände. Die Art der Messung entscheidet, ob das Photon als Teilchen agiert oder als Welle zur Interferenz führt. Verschränkte Quantenobjekte widersprechen dem lokalen Realismus: Ihre Eigenschaften sind vor einer Messung nicht eindeutig definiert und danach stärker korreliert, als dies durch eine klassische Wechselwirkung erklärbar wäre.

Gute Ansätze für Quantencomputer bietet die Technik der Quanten-Teleportation. Mittels Teleporation können Quanteninformationen zwischen Quantenprozessoren übertragen werden. Das schwierigste wird sein, die Quanten unterscheidbar zu machen, so dass man genaue Zustandsanalysen machen kann.

Kurz zur Teleportation, sie ist nur auf Quantenebene nachgewiesen, bei sehr kleinen Teilen also Elektronen oder Photonen. Leichter als Verschränkung oder Teleportation lässt sich die Quanteninterferenz erzeugen, die mit sogenannten Fullerenen, Hohlkügelchen auch 60 Kohlenstoffatomen, schon nachgewiesen wurde.
Ein weiteres Problem ist die Bell-Zustandsmessung. Eine komplette Bell-Zustandsmessung, die zum Teleportieren notwendig ist, ist bereits ein rudimentäre Form der Zwei-Qubit-Verarbeitung.
Würde man sie an einem Virus durchführen, der aus rund 10hoch7 Atomen besteht, gewinnen wir 10hoch8, oder mehr, Bits an Informationen. Nehmen wir ein Objekt aus wenigen Gramm, werden die Zahlen ungeheuerlich, mindestens 10hoch24 Bits an Daten.

[smalonius]

Ich verstehe nix von Quantencomputern.

Für mich klingt das, was ich über Quantencomputer höre, danach, als könnte man damit P != NP aushebeln.

Und das glaube ich nicht. Habe ich einen Denkfehler?

[Klaus]

Du hast keinen Denkfehler. Es gibt momentan keinen effizienten Algorithmus der ein NP-vollständiges Problem effizient lösen kann.
Mit Quantencomputern, wenn es sie denn gäbe könnte man heute effizient P-Probleme und BQP lösen. BQP=bounded-error quantum polynomial time.

Die effiziente Lösung von Sudoku wäre ein NP-vollständiges Problem. Als Lösung ist hier gemeint alle in Frage kommenden Lösungen.
BQP Probleme sind Bestandteil der Klasse PSPACE. Das sind solche Probleme, die ein herkömmlicher Computer mit einer polynomialen Menge an Speicher, aber möglichweise nur mit exponentiellem Aufwand bewältigt (Schach, Go z.B.)

Die Stärke von Quantencomputern käme eben in den Berechnungen zur Quantenmechanik, der theoretischen Physik, Chemie und Nanotechnik zum tragen. Die Quanteninformatik selbst ist ein starker Prüfstein für die QM.

[smalonius]

OK, dann bin ich erstmal beruhigt.

[Mark]

Man könnte auch sagen : ein Quantencomputer ist begrenzt durch die Geschwindigkeit mit der Informationen übertragen werden können ?

Nein. Bei verschränkten Quantenteilchen ist die Information sofort da.

Aber diese müssen erstmal verchränkt werden und dann örtlich getrennt. Und dann kann jedes Paar nur eine binäre Information übertragen, und das wars. Wie will man das nutzen um Informationen schnell in grossen Mengen zu übertragen ?

[Gandalf]

Wie will man das nutzen um Informationen schnell in grossen Mengen zu übertragen ?

Na, - ganz einfach: Indem man 'natürliche Quantencomputer' nutzt, die allgegenwärtig sind. Man beobachtet z.B. Wetter(quanten)systeme (= fragt diese ab) und schließt darauf, wie das Wetter morgen wird

[Klaus]

Und dann kann jedes Paar nur eine binäre Information übertragen,...

Wir sprechen in der Quantenmechanik von Quanten-Bits oder einfacher von Qubits. Zu den bekannten Zuständen aus deiner "lieblichen" binären Welt, existieren die Qubits als Superpositionen von Nullen und Einsen. Das heisst, einfach gesagt, ein Qubit kann alle möglichen Positionen zwischen 0 und 1 einnehmen. Das Messergebniss kann nach den Gesetzen der Quantenmechanik nur binär sein, dass ist richtig. Das heißt aber auch, dein Ergebnis ist eben wesentlich schneller da. Die Wahrscheinlichkeit des "binären" Resultats hängt dann noch von der "geografischen Breite" des Qubits ab.

Nur ein Beispiel: Gesucht seien die Rechenschritte, die erforderlich sind, um die Primfaktoren einer 300-stelligen Zahl zu finden.
Der beste, momentane klassische Algorithmus würde dafür 5mal10hoch24 Rechenschritte benötigen, oder mit einer Terahertz-Geschwindigkeit 10hoch12 Schritte pro Sekunde, dass sind rund 150.000 Jahre. Ein Quanten-Algorithmus könnte eine Superposition unzähliger Quantenzustände nutzen und würde nur 5mal10hoch10 Schritte benötigen, oder bei der o.g. Geschwindigkeit weniger als eine Sekunde.