Was genau ist ein Orakel?

18

Was genau ist ein " Orakel "? Wikipedia sagt, dass ein Orakel eine " Blackbox " ist, aber ich bin nicht sicher, was das bedeutet.

Zum Beispiel in dem Deutsch-Jozsa Algorithmus , , ist das Orakel nur das Feld mit der Bezeichnung oder ist es alles zwischen der Messung und den Eingängen (einschließlich den Hadamard Tor)?

''Uf",

Und um das Orakel zu geben, muss ich Uf in Matrixform oder in kondensierter Form schreiben : Uf gibt y→y⊕f(x) und x→x ist ausreichend für die Definition eines Orakels?

quantum-information terminology oracles StarBucK
quelle
Microsoft hat eine gute Dokumentation zu Quantenorakeln .
Sanchayan Dutta

Antworten:

22

Ein Orakel (zumindest in diesem Zusammenhang) ist einfach eine Operation, die eine Eigenschaft hat, die Sie nicht kennen und die Sie herausfinden möchten. Der Begriff "Black Box" wird gleichbedeutend verwendet, um die Idee zu vermitteln, dass es sich nur um eine Box handelt, die Sie nicht sehen können und daher nicht wissen, was sie tut. Sie wissen nur, dass Sie Eingänge liefern und Ausgänge empfangen können. In dem von Ihnen dargestellten Schaltplan handelt es sich nur um das Feld . Alles andere sind Dinge, die Sie hinzufügen, um das Orakel zu befragen und seine Eigenschaften zu entdecken.Uf

Um das Orakel zu geben, können Sie es in jeder gültigen Form schreiben, die eine Karte von allen möglichen Eingaben zu Ausgaben definiert. Dies könnte eine Matrix sein (vermutlich mit einem unbekannten Parameter) oder die Map (genau genommen ), da bei beiden Beschreibungen die jeweils andere berechnet werden kann.U:(x,y)↦(x,y⊕f(x))∀x,y∈{0,1}

DaftWullie
quelle
Können Sie klarstellen, was Sie im letzten Satz genau gemeint haben?
Aritra Das
@tparker nicht wirklich - der Zweck solcher Orakelformen ist oft, dass es eine Beschreibung nicht nur des Algorithmus, sondern zur Optimierung des Algorithmus ermöglicht. Das wird einfach als Anzahl der Verwendungen des Orakels gemessen. Es ist egal, wie lange das Orakel braucht, um zu rennen. Für Grover erfordert dies die Quadratwurzel der Anzahl der Orakelrufe, die der klassische macht.
DaftWullie
Du hast recht; Mein Kommentar war schlecht formuliert. Was ich damit sagen wollte ist, dass, wenn Sie möchten, dass ein Oracle-Ergebnis einen Einblick in eine "reale" Laufzeit gibt, Sie (zusätzlich zu der Black-Box-Annahme) davon ausgehen müssen, welche Subroutine Sie ausführen, um sie tatsächlich zu implementieren Der Oracle-Aufruf dominiert die Laufzeit des Algorithmus, so dass die Anzahl der Oracle-Aufrufe tatsächlich proportional zur tatsächlichen Laufzeit ist. Dies ist jedoch eine zusätzliche Annahme für die Relevanz in der "realen Welt" und kein notwendiger Bestandteil der Definition eines Orakels.
tparker