Q ⟩ Curriculum 03

Quantenüberlegenheit – der Deutsch-Jozsa Algorithmus

Wir haben bereits gesehen, dass Quantencomputer mit Qubits rechnen. Ein Vorteil der Qubits ist die Möglichkeit, Superpositionszustände anzunehmen. Für Aufgaben, wie die Addition zweier Zahlen, haben Quantencomputer dabei keine Vorteile gegenüber herkömmlichen Computern. Aber bei manchen Aufgaben sind diese Superpositionszustände sehr hilfreich und beschleunigen Berechnungen ungemein. Die dabei angewendeten Quantenschaltkreise können allerdings sehr kompliziert werden. Trotzdem können wir die Quantenüberlegenheit an einem kleineren Beispiel verstehen.

Stell dir vor, wir haben eine antike Kiste gefunden, die drei verschiedene Knöpfe und auf der Vorder- und Rückseite einen Bildschirm hat. Man kann die Truhe nur öffnen, wenn man angibt, ob beide Bildschirme denselben Inhalt anzeigen.

Der erste Knopf aktiviert den Bildschirm auf der Vorderseite und zeigt eine 0 oder 1 an.
Der zweite Knopf aktiviert den Bildschirm auf der Rückseite und zeigt eine 0 oder 1 an.

Eigentlich ganz einfach oder? Probiere es einmal aus, indem du die Knöpfe in der obigen Grafik anklickst! Zeigen beide Display dieselbe Zahl oder unterschiedliche Zahlen?

Lösung

Wir betätigen den ersten Knopf und schauen auf das vordere Display. Anschließend betätigen wir den zweiten Knopf und schauen auf das hintere Display. Wir sehen, dass die beiden Zahlen unterschiedlich sind.

Knifflig wird es allerdings, wenn wir nur einen Knopf drücken dürfen.

Probiere es einmal aus, indem du einen der beiden Knöpfe in der untenstehenden Grafik anklickst! Kannst du noch herausfinden, ob beide Display dieselbe Zahl oder unterschiedliche Zahlen zeigen?

Lösung

Mit nur einem Knopf, können wir nicht sagen, ob die beiden Seiten die gleiche Zahl zeigen oder nicht. Drücken wir jetzt den vorderen Knopf und wird beispielsweise eine 0 angezeigt, dann wissen wir immer noch nicht, ob hinten eine 0 oder eine 1 angezeigt wird.

Zum Glück gibt es noch einen dritten Knopf: Der dritte Knopf wechselt in den Quantenmodus und führt eine Quantenoperation auf einem Qubit aus, die wir uns im Folgenden anschauen möchten.

Unser Qubit ist zuerst im Zustand 0, das heißt, es zeigt auf den Nordpol der Zustandskugel.

Im zweiten Schritt wenden wir ein Hadamard-Gatter H an, das du aus Kapitel 02 kennst:

Nun kommt der Quantentrick: Der dritte Knopf dreht für jede 1, die auf der Kiste gezeigt wird, um \(180^\circ\) an der Achse zwischen Nord- und Südpol. Daraus ergeben sich folgende Möglichkeiten:

Falls beide Bildschirme eine 1 zeigen würden, wird das Qubit um \(2 \cdot 180^\circ = 360^\circ\) gedreht ( \(360^\circ\) entspricht auch \(0^\circ\)).
Falls beide eine 0 zeigen würden, wir das Qubit um \(0^\circ\) gedreht.
Falls das vordere Display eine 1 und das hintere eine 0 zeigen würde, wird das Qubit um \(180^\circ\) gedreht.
Falls das vordere Display eine 0 und das hintere eine 1 zeigen würde, wird das Qubit um \(180^\circ\) gedreht.

Es zeigt sich, dass das Qubit "nach vorne zeigt", falls beide Display die gleiche Zahl anzeigen würden. Würden beide Displays unterschiedliche Zahlen anzeigen, zeigt das Qubit nach der Drehung "nach hinten".
Nun kommt erneut das Hadamard-Gatter H zum Einsatz: Nach Anwendung des Hadamard-Gatters ergeben sich damit die folgenden zwei finalen Zustände:

Falls das Qubit nach vorne zeigt (und damit beide Displays die gleichen Zahlen zeigen würden), zeigt das Qubit nach Anwendung von Hadamard nach oben und wir erhalten das Messergebnis 0.
Falls das Qubit nach hinten zeigt (und damit beide Displays unterschiedliche Zahlen zeigen würden), zeigt das Qubit nach Anwendung von Hadamard nach unten und wir erhalten das Messergebnis 1.

Probiere nun den Quantenmodus der Truhe aus! Wie viele Werte musst du auslesen, um die Truhe zu öffnen (also zu entscheiden, ob beide Displays dieselbe Zahl anzeigen)?

Lösung

Mit nur einem Knopf können wir sagen, ob die beiden Bildschirme das Gleiche zeigen oder nicht.

Verrückt oder? Während man bei unserem Beispiel mit der Truhe mit einem herkömmlichen Computer 2 Werte überprüfen muss, muss mit Quantencomputern nur ein Wert überprüft werden. Es geht aber noch beeindruckender: Wenn wir nicht nur auf der Vorder- und Rückseite einen Bildschirm haben, sondern auf jeder Seite einen Bildschirm haben, funktioniert der Quantentrick auch. Dann muss allerdings um 60° gedreht werden. Das, was wir uns hier anhand einer geheimnisvollen Truhe überlegt haben, heißt in der Welt der Quanteninformatik Deutsch-Josza-Algorithmus. Er ist das einfachste Beispiel, das aufzeigt:

Quantencomputer können bestimmte aber nicht alle Probleme effizienter lösen als klassische Computer.