5.1 Mit Quantenorakeln sprechen

In dieser Quest werden wir uns einige Quantenalgorithmen anschauen und mit klassischen Algorithmen vergleichen, die dasselbe Problem lösen. Da es im Allgemeinen sehr schwer ist, die tatsächliche Anzahl an elementaren Operationen für das lösen eines Problems zu zählen, werden wir hier ein vereinfachtes Maß der Komplexität nutzen (das machen Informatiker:innen immer dann, wen sie sich das Leben einfacher machen wollen).

Wenn ein Computer ein Programm ausführt, muss er verschiedene Arten von Operationen ausführen. Die langsamsten davon sind jene, welche auf Daten zugreifen müssen. Zum Beispiel, wenn Daten aus dem Speicher, von einer Festplatte – oder im schlimmsten Fall – von einem anderen Computer über das Internet ausgelesen werden müssen. Sobald die relevanten Daten eingelesen wurden, kann das eigentliche verarbeiten sehr schnell gehen. Daher können wir die Laufzeit eines Programms grob einschätzen, indem wir nur die Operationen zählen, die auf Daten zugreifen.

Das kennst du vielleicht vom öffnen von komplizierten Webseiten oder großen Dokumenten. Es kann eine Weile dauern, bis diese geladen sind, danach ist geht das interagieren mit der Webseite oder das Einfügen einer weiteren Zeile in das Dokument recht schnell.

Man könnte sich das auch so vorstellen, dass die Informationen, auf die man zugreifen will, eigentlich durch einen anderen Algorithmus, oder eine Subroutine (ein Unterprogramm) des Algorithmus’ produziert wird. Und diese Subroutine ist sehr langsam. Zum Beispiel könnte sie die Informationen aus der Festplatte auslesen oder über das Internet empfangen. Oder die Informationen könnten gar nicht direkt verfügbar sein und müssen erst durch sehr komplizierte Berechnungen produziert werden. Auf jeden Fall braucht die Subroutine sehr lange um die Informationen zu liefern, also rufst du sie so selten wie möglich auf. Wir nennen solch eine Subroutine Orakel, da sie sehr klug ist und alle Antworten kennt, aber auch ein bisschen langsam ist und eine Weile nachdenken muss, um die Antwort zu liefern.

Formal gesagt ist ein klassisches Orakel einfach eine Funktion $f\colon\{0,1\}^{n}\to\{0,1\}$ wobei $\{0,1\}^{n}$ die Menge aller Bitstrings der Länge $n$ bezeichnet. Du kannst dir die Eingabe $x\in\{0,1\}^{n}$ als Frage und die Ausgabe, das Bit $f(x)$ als Antwort vorstellen. Jedes mal wenn du die Funktion $f$ für eine Eingabe auswertest, stellst du eine Frage, die dieser Eingabe entspricht, und erhältst eine Ja/Nein-Antwort, die dem Wert der Funktion entspricht.

Beispielsweise kannst du Zugriff auf eine Festplatte oder anderen Speicher durch ein Orakel modellieren. Wenn du beispielsweise 4 Bits Speicherplatz hast, kannst du diesen als Funktion $f:\{0,1\}^{2}\to\{0,1\}$ modellieren, die, gegeben der binären Adresse, das zugehörige Bit ausgibt. Willst du dann alle vier Bits herausfinden, musst du $f$ vier mal ausführen, um die vier Bitwerte $f(00),f(01),f(10),f(11)$ zu erhalten.

Wichtig ist, dass es bei den Rechenproblemen, die wir lösen wollen nicht darum geht, den Wert von $f$ auf einer bestimmten Eingabe zu finden. Solche Probleme wären trivial, da man sie lösen kann indem man das Orakel nur einmal fragt, da das genau die Aufgabe des Orakels ist – es gibt dir den Wert einer Funktion für eine beliebige Eingabe deiner Wahl. Die Probleme, an denen wir interessiert sind, sind etwas komplizierter. Wir wollen stattdessen eine Eigenschaft der Funktion $f$ bestimmen, indem wir sie so selten wie möglich auswerten.

Zum Beispiel könnten wir wissen wollen, ob $f(x)=0$ für alle $x\in\{0,1\}^{n}$ gilt. In diesem Fall könnten wir das Orakel zufällige Werte von $x$ fragen, bis wir eines finden, für das $f(x)=1$ gilt. Wir werden bald noch andere solche Beispiele sehen.