5.1.2 Bit-Orakel

Dieser Ansatz funktioniert nicht nur für die logische $\operatorname{AND}$-Funktion, sondern für jede beliebige Funktion

die $n$ Bits als Eingabe erhält und ein einzelnes Bit ausgibt. Für jede solche Funktion können wir eine Operation auf $(n+1)$ Bits definieren:

für alle $x_{1},\dotsc,x_{n},y\in\{0,1\}$. Genau wie Gl. 5.3 ist diese Operation ihr eigenes Inverse, zweimaliges anwenden verändert den Zustand also nicht.

Es ist beruhigend, dass wir jede Funktion $f:\{0,1\}^{n}\to\{0,1\}$ wie in Gl. 5.4 umkehrbar implementieren können. Zunächst einmal bedeutet das, dass jede Berechnung auf einem klassischen Computer so durchgeführt werden kann, dass die ursprüngliche Eingabe wiederhergestellt werden kann. Weiterhin können Berechnungen, die umkehrbar sind, auch auf Quantencomputern durchführen. Das bedeutet, dass Quantencomputer alles berechnen können was auch klassische Computer können! Außerdem können wir damit jede Funktion $f$ als Orakel auf einem Quantencomputer implementieren.

Lass uns einmal sehen, wie das funktioniert. Die Quantenversion der Operation aus Gl. 5.4 ist wie folgt definiert:

für alle $x_{1},\dotsc,x_{n},y\in\{0,1\}$. Gl. 5.5 bestimmt dabei, wie $U_{f}$ sich auf allen Basiszuständen von $n+1$ Qubits verhält. Wie immer können wir diese Definition durch Linearität auf auf beliebige Zustände auf $n+1$ Qubits erweitern. Da $U_{f}$ einfach nur die Basiszustände permutiert, kannst du wie in 4.4 zeigen, dass es eine gültige Quantenoperation darstellt.

Wir nennen die Quantenoperation $U_{f}$ aus Gl. 5.5 das Bit-Orakel für $f$ (wir könnten auch die Funktion aus Gl. 5.4 als klassisches Bit-Orakel bezeichnen, aber wir brauchen diesen Namen nicht). Die Bezeichnung ‘Orakel’ bedeutet einfach, dass sich das Anwenden dieser Operation so verhält, als würden wir ein allmächtiges Orakel bitten, uns den Wert der Funktion für jede beliebige Eingabe zu geben. Wir wissen nicht genau, wie das Orakel implementiert ist oder woher es die Antworten bekommt, wir werden nur zählen, wie viele Fragen wir an das Orakel stellen müssen, um eine gewisse Eigenschaft der Funktion $f$ herauszufinden. Viele interessante Algorithmische Probleme können so modelliert werden, wie wir im Rest der Quest sehen werden.

Das Konzept eines Orakels ist ein wenig wie das ‘Rate meine Zahl’-Spiel. Ein:e Freund:in von dir denkt sich eine Zahl aus und du fragst dann Fragen der Form “Ist deine Zahl x”? Darauf erhältst du dann entweder “Ja” oder “Nein” als Antwort. Mit anderen Worten stellt dein:e Freund:in eine Funktion dar, die “Nein” auf allen Eingaben außer einer einzigen (der Zahl, die festgelegt wurde) ausgibt. Jede Frage die du stellst gibt dir mehr Informationen über die Zahl. Du könntest dir zum Beispiel gedanken darüber machen, wie viele Fragen du stellen musst, um die Zahl zu finden. Und was wäre, wenn du deine Fragen an ein Quantenorakel $U_{f}$ stellen könntest, anstelle an deine:n Freund:in? Könntest du die Lösung dann mit weniger Fragen finden? In dieser Woche wirst du mehrere interessante Beispiele kennenlernen, wo das tatsächlich der Fall ist!

Lass uns mal einige Beispiele für Bit-Orakel besprechen. Nehmen wir an, $f$ ist die AND-Funktion. Laut Gl. 5.1 können wir AND als Multiplikation modulo 2 interpretieren, da $AND(x_{1},x_{2})=x_{1}x_{2}$. Das entsprechende Bit-Orakel

ist nichts anderes als das Toffoli Gatter aus 4.4. Selbst für $n=1$ und die Funktion $f(x)=x$, die einfach ihre Eingabe ausgibt, erhalten wir ein interessantes Ergebnis: für alle $a,b\in\{0,1\}$ gilt dann

Das entspricht einfach dem bekannten kontrolliertem-NOT-Gatter $\mathrm{CNOT}_{1\to 2}$ aus Gl. 3.64 in Abschnitt 3.2.4! Das Bit-Orakel bildet also mehrere interessante Quantenoperationen, die wir zuvor per Hand definiert hatten. In der folgenden Übung kannst du versuchen, alle anderen Ein-Bit-Orakel zu implementieren.