Größter Satz für einstufige unstrukturierte Quantensuche

Was ist die größte Menge, die einen deterministischen Quantensuchalgorithmus für ein einzelnes markiertes Element zulässt, das nur mit einem einzigen Aufruf des Orakels arbeitet?

Die Frage ist interessant, da Grovers Algorithmus, der für die unstrukturierte Suche in einem Element-Satz O ( $N$ruft das Orakel an, kann tatsächlich einen 4-Elemente-Satz mit nur einem einzigen Anruf durchsuchen.$O(\sqrt{N})$

Im Allgemeinen ist es interessant, nach der Mindestanzahl von Aufrufen eines Quantenorakels zu fragen, die erforderlich sind, um einen unstrukturierten Satz der Größe deterministisch nach einem einzelnen markierten Element zu durchsuchen .$N$

Beachten Sie, dass der Grover-Algorithmus bis zu einem konstanten Faktor in der Grenze von großem optimal ist, obwohl dies natürlich nicht bedeutet, dass er für eine gegebene endliche Menge optimal ist.$N$

Vielleicht eine geeignetere für Ihre Frage: Dong Pyo Chi und Jinsoo Kim zeigten , dass für alle „Grover-like“ Algorithmus, bei dem können wir die Phase des Diffusions Operators und das Orakel Tor von ändern möglicherweise unabhängig und beliebigen komplexen Phasen kann ein markiertes Element mit einer einzigen Abfrage , wenn gefunden wird , wenn und nur gibt es mindestens N / 4 markierte Elemente. Hier ist ein Link zu ihrem Artikel.$-1$$N/4$

Beachten Sie, dass der Fall früher von Brassard, Boyer, Hoyer und Tapp entdeckt wurde.$t=N/4$

Lov Grover veröffentlichte 1997 einen Artikel, in dem er zeigt, dass eine einzige Abfrage ausreicht, um das markierte Element zu finden, wenn Sie die Datenbank für mehrere Elemente abfragen können. Es erfordert jedoch eine Anzahl von Vorverarbeitungs- und Nachverarbeitungsschritten in .$\Omega(N\log N)$

Wenn Sie die Elemente der Datenbank bezeichnen lassen, fragen Sie das Orakel mit der Zeichenfolge S i 1 , … , S i η nach einer Zahl η ab, und das Orakel gibt 1 zurück, wenn der markierte Zustand als ungerade Zahl erscheint Anzahl der Male in der Zeichenfolge und 0, wenn sie gerade erscheint. Sie fragen diese Orakel auf einer Überlagerung ( | S $S_1, \dots, S_N$$S_{i_1}, \dots, S_{i_\eta}$$\eta$$1$$0$$(|S_1\rangle+ \dots+ |S_N\rangle)^\eta$und wenden Sie dann die Inversion über den Mittelwertoperator aus dem Grover-Algorithmus an. In jedem der Subsysteme hat das markierte Element eine größere Amplitude als die nicht markierten. Das Messen aller Subsysteme ergibt den markierten Zustand mit größerer Wahrscheinlichkeit und um eine ausreichende Gewissheit über den resultierenden Zustand zu haben, muss η in Ω ( N log N ) sein .$\eta$$\eta$$\Omega(N\log N)$