Das Phasenschätzungsproblem

Dieser Abschnitt der Lektion erläutert das Phasenschätzungsproblem. Wir beginnen mit einer kurzen Besprechung des Spektralsatzes aus der linearen Algebra und gehen dann zur Formulierung des Phasenschätzungsproblems selbst über.

Spektralsatz

Der Spektralsatz ist ein wichtiges Ergebnis der linearen Algebra, das besagt, dass Matrizen eines bestimmten Typs – sogenannte normale Matrizen – auf eine einfache und nützliche Weise dargestellt werden können. Wir benötigen diesen Satz in dieser Lektion nur für unitäre Matrizen, aber später in dieser Reihe werden wir ihn auch auf hermitesche Matrizen anwenden.

Normale Matrizen

Eine quadratische Matrix $M$ mit komplexen Einträgen heißt normale Matrix, wenn sie mit ihrer konjugierten Transponierten kommutiert: $M M^{\dagger} = M^{\dagger} M.$

Jede unitäre Matrix $U$ ist normal, weil

$$U U^{\dagger} = \mathbb{I} = U^{\dagger} U.$$

Hermitesche Matrizen, also Matrizen, die ihrer eigenen konjugierten Transponierten gleichen, sind eine weitere wichtige Klasse normaler Matrizen. Wenn $H$ eine hermitesche Matrix ist, dann gilt

$$H H^{\dagger} = H^2 = H^{\dagger} H,$$

also ist $H$ normal.

Nicht jede quadratische Matrix ist normal. Zum Beispiel ist diese Matrix nicht normal:

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}$$

(Dies ist ein einfaches, aber großartiges Beispiel einer Matrix, die oft sehr hilfreich zu betrachten ist.) Sie ist nicht normal, weil

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}^{\dagger} = \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0\\ 0 & 0 \end{pmatrix}$$

während

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}^{\dagger} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0\\ 0 & 1 \end{pmatrix}.$$

Satzformulierung

Hier ist eine Formulierung des Spektralsatzes.

Satz

Spektralsatz: Sei $M$ eine normale $N\times N$ komplexe Matrix. Es existiert eine orthonormale Basis $N$-dimensionaler komplexer Vektoren $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ sowie komplexe Zahlen $\lambda_1,\ldots,\lambda_N$ sodass

$$M = \lambda_1 \vert \psi_1\rangle\langle \psi_1\vert + \cdots + \lambda_N \vert \psi_N\rangle\langle \psi_N\vert.$$

Die Darstellung einer Matrix in der Form

$$M = \sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert \tag{1}$$

wird allgemein als Spektralzerlegung bezeichnet. Beachte: Wenn $M$ eine normale Matrix ist, die in der Form $(1)$ ausgedrückt wird, dann muss die Gleichung

$$M \vert \psi_j \rangle = \lambda_j \vert \psi_j \rangle$$

für jedes $j = 1,\ldots,N$ gelten. Das folgt aus der Tatsache, dass $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ orthonormal ist:

$$M \vert \psi_j \rangle = \left(\sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert\right)\vert \psi_j\rangle = \sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert\psi_j \rangle = \lambda_j \vert\psi_j \rangle$$

Das heißt, jede Zahl $\lambda_j$ ist ein Eigenwert von $M$ und $\vert\psi_j\rangle$ ist ein Eigenvektor, der zu diesem Eigenwert gehört.

• Beispiel 1. Sei

  $$\mathbb{I} = \begin{pmatrix}1 & 0\\0 & 1\end{pmatrix},$$

  die normal ist. Der Satz impliziert, dass $\mathbb{I}$ in der Form $(1)$ für eine geeignete Wahl von $\lambda_1,$ $\lambda_2,$ $\vert\psi_1\rangle$ und $\vert\psi_2\rangle$ geschrieben werden kann. Es gibt mehrere Möglichkeiten, darunter

  $$\lambda_1 = 1, \hspace{5pt} \lambda_2 = 1, \hspace{5pt} \vert\psi_1\rangle = \vert 0\rangle, \hspace{5pt} \vert\psi_2\rangle = \vert 1\rangle.$$

  Beachte, dass der Satz nicht besagt, dass die komplexen Zahlen $\lambda_1,\ldots,\lambda_N$ verschieden sein müssen – dieselbe komplexe Zahl kann mehrfach auftreten, was in diesem Beispiel notwendig ist. Diese Wahl funktioniert, weil

  $$\mathbb{I} = \vert 0\rangle\langle 0\vert + \vert 1\rangle\langle 1\vert.$$

  Tatsächlich könnten wir $\{\vert\psi_1\rangle,\vert\psi_2\rangle\}$ als beliebige orthonormale Basis wählen, und die Gleichung würde gelten. Zum Beispiel:

  $$\mathbb{I} = \vert +\rangle\langle +\vert + \vert -\rangle\langle -\vert.$$

• Beispiel 2. Betrachte eine Hadamard-Operation.

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

  Das ist eine unitäre Matrix, also ist sie normal. Der Spektralsatz impliziert, dass $H$ in der Form $(1)$ geschrieben werden kann, und insbesondere gilt

  $$H = \vert\psi_{\pi/8}\rangle \langle \psi_{\pi/8}\vert - \vert\psi_{5\pi/8}\rangle \langle \psi_{5\pi/8}\vert$$

  wobei

  $$\vert\psi_{\theta}\rangle = \cos(\theta)\vert 0\rangle + \sin(\theta) \vert 1\rangle.$$

  Expliziter:

  $$\begin{aligned} \vert\psi_{\pi/8}\rangle & = \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 - \sqrt{2}}}{2}\vert 1\rangle, \\[3mm] \vert\psi_{5\pi/8}\rangle & = -\frac{\sqrt{2 - \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 1\rangle. \end{aligned}$$

  Wir können überprüfen, dass diese Zerlegung korrekt ist, indem wir die erforderlichen Berechnungen durchführen:

  $$\vert\psi_{\pi/8}\rangle \langle \psi_{\pi/8}\vert - \vert\psi_{5\pi/8}\rangle \langle \psi_{5\pi/8}\vert = \begin{pmatrix} \frac{2 + \sqrt{2}}{4} & \frac{\sqrt{2}}{4}\\[2mm] \frac{\sqrt{2}}{4} & \frac{2 - \sqrt{2}}{4} \end{pmatrix} - \begin{pmatrix} \frac{2 - \sqrt{2}}{4} & -\frac{\sqrt{2}}{4}\\[2mm] -\frac{\sqrt{2}}{4} & \frac{2 + \sqrt{2}}{4} \end{pmatrix} = H.$$

Wie das erste Beispiel oben zeigt, kann es bei der Wahl der Eigenvektoren einige Freiheit geben. Bei der Wahl der Eigenwerte gibt es jedoch überhaupt keine Freiheit, abgesehen von ihrer Reihenfolge: Für eine gegebene Matrix $M$ treten in Gleichung $(1)$ immer dieselben $N$ komplexen Zahlen $\lambda_1,\ldots,\lambda_N$ auf, die Wiederholungen derselben komplexen Zahl enthalten können.

Konzentrieren wir uns nun auf unitäre Matrizen. Nehmen wir an, wir haben eine komplexe Zahl $\lambda$ und einen Nicht-Null-Vektor $\vert\psi\rangle$, die die Gleichung

$$U\vert\psi\rangle = \lambda\vert\psi\rangle \tag{2}$$

erfüllen.

Das heißt, $\lambda$ ist ein Eigenwert von $U$ und $\vert\psi\rangle$ ist ein Eigenvektor, der zu diesem Eigenwert gehört.

Unitäre Matrizen erhalten die euklidische Norm, und daher schließen wir aus $(2)$ Folgendes.

$$\bigl\| \vert\psi\rangle \bigr\| = \bigl\| U \vert\psi\rangle \bigr\| = \bigl\| \lambda \vert\psi\rangle \bigr\| = \vert \lambda \vert \bigl\| \vert\psi\rangle \bigr\|$$

Die Bedingung, dass $\vert\psi\rangle$ nicht null ist, impliziert, dass $\bigl\| \vert\psi\rangle \bigr\|\neq 0$, sodass wir auf beiden Seiten kürzen können und erhalten:

$$\vert \lambda \vert = 1.$$

Das zeigt, dass Eigenwerte unitärer Matrizen stets den Betrag eins haben und daher auf dem Einheitskreis liegen.

$$\mathbb{T} = \{\alpha\in\mathbb{C} : \vert\alpha\vert = 1\}$$

(Das Symbol $\mathbb{T}$ ist ein gebräuchlicher Name für den komplexen Einheitskreis. Der Name $S^1$ ist ebenfalls verbreitet.)

Problemstellung der Phasenschätzung

Beim Phasenschätzungsproblem wird ein Quantenzustand $\vert \psi\rangle$ von $n$ Qubits zusammen mit einem unitären Quantencircuit gegeben, der auf $n$ Qubits wirkt. Es wird versprochen, dass $\vert \psi\rangle$ ein Eigenvektor der unitären Matrix $U$ ist, die die Wirkung des Circuits beschreibt, und unser Ziel ist es, den Eigenwert $\lambda$, dem $\vert \psi\rangle$ entspricht, zu berechnen oder zu approximieren. Da $\lambda$ auf dem komplexen Einheitskreis liegt, können wir

$$\lambda = e^{2\pi i \theta}$$

für eine eindeutige reelle Zahl $\theta$ mit $0\leq\theta<1$ schreiben. Das Ziel des Problems ist es, diese reelle Zahl $\theta$ zu berechnen oder zu approximieren.

Phasenschätzungsproblem

Eingabe: Ein unitärer Quantencircuit für eine $n$-Qubit-Operation $U$ sowie ein $n$-Qubit-Quantenzustand $\vert\psi\rangle$
Versprechen: $\vert\psi\rangle$ ist ein Eigenvektor von $U$
Ausgabe: eine Approximation der Zahl $\theta\in[0,1)$ mit $U\vert\psi\rangle = e^{2\pi i \theta}\vert\psi\rangle$

Hier sind einige Anmerkungen zu dieser Problemformulierung:

1. Das Phasenschätzungsproblem unterscheidet sich von anderen bisher im Kurs behandelten Problemen darin, dass die Eingabe einen Quantenzustand umfasst. Normalerweise konzentrieren wir uns auf Probleme mit klassischen Ein- und Ausgaben, aber nichts hindert uns daran, Quantenzustände als Eingaben zu betrachten. Hinsichtlich seiner praktischen Relevanz tritt das Phasenschätzungsproblem typischerweise als Teilproblem innerhalb einer größeren Berechnung auf, wie wir es später in der Lektion im Kontext der ganzzahligen Faktorisierung sehen werden.

2. Die obige Formulierung des Phasenschätzungsproblems ist nicht spezifisch darüber, was eine Approximation von $\theta$ ausmacht, aber wir können je nach unseren Bedürfnissen und Interessen präzisere Problemformulierungen festlegen. Im Kontext der ganzzahligen Faktorisierung fordern wir eine sehr genaue Approximation von $\theta$, aber in anderen Fällen könnte uns eine sehr grobe Approximation genügen. Wir werden kurz darauf eingehen, wie die geforderte Genauigkeit die Berechnungskosten einer Lösung beeinflusst.

3. Beachte: Wenn wir im Phasenschätzungsproblem von $\theta = 0$ in Richtung $\theta = 1$ gehen, umrunden wir den Einheitskreis vollständig, beginnend bei $e^{2\pi i \cdot 0} = 1$ und bewegend uns gegen den Uhrzeigersinn in Richtung $e^{2\pi i \cdot 1} = 1$. Das heißt, wenn wir $\theta = 1$ erreichen, sind wir wieder dort, wo wir bei $\theta = 0$ angefangen haben. Wenn wir also die Genauigkeit von Approximationen beurteilen, sollten Werte von $\theta$ nahe $1$ als nahe an $0$ betrachtet werden. Zum Beispiel sollte eine Approximation $\theta = 0{,}999$ als innerhalb von $1/1000$ von $\theta = 0$ liegend betrachtet werden.