Simons Algorithmus

Simons Algorithmus ist ein Quanten-Abfragealgorithmus für ein Problem, das als Simons Problem bekannt ist. Es ist ein Promise-Problem mit einer ähnlichen Grundstruktur wie die Deutsch-Jozsa- und Bernstein-Vazirani-Probleme, aber mit anderen Einzelheiten.

Simons Algorithmus ist bedeutsam, weil er einen exponentiellen Vorteil von Quanten- gegenüber klassischen (einschließlich probabilistischen) Algorithmen bietet, und die darin verwendete Technik inspirierte Peter Shor zur Entdeckung eines effizienten Quantenalgorithmus für die ganzzahlige Faktorisierung.

Simons Problem

Die Eingabefunktion für Simons Problem hat die Form

$$f:\Sigma^n \rightarrow \Sigma^m$$

für positive ganze Zahlen $n$ und $m$. Wir könnten uns auf den Fall $m = n$ beschränken, aber es gibt kaum etwas zu gewinnen, wenn wir diese Annahme machen – Simons Algorithmus und seine Analyse sind in beiden Fällen im Wesentlichen gleich.

Simons Problem

Eingabe: eine Funktion $f:\Sigma^n \rightarrow \Sigma^m$
Versprechen: Es existiert eine Zeichenkette $s\in\Sigma^n$ sodass $[f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)]$ für alle $x,y\in\Sigma^n$ gilt
Ausgabe: die Zeichenkette $s$

Wir werden das Versprechen gleich entpacken, um besser zu verstehen, was es besagt, aber zunächst sollte klar sein, dass es erfordert, dass $f$ eine sehr spezielle Struktur hat – also werden die meisten Funktionen dieses Versprechen nicht erfüllen. Es ist auch angemessen anzuerkennen, dass dieses Problem nicht für seine praktische Bedeutung gedacht ist. Vielmehr ist es ein etwas künstliches Problem, das maßgeschneidert ist, um für Quantencomputer einfach und für klassische Computer schwer zu sein.

Es gibt zwei Hauptfälle: Der erste Fall ist, dass $s$ die Null-Zeichenkette $0^n$ ist, und der zweite Fall ist, dass $s$ nicht die Null-Zeichenkette ist.

• Fall 1: $s=0^n.$ Wenn $s$ die Null-Zeichenkette ist, können wir die Genau-dann-Aussage im Versprechen vereinfachen, sodass sie lautet: $[f(x) = f(y)] \Leftrightarrow [x = y].$ Das entspricht der Injektivität von $f$.

• Fall 2: $s\neq 0^n.$ Wenn $s$ nicht die Null-Zeichenkette ist, impliziert das erfüllte Versprechen für diese Zeichenkette, dass $f$ zweieindeutig ist (two-to-one), d.h. für jede mögliche Ausgabezeichenkette von $f$ gibt es genau zwei Eingabezeichenketten, die $f$ dazu bringen, diese Zeichenkette auszugeben. Außerdem müssen diese zwei Eingabezeichenketten die Form $w$ und $w \oplus s$ für eine Zeichenkette $w$ haben.

Es ist wichtig zu erkennen, dass es nur eine Zeichenkette $s$ geben kann, die funktioniert, wenn das Versprechen erfüllt ist, sodass es für Funktionen, die das Versprechen erfüllen, immer eine eindeutig korrekte Antwort gibt.

Hier ist ein Beispiel einer Funktion der Form $f:\Sigma^3 \rightarrow \Sigma^5$, die das Versprechen für die Zeichenkette $s = 011$ erfüllt.

$$\begin{aligned} f(000) & = 10011 \\ f(001) & = 00101 \\ f(010) & = 00101 \\ f(011) & = 10011 \\ f(100) & = 11010 \\ f(101) & = 00001 \\ f(110) & = 00001 \\ f(111) & = 11010 \end{aligned}$$

Es gibt $8$ verschiedene Eingabezeichenketten und $4$ verschiedene Ausgabezeichenketten, jede davon erscheint zweimal – das ist also eine zweieindeutige Funktion. Außerdem ist für je zwei verschiedene Eingabezeichenketten, die dieselbe Ausgabezeichenkette erzeugen, das bitweise XOR dieser zwei Eingabezeichenketten gleich $011$, was gleichbedeutend damit ist, dass eine der beiden gleich der anderen XOR-verknüpft mit $s$ ist.

Beachte, dass das Einzige, was an den tatsächlichen Ausgabezeichenketten wichtig ist, ist, ob sie für verschiedene Eingabezeichenketten gleich oder verschieden sind. Im obigen Beispiel erscheinen zum Beispiel vier Zeichenketten ($10011,$ $00101,$ $00001$ und $11010$) als Ausgaben von $f$. Wir könnten diese vier Zeichenketten durch andere ersetzen, solange sie alle verschieden sind, und die korrekte Lösung $s = 011$ würde sich nicht ändern.

Algorithmusbeschreibung

Hier ist ein Quantencircuit-Diagramm, das Simons Algorithmus darstellt.

Um klar zu sein: Oben sind $n$ Qubits, auf die Hadamard-Gates wirken, und unten sind $m$ Qubits, die direkt in das Abfrage-Gate gehen. Es sieht den bereits in der Lektion besprochenen Algorithmen sehr ähnlich, aber diesmal gibt es keinen Phase-Kickback; die unteren $m$ Qubits gehen alle im Zustand $\vert 0\rangle$ in das Abfrage-Gate.

Um Simons Problem mit diesem Circuit zu lösen, sind tatsächlich mehrere unabhängige Ausführungen erforderlich, gefolgt von einem klassischen Nachbearbeitungsschritt, der später nach der Analyse des Verhaltens des Circuits beschrieben wird.

Analyse

Die Analyse von Simons Algorithmus beginnt ähnlich wie beim Deutsch-Jozsa-Algorithmus. Nachdem die erste Schicht der Hadamard-Gates auf den oberen $n$ Qubits ausgeführt wurde, wird der Zustand zu

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert 0^m \rangle \vert x\rangle.$$

Wenn $U_f$ ausgeführt wird, wird die Ausgabe der Funktion $f$ mit dem Null-Zustand der unteren $m$ Qubits XOR-verknüpft, sodass der Zustand wird zu

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert f(x) \rangle \vert x\rangle.$$

Wenn die zweite Schicht der Hadamard-Gates ausgeführt wird, erhalten wir mit der gleichen Formel für die Wirkung einer Schicht von Hadamard-Gates wie zuvor den folgenden Zustand.

$$\frac{1}{2^n} \sum_{x\in\Sigma^n} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \vert y\rangle$$

An diesem Punkt weicht die Analyse von derjenigen für die vorherigen Algorithmen in dieser Lektion ab.

Wir sind an der Wahrscheinlichkeit interessiert, dass die Messungen für jede mögliche Zeichenkette $y\in\Sigma^n$ ein bestimmtes Ergebnis liefern. Mithilfe der Regeln für die Analyse von Messungen, die in der Lektion Mehrere Systeme des Kurses Grundlagen der Quanteninformation beschrieben wurden, stellen wir fest, dass die Wahrscheinlichkeit $p(y)$, die Zeichenkette $y$ zu erhalten, gleich

$$p(y) = \left\|\frac{1}{2^n} \sum_{x\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \right\|^2$$

ist.

Um diese Wahrscheinlichkeiten besser zu verstehen, brauchen wir noch etwas mehr Notation und Terminologie. Erstens ist das Bild der Funktion $f$ die Menge aller Ausgabezeichenketten.

$$\operatorname{range}(f) = \{ f(x) : x\in \Sigma^n \}$$

Zweitens können wir für jede Zeichenkette $z\in\operatorname{range}(f)$ die Menge aller Eingabezeichenketten, die dazu führen, dass die Funktion diese Ausgabezeichenkette $z$ ergibt, als $f^{-1}(\{z\})$ ausdrücken.

$$f^{-1}(\{z\}) = \{ x\in\Sigma^n : f(x) = z \}$$

Die Menge $f^{-1}(\{z\})$ ist als Urbild von $\{z\}$ unter $f$ bekannt. Wir können das Urbild unter $f$ einer beliebigen Menge anstelle von $\{z\}$ auf analoge Weise definieren – es ist die Menge aller Elemente, die $f$ auf diese Menge abbildet. (Diese Notation sollte nicht mit der Inversen der Funktion $f$ verwechselt werden, die möglicherweise nicht existiert. Die Tatsache, dass das Argument auf der linken Seite die Menge $\{z\}$ und nicht das Element $z$ ist, ist der Hinweis, der uns hilft, diese Verwechslung zu vermeiden.)

Mit dieser Notation können wir die Summe in unserem obigen Ausdruck für die Wahrscheinlichkeiten aufteilen und erhalten

$$p(y) = \left\| \frac{1}{2^n} \sum_{z\in\operatorname{range}(f)} \Biggl(\sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y}\Biggr) \vert z \rangle \right\|^2.$$

Jede Zeichenkette $x\in\Sigma^n$ wird genau einmal durch die beiden Summationen repräsentiert – wir legen diese Zeichenketten je nachdem, welche Ausgabezeichenkette $z = f(x)$ sie erzeugen, wenn wir die Funktion $f$ auswerten, in separate Eimer und summieren dann separat über alle Eimer.

Wir können nun die euklidische Norm zum Quadrat auswerten und erhalten

$$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2.$$

Um diese Wahrscheinlichkeiten weiter zu vereinfachen, betrachten wir den Wert

$$\left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 \tag{1}$$

für eine beliebige Wahl von $z\in\operatorname{range}(f)$.

Wenn $s = 0^n$ gilt, dann ist $f$ eine injektive Funktion und es gibt immer genau ein Element $x\in f^{-1}(\{z\})$, für jedes $z\in\operatorname{range}(f)$. Der Wert des Ausdrucks $(1)$ ist in diesem Fall $1$.

Wenn hingegen $s\neq 0^n$ gilt, dann gibt es genau zwei Zeichenketten in der Menge $f^{-1}(\{z\})$. Genauer gesagt, wenn wir $w\in f^{-1}(\{z\})$ als eine dieser zwei Zeichenketten wählen, dann muss die andere Zeichenkette $w \oplus s$ sein, gemäß dem Versprechen in Simons Problem. Mit dieser Beobachtung können wir $(1)$ wie folgt vereinfachen.

$$\begin{aligned} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 & = \Bigl\vert (-1)^{w\cdot y} + (-1)^{(w\oplus s)\cdot y} \Bigr\vert^2 \\ & = \Bigl\vert (-1)^{w\cdot y} \Bigl(1 + (-1)^{s\cdot y}\Bigr) \Bigr\vert^2 \\ & = \Bigl\vert 1 + (-1)^{y\cdot s} \Bigr\vert^2 \\ & = \begin{cases} 4 & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases} \end{aligned}$$

Es stellt sich heraus, dass der Wert $(1)$ in beiden Fällen unabhängig von der spezifischen Wahl von $z\in\operatorname{range}(f)$ ist.

Wir können nun die Analyse abschließen, indem wir dieselben zwei Fälle wie zuvor separat betrachten.

• Fall 1: $s = 0^n.$ In diesem Fall ist die Funktion $f$ injektiv, also gibt es $2^n$ Zeichenketten $z\in\operatorname{range}(f)$, und wir erhalten

  $$p(y) = \frac{1}{2^{2n}} \cdot 2^n = \frac{1}{2^n}.$$

  Mit anderen Worten: Die Messungen ergeben eine gleichmäßig zufällig gewählte Zeichenkette $y\in\Sigma^n$.

• Fall 2: $s \neq 0^n.$ In diesem Fall ist $f$ zweieindeutig, also gibt es $2^{n-1}$ Elemente in $\operatorname{range}(f)$. Mit der obigen Formel schließen wir, dass die Wahrscheinlichkeit, jedes $y\in\Sigma^n$ zu messen, gleich

  $$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \Biggl\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \Biggr\vert^2 = \begin{cases} \frac{1}{2^{n-1}} & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases}$$

  ist. Mit anderen Worten: Wir erhalten eine gleichmäßig zufällig aus der Menge $\{y\in\Sigma^n : y \cdot s = 0\}$ gewählte Zeichenkette, die $2^{n-1}$ Zeichenketten enthält. (Da $s\neq 0^n$ gilt, haben genau die Hälfte der Binärzeichenketten der Länge $n$ das binäre Skalarprodukt $1$ mit $s$ und die andere Hälfte das binäre Skalarprodukt $0$ mit $s$, wie wir bereits bei der Analyse des Deutsch-Jozsa-Algorithmus für das Bernstein-Vazirani-Problem festgestellt haben.)

Klassische Nachbearbeitung

Wir wissen nun, wie hoch die Wahrscheinlichkeiten für die möglichen Messergebnisse sind, wenn wir den Quantencircuit für Simons Algorithmus ausführen. Reicht das aus, um $s$ zu bestimmen?

Die Antwort ist ja, vorausgesetzt, wir sind bereit, den Prozess mehrmals zu wiederholen und akzeptieren, dass er mit einer gewissen Wahrscheinlichkeit scheitern kann, die wir durch ausreichend viele Ausführungen des Circuits sehr klein machen können. Die wesentliche Idee ist, dass jede Ausführung des Circuits uns statistische Hinweise auf $s$ liefert, und wir können diese Hinweise nutzen, um $s$ mit sehr hoher Wahrscheinlichkeit zu finden, wenn wir den Circuit ausreichend oft ausführen.

Nehmen wir an, wir führen den Circuit $k$ Mal unabhängig aus, für $k = n + 10$. Diese bestimmte Anzahl von Iterationen ist nicht besonders – wir könnten $k$ je nach der Fehlerwahrscheinlichkeit, die wir tolerieren möchten, größer (oder kleiner) wählen, wie wir sehen werden. Die Wahl $k = n + 10$ stellt sicher, dass wir mit einer Wahrscheinlichkeit von mehr als $99{,}9\%$ $s$ bestimmen.

Durch $k$-maliges Ausführen des Circuits erhalten wir Zeichenketten $y^1,...,y^{k} \in \Sigma^n$. Die Hochindizes hier sind Teil der Namen dieser Zeichenketten, keine Exponenten oder Indizes ihrer Bits:

$$\begin{aligned} y^1 & = y^1_{n-1} \cdots y^1_{0}\\[1mm] y^2 & = y^2_{n-1} \cdots y^2_{0}\\[1mm] & \;\; \vdots\\[1mm] y^{k} & = y^{k}_{n-1} \cdots y^{k}_{0} \end{aligned}$$

Wir bilden nun eine Matrix $M$ mit $k$ Zeilen und $n$ Spalten, indem wir die Bits dieser Zeichenketten als binärwertige Einträge verwenden.

$$M = \begin{pmatrix} y^1_{n-1} & \cdots & y^1_{0}\\[1mm] y^2_{n-1} & \cdots & y^2_{0}\\[1mm] \vdots & \ddots & \vdots \\[1mm] y^{k}_{n-1} & \cdots & y^{k}_{0} \end{pmatrix}$$

Wir kennen $s$ zu diesem Zeitpunkt nicht – unser Ziel ist es, diese Zeichenkette zu finden. Stellen wir uns aber kurz vor, wir kennen $s$, und wir bilden einen Spaltenvektor $v$ aus den Bits der Zeichenkette $s = s_{n-1} \cdots s_0$ wie folgt.

$$v = \begin{pmatrix} s_{n-1}\\ \vdots\\ s_0 \end{pmatrix}$$

Wenn wir die Matrix-Vektor-Multiplikation $M v$ modulo $2$ durchführen – das heißt, wir führen die Multiplikation wie üblich durch und nehmen dann den Rest der Einträge des Ergebnisses nach Division durch $2$ – erhalten wir den Nullvektor.

$$M v = \begin{pmatrix} y^1 \cdot s\\ y^2 \cdot s\\ \vdots\\[1mm] y^{k} \cdot s \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ \vdots\\[1mm] 0 \end{pmatrix}$$

Das heißt, als Spaltenvektor $v$ wie soeben beschrieben betrachtet, wird die Zeichenkette $s$ immer ein Element des Nullraums der Matrix $M$ sein, vorausgesetzt, wir rechnen modulo $2$. Das gilt sowohl im Fall $s = 0^n$ als auch im Fall $s\neq 0^n$. Genauer gesagt ist der Nullvektor immer im Nullraum von $M$ enthalten, und er wird durch den Vektor, dessen Einträge die Bits von $s$ sind, ergänzt, falls $s\neq 0^n$ gilt.

Die verbleibende Frage ist, ob es im Nullraum von $M$ andere Vektoren geben wird als diejenigen, die $0^n$ und $s$ entsprechen. Die Antwort ist, dass dies zunehmend unwahrscheinlich wird, je größer $k$ ist – und wenn wir $k = n + 10$ wählen, enthält der Nullraum von $M$ mit einer Wahrscheinlichkeit von mehr als $99{,}9\%$ keine anderen Vektoren neben denen, die $0^n$ und $s$ entsprechen. Allgemeiner gilt: Wenn wir $k = n + 10$ durch $k = n + r$ für eine beliebige positive ganze Zahl $r$ ersetzen, beträgt die Wahrscheinlichkeit, dass die Vektoren, die $0^n$ und $s$ entsprechen, allein im Nullraum von $M$ sind, mindestens $1 - 2^{-r}$.

Mithilfe linearer Algebra ist es möglich, eine Beschreibung des Nullraums von $M$ modulo $2$ effizient zu berechnen. Insbesondere kann dies mit dem Gaußschen Eliminationsverfahren erfolgen, das auf die gleiche Weise funktioniert, wenn die Arithmetik modulo $2$ erfolgt, wie mit reellen oder komplexen Zahlen. Solange die Vektoren, die $0^n$ und $s$ entsprechen, allein im Nullraum von $M$ sind – was mit hoher Wahrscheinlichkeit eintritt –, können wir $s$ aus den Ergebnissen dieser Berechnung ableiten.

Klassische Schwierigkeit

Wie viele Abfragen braucht ein klassischer Abfragealgorithmus, um Simons Problem zu lösen? Die Antwort ist: viele, im Allgemeinen.

Es gibt verschiedene präzise Aussagen über die klassische Schwierigkeit dieses Problems, und hier ist nur eine davon. Wenn wir einen beliebigen probabilistischen Abfragealgorithmus haben, der weniger als $2^{n/2 - 1} - 1$ Abfragen stellt – eine Anzahl von Abfragen, die exponentiell in $n$ ist –, dann wird dieser Algorithmus Simons Problem mit einer Wahrscheinlichkeit von mindestens $1/2$ nicht lösen.

Manchmal kann der Beweis solcher Unmöglichkeitsergebnisse sehr anspruchsvoll sein, aber dieser ist durch eine elementare probabilistische Analyse nicht allzu schwer zu beweisen. Hier werden wir jedoch nur kurz die grundlegende Intuition dahinter betrachten.

Wir versuchen, die verborgene Zeichenkette $s$ zu finden, aber solange wir die Funktion nicht für zwei Zeichenketten mit demselben Ausgabewert abfragen, erhalten wir nur sehr begrenzte Informationen über $s$. Intuitiv gesprochen werden wir nur lernen, dass die verborgene Zeichenkette $s$ nicht das exklusive ODER zweier verschiedener Zeichenketten ist, die wir abgefragt haben. Und wenn wir weniger als $2^{n/2 - 1} - 1$ Zeichenketten abfragen, gibt es immer noch viele Möglichkeiten für $s$, die wir nicht ausgeschlossen haben, weil es nicht genug Paare von Zeichenketten gibt, um das zu tun. Das ist kein formeller Beweis, nur die grundlegende Idee.

Zusammenfassend bietet Simons Algorithmus also einen bemerkenswerten Vorteil von Quanten- gegenüber klassischen Algorithmen im Abfragemodell. Insbesondere löst Simons Algorithmus Simons Problem mit einer Anzahl von Abfragen, die linear in der Anzahl der Eingabebits $n$ unserer Funktion ist, während jeder klassische Algorithmus, auch ein probabilistischer, eine Anzahl von Abfragen benötigt, die exponentiell in $n$ ist, um Simons Problem mit einer vernünftigen Erfolgswahrscheinlichkeit zu lösen.