Das Abfragemodell der Berechnung

Wenn wir Berechnungen mathematisch modellieren, haben wir typischerweise den in der folgenden Abbildung dargestellten Prozess vor Augen: Informationen werden als Eingabe bereitgestellt, eine Berechnung findet statt, und eine Ausgabe wird erzeugt.

Auch wenn es stimmt, dass die Computer, die wir heute verwenden, kontinuierlich Eingaben empfangen und Ausgaben erzeugen und dabei sowohl mit uns als auch mit anderen Computern in einer Weise interagieren, die in der Abbildung nicht dargestellt ist, soll dies nicht den laufenden Betrieb von Computern repräsentieren. Vielmehr geht es darum, eine einfache Abstraktion der Berechnung zu schaffen, die sich auf isolierte Berechnungsaufgaben konzentriert. Die Eingabe könnte beispielsweise eine Zahl, einen Vektor, eine Matrix, einen Graphen, eine Beschreibung eines Moleküls oder etwas Komplizierteres kodieren, während die Ausgabe eine Lösung für die betrachtete Berechnungsaufgabe kodiert.

Der entscheidende Punkt ist, dass die Eingabe der Berechnung vollständig bereitgestellt wird, üblicherweise in Form einer Binärzeichenkette, ohne dass ein Teil davon verborgen ist.

Beschreibung des Modells

Im Abfragemodell der Berechnung wird die gesamte Eingabe nicht wie in einem eher standardmäßigen Modell bereitgestellt. Stattdessen wird die Eingabe in Form einer Funktion zur Verfügung gestellt, auf die die Berechnung durch Abfragen zugreift. Alternativ können wir Berechnungen im Abfragemodell als solche betrachten, die Direktzugriff auf Bits (oder Abschnitte von Bits) der Eingabe haben.

Im Zusammenhang mit dem Abfragemodell wird die Eingabe oft als von einem Orakel oder einer Black Box bereitgestellt bezeichnet. Beide Begriffe deuten darauf hin, dass eine vollständige Beschreibung der Eingabe vor der Berechnung verborgen ist und der einzige Zugang über Fragen möglich ist. Es ist, als würden wir das Orakel von Delphi über die Eingabe befragen: Es teilt uns nicht alles mit, was es weiß, sondern beantwortet nur spezifische Fragen. Der Begriff Black Box ist besonders sinnvoll, wenn wir die Eingabe als durch eine Funktion repräsentiert betrachten: Wir können nicht in die Funktion hineinschauen und verstehen, wie sie funktioniert – wir können sie nur für von uns ausgewählte Argumente auswerten.

In dieser Lektion arbeiten wir ausschließlich mit Binärzeichenketten, nicht mit Zeichenketten aus anderen Symbolen. Schreiben wir daher $\Sigma = \{0,1\}$ für das binäre Alphabet. Wir werden verschiedene Berechnungsprobleme betrachten – einige einfache Beispiele folgen kurz darauf –, aber bei allen wird die Eingabe durch eine Funktion der Form

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

für zwei positive ganze Zahlen $n$ und $m$ dargestellt. Natürlich könnte man anstelle von $f$ einen anderen Namen wählen, aber wir bleiben in dieser Lektion bei $f$.

Eine Berechnung, die eine Abfrage stellt, bedeutet, dass eine Zeichenkette $x \in \Sigma^n$ ausgewählt wird und dann die Zeichenkette $f(x)\in\Sigma^m$ vom Orakel für die Berechnung verfügbar gemacht wird. Die genaue Funktionsweise bei Quantenalgorithmen wird gleich besprochen – wir müssen sicherstellen, dass dies mit einer unitären Quantenoperation möglich ist, die Abfragen in Überlagerung erlaubt –, aber zunächst können wir intuitiv auf hohem Niveau darüber nachdenken.

Schließlich ist die Art, wie wir die Effizienz von Abfragealgorithmen messen, einfach: Wir zählen die Anzahl der Abfragen, die sie benötigen. Dies hängt mit der Zeit zusammen, die für eine Berechnung benötigt wird, ist aber nicht genau dasselbe, da wir die Zeit für andere Operationen als die Abfragen ignorieren und die Abfragen so behandeln, als hätten sie jeweils Einheitskosten. Wir können die anderen Operationen berücksichtigen, wenn wir möchten (und das wird manchmal getan), aber die Beschränkung auf die Anzahl der Abfragen hält die Dinge einfach.

Beispiele für Abfrageprobleme

Hier sind einige einfache Beispiele für Abfrageprobleme.

• OR. Die Eingabefunktion hat die Form $f:\Sigma^n \rightarrow \Sigma$ (also $m=1$ für dieses Problem). Die Aufgabe besteht darin, $1$ auszugeben, wenn es eine Zeichenkette $x\in\Sigma^n$ gibt, für die $f(x) = 1$ gilt, und $0$ auszugeben, wenn keine solche Zeichenkette existiert. Wenn man die Funktion $f$ als Repräsentation einer Folge von $2^n$ Bits betrachtet, auf die man Direktzugriff hat, ist das Problem die Berechnung des OR dieser Bits.

• Parität. Die Eingabefunktion hat wieder die Form $f:\Sigma^n \rightarrow \Sigma$. Die Aufgabe besteht darin, festzustellen, ob die Anzahl der Zeichenketten $x\in\Sigma^n$, für die $f(x) = 1$ gilt, gerade oder ungerade ist. Genauer gesagt ist die geforderte Ausgabe $0$, wenn die Menge $\{x\in\Sigma^n : f(x) = 1\}$ eine gerade Anzahl von Elementen hat, und $1$, wenn sie eine ungerade Anzahl hat. Wenn man $f$ als Folge von $2^n$ Bits mit Direktzugriff betrachtet, ist das Problem die Berechnung der Parität (oder des exklusiven ODER) dieser Bits.

• Minimum. Die Eingabefunktion hat die Form $f:\Sigma^n \rightarrow \Sigma^m$ für beliebige positive ganze Zahlen $n$ und $m$. Die geforderte Ausgabe ist die Zeichenkette $y \in \{f(x) : x\in\Sigma^n\}$, die in der lexikografischen (d.h. alphabetischen) Reihenfolge von $\Sigma^m$ als erste erscheint. Wenn man $f$ als Folge von $2^n$ ganzen Zahlen betrachtet, die als Zeichenketten der Länge $m$ in Binärschreibweise mit Direktzugriff kodiert sind, ist das Problem die Berechnung des Minimums dieser ganzen Zahlen.

Wir betrachten auch Abfrageprobleme mit einem Versprechen (Promise) über die Eingabe. Das bedeutet, dass wir eine Art Garantie für die Eingabe erhalten und nicht dafür verantwortlich sind, was passiert, wenn diese Garantie nicht erfüllt ist. Eine andere Möglichkeit, diese Art von Problem zu beschreiben, ist zu sagen, dass einige Eingabefunktionen (diejenigen, für die das Versprechen nicht erfüllt ist) als „egal"-Eingaben betrachtet werden. Für Algorithmen, denen „egal"-Eingaben gegeben werden, gelten keinerlei Anforderungen.

Hier ist ein Beispiel für ein Problem mit einem Versprechen:

• Eindeutige Suche. Die Eingabefunktion hat die Form $f:\Sigma^n \rightarrow \Sigma$, und wir erhalten das Versprechen, dass es genau eine Zeichenkette $z\in\Sigma^n$ gibt, für die $f(z) = 1$ gilt, mit $f(x) = 0$ für alle Zeichenketten $x\neq z$. Die Aufgabe besteht darin, diese eindeutige Zeichenkette $z$ zu finden.

Alle vier gerade beschriebenen Beispiele sind natürlich, in dem Sinne, dass sie leicht zu beschreiben sind und man sich eine Vielzahl von Situationen oder Kontexten vorstellen kann, in denen sie auftreten könnten.

Im Gegensatz dazu sind manche Abfrageprobleme überhaupt nicht so „natürlich". Tatsächlich kommen wir bei der Untersuchung des Abfragemodells manchmal auf sehr komplizierte und stark konstruierte Probleme, bei denen es schwer vorstellbar ist, dass jemand sie in der Praxis tatsächlich lösen möchte. Das bedeutet aber nicht, dass die Probleme nicht interessant sind! Was zunächst konstruiert oder unnatürlich erscheint, kann unerwartete Hinweise liefern oder neue Ideen inspirieren. Shors Quantenalgorithmus zur Faktorisierung, der durch Simons Algorithmus inspiriert wurde, ist ein großartiges Beispiel dafür. Es ist auch ein wichtiger Teil der Untersuchung des Abfragemodells, nach Extremen zu suchen, die sowohl die potenziellen Vorteile als auch die Grenzen des Quantencomputings beleuchten können.

Abfrage-Gates

Wenn wir Berechnungen mit Circuits beschreiben, werden Abfragen durch spezielle Gates namens Abfrage-Gates durchgeführt.

Die einfachste Möglichkeit, Abfrage-Gates für klassische Boolesche Circuits zu definieren, besteht darin, ihnen zu erlauben, die Eingabefunktion $f$ direkt zu berechnen, wie die folgende Abbildung zeigt.

Wenn ein Boolescher Circuit für ein Abfrageproblem erstellt wird, wird die Eingabefunktion $f$ über diese Gates abgerufen, und die Anzahl der Abfragen des Circuits ist einfach die Anzahl der Abfrage-Gates im Circuit. Die Eingabeleitungen des Booleschen Circuits selbst werden auf feste Werte initialisiert, die als Teil des Algorithmus betrachtet werden sollten (im Gegensatz zu Eingaben des Problems).

Hier ist beispielsweise ein Boolescher Circuit mit klassischen Abfrage-Gates, der das oben beschriebene Paritätsproblem für eine Funktion der Form $f:\Sigma\rightarrow\Sigma$ löst:

Dieser Algorithmus stellt zwei Abfragen, da zwei Abfrage-Gates vorhanden sind. Die Funktionsweise: Die Funktion $f$ wird für die beiden möglichen Eingaben, $0$ und $1$, abgefragt, und die Ergebnisse werden in einen Booleschen Circuit eingespeist, der das XOR berechnet. (Dieser Circuit erschien als Beispiel eines Booleschen Circuits in der Lektion Quantencircuits des Kurses Grundlagen der Quanteninformation.)

Bei Quantencircuits funktioniert diese Definition von Abfrage-Gates nicht, da diese Gates für manche Wahlen der Funktion $f$ nicht-unitär sein werden. Stattdessen definieren wir unitäre Abfrage-Gates, die auf Standard-Basiszuständen wie in dieser Abbildung beschrieben wirken:

Dabei nehmen wir an, dass $x\in\Sigma^n$ und $y\in\Sigma^m$ beliebige Zeichenketten sind. Die Notation $y\oplus f(x)$ bezeichnet das bitweise exklusive ODER zweier Zeichenketten, die in diesem Fall die Länge $m$ haben. Zum Beispiel gilt $001 \oplus 101 = 100$.

Intuitiv gesprochen: Das Gate $U_f$ (für eine beliebige Funktion $f$) gibt die obere Eingabezeichenkette $x$ unverändert zurück und XOR-verknüpft den Funktionswert $f(x)$ mit der unteren Eingabezeichenkette $y$ – eine unitäre Operation für jede Wahl der Funktion $f$. Tatsächlich handelt es sich um eine deterministische Operation, die ihre eigene Inverse ist. Das bedeutet, dass $U_f$ als Matrix stets eine Permutationsmatrix ist – eine Matrix mit einer einzigen $1$ in jeder Zeile und jeder Spalte und Nullen überall sonst. Das Anwenden einer Permutationsmatrix auf einen Vektor permutiert lediglich die Einträge des Vektors (daher der Begriff Permutationsmatrix) und ändert damit nicht die euklidische Norm des Vektors – was zeigt, dass Permutationsmatrizen immer unitär sind.

Es sollte hervorgehoben werden, dass wir bei der Analyse von Abfragealgorithmen durch einfaches Zählen der Abfragen die Schwierigkeit der physischen Konstruktion der Abfrage-Gates völlig ignorieren – sowohl bei der klassischen als auch bei der soeben beschriebenen Quantenversion. Intuitiv gesprochen ist die Konstruktion der Abfrage-Gates Teil der Vorbereitung der Eingabe, nicht Teil der Lösungsfindung.

Das mag unvernünftig erscheinen, aber man muss bedenken, dass wir nicht versuchen, praktisches Rechnen zu beschreiben oder die erforderlichen Ressourcen vollständig zu berücksichtigen. Vielmehr definieren wir ein theoretisches Modell, das dabei hilft, die potenziellen Vorteile des Quantencomputings zu beleuchten. Mehr dazu sagen wir in der folgenden Lektion, wenn wir uns einem standardmäßigeren Berechnungsmodell zuwenden, bei dem Eingaben Circuits als Binärzeichenketten explizit übergeben werden.