Interaktives Modell: Quantencomputer 1
 

Aufgabenstellung: Es gibt vier Funktionen f : {0, 1} –® {0, 1}, nämlich:
  • f (0) = 0,    f (1) = 0      (konstant 0)
  • f (0) = 1,    f (1) = 1      (konstant 1)
  • f (0) = 0,    f (1) = 1      (Identität)
  • f (0) = 1,    f (1) = 0      (Vertauschung)
Auf der Seite Funktionsaufruf und Oracle haben wir gesehen, dass jede dieser Funktionen durch einen "Bauteil" berechnet werden kann, den wir Uf  genannt haben. Stellen wir uns vor, jemand überreicht uns einen solchen als "Oracle": Der Bauteil berechnet eine dieser vier Funktionen - wir wissen allerdings nicht, welche. Die Aufgabe besteht darin, herauszufinden, ob die betreffende Funktion konstant oder nicht-konstant ist.

Interaktives Modell: Ein gemäß dem folgenden (auf David Deutsch zurückgehenden) "Schaltplan" aufgebauter Quantencomputer löst diese Aufgabe. Neben den einfachen Bauteilen NOT-Gate (N) und Hadamard-Transformation (H) ist auch das überreichte Oracle eingebaut. Sie können mit Hilfe des Select-Menüs zunächst die Funktion, die es berechnen soll, selbst wählen. Weiters läßt sich jeder Bauteil mit Hilfe einer Checkbox ein- und ausschalten, damit Sie seine Wirkung besser erkennen können. Zu Beginn wird jedes der beiden Register (Qubits) dieses 2-Qubit-Systems in den Basiszustand |0> gebracht. (Das ist der für Quantencomputer übliche "Input"). Zum Schluß kann im ersten Register eine Messung (Ablesung) durchgeführt werden, die das Ergebnis 0 oder 1 liefert. Wiederholtes Klicken auf den Button "Messung" entspricht einem erneuten Durchlauf des gesamten Prozesses.
Funktion wählen:    
Register 1 Register 2    
¯ ¯    
           ..|............ .............|............ ...............    |y> =
 |
N
   
           ..|............ .............|............ ...............    |y> =
H
H
   
           ..|............ .............|............ ...............    |y> =
Uf  
   
           ..|............ .............|............ ...............    |y> =
H
 |    
           ..|............ .............|............ ...............    |y> =
 |  |    
.............|............ ...............    Ergebnis:
 |  |    
           ..|............ .............|............ ...............    |y> =
Indem Sie alle vier Funktionen nacheinander durchgehen, können Sie leicht feststellen, dass - sofern alle Bauteile eingeschaltet sind - das Messergebnis
  • immer 0 ist, wenn die Funktion f  konstant ist und
  • immer 1 ist, wenn die Funktion f  nicht-konstant ist.
Das Messergebnis teilt uns also auf eindeutige Weise mit, ob die vom Oracle Uf  berechnete Funktion f  konstant oder nicht-konstant ist. Damit hat der Quantencomputer seine Aufgabe gelöst. (Durch Probieren können Sie sich davon überzeigen, dass die Sache nicht funktioniert, wenn nicht alle N- und H-Bauteile eingeschaltet sind).

Das Revolutionäre daran ist, dass dazu nur ein einziger Aufruf des Oracles (der Funktion) nötig ist!  Ein klassischer Computer muß die übergebene Funktion zweimal aufrufen, um die gestellte Frage zu entscheiden, denn aus der Kenntnis des einen Funktionswertes folgt ja nicht, ob er gleich dem anderen ist. Der Quantencomputer hingegen ist fähig, durch einen einzigen Aufruf alle Funktionsweise "gleichzeitig" in die Superposition zu packen. Die Gesetze der Quantenphysik erlauben uns zwar nicht, sie alle abzulesen (siehe Interpretation und Messung), aber sie gestatten uns immerhin, durch eine einzige Messung die Konstant bzw. Nicht-Konstanz der Funktion eindeutig zu erschließen.

In diesem einfachen Problem spart ein Quantencomputer im Vergleich zum klassichen Computer die Hälfte aller notwendigen Funktionsaufrufe ein. Das mag nicht gerade großartig erscheinen, ändert sich aber gewaltig, wenn es um komplexere Probleme geht und kann zu einer vielmilliardenfachen Verkürzung der Rechenzeit führen.