5.1.1 Umkehrbare Berechnungen

Bevor wir spannende neue Quantenalgorithmen suchen, sollten wir erst einmal sichergehen, dass wir auf Quantencomputern immer noch alles berechnen können, was wir auch auf klassischen Computern berechnen können. Wir wollen also sichergehen, dass Quantencomputer nicht weniger leistungsfähig sind als klassische Computer! Das ist nicht direkt offensichtlich, da Quantencomputer ganz anders als klassische funktionieren. Insbesondere müssen alle Operationen, die ein Quantencomputer ausführen kann umkerhbar oder invertierbar sein, wie wir schon in Abschnitt 2.4.2 und Abschnitt 4.1.3 gesehen haben, aber das ist für klassische Computer normalerweise nicht der Fall. Wer hat noch nie versehentlich eine Datei gelöscht oder vergessen, die Änderungen in einem Dokument zu speichern, und damit die gesamte Arbeit verloren? Wenn alle Vorgänge umkehrbar wären, bräuchte man sich um solche Kleinigkeiten keine Gedanken machen.

Das wirft also folgende Frage auf: woher wissen wir, dass Quantencomputer alles berechnen können, was klassische Computer auch berechnen können? Man kann diese Frage beantworten, indem man zeigt, dass Umkehrbarkeit die Rechenmöglichkeiten eines gewöhnlichen Computers nicht einschränkt und daher auch keine Einschränung für Quantencomputer darstellt. Anders gesagt: Wir zeigen, dass jede Berechnung umkehrbar gemacht werden kann, also auch auf einem Quantencomputer ausgeführt werden kann.

Um zu verstehen, wie das funktionieren kann, schauen wir uns beispielhaft das berechnen der logischen AND Funktion (engl. für “UND”) auf zwei Bits an. Wenn beide Bits 1 sind, ergibt die Funktion auch 1, ansonsten ergibt sie 0. Also können wir die Funktion mit folgender Wahrheitstabelle beschreiben:

Mit der Notation aus Abschnitt 3.1 können wir sie mathematisch als Operation auf zwei Bits schreiben:

Diese Operation ist offensichtlich nicht umkerhbar, da sie nicht genauso viele Eingabe- wie Ausgabe-Bits hat. Wenn wir wissen, dass das Ergebnis der AND Operation $0$ ist, können wir keine präzisen Aussagen über die beiden Eingabebits treffen – wie die Wahrheitstabelle zeigt, gibt es drei Möglichkeiten.

Wie können wir dieses Problem lösen? Lass uns doch mal versuchen, dass erste Bit zu behalten und ein zweites Ausgabebit hinzuzufügen, welches das Ergebnis beinhaltet:

Schon besser, nun haben wir zwei Eingabe- und zwei Ausgabe-Bits. Aber ist die Operation umkerhbar? Also können wir aus jeder Ausgabe die Eingabe rekonstruieren? Offensichtlich können wir das erste Bit $x_{1}$ immer rekonstruieren, da es in der Ausgabe enthalten ist. Aber was ist mit $x_{2}$? Wenn $x_{1}=0$ gilt, muss laut Wahrheitstabelle das Ergebnis immer $[00]$ sein – egal welchen Wert $x_{2}$ hat. Daher ist auch diese Operation nicht umkehrbar und dieser Ansatz funktioniert nicht.

Es scheint hoffnungslos zu sein. Ist es überhaupt möglich die AND-Funktion umkehrbar zu bauen? Wenn man nicht weiter kommt, muss man manchmal um die Ecke denken! Warum müssen wir uns überhaupt auf nur zwei Bits beschränken? Durch behalten der beiden Eingabebits und hinzuzufügen eines dritten Bits zur Ausgabe, sollte die Operation umkehrbar werden:

Jetzt ist es ganz einfach die Operation zu invertieren – gegeben eines beliebigen Ausgabe Bitstrings können wir einfach das letzte Bit vergessen und durch $[0]$ ersetzen um die Eingabe wiederherzustellen. Ist zum Beispiel die Ausgabe $[111]$, so muss die Eingabe $[110]$ gewesen sein.

Sind wir also jetzt fertig? Noch nicht ganz! Beachte, dass Gl. 5.2 die Operation nur teilweise festlegt – wenn die Eingabe $[111]$, oder ein beliebiger anderer auf $1$ endender Bitstring ist, sagt uns Gl. 5.2 nichts darüber wie sich die Operation verhalten sollte. Da die vier Inputstrings, welche auf $0$ enden, auf vier verschiedene Ausgaben abgebildet werden, können wir Gl. 5.2 auf eine beliebige Art zu einer umkehrbaren Operation auf drei Bits erweitern. Aber gibt es einen systematischen Ansatz dafür?

Bemerke, dass Gl. 5.2 das letzte Bit von $[0]$ zu $[1]$ flippt, wenn $\operatorname{AND}(x_{1},x_{2})=1$ gilt. Genauso könnten wir sagen, wenn das letzte Bit $[1]$ ist, flippt unsere Operation es zurück zu $[0]$, falls $\operatorname{AND}(x_{1},x_{2})=1$ gilt. Wir können also Gl. 5.2 wie folgt auf alle möglichen Eingaben erweitern:

für alle $x_{1},x_{2},y\in\{0,1\}$, wobei ‘$\oplus$’ die Addition Modulo 2 darstellt.

Die Operation in Gl. 5.3 ist also auf allen möglichen Eingaben definiert. Aber ist sie auch endlich umkehrbar? Ja, ist sie! Tatsächlich ist sie sogar ihr eigenes Inverses! Das bedeutet, wenn man sie zweimal hintereinander ausführt, erhält man wieder die ursprüngliche Eingabe:

Im dritten Schritten haben wir ausgenutzt, dass $a\oplus a=0$ für alle $a\in\{0,1\}$, siehe Gl. 3.21. Also haben wir erfolgreich einen Weg gefunden, die AND-Funktion umkehrbar umzusetzen.