A4/Ein Quanten-Algorithmus

Aus QuaNTH
Wechseln zu: Navigation, Suche

A4

Rechnen
Einführung

Lektionen


Der Deutsch-Algorithmus

Um die Idee des Quantenrechnens zu illustrieren, betrachten wir ein so genanntes Nachfrage-Problem (eng. query complexity problem). Bei einem solchen Problem darf ein Fragender einem Orakel Fragen stellen, um eine Aufgabe zu lösen. Als Ressource dient hierbei, wie oft das Orakel befragt werden muss. In unserem Beispiel soll festgestellt werden, ob eine Münze entweder fair oder unfair ist. Fair bedeutet hierbei, dass die Münze auf Vorder- und Rückseite unterschiedliche Symbole zeigt, während eine unfaire Münze auf beiden Seiten dieselben Symbole zeigt. Die beiden Fragen, die man dem Orakel klassisch stellen darf, lauten: "Was ist auf der Vorderseite der Münze zu sehen?" und "Was ist auf der Rückseite der Münze zu sehen?". Die Antwort, die das Orakel geben kann lauten entweder "Kopf" oder "Zahl". Wenn man nun rein klassisch herausfinden möchte, ob die Münze fair oder unfair ist, muss man beide Fragen stellen - eine Frage allein reicht nicht aus.

Wie sieht das Problem nun in der Quantenwelt aus? Hier muss man die beiden Fragen in ein Qubit kodieren, also eine Vorschrift finden, wie ein Quantenzustand als "Frage" interpretiert werden kann. Wählt man als Qubit wieder polarisiertes Licht, so könnte man horizontal polarisiertes Licht nehmen, um die Frage "Vorderseite?" zu kodieren und vertikal polarisiertes Licht, um die Frage "Rückseite?" zu kodieren. Das Orakel ist dann ein Quantengatter, welches ebenfalls ein Qubit kodiert in polarisiertem Licht zurückgibt, beispielsweise könnte "horizontal polarisiert" für "Kopf" und "vertikal polarisiert" für "Zahl" stehen.

Es ist nun aber gerade eine der Grundeigenschaften von Quantensystemen, dass sie Konfigurationen zulassen, die klassisch nicht möglich sind. So kann man einen Zustand in einer kohärenten Superposition präparieren. In unserem Fall ergäbe eine kohärente Überlagerung von horizontal und vertikal polarisiertem Licht beispielsweise rechts-zirkular polarisiertes Licht. Aus Sicht der von uns gewählten Basis von Kopf und Zahl befindet sich der Zustand dann, sehr salopp ausgedrückt, in beiden Zuständen gleichzeitig. Sendet man nun eine solche Superposition an das Orakel, werden beide Fragen, also die nach der Vorderseite und die nach der Rückseite, in nur einem Schritt beantwortet. Genauer gesagt enthält der vom Orakel zurückgegebene Zustand wieder eine Superposition aus beiden Antwortzuständen.

Als letztes muss nun noch sichergestellt werden, dass dieser Superpositionszustand auch so ausgemessen werden kann, dass die Eingangsfrage beantwortet werden kann. Es ist nämlich auch eine Eigenschaft der Quantenmechanik, dass eine einzelne Messung nie ausreichen kann, um sämtliche Eigenschaften eines Quantenzustandes festzustellen. Konkret bedeutet dies, dass der Zustand zwar die Antworten auf beide Fragen enthält, aber nicht beide Antworten mit einer Messung gelesen werden können. Um die Eingangsfrage zu beantworten, muss der Zustand in einer entsprechend gewählten Basis vermessen werden (also in unserem Falle beispielsweise in der rechts-/links-zirkulären Basis). In dieser Basis kann gerade der Zustand, der sich ergibt, wenn die Münze fair ist, mit Sicherheit von dem Zustand unterschieden werden, bei denen die Münze unfair ist und die Frage kann beantwortet werden.

Hierbei ist aber zu bemerken, dass das Messergebnis nichts darüber sagt, welche der beiden Seiten Kopf oder Zahl zeigt. Bei der klassischen Messung mussten wir zweimal messen, bekamen aber auch zwei Bit an Information, nämlich die Information, welches Symbol auf der Vorderseite und welches auf der Rückseite abgebildet ist. Benutzt man den Quantenalgorithmus, so braucht man nur eine Frage um zu entscheiden, ob die Münze fair oder unfair ist, erhält aber auch nur ein Bit an Information. Um im Quantenfall zu unterscheiden, welches Symbol sich auf der Vorderseite bzw. der Rückseite befindet, muss ein zweites Mal gefragt werden. Nehmen wir beispielsweise an, die erste Messung hat ergeben, dass die Münze unfair ist. Dann benötigt man noch eine zweite Frage, um zu entscheiden, ob es sich um die Kopf/Kopf- oder die Zahl/Zahl-Münze handelt.


Prinzipien des Quantenrechnens

Viele der Motive, die wir beim Deutsch-Algorithmus gesehen hatten, gelten für alle Aufgaben beim Quantenrechnen. Vor allem kann mithilfe von Quantenmessungen nicht quantitativ mehr Information gewonnen werden (eine Messung mit zwei Messwerten liefert weiterhin ein Bit an Information), aber durch die spezielle Struktur von Quantenzuständen können andere Fragen gestellt werden. Es hat sich gezeigt, dass Fragen von einem Quantenprozessor gut bearbeitet werden können, bei denen es darum geht, Symmetrien in den Antworten einer Funktion zu finden.

Beim Shor-Algorithmus wird es später darauf ankommen, die Periode einer Funktion zu bestimmen. Hierfür müsste man klassisch die Funktionswerte der Funktion an mehreren Stellen bestimmen, um dann daraus die Periode zu bestimmen. Dies ist jedoch aufwendig und liefert mehr Information, als man braucht, da einen die konkreten Funktionswerte gar nicht interessieren. Ein Quantenprozessor kann die Periode direkt bestimmen, indem er eine Superposition von Antworten verarbeitet, somit also eine Reihe von Stützstellen parallel verarbeitet.

Grenzen des Quantenrechnens

Dieses Grundprinzip für den Vorteil der Quantenrechner gegenüber den klassischen Rechnern wird auch als Quanten-Parallelismus bezeichnet. Es gibt jedoch auch Probleme, bei denen diese Sorte von Verarbeitung keinen Vorteil bringt. In der Frühzeit des Quantencomputings in den 1990er Jahren war es durchaus eine legitime Frage, ob ein Quantencomputer einem klassischen Computer in sämtlichen Belangen (also für sämtliche Aufgaben) überlegen sein würde. Es zeigte sich jedoch, dass dies mit großer Wahrscheinlichkeit nicht der Fall sein wird. Ein Quantenrechner sollte daher immer als eine Ergänzung der klassischen Rechnerarchitektur gesehen werden, der für bestimmte Klassen von Aufgaben genutzt werden kann.