5.2 Quantenalgortihmen

In diesem Abschnitt werden wir uns verschiedene Quantenalgorithmen anschauen, die ein Rechenproblem viel schneller als klassische Computer lösen können. Solche Verbesserungen der Laufzeit sind sehr unerwartet, da Quantenmechanik auf den ersten Blick nichts mit der eigentlichen Berechnung zu tun haben scheint. Trotzdem können Quantenmechanische Phänomene wie Interferenz beeindruckende Beschleunigungen erzielen. Wie wir bereits im Voraus erklärt hatten, zählen wir dabei nur die Anzahl der Fragen, die an ein Orakel gestellt werden. Angenommen wir können also die Funktion $f$ auf jeder Eingabe evaluieren, auf wie vielen Eingaben müssen wir die Funktion auswerten um eine Eigenschaft von $f$ zu bestimmen. Oder anders gesagt, wie oft müssen wir das Orakel $O_{f}$, welches $f$ auswerten kann, benutzen, um die Eigenschaft von $f$ zu bestimmen.