Quantencomputing-Algorithmen

In der Vorlesung „Foundations of Quantum Computing“ haben wir die grundlegenden Konzepte des Quantencomputings kennengelernt, doch die eigentlichen Algorithmen wurden für den Folgekurs „Quantum Computing Algorithms“ aufgespart. Die zentrale Idee hinter vielen Quantenalgorithmen ist der Einsatz von Phasenorakeln und Amplitudenverstärkung, was ich persönlich besonders spannend fand. Im Folgenden gebe ich eine Zusammenfassung dieser Konzepte, erkläre, wie sie im Grover-Algorithmus zur Anwendung kommen, und füge außerdem das Formelskript hinzu, das ich mir als Prüfungsvorbereitung zusammengestellt habe.

Phasenorakel

Für eine Boolesche Funktion $f: \{0,1\}^n \to \{0,1\}$ wirkt ein Bit-Flip-Oracle $U_f$ wie folgt:

U_f |x\rangle |y\rangle = |x\rangle |y \oplus f(x)\rangle

Auf den ersten Blick wirkt das nicht sonderlich aufregend: Es schreibt das Ergebnis $f(x)$ in das zweite Register, indem es dieses genau dann invertiert, wenn $f(x) = 1$ gilt. Doch der Trick liegt darin, dass wir für das zweite Register den Zustand $\ket{y} = |-\rangle = \tfrac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$ wählen. Dann gilt:

U_f |x\rangle |-\rangle = (-1)^{f(x)} |x\rangle |-\rangle

Dies ist ein Phasenorakel. Das Ergebnis $f(x)$ erscheint nun nicht mehr explizit im zweiten Qubit, sondern es wirkt als relativer Phasenfaktor auf dem ersten Qubit.

Diese Konstruktion ist für Quantenalgorithmen enorm nützlich, weil sie uns erlaubt, die Phase von Quantenzuständen auf der Grundlage von Funktionsauswertungen zu manipulieren.

Warum das funktioniert: Phase Kickback

Der Grund, warum das oben Gesagte funktioniert, liegt in einer besonderen Eigenschaft des Zustands $|-\rangle$ , die als Phase Kickback bezeichnet wird.

Zur Erinnerung: die polaren Zustände sind definiert als

|+\rangle = \tfrac{1}{\sqrt{2}} (|0\rangle + |1\rangle), \quad |-\rangle = \tfrac{1}{\sqrt{2}} (|0\rangle - |1\rangle)

Es handelt sich um Eigenzustände des Pauli-X-Operators, der wie folgt wirkt:

X|+\rangle = +|+\rangle, \quad X|-\rangle = -|-\rangle

Das spiegelt ein allgemeines Phänomen in der Quantenmechanik wider: Befindet sich ein Qubit in einem Eigenzustand eines Operators, so verändert die Anwendung dieses Operators den Zustand nicht, außer dass er mit einem Phasenfaktor (dem Eigenwert) multipliziert wird. Ist ein Steuerqubit in einer Superposition und das Zielqubit im Eigenzustand des Operators, so „wandert“ der Eigenwert als relativer Phasenfaktor zurück auf das Steuerqubit.

Genau deshalb führt die Wahl von $|-\rangle$ als Hilfsregister in $U_f$ dazu, dass wir $(-1)^{f(x)}$ auf $|x\rangle$ erhalten: Der Eigenwert aus der $X$ -Operation auf $|-\rangle$ wird zurück in das Eingaberegister „gekickt“.

Grovers Algorithmus

Der Grover-Algorithmus ist ein Quanten-Suchverfahren. Stellen wir uns vor, wir möchten unter $N$ möglichen Kandidaten ein markiertes Element $x^*$ finden. Klassisch bräuchten wir im Durchschnitt $O(N)$ Abfragen der Funktion, die überprüft, ob $x = x^*$ gilt. Der Grover-Algorithmus reduziert dies mithilfe der Phasenorakel-Idee auf nur $O(\sqrt{N})$ Abfragen.

Praktisch ist Grovers Algorithmus auch bei SAT-Problemen oder allgemein in Situationen nützlich, in denen man ein $x$ finden möchte, sodass $f(x) = 1$ gilt.

Die Grundidee ist, dass ein Orakel die richtige Lösung mit einer negativen Phase markiert. Reflektieren wir danach alle Amplituden um ihren Mittelwert, so werden die markierten Zustände verstärkt und die übrigen unterdrückt. Wiederholen wir diesen Prozess einige Male, steigt die Wahrscheinlichkeit, den richtigen Zustand zu messen, sehr stark an. Während klassisch $O(N)$ Abfragen notwendig wären, reichen im Quantenfall $O(\sqrt{N})$ Iterationen.

Schritt 1: Uniforme Superposition

Zunächst werden Hadamard-Gatter auf alle Qubits angewandt, um eine gleichverteilte Superposition zu erzeugen:

|s\rangle = H^{\otimes n} |0\rangle^{\otimes n} = \tfrac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle

Damit besitzen alle möglichen Zustände die gleiche Amplitude.

Schritt 2: Phasenflip

Das Orakel invertiert nun das Vorzeichen des markierten Zustands mithilfe eines Phasenorakels, wobei $x^*$ das gesuchte Element ist:

S_f = I_{2^n} - 2|x^*\rangle \langle x^*|

Dies entspricht dem Multiplizieren von $\ket{x^*}$ mit $-1$ , während alle anderen Zustände unverändert bleiben.

Zugegeben wirkt das zunächst paradox, denn um $S_f$ explizit zu konstruieren, müssten wir $x^*$ bereits kennen. Praktisch verwendet man jedoch ein Black-Box-Phasenorakel, das $f(x)$ auswertet, ohne $x^*$ direkt preiszugeben.

Schritt 3: Diffusionsoperator

Um die Amplituden um den Mittelwert zu reflektieren, nutzen wir den sogenannten Diffusionsoperator:

D = 2|s\rangle \langle s| - I_{2^n}

Dieser lässt sich mit Hadamard-Gattern wie folgt aufbauen:

D = H^{\otimes n} \big[2|0\rangle^{\otimes n}\langle 0|^{\otimes n} - I_{2^n}\big] H^{\otimes n}

Schritt 4: Grover-Iteration

Fasst man die beiden vorherigen Schritte zusammen, erhält man den Grover-Iterationsoperator:

G = D S_f

Jede Iteration verstärkt die Amplitude von $|x^*\rangle$ , während die anderen Zustände geschwächt werden.

Geometrische Sichtweise

Anschaulich lässt sich das Ganze als eine Rotation in einem zweidimensionalen Unterraum verstehen: Die eine Achse entspricht dem markierten Zustand $|x^*\rangle$ , die andere der gleichverteilten Superposition aller unmarkierten Zustände.

Bezeichnen wir mit $\theta$ den Winkel zwischen $|s\rangle$ und $|x^*\rangle$ . Anfangs beträgt die Amplitude von $|x^*\rangle$ in $|s\rangle$ :

\sin\theta = \frac{1}{\sqrt{2^n}}

Der Zustandsvektor rotiert in jeder Iteration um den Winkel $2\theta$ . Nach $r$ Iterationen ist die Überlappung mit dem markierten Unterraum

\sin((2r+1)\theta)

und die Erfolgswahrscheinlichkeit beträgt

P(r) = \sin^2\!\left((2r+1)\theta\right)

Da dies oszilliert, ist es entscheidend, die richtige Anzahl an Iterationen zu wählen.

Wie viele Iterationen sind nötig?

Aus der obigen Formel können wir ableiten, dass die Wahrscheinlichkeit, $|x^*\rangle$ zu messen, maximiert wird, wenn gilt:

r \approx \left\lfloor \tfrac{\pi}{4} \sqrt{\tfrac{2^n}{k}} \right\rfloor

wobei $k$ die Anzahl der markierten Lösungen bezeichnet.

Merkblatt

Kommentare

Noch Fragen?

Durch das Anmelden mit Github wird ein Login-Cookie erstellt und gespeichert. Sie können dies jederzeit rückgängig machen, indem Sie 'Cookie löschen' anklicken.