5.3.1 Winkelverstärkung

Der letzte Quantenalgorithmus den wir besprechen werden ist ein sehr wichtiges Unterprogramm, welches von vielen anderen Quantenalgorithmen genutzt wird (zum Beispiel ist es das Herz von Grovers Algorithmus für Funktionen mit mehr als $n=2$ Eingabebits).

Das Problem, das das Unterprogramm löst mag auf den ersten Blick seltsam wirken. Tatsächlich ist es ein reines Quantenproblem in dem Sinne, dass es kein sinnvolles klassisches Äquivalent gibt. Trotzdem taucht es auf natürliche Art in anderen Algorithmen auf, was das Unterprogramm nützlich macht. Das unterstreicht noch einmal, wie anders die Ideen hinter Quantenalgorithmen sind und das neuartige Ansätze für das erfinden neuer Quantenalgorithmen notwendig sind!

Weiterhin ist das Problem ein Beispiel, wo mehr als eine Orakel-Anfrage notwendig sind, um zu einer Lösung zu gelangen. Das ist ein Unterschied zu den Quantenalgorithmen, die wir bisher in dieser Quest kennengelernt haben, welche das Orakel nur genau ein mal benötigen.

Hausaufgabe 5.6 (Mit welchem Winkel? (schwierig)).

Alice und Bob sind verzweifelt. “Es tut uns leid,” erzählen sie dir. “Wir haben diese schöne Reflektion $V(\theta)$ mit dem Winkel

\theta=+\frac{\pi}{4k}\quad\text{oder}\quad\theta=-\frac{\pi}{4k},

gebaut, aber wir können uns einfach nicht mehr erinnern welcher von beiden es war – wir wissen nur noch, dass $k\geq 1$ war!” ¹⁶¹⁶ 16 Wenn du möchtest, kannst du dir die Reflektion wie ein Orakel vorstellen, das einen der beiden Winkel seltsam versteckt. Was das Problem noch schlimmer macht: Das Gatter wird sich selbst zerstören, wenn es mehr als $k$ mal benutzt wird.

Kannst du ihnen helfen? Deine Aufgabe, wenn du sie annimst, ist es, herauszufinden, welcher der beiden Winkel der richtige ist, indem du das Gatter $V(\theta)$ maximal $k$ mal benutzt.

Hinweis: Zwei aufeinanderfolgende Reflexionen ergeben eine Rotation. Was erhältst du, wenn du $\mathrm{NOT}$ und $V(\theta)$ kombinierst? (Du brauchst die allgemeine Formel aus 4.6 nicht um diese Frage zu beantworten).

Hack.

Dem Hinweis folgend betrachten wir $R=\mathrm{NOT}\,V(\theta)$ . Wir sehen, dass

\displaystyle\mathrm{NOT}\,V(\theta)=\mathrm{NOT}\,\mathrm{NOT}\,U(\theta)=U(\theta)

eine Drehung um den Winkel $\theta$ ist. Im zweiten Schritt haben wir ausgenutzt, dass $V(\theta)=\mathrm{NOT}\,U(\theta)$ , was der Definition von $V(\theta)$ aus Gl. 2.33 entspricht.

In Abschnitt 4.1.4 haben wir besprochen, dass zwei aufeinanderfolgende Drehungen einer einzelnen Drehung entsprechen, deren Winkel die Summe der beiden ursprünglichen Winkel ist. Da $R$ eine Rotation um den Winkel $\theta$ ist, erhalten wir durch $k$ -maliges wiederholen eine Drehung um den Winkel $k\theta=\pm\frac{\pi}{4}$ . Das bedeutet:

\displaystyle\underbrace{R\dotsb R}_{k\text{}}=U(\pm\pi/4)

Wenn wir annehmen, dass der anfängliche Zustand $\left|+\right\rangle=\left|\psi(\pi/4)\right\rangle$ war, dann gilt

\underbrace{R\dotsb R}_{k\text{}}\left|+\right\rangle=U(\pm\pi/4)\left|\psi(% \pi/4)\right\rangle=\left|\psi(\pi/4\pm\pi/4)\right\rangle.

Daher ist der endgültige Zustand entweder $\left|\psi(\pi/2)\right\rangle=\left|1\right\rangle$ (wenn das Vorzeichen ‘ $+$ ’ war) oder $\left|\psi(0)\right\rangle=\left|0\right\rangle$ (wenn das Vorzeichen ‘ $-$ ’ war). Wir können die beiden Zustände also durch eine Messung unterscheiden.