Zur Optimalität des Grover-Algorithmus mit hoher Erfolgswahrscheinlichkeit

Es ist bekannt , dass beschränkte Fehler quantum query Komplexität der Funktion ist , Θ ( $OR(x_1,x_2,\ldots, x_n)$. Nun ist die Fragewas passiertwenn wir unser Quantenalgorithmus für jede Eingabe mitWahrscheinlichkeit erfolgreich sein wollen1-εanstatt der üblichen2/3. Was wärenun in Bezug aufϵdie geeignete Ober- und Untergrenze?$\Theta(\sqrt{n})$$1-\epsilon$$2/3$$\epsilon$

Es ist unmittelbar, dass Abfragen reichen für diese Aufgabe aus, indem der Grover-Algorithmus wiederholt wird. Soweit ich mich erinnere, ist dies jedoch keineswegs optimal, da selbst ein einfacher Grover-Algorithmus bei sorgfältiger Ausführung, dh bei einer angemessenen Anzahl von Iterationen,mit nurO( √ )so etwas wieϵ=O(1/n)erreichen kann$O(\sqrt{n} \log(1/\epsilon))$$\epsilon=O(1/n)$Iterationen. Und daher mitdass man eine Verbesserung für alle erhalten könnenε‚s. Andererseits erwarte ich nicht, dassΩ($O(\sqrt{n})$$\epsilon$die richtige Antwort für sehr kleineϵ sein.$\Omega(\sqrt{n})$$\epsilon$

Aber ich bin interessiert zu sehen, was man in Bezug auf abhängige Ober- und Untergrenzen für verschiedene Bereiche von ϵ zeigen kann, besonders wenn ϵ sehr klein ist, sagen wir ϵ = exp ( - Ω ( n ) ) oder ϵ = 1 / n k für große k 's.$\epsilon$$\epsilon$$\epsilon$$\epsilon= \exp(-\Omega(n))$$\epsilon=1/n^k$$k$

(Um einen gewissen Kontext zu geben, ist das allgemeine Phänomen, auf das ich stoße, die Verstärkung im Kontext der Komplexität von Quantenabfragen.)

Der Vollständigkeit halber hier eine Antwort.

$Q_\epsilon(f)$$\epsilon$$f$$\mathsf{OR}_n$$n$$\mathsf{OR}_n(x_1,\ldots,x_n)=\bigvee_{i=1}^n x_i$$\Theta(\sqrt{n})$

$\epsilon \in [2^{-n},1/3]$

$Q_\epsilon(\mathsf{OR}_n) = \Theta(\sqrt{n\log(1/\epsilon)})$

Dies folgt aus den Grenzen für Quantenalgorithmen mit kleinen Fehlern und mit null Fehlern .

$f$$\epsilon \in [2^{-n},1/3]$

$Q_\epsilon(f) = \Theta(Q_{1/3}(f)+\sqrt{n\log(1/\epsilon)})$

Dies wurde in einem Hinweis zu Quantenalgorithmen und dem minimalen Grad an Epsilon-Fehler-Polynomen für symmetrische Funktionen gezeigt .