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 schlüsseln das Versprechen gleich auf, um besser zu verstehen, was es besagt, vorab aber schon so viel: Es verlangt, dass $f$ eine sehr spezielle Struktur hat – die meisten Funktionen erfüllen dieses Versprechen also nicht. Es sei auch offen gesagt, dass dieses Problem nicht auf praktischen Nutzen abzielt. Vielmehr ist es ein etwas künstliches Problem, das gezielt so konstruiert ist, dass es für Quantencomputer leicht und für klassische Computer schwer ist.

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 von Hadamard-Gates auf den obersten $n$ Qubits angewendet 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$ angewendet wird, wird die Ausgabe der Funktion $f$ per XOR mit dem Nullzustand der untersten $m$ Qubits verknüpft, sodass der Zustand zu

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

Wenn die zweite Schicht von Hadamard-Gates angewendet wird, erhalten wir den folgenden Zustand, indem wir dieselbe Formel für die Wirkung einer Schicht von Hadamard-Gates wie zuvor verwenden.

$$\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 dieser Stelle weicht die Analyse von denen der vorherigen Algorithmen in dieser Lektion ab.

Wir interessieren uns für die Wahrscheinlichkeit, dass die Messungen zu jeder möglichen Zeichenkette $y\in\Sigma^n$ führen. Mithilfe der Regeln zur Analyse von Messungen, die in der Lektion Mehrere Systeme des Kurses Grundlagen der Quanteninformation beschrieben werden, 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.$$

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 sortieren diese Zeichenketten je nach der erzeugten Ausgabezeichenkette $z = f(x)$ in getrennte Töpfe und summieren dann separat über alle Töpfe.

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$. An dieser konkreten Anzahl von Iterationen ist nichts Besonderes – 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 $s$ mit einer Wahrscheinlichkeit von mehr als $99{,}9\%$ 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.