Das Phasenabschätzungsverfahren

Als nächstes besprechen wir das Phasenabschätzungsverfahren, einen Quantenalgorithmus zur Lösung des Phasenabschätzungsproblems.

Wir beginnen mit einer Aufwärmübung mit niedriger Genauigkeit, die die grundlegende Intuition hinter der Methode vermittelt. Anschließend sprechen wir über die Quanten-Fourier-Transformation, eine wichtige Quantenoperation, die im Phasenabschätzungsverfahren verwendet wird, sowie über ihre Implementierung als Quantenschaltkreis. Sobald wir die Quanten-Fourier-Transformation verstanden haben, beschreiben wir das Phasenabschätzungsverfahren in voller Allgemeinheit und analysieren seine Leistung.

Aufwärmübung: Phasen mit niedriger Genauigkeit annähern

Wir beginnen mit ein paar einfachen Varianten des Phasenabschätzungsverfahrens, die Lösungen mit niedriger Genauigkeit für das Phasenabschätzungsproblem liefern. Dies hilft dabei, die Intuition hinter dem allgemeinen Verfahren zu erklären, das wir etwas später in der Lektion kennenlernen werden.

Den Phase-Kickback nutzen

Ein einfacher Ansatz für das Phasenabschätzungsproblem, mit dem wir etwas über den gesuchten Wert $\theta$ erfahren können, basiert auf dem Phase-Kickback-Phänomen. Wie wir sehen werden, handelt es sich dabei im Wesentlichen um eine Einzel-Qubit-Version des allgemeinen Phasenabschätzungsverfahrens, das später in der Lektion besprochen wird.

Als Teil der Eingabe für das Phasenabschätzungsproblem haben wir einen unitären Quantenschaltkreis für die Operation $U$. Wir können die Beschreibung dieses Schaltkreises nutzen, um einen Schaltkreis für eine kontrollierte-$U$-Operation zu erstellen, was die folgende Abbildung veranschaulicht (mit der Operation $U$, betrachtet als Quantengate, links und einer kontrollierten-$U$-Operation rechts).

Wir können einen Quantenschaltkreis für eine kontrollierte-$U$-Operation erstellen, indem wir zunächst dem Schaltkreis für $U$ ein Kontroll-Qubit hinzufügen und dann jedes Gate im Schaltkreis für $U$ durch eine kontrollierte Version dieses Gates ersetzen — unser neues Kontroll-Qubit kontrolliert also effektiv jedes einzelne Gate im Schaltkreis für $U$. Dies erfordert, dass wir eine kontrollierte Version jedes Gates in unserem Schaltkreis haben, aber wir können stets Schaltkreise für diese kontrollierten Operationen aufbauen, falls sie nicht in unserem Gate-Set enthalten sind.

Betrachten wir nun den folgenden Schaltkreis, bei dem der Eingangszustand $\vert\psi\rangle$ aller Qubits außer dem obersten der Eigenvektor-Quantenzustand von $U$ ist.

Die Messausgangswahrscheinlichkeiten für diesen Schaltkreis hängen vom Eigenwert von $U$ ab, der dem Eigenvektor $\vert\psi\rangle$ entspricht. Analysieren wir den Schaltkreis im Detail, um genau herauszufinden, wie.

Der Anfangszustand des Schaltkreises ist

$$\vert\pi_0\rangle = \vert\psi\rangle \vert 0\rangle$$

und das erste Hadamard-Gate transformiert diesen Zustand zu

$$\vert\pi_1\rangle = \vert\psi\rangle \vert +\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle.$$

Als nächstes wird die kontrollierte-$U$-Operation ausgeführt, was zum Zustand führt

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \bigl(U \vert\psi\rangle\bigr) \vert 1\rangle.$$

Unter der Annahme, dass $\vert\psi\rangle$ ein Eigenvektor von $U$ mit dem Eigenwert $\lambda = e^{2\pi i\theta}$ ist, können wir diesen Zustand alternativ wie folgt ausdrücken.

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle = \vert\psi\rangle \otimes \left( \frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle\right)$$

Hier beobachten wir das Phase-Kickback-Phänomen. Es unterscheidet sich diesmal etwas von dem, was wir bei Deutschs Algorithmus und dem Deutsch-Jozsa-Algorithmus gesehen haben, da wir nicht mit einem Query-Gate arbeiten — aber die Idee ist ähnlich.

Schließlich wird das zweite Hadamard-Gate ausgeführt. Nach einer kleinen Vereinfachung erhalten wir folgenden Ausdruck für diesen Zustand.

$$\vert\pi_3\rangle = \vert\psi\rangle \otimes \left( \frac{1+ e^{2\pi i \theta}}{2} \vert 0\rangle + \frac{1 - e^{2\pi i \theta}}{2} \vert 1\rangle\right)$$

Die Messung liefert daher die Ergebnisse $0$ und $1$ mit diesen Wahrscheinlichkeiten:

$$\begin{aligned} p_0 &= \left\vert \frac{1+ e^{2\pi i \theta}}{2} \right\vert^2 = \cos^2(\pi\theta)\\[1mm] p_1 &= \left\vert \frac{1- e^{2\pi i \theta}}{2} \right\vert^2 = \sin^2(\pi\theta). \end{aligned}$$

Hier ist ein Diagramm der Wahrscheinlichkeiten für die beiden möglichen Ergebnisse, $0$ und $1$, als Funktionen von $\theta$.

Naturgemäß ergeben die beiden Wahrscheinlichkeiten stets die Summe $1$. Beachte, dass wenn $\theta = 0$, das Messergebnis immer $0$ ist, und wenn $\theta = 1/2$, das Messergebnis immer $1$ ist. Obwohl das Messergebnis also nicht genau preisgibt, was $\theta$ ist, liefert es uns doch einige Informationen darüber — und wenn uns versprochen worden wäre, dass entweder $\theta = 0$ oder $\theta = 1/2$ gilt, könnten wir aus dem Schaltkreis fehlerfrei erfahren, welches der Fall ist.

Intuitiv lässt sich das Messergebnis des Schaltkreises als eine Schätzung von $\theta$ mit „einem Bit Genauigkeit" verstehen. Mit anderen Worten: Würden wir $\theta$ in Binärdarstellung schreiben und auf ein Bit runden, erhielten wir eine Zahl wie diese:

$$0.a = \begin{cases} 0 & a = 0\\ \frac{1}{2} & a = 1. \end{cases}$$

Das Messergebnis kann als Schätzung des Bits $a$ betrachtet werden. Wenn $\theta$ weder $0$ noch $1/2$ ist, besteht eine von null verschiedene Wahrscheinlichkeit, dass die Schätzung falsch ist — aber die Fehlerwahrscheinlichkeit wird immer kleiner, je näher wir $0$ oder $1/2$ kommen.

Es ist naheliegend zu fragen, welche Rolle die beiden Hadamard-Gates in diesem Verfahren spielen:

• Das erste Hadamard-Gate versetzt das Kontroll-Qubit in eine gleichmäßige Superposition von $\vert 0\rangle$ und $\vert 1\rangle$, sodass der Phase-Kickback beim Zustand $\vert 1\rangle$ und nicht beim Zustand $\vert 0\rangle$ auftritt und eine relative Phasendifferenz erzeugt, die die Messergebnisse beeinflusst. Würden wir dies nicht tun und würde der Phase-Kickback eine globale Phase erzeugen, hätte er keinen Einfluss auf die Wahrscheinlichkeiten verschiedener Messergebnisse.

• Das zweite Hadamard-Gate ermöglicht es uns, durch das Phänomen der Interferenz etwas über die Zahl $\theta$ zu erfahren. Vor dem zweiten Hadamard-Gate befindet sich das oberste Qubit im Zustand

  $$\frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle,$$

  und wenn wir diesen Zustand messen würden, erhielten wir $0$ und $1$ jeweils mit Wahrscheinlichkeit $1/2$, was uns nichts über $\theta$ verrät. Durch das zweite Hadamard-Gate bewirken wir jedoch, dass die Zahl $\theta$ die Ausgangswahrscheinlichkeiten beeinflusst.

Die Phase verdoppeln

Der obige Schaltkreis nutzt das Phase-Kickback-Phänomen, um $\theta$ auf ein einzelnes Bit Genauigkeit anzunähern. Ein Bit Genauigkeit mag in manchen Situationen ausreichen — aber für die Faktorisierung werden wir sehr viel mehr Genauigkeit benötigen. Eine naheliegende Frage ist: Wie können wir mehr über $\theta$ erfahren?

Eine sehr einfache Möglichkeit besteht darin, die kontrollierte-$U$-Operation in unserem Schaltkreis durch zwei Kopien dieser Operation zu ersetzen, wie in diesem Schaltkreis:

Zwei Kopien einer kontrollierten-$U$-Operation entsprechen einer kontrollierten-$U^2$-Operation. Wenn $\vert\psi\rangle$ ein Eigenvektor von $U$ mit dem Eigenwert $\lambda = e^{2\pi i \theta}$ ist, dann ist dieser Zustand auch ein Eigenvektor von $U^2$, diesmal mit dem Eigenwert $\lambda^2 = e^{2\pi i (2\theta)}$.

Wenn wir diese Version des Schaltkreises ausführen, führen wir also effektiv dieselbe Berechnung wie zuvor durch, nur dass die Zahl $\theta$ durch $2\theta$ ersetzt wird. Hier ist ein Diagramm, das die Ausgangswahrscheinlichkeiten zeigt, während $\theta$ von $0$ bis $1$ variiert.

Dies kann uns tatsächlich einige zusätzliche Informationen über $\theta$ liefern. Wenn die Binärdarstellung von $\theta$ lautet

$$\theta = 0.a_1 a_2 a_3\cdots$$

dann verschiebt die Verdopplung von $\theta$ den Binärpunkt effektiv um eine Stelle nach rechts:

$$2\theta = a_1. a_2 a_3\cdots$$

Da wir $\theta = 1$ mit $\theta = 0$ gleichsetzen, wenn wir uns auf dem Einheitskreis bewegen, hat das Bit $a_1$ keinen Einfluss auf unsere Wahrscheinlichkeiten, und wir erhalten effektiv eine Schätzung für das zweite Bit nach dem Binärpunkt, wenn wir $\theta$ auf zwei Bits runden. Wenn wir beispielsweise im Voraus wüssten, dass $\theta$ entweder $0$ oder $1/4$ ist, könnten wir dem Messergebnis vollständig vertrauen.

Es ist jedoch nicht unmittelbar klar, wie diese Schätzung mit dem, was wir aus dem ursprünglichen (nicht verdoppelten) Phase-Kickback-Schaltkreis gelernt haben, in Einklang gebracht werden sollte, um möglichst genaue Informationen über $\theta$ zu erhalten. Lass uns daher einen Schritt zurücktreten und überlegen, wie wir vorgehen sollten.

Zwei-Qubit-Phasenabschätzung

Anstatt die beiden oben beschriebenen Optionen getrennt zu betrachten, kombinieren wir sie in einem einzigen Schaltkreis wie folgt.

Die Hadamard-Gates nach den kontrollierten Operationen wurden entfernt, und es gibt hier noch keine Messungen. Wir werden den Schaltkreis erweitern, wenn wir unsere Optionen zur bestmöglichen Gewinnung von Informationen über $\theta$ abwägen.

Wenn wir diesen Schaltkreis ausführen, während $\vert\psi\rangle$ ein Eigenvektor von $U$ ist, bleibt der Zustand der unteren Qubits während des gesamten Schaltkreises $\vert\psi\rangle$, und Phasen werden in den Zustand der oberen zwei Qubits „gekickt". Analysieren wir den Schaltkreis sorgfältig anhand der folgenden Abbildung.

Wir können den Zustand $\vert\pi_1\rangle$ wie folgt schreiben:

$$\vert\pi_1\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 \vert a_1 a_0 \rangle.$$

Wenn die erste kontrollierte-$U$-Operation ausgeführt wird, wird der Eigenwert $\lambda = e^{2\pi i\theta}$ in die Phase „gekickt", wenn $a_0$ (das oberste Qubit) gleich $1$ ist, aber nicht wenn es $0$ ist. Den resultierenden Zustand können wir so ausdrücken:

$$\vert\pi_2\rangle = \vert\psi\rangle \otimes \frac{1}{2} \sum_{a_0=0}^1 \sum_{a_1=0}^1 e^{2 \pi i a_0 \theta} \vert a_1 a_0 \rangle.$$

Das zweite und das dritte kontrollierte-$U$-Gate tun etwas Ähnliches, jedoch für $a_1$ anstatt $a_0$, wobei $\theta$ durch $2\theta$ ersetzt wird. Den resultierenden Zustand können wir so ausdrücken:

$$\vert\pi_3\rangle = \vert\psi\rangle\otimes\frac{1}{2}\sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 e^{2\pi i (2 a_1 + a_0)\theta} \vert a_1 a_0 \rangle.$$

Wenn wir den Binärstring $a_1 a_0$ als eine ganze Zahl $x \in \{0,1,2,3\}$ in Binärdarstellung betrachten, also $x = 2 a_1 + a_0$, können wir diesen Zustand alternativ wie folgt ausdrücken.

$$\vert\pi_3\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x \theta} \vert x \rangle$$

Unser Ziel ist es, aus diesem Zustand so viele Informationen wie möglich über $\theta$ zu gewinnen.

An dieser Stelle betrachten wir einen Spezialfall, bei dem uns zugesichert wird, dass $\theta = \frac{y}{4}$ für eine ganze Zahl $y\in\{0,1,2,3\}$ gilt. Mit anderen Worten, wir haben $\theta\in \{0, 1/4, 1/2, 3/4\}$, sodass wir diese Zahl mit binärer Notation und zwei Bits exakt ausdrücken können, als .$00$, .$01$, .$10$ oder .$11$. Im Allgemeinen ist $\theta$ möglicherweise nicht einer dieser vier Werte, aber das Nachdenken über diesen Spezialfall wird uns helfen herauszufinden, wie wir Informationen über $\theta$ im Allgemeinen am effektivsten extrahieren können.

Zunächst definieren wir für jeden möglichen Wert $y \in \{0, 1, 2, 3\}$ einen Zwei-Qubit-Zustandsvektor.

$$\vert \phi_y\rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x (\frac{y}{4})} \vert x \rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i \frac{x y}{4}} \vert x \rangle$$

Nach Vereinfachung der Exponentialterme können wir diese Vektoren wie folgt schreiben.

$$\begin{aligned} \vert\phi_0\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle + \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_1\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle - \frac{i}{2} \vert 3 \rangle \\[3mm] \vert\phi_2\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle - \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_3\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle + \frac{i}{2} \vert 3 \rangle \end{aligned}$$

Diese Vektoren sind orthogonal: Wenn wir ein beliebiges Paar von ihnen wählen und ihr inneres Produkt berechnen, erhalten wir $0$. Jeder ist auch ein Einheitsvektor, sodass $\{\vert\phi_0\rangle, \vert\phi_1\rangle, \vert\phi_2\rangle, \vert\phi_3\rangle\}$ eine Orthonormalbasis ist. Wir wissen daher sofort, dass es eine Messung gibt, die sie perfekt unterscheiden kann — das heißt, wenn einer von ihnen vorgegeben wird, ohne zu sagen welcher, können wir fehlerfrei herausfinden, welcher es ist.

Um eine solche Unterscheidung mit einem Quantenschaltkreis durchzuführen, können wir zunächst eine unitäre Operation $V$ definieren, die Standardbasiszustände in die vier oben aufgelisteten Zustände transformiert.

$$\begin{aligned} V \vert 00 \rangle & = \vert\phi_0\rangle \\ V \vert 01 \rangle & = \vert\phi_1\rangle \\ V \vert 10 \rangle & = \vert\phi_2\rangle \\ V \vert 11 \rangle & = \vert\phi_3\rangle \end{aligned}$$

Um $V$ als $4\times 4$-Matrix aufzuschreiben, nimmt man einfach die Zustände $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ als Spalten von $V$.

$$V = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

Dies ist eine besondere Matrix, die einigen Lesern wahrscheinlich schon begegnet ist: Es handelt sich um die Matrix, die mit der $4$-dimensionalen diskreten Fourier-Transformation assoziiert ist. Angesichts dieser Tatsache bezeichnen wir sie nicht mit $V$, sondern mit $\mathrm{QFT}_4$. Der Name $\mathrm{QFT}$ steht für Quanten-Fourier-Transformation — was im Wesentlichen nur die diskrete Fourier-Transformation ist, betrachtet als unitäre Operation. Wir werden die Quanten-Fourier-Transformation in Kürze ausführlicher und allgemeiner diskutieren.

$$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

Wir können die Inverse dieser Operation anwenden, um den umgekehrten Weg zu gehen und die Zustände $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ in die Standardbasiszustände $\vert 0\rangle,\ldots,\vert 3\rangle$ zu transformieren. Wenn wir das tun, können wir messen, um herauszufinden, welcher Wert $y\in\{0,1,2,3\}$ $\theta$ als $\theta = y/4$ beschreibt. Hier ist ein Diagramm eines Quantenschaltkreises, der genau das tut.

Zusammenfassend lässt sich sagen: Wenn wir diesen Schaltkreis ausführen, wenn $\theta = y/4$ für $y\in\{0,1,2,3\}$, ist der Zustand unmittelbar vor den Messungen $\vert \psi\rangle \vert y\rangle$ (wobei $y$ als zweistelliger Binärstring kodiert ist), sodass die Messungen den Wert $y$ fehlerfrei enthüllen.

Dieser Schaltkreis ist durch den Sonderfall $\theta \in \{0,1/4,1/2,3/4\}$ motiviert — aber wir können ihn für jede beliebige Wahl von $U$ und $\vert \psi\rangle$ und damit jeden beliebigen Wert von $\theta$ ausführen. Hier ist ein Diagramm der Ausgangswahrscheinlichkeiten, die der Schaltkreis für beliebige Werte von $\theta$ erzeugt.

Dies ist eine deutliche Verbesserung gegenüber der Einzel-Qubit-Variante, die zuvor in der Lektion beschrieben wurde. Es ist nicht perfekt — es kann uns eine falsche Antwort liefern — aber das Ergebnis ist stark auf Werte von $y$ konzentriert, für die $y/4$ nahe bei $\theta$ liegt. Insbesondere entspricht das wahrscheinlichste Ergebnis stets dem Wert $y/4$, der $\theta$ am nächsten liegt (wobei $\theta = 0$ und $\theta = 1$ wieder gleichgesetzt werden), und aus dem Diagramm sieht es so aus, als erscheine dieser nächste Wert für $x$ stets mit einer Wahrscheinlichkeit knapp über $40\%$. Wenn $\theta$ genau in der Mitte zwischen zwei solchen Werten liegt, wie z. B. $\theta = 0.375$, sind die beiden gleich nahen Werte von $y$ gleich wahrscheinlich.

Vorbereitung zur Verallgemeinerung auf viele Qubits

Angesichts der Verbesserung, die wir soeben durch die Verwendung von zwei Kontroll-Qubits statt einem in Verbindung mit der Inversen der $4$-dimensionalen Quanten-Fourier-Transformation erzielt haben, liegt es nahe, dies weiter zu verallgemeinern — indem wir weitere Kontroll-Qubits hinzufügen. Wenn wir das tun, erhalten wir das allgemeine Phasenabschätzungsverfahren. Wir werden in Kürze sehen, wie das funktioniert, aber um es präzise beschreiben zu können, müssen wir die Quanten-Fourier-Transformation in größerer Allgemeinheit besprechen, um zu sehen, wie sie für andere Dimensionen definiert ist und wie wir sie (bzw. ihre Inverse) mit einem Quantenschaltkreis implementieren können.

Quanten-Fourier-Transformation

Die Quanten-Fourier-Transformation ist eine unitäre Operation, die für jede Dimension $N$ (eine beliebige positive ganze Zahl) definiert werden kann. In diesem Abschnitt sehen wir, wie diese Operation definiert ist und wie sie mit einem Quantenschaltkreis auf $m$ Qubits mit Kosten $O(m^2)$ implementiert werden kann, wenn $N = 2^m$.

Die Matrizen, die die Quanten-Fourier-Transformation beschreiben, leiten sich von einer analogen Operation auf $N$-dimensionalen Vektoren ab, die als diskrete Fourier-Transformation bekannt ist. Diese Operation lässt sich auf verschiedene Arten verstehen. Zum Beispiel können wir die diskrete Fourier-Transformation in rein abstrakten, mathematischen Begriffen als lineare Abbildung betrachten. Oder wir können sie in rechnerischen Begriffen betrachten, bei denen uns ein $N$-dimensionaler Vektor komplexer Zahlen gegeben wird (unter der Annahme, dass Real- und Imaginärteile der Einträge in Binärdarstellung kodiert sind) und das Ziel darin besteht, den $N$-dimensionalen Vektor zu berechnen, der durch Anwendung der diskreten Fourier-Transformation entsteht. Unser Fokus liegt auf einer dritten Betrachtungsweise, nämlich diese Transformation als unitäre Operation zu sehen, die auf einem Quantensystem ausgeführt werden kann.

Es gibt einen effizienten Algorithmus zur Berechnung der diskreten Fourier-Transformation auf einem gegebenen Eingabevektor, der als schnelle Fourier-Transformation bekannt ist. Sie findet Anwendung in der Signalverarbeitung und vielen anderen Bereichen und gilt für viele als einer der wichtigsten je entdeckten Algorithmen. Die Implementierung der Quanten-Fourier-Transformation für den Fall, dass $N$ eine Zweierpotenz ist, basiert auf genau derselben zugrundeliegenden Struktur, die die schnelle Fourier-Transformation ermöglicht.

Definition der Quanten-Fourier-Transformation

Um die Quanten-Fourier-Transformation zu definieren, definieren wir zunächst eine komplexe Zahl $\omega_N$ für jede positive ganze Zahl $N$ wie folgt:

$$\omega_N = e^{\frac{2\pi i}{N}} = \cos\left(\frac{2\pi}{N}\right) + i \sin\left(\frac{2\pi}{N}\right).$$

Dies ist die Zahl auf dem komplexen Einheitskreis, die wir erhalten, wenn wir bei $1$ beginnen und uns gegen den Uhrzeigersinn um einen Winkel von $2\pi/N$ Radiant bewegen, also um einen Bruchteil von $1/N$ des Kreisumfangs. Hier sind einige Beispiele:

$$\begin{gathered} \omega_1 = 1\\[1mm] \omega_2 = -1\\[1mm] \omega_3 = -\frac{1}{2} + \frac{\sqrt{3}}{2} i\\[2mm] \omega_4 = i\\[1mm] \omega_8 = \frac{1+i}{\sqrt{2}}\\[3mm] \omega_{16} = \frac{\sqrt{2 + \sqrt{2}}}{2} + \frac{\sqrt{2 - \sqrt{2}}}{2} i\\[2mm] \omega_{100} \approx 0.998 + 0.063 i \end{gathered}$$

Nun können wir die $N$-dimensionale Quanten-Fourier-Transformation definieren, die durch eine $N\times N$-Matrix beschrieben wird, deren Zeilen und Spalten den Standardbasiszuständen $\vert 0\rangle,\ldots,\vert N-1\rangle$ zugeordnet sind. Für die Phasenabschätzung benötigen wir diese Operation nur für $N = 2^m$ als Zweierpotenz, aber die Operation kann für jede positive ganze Zahl $N$ definiert werden.

$$\mathrm{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \sum_{y = 0}^{N-1} \omega_N^{xy} \vert x \rangle\langle y\vert$$

Wie bereits erwähnt, ist dies die Matrix, die mit der $N$-dimensionalen diskreten Fourier-Transformation assoziiert ist. Oft wird der führende Faktor $1/\sqrt{N}$ nicht in der Definition dieser Matrix berücksichtigt, aber wir müssen ihn einschließen, um eine unitäre Matrix zu erhalten.

Hier ist die Quanten-Fourier-Transformation als Matrix für einige kleine Werte von $N$.

$$\mathrm{QFT}_1 = \begin{pmatrix} 1 \end{pmatrix}$$ $$\mathrm{QFT}_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\[1mm] 1 & -1 \end{pmatrix}$$ $$\mathrm{QFT}_3 = \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1\\[2mm] 1 & \frac{-1 + i\sqrt{3}}{2} & \frac{-1 - i\sqrt{3}}{2}\\[2mm] 1 & \frac{-1 - i\sqrt{3}}{2} & \frac{-1 + i\sqrt{3}}{2} \end{pmatrix}$$ $$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$ $$\mathrm{QFT}_8 = \frac{1}{2\sqrt{2}} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\[2mm] 1 & \frac{1+i}{\sqrt{2}} & i & \frac{-1+i}{\sqrt{2}} & -1 & \frac{-1-i}{\sqrt{2}} & -i & \frac{1-i}{\sqrt{2}}\\[2mm] 1 & i & -1 & -i & 1 & i & -1 & -i\\[2mm] 1 & \frac{-1+i}{\sqrt{2}} & -i & \frac{1+i}{\sqrt{2}} & -1 & \frac{1-i}{\sqrt{2}} & i & \frac{-1-i}{\sqrt{2}}\\[2mm] 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\[2mm] 1 & \frac{-1-i}{\sqrt{2}} & i & \frac{1-i}{\sqrt{2}} & -1 & \frac{1+i}{\sqrt{2}} & -i & \frac{-1+i}{\sqrt{2}}\\[2mm] 1 & -i & -1 & i & 1 & -i & -1 & i\\[2mm] 1 & \frac{1-i}{\sqrt{2}} & -i & \frac{-1-i}{\sqrt{2}} & -1 & \frac{-1+i}{\sqrt{2}} & i & \frac{1+i}{\sqrt{2}}\\[2mm] \end{pmatrix}$$

Beachte insbesondere, dass $\mathrm{QFT}_2$ ein anderer Name für die Hadamard-Operation ist.

Unitarität

Überprüfen wir, dass $\mathrm{QFT}_N$ für jede Wahl von $N$ unitär ist. Eine Möglichkeit dazu besteht darin, zu zeigen, dass seine Spalten eine Orthonormalbasis bilden. Wir können einen Vektor definieren, der der Spalte mit der Nummer $y$ entspricht, beginnend bei $y = 0$ und bis $y = N-1$, wie folgt:

$$\vert\phi_y\rangle = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \omega_N^{xy} \vert x \rangle.$$

Das innere Produkt zweier beliebiger dieser Vektoren ergibt den folgenden Ausdruck:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \sum_{x = 0}^{N-1} \omega_N^{x (y - z)}$$

Solche Summen lassen sich mithilfe der folgenden Formel für die Summe der ersten $N$ Glieder einer geometrischen Reihe berechnen.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

Insbesondere können wir diese Formel mit $\alpha = \omega_N^{y-z}$ anwenden. Für $y = z$ gilt $\alpha = 1$, und die Formel liefert nach Division durch $N$:

$$\langle \phi_y \vert \phi_y \rangle = 1.$$

Für $y\neq z$ gilt $\alpha \neq 1$, und die Formel ergibt:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \frac{\omega_N^{N(y-z)} - 1}{\omega_N^{y-z} - 1} = \frac{1}{N} \frac{1 - 1}{\omega_N^{y-z} - 1} = 0.$$

Das liegt daran, dass $\omega_N^N = e^{2\pi i} = 1$, also $\omega_N^{N(y-z)} = 1^{y-z} = 1$, was den Zähler zu null macht, während der Nenner von null verschieden ist, da $\omega_N^{y-z} \neq 1$. Anschaulich gesprochen summieren wir dabei eine Reihe von Punkten, die über den Einheitskreis verteilt sind – sie heben sich gegenseitig auf und ergeben $0$.

Wir haben damit gezeigt, dass $\{\vert\phi_0\rangle,\ldots,\vert\phi_{N-1}\rangle\}$ eine Orthonormalmenge ist,

$$\langle \phi_z \vert \phi_y \rangle = \begin{cases} 1 & y=z\\ 0 & y\neq z, \end{cases}$$

was zeigt, dass $\mathrm{QFT}_N$ unitär ist.

Kontrollierte Phasengatter

Um die Quanten-Fourier-Transformation mit einem Quantenschaltkreis zu implementieren, benötigen wir kontrollierte Phasengatter. Zur Erinnerung: Eine Phasenoperation ist eine unitäre Einqubit-Operation der Form

$$P_{\alpha} = \begin{pmatrix} 1 & 0\\[1mm] 0 & e^{i\alpha} \end{pmatrix}$$

für eine beliebige reelle Zahl $\alpha$. Die kontrollierte Version dieses Gatters hat die folgende Matrix:

$$CP_{\alpha} = \begin{pmatrix} 1 & 0 & 0 & 0\\[1mm] 0 & 1 & 0 & 0\\[1mm] 0 & 0 & 1 & 0\\[1mm] 0 & 0 & 0 & e^{i\alpha} \end{pmatrix}$$

Bei diesem kontrollierten Gatter spielt es keine Rolle, welches Qubit das Kontroll-Qubit und welches das Ziel-Qubit ist, da beide Möglichkeiten äquivalent sind. In Quantenschaltkreis-Diagrammen kann dieses Gatter durch eines der folgenden Symbole dargestellt werden.

Bei der dritten Form wird die Bezeichnung $\alpha$ manchmal auch seitlich an der Kontrolllinie oder unter dem unteren Kontrollpunkt platziert, wenn das praktischer ist.

Um die Quanten-Fourier-Transformation für $N = 2^m$ mit $m\geq 2$ durchzuführen, müssen wir eine Operation auf $m$ Qubits ausführen, deren Wirkung auf Standardbasiszustände wie folgt beschrieben werden kann:

$$\vert y \rangle \vert a \rangle \mapsto \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle,$$

wobei $a$ ein Bit ist und $y \in \{0,\ldots,2^{m-1} - 1\}$ eine Zahl ist, die in Binärdarstellung als eine Zeichenkette von $m-1$ Bits kodiert ist. Dies lässt sich mithilfe kontrollierter Phasengatter realisieren, indem das folgende Beispiel für $m=5$ verallgemeinert wird.

Allgemein kann für eine beliebige Wahl von $m\geq 2$ das oberste Qubit, das dem Bit $a$ entspricht, als Kontroll-Qubit betrachtet werden, wobei die Phasengatter $P_{\alpha}$ von $\alpha = \pi/2^{m-1}$ am Qubit des niedrigstwertigen Bits von $y$ bis $\alpha = \frac{\pi}{2}$ am Qubit des höchstwertigen Bits von $y$ reichen. Diese kontrollierten Phasengatter kommutieren alle miteinander und können in beliebiger Reihenfolge ausgeführt werden.

Schaltkreisimplementierung der QFT

Jetzt sehen wir, wie die Quanten-Fourier-Transformation mit einem Schaltkreis implementiert werden kann, wenn die Dimension $N = 2^m$ eine Zweierpotenz ist. Es gibt tatsächlich mehrere Möglichkeiten, die Quanten-Fourier-Transformation zu implementieren, aber dies ist wohl die einfachste bekannte Methode. Sobald wir wissen, wie die Quanten-Fourier-Transformation mit einem Quantenschaltkreis implementiert wird, ist die Implementierung ihrer Inversen unkompliziert: Wir können jedes Gatter durch seine Inverse (bzw. konjugierte Transponierte) ersetzen und die Gatter in umgekehrter Reihenfolge anwenden. Jeder Quantenschaltkreis, der ausschließlich aus unitären Gattern besteht, kann auf diese Weise invertiert werden.

Die Implementierung ist rekursiver Natur, weshalb sie am natürlichsten so beschrieben wird. Der Basisfall ist $m=1$, in dem die Quanten-Fourier-Transformation einer Hadamard-Operation entspricht.

Um die Quanten-Fourier-Transformation auf $m$ Qubits für $m \geq 2$ durchzuführen, können wir die folgenden Schritte ausführen, deren Wirkung wir für Standardbasiszustände der Form $\vert x \rangle \vert a\rangle$ beschreiben, wobei $x\in\{0,\ldots,2^{m-1} - 1\}$ eine ganze Zahl ist, die als $m-1$ Bits in Binärdarstellung kodiert ist, und $a$ ein einzelnes Bit ist.

1. Zuerst wird die $2^{m-1}$-dimensionale Quanten-Fourier-Transformation auf die unteren/linken $m-1$ Qubits angewendet, um diesen Zustand zu erhalten:

   $$\Bigl(\mathrm{QFT}_{2^{m-1}} \vert x \rangle\Bigr) \vert a\rangle = \frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \vert y \rangle \vert a \rangle.$$

   Dies geschieht durch rekursive Anwendung der hier beschriebenen Methode für ein Qubit weniger, mit der Hadamard-Operation auf einem einzelnen Qubit als Basisfall.

2. Das obere/rechteste Qubit wird als Kontroll-Qubit genutzt, um die Phase $\omega_{2^m}^y$ für jeden Standardbasiszustand $\vert y\rangle$ der verbleibenden $m-1$ Qubits einzuspeisen (wie oben beschrieben), um diesen Zustand zu erhalten:

   $$\frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle.$$

3. Ein Hadamard-Gatter wird auf das obere/rechteste Qubit angewendet, um diesen Zustand zu erhalten:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert b \rangle.$$

4. Die Reihenfolge der Qubits wird so permutiert, dass das niedrigstwertige Bit zum höchstwertigen Bit wird und alle anderen nach oben/rechts verschoben werden:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b \rangle \vert y \rangle.$$

Hier ist zum Beispiel der Schaltkreis, den wir für $N = 32 = 2^5$ erhalten. In diesem Diagramm werden die Qubits mit Namen versehen, die den Standardbasisvektoren $\vert x\rangle \vert a\rangle$ (für die Eingabe) und $\vert b\rangle \vert y\rangle$ (für die Ausgabe) entsprechen, um die Übersichtlichkeit zu erhöhen.

Analyse

Die Schlüsselformel, die wir benötigen, um zu überprüfen, dass der soeben beschriebene Schaltkreis die $2^m$-dimensionale Quanten-Fourier-Transformation implementiert, lautet:

$$(-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} = \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)}.$$

Diese Formel gilt für beliebige ganze Zahlen $a$, $b$, $x$ und $y$, wird aber nur für $a,b\in\{0,1\}$ und $x,y\in\{0,\ldots,2^{m-1}-1\}$ benötigt. Sie lässt sich durch Ausmultiplizieren des Produkts im Exponenten auf der rechten Seite überprüfen:

$$\omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} = \omega_{2^m}^{2^m xb} \omega_{2^m}^{2xy} \omega_{2^m}^{2^{m-1}ab} \omega_{2^m}^{ay} = (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay},$$

wobei die zweite Gleichheit die Beobachtung nutzt, dass

$$\omega_{2^m}^{2^m xb} = \bigl(\omega_{2^m}^{2^m}\bigr)^{xb} = 1^{xb} = 1.$$

Die $2^m$-dimensionale Quanten-Fourier-Transformation ist für jedes $u\in\{0,\ldots,2^m - 1\}$ wie folgt definiert.

$$\mathrm{QFT}_{2^m} \vert u\rangle = \frac{1}{\sqrt{2^m}} \sum_{v = 0}^{2^m - 1} \omega_{2^m}^{uv} \vert v\rangle$$

Schreiben wir $u$ und $v$ als

$$\begin{aligned} u & = 2x + a\\ v & = 2^{m-1}b + y \end{aligned}$$

für $a,b\in\{0,1\}$ und $x,y\in\{0,\ldots,2^{m-1} - 1\}$, so ergibt sich

$$\begin{aligned} \mathrm{QFT}_{2^m} \vert 2x + a\rangle & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} \vert b 2^{m-1} + y\rangle\\[2mm] & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b 2^{m-1} + y\rangle. \end{aligned}$$

Wenn wir schließlich die Standardbasiszustände $\vert x \rangle \vert a\rangle$ und $\vert b \rangle \vert y \rangle$ als Binärkodierungen ganzer Zahlen im Bereich $\{0,\ldots,2^m-1\}$ betrachten,

$$\begin{aligned} \vert x \rangle \vert a\rangle & = \vert 2x + a \rangle\\ \vert b \rangle \vert y \rangle & = \vert 2^{m-1}b + y\rangle, \end{aligned}$$

erkennen wir, dass der obige Schaltkreis die gewünschte Operation implementiert. Falls diese Methode zur Durchführung der Quanten-Fourier-Transformation bemerkenswert erscheint — das ist sie auch: Sie ist im Wesentlichen die schnelle Fourier-Transformation in Form eines Quantenschaltkreises.

Zum Abschluss zählen wir, wie viele Gatter der beschriebene Schaltkreis verwendet. Die kontrollierten Phasengatter gehören nicht zum Standardgattersatz, den wir in der vorherigen Lektion besprochen haben, aber zunächst ignorieren wir das und zählen jedes von ihnen als ein einzelnes Gatter.

Sei $s_m$ die Anzahl der Gatter, die für jede mögliche Wahl von $m$ benötigt werden. Für $m=1$ ist die Quanten-Fourier-Transformation nur eine Hadamard-Operation, also gilt

$$s_1 = 1.$$

Für $m\geq 2$ benötigen wir im obigen Schaltkreis $s_{m-1}$ Gatter für die Quanten-Fourier-Transformation auf $m-1$ Qubits, plus $m-1$ kontrollierte Phasengatter, plus ein Hadamard-Gatter, plus $m-1$ Swap-Gatter, also gilt

$$s_m = s_{m-1} + (2m - 1).$$

Durch Summation erhalten wir einen geschlossenen Ausdruck:

$$s_m = \sum_{k = 1}^m (2k - 1) = m^2.$$

Tatsächlich benötigen wir nicht so viele Swap-Gatter, wie die Methode es beschreibt. Wenn wir die Gatter etwas umordnen, können wir alle Swap-Gatter nach rechts schieben und die Anzahl der benötigten Swap-Gatter auf $\lfloor m/2\rfloor$ reduzieren. Asymptotisch gesehen ist das keine wesentliche Verbesserung: Wir erhalten nach wie vor Schaltkreise der Größe $O(m^2)$ für die Berechnung von $\mathrm{QFT}_{2^m}$.

Wenn wir die Quanten-Fourier-Transformation ausschließlich mit Gattern aus unserem Standardgattersatz implementieren möchten, müssen wir jedes kontrollierte Phasengatter entweder exakt aufbauen oder durch Gatter aus unserem Satz approximieren. Die benötigte Anzahl hängt davon ab, wie viel Genauigkeit wir fordern, aber als Funktion von $m$ bleibt der Gesamtaufwand quadratisch.

Tatsächlich ist es möglich, die Quanten-Fourier-Transformation mit einer subquadratischen Anzahl von Gattern sehr gut zu approximieren, indem man sich zunutze macht, dass $P_{\alpha}$ der Identitätsoperation sehr nahe kommt, wenn $\alpha$ sehr klein ist — was bedeutet, dass wir die meisten kontrollierten Phasengatter einfach weglassen können, ohne dabei zu viel an Genauigkeit einzubüßen.

Allgemeines Verfahren und Analyse

Nun untersuchen wir das Phasenschätzungsverfahren im Allgemeinen. Die Idee besteht darin, die Zweiqubit-Version der Phasenschätzung, die wir oben betrachtet haben, auf die naheliegende Weise zu verallgemeinern, wie das folgende Diagramm zeigt.

Beachte, dass für jedes neu hinzugefügte Kontroll-Qubit oben die Anzahl der Ausführungen der unitären Operation $U$ verdoppelt wird. Dies wird im Diagramm durch die Potenzen von $U$ bei den einzelnen kontrollierten unitären Operationen angezeigt.

Die naheliegendste Methode, eine kontrollierte $U^k$-Operation für eine Wahl von $k$ zu implementieren, besteht darin, eine kontrollierte $U$-Operation einfach $k$-mal zu wiederholen. Wenn diese Methode tatsächlich verwendet wird, ist zu beachten, dass das Hinzufügen von Kontroll-Qubits die Größe des Schaltkreises erheblich beeinflusst: Wenn wir $m$ Kontroll-Qubits haben, wie im Diagramm dargestellt, sind insgesamt $2^m - 1$ Kopien der kontrollierten $U$-Operation erforderlich. Das bedeutet, dass mit zunehmendem $m$ ein erheblicher Rechenaufwand entsteht — aber wie wir sehen werden, führt dies auch zu einer deutlich genaueren Approximation von $\theta$.

Es ist jedoch wichtig zu beachten, dass es für bestimmte Wahlen von $U$ möglich sein kann, einen Schaltkreis zu erstellen, der die Operation $U^k$ für große Werte von $k$ effizienter implementiert, als einfach den Schaltkreis für $U$ $k$-mal zu wiederholen. Wir werden ein konkretes Beispiel dafür im Kontext der ganzzahligen Faktorisierung später in dieser Lektion sehen, wo der effiziente Algorithmus für die modulare Exponentiation, der in der vorherigen Lektion behandelt wurde, zu Hilfe kommt.

Nun analysieren wir den soeben beschriebenen Schaltkreis. Der Zustand unmittelbar vor der inversen Quanten-Fourier-Transformation sieht wie folgt aus:

$$\frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \bigl( U^x \vert\psi\rangle \bigr) \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i x\theta} \vert x\rangle.$$

Ein Sonderfall

Ähnlich wie bei der $m=2$-Version betrachten wir zunächst den Sonderfall, dass $\theta = y/2^m$ für $y\in\{0,\ldots,2^m-1\}$. In diesem Fall kann der Zustand vor der inversen Quanten-Fourier-Transformation alternativ wie folgt geschrieben werden:

$$\vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i \frac{xy}{2^m}} \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \omega_{2^m}^{xy} \vert x\rangle = \vert\psi\rangle \otimes \mathrm{QFT}_{2^m} \vert y\rangle.$$

Nach Anwendung der inversen Quanten-Fourier-Transformation wird der Zustand zu

$$\vert\psi\rangle \vert y\rangle$$

und die Messungen ergeben $y$ (in Binärkodierung).

Abschätzung der Wahrscheinlichkeiten

Für andere Werte von $\theta$, also solche, die nicht die Form $y/2^m$ für eine ganze Zahl $y$ haben, sind die Messergebnisse nicht mit Sicherheit vorhersagbar, aber wir können Schranken für die Wahrscheinlichkeiten verschiedener Ergebnisse beweisen. Im Folgenden betrachten wir eine beliebige Wahl von $\theta$ mit $0\leq \theta < 1$.

Nach Anwendung der inversen Quanten-Fourier-Transformation befindet sich der Schaltkreis im Zustand:

$$\vert \psi \rangle \otimes \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (\theta - y/2^m)} \vert y\rangle.$$

Bei der Messung der oberen $m$ Qubits tritt jedes Ergebnis $y$ mit der Wahrscheinlichkeit

$$p_y = \left\vert \frac{1}{2^m} \sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} \right\vert^2.$$

Um diese Wahrscheinlichkeiten besser in den Griff zu bekommen, verwenden wir dieselbe Formel wie zuvor, für die Summe des Anfangsabschnitts einer geometrischen Reihe.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

Wir können die Summe, die in der Formel für $p_y$ auftritt, vereinfachen, indem wir $\alpha = e^{2\pi i (\theta - y/2^m)}$ setzen. Hier ist, was wir erhalten.

$$\sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} = \begin{cases} 2^m & \theta = y/2^m\\[2mm] \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1} & \theta\neq y/2^m \end{cases}$$

Im Fall $\theta = y/2^m$ stellen wir also fest, dass $p_y = 1$ ist (wie wir bereits durch die Betrachtung dieses Sonderfalls wussten), und im Fall $\theta \neq y/2^m$ stellen wir fest, dass

$$p_y = \frac{1}{2^{2m}} \left\vert \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1}\right\vert^2.$$

Wir können mehr über diese Wahrscheinlichkeiten erfahren, indem wir darüber nachdenken, wie Bogenlängen und Sehnenlängen auf dem Einheitskreis zusammenhängen. Hier ist eine Abbildung, die die Beziehungen veranschaulicht, die wir für jede reelle Zahl $\delta\in \bigl[ -\frac{1}{2},\frac{1}{2}\bigr]$ benötigen.

Zunächst kann die Sehnenlänge (blau eingezeichnet) unmöglich größer sein als die Bogenlänge (violett eingezeichnet):

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \leq 2\pi\vert\delta\vert.$$

Wenn wir diese Längen in die andere Richtung in Beziehung setzen, sehen wir, dass das Verhältnis von Bogenlänge zu Sehnenlänge am größten ist, wenn $\delta = \pm 1/2$ ist, und in diesem Fall ist das Verhältnis der halbe Umfang des Kreises geteilt durch den Durchmesser, also $\pi/2$. Somit erhalten wir

$$\frac{2\pi\vert\delta\vert}{\bigl\vert e^{2\pi i \delta} - 1\bigr\vert} \leq \frac{\pi}{2},$$

und somit

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \geq 4\vert\delta\vert.$$

Eine Analyse auf Grundlage dieser Beziehungen offenbart die folgenden zwei Tatsachen.

1. Angenommen, $\theta$ ist eine reelle Zahl und $y\in \{0,\ldots,2^m-1\}$ erfüllt

   $$\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq 2^{-(m+1)}.$$

   Das bedeutet, dass $y/2^m$ entweder die beste $m$-Bit-Approximation von $\theta$ ist, oder dass sie genau auf halbem Weg zwischen $y/2^m$ und entweder $(y-1)/2^m$ oder $(y+1)/2^m$ liegt — also eine der beiden besten Approximationen von $\theta$ darstellt.

   Wir werden zeigen, dass $p_y$ in diesem Fall recht groß sein muss. Aus der betrachteten Annahme folgt, dass $\vert 2^m \theta - y \vert \leq 1/2$, sodass wir die zweite Beobachtung über Bogen- und Sehnenlängen anwenden können, um zu schließen:

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \geq 4 \vert 2^m \theta - y \vert = 4 \cdot 2^m \cdot \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   Wir können außerdem die erste Beobachtung über Bogen- und Sehnenlängen nutzen, um zu schließen:

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \leq 2\pi \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   Aus diesen beiden Ungleichungen ergibt sich für $p_y$:

   $$p_y \geq \frac{1}{2^{2m}} \frac{16 \cdot 2^{2m}}{4 \pi^2} = \frac{4}{\pi^2} \approx 0.405.$$

   Das erklärt unsere Beobachtung, dass das beste Ergebnis bei der $m=2$-Version der Phasenschätzung mit einer Wahrscheinlichkeit von mehr als $40\%$ auftritt. Genau genommen sind es nicht $40\%$, sondern $4/\pi^2$, und diese Schranke gilt für jede Wahl von $m$.

2. Angenommen nun, dass $y\in \{0,\ldots,2^m-1\}$ folgendes erfüllt:

   $$2^{-m} \leq \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq \frac{1}{2}.$$

   Das bedeutet, dass es eine bessere Approximation $z/2^m$ von $\theta$ gibt, die zwischen $\theta$ und $y/2^m$ liegt.

   Diesmal zeigen wir, dass $p_y$ nicht zu groß sein kann. Wir beginnen mit der einfachen Beobachtung, dass

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \leq 2,$$

   was aus der Tatsache folgt, dass zwei beliebige Punkte auf dem Einheitskreis im Absolutbetrag höchstens $2$ voneinander entfernt sein können.

   Wir können außerdem die zweite Beobachtung über Bogen- und Sehnenlängen von oben anwenden, diesmal auf den Nenner von $p_y$ statt den Zähler, um zu schließen:

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \geq 4\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \geq 4 \cdot 2^{-m}.$$

   Zusammen ergeben die beiden Ungleichungen:

   $$p_y \leq \frac{1}{2^{2m}} \frac{4}{16 \cdot 2^{-2m}} = \frac{1}{4}.$$

   Diese Schranke ist zwar für unsere Zwecke ausreichend, aber recht grob — die Wahrscheinlichkeit ist in der Regel deutlich kleiner als $1/4$.

Die wichtigste Erkenntnis aus dieser Analyse ist, dass sehr gute Approximationen von $\theta$ mit hoher Wahrscheinlichkeit auftreten — wir erhalten eine beste $m$-Bit-Approximation mit einer Wahrscheinlichkeit von über $40\%$ — während Approximationen, die um mehr als $2^{-m}$ abweichen, seltener auftreten, mit einer Wahrscheinlichkeit von höchstens $25\%$.

Angesichts dieser Garantien ist es möglich, das Vertrauen in das Ergebnis zu erhöhen, indem das Phasenschätzungsverfahren mehrfach wiederholt wird, um statistische Belege über $\theta$ zu sammeln. Wichtig ist dabei, dass der Zustand $\vert\psi\rangle$ der unteren Qubit-Gruppe durch das Phasenschätzungsverfahren unverändert bleibt und daher für beliebig viele Durchläufe des Verfahrens verwendet werden kann. Insbesondere erhalten wir bei jedem Durchlauf des Schaltkreises eine beste $m$-Bit-Approximation von $\theta$ mit einer Wahrscheinlichkeit von über $40\%$, während die Wahrscheinlichkeit einer Abweichung um mehr als $2^{-m}$ durch $25\%$ nach oben begrenzt ist. Führen wir den Schaltkreis mehrmals aus und nehmen das am häufigsten auftretende Ergebnis, so ist es höchst unwahrscheinlich, dass dieses am häufigsten auftretende Ergebnis eines ist, das höchstens $25\%$ der Zeit vorkommt. Infolgedessen werden wir mit sehr hoher Wahrscheinlichkeit eine Approximation $y/2^m$ erhalten, die von $\theta$ um weniger als $1/2^m$ abweicht. Die Wahrscheinlichkeit, um mehr als $1/2^m$ danebenzuliegen, nimmt tatsächlich exponentiell mit der Anzahl der Durchläufe des Verfahrens ab.

Hier sind zwei Diagramme, die die Wahrscheinlichkeiten für drei aufeinanderfolgende Werte von $y$ bei $m = 3$ und $m=4$ als Funktionen von $\theta$ zeigen. (Aus Gründen der Übersichtlichkeit werden nur drei Ergebnisse dargestellt. Die Wahrscheinlichkeiten für andere Ergebnisse erhält man durch zyklische Verschiebung derselben Grundfunktion.)