Wie ist die Ausgabe von Grovers Algorithmus nützlich, wenn das Ergebnis zur Verwendung des Orakels benötigt wird? Wenn wir den gewünschten Zustand bereits kennen, was bringt es dann, den Algorithmus zu verwenden?
Können Sie mir also ein konkretes Beispiel für eine Orakelfunktion geben? Wenn die indizierten Elemente in einer Grover-Suche beispielsweise beliebige Muster wären, wie würde die entsprechende Orakelfunktion aussehen? Machen wir das Beispiel konkreter. Jedes Muster ist das Bild eines Gesichts und wir wollen sehen, ob sich ein unbekanntes Gesicht innerhalb des Mustersatzes befindet. Klassischerweise ist unser Suchalgorithmus ein Korrelationsalgorithmus (zB Kendall-Tau, Rangkorrelation etc.). Was wäre das Analogon dazu für eine Quantensuche?
Es gibt einen Unterschied zwischen dem Finden einer Lösung und dem Erkennen einer Lösung. Oracle kann die Lösung erkennen oder eine bestimmte Instanz des Problems lösen, kann Ihnen jedoch keine Lösung für das vollständige Problem geben. Oder mit anderen Worten, Oracle gibt Ihnen einen Teil der Lösung und Sie müssen Oracle möglicherweise mehrmals konsultieren, um die vollständige Lösung zu erhalten. Oracle kann auch als Bibliotheksfunktion (wie in Programmiersprachen) betrachtet werden, die Ihnen eine Lösung für eine Instanz eines Problems bietet, und die tatsächlichen Berechnungskosten werden daran gemessen, wie oft Sie die Funktion aufrufen, und nicht an der inhärenten Komplexität der Funktion selbst, die als Blackbox genommen wird. Nehmen wir zum Beispiel an, wir haben ein Orakel für eine Funktion , wenn man diesem Orakel ein Paar überreicht es wird sich zeigen, ob oder nicht. In diesem Fall wird die Zeitkomplexität als die Zeit angesehen, die Sie benötigen, um das Orakel zu konsultieren, um das gewünschte Ergebnis zu erhalten.
Ein konkreteres Beispiel kann dem Orakel entnommen werden, um zu überprüfen, ob die Zahl eine Primzahl ist. Nehmen wir an, wir wollen die erste Primzahl finden . Das Problem ist unterschiedlich komplex, wenn Sie Zugriff auf das Orakel erhalten und wenn Sie keinen Zugriff erhalten.
Physikalisches Beispiel eines Orakels: Nehmen wir an, unser Problem besteht darin, den Winkel zwischen Boden und Wand zu bestimmen, was nicht unbedingt der Fall sein muss dazu. Alles, was Sie tun können, ist, einen Ball zu werfen, der elastisch an der Wand kollidiert und zurückkehrt. Sie haben die Kontrolle über den Winkel, den Sie werfen, und Sie können den Winkel notieren, in dem er zurückgekommen ist. Jeder Wurf eines Balls kann mit dem Aufruf einer Orakelfunktion verglichen werden und die Einschränkung des Winkels des zurückkehrenden Balls (Reflexion, die einen Hinweis auf die Ausrichtung der Wand gibt) kann als Orakel betrachtet werden. Die Anzahl der Male, die Sie das Werfen des Balls wiederholen müssen, um die Orientierung mit der gewünschten Genauigkeit zu erhalten, kann als die Komplexität des Problems relativ zum Orakel angesehen werden.
Das Orakel muss den gewünschten Zustand nicht kennen , um zu überprüfen , ob ein gegebener Zustand der gewünschte Zustand ist.
Der Algorithmus von Grover kann auf NP-vollständige Probleme angewendet werden . Dies ist der Satz von Problemen, für die es keinen bekannten Weg gibt, eine Lösung in polynomieller Zeit zu generieren, aber eine gegebene Lösung kann in polynomieller Zeit erkannt werden.