Sur l'optimalité de l'algorithme de Grover avec une probabilité de réussite élevée

Il est bien connu que la complexité de la requête quantique d'erreur bornée de la fonction est Θ ( $OR(x_1,x_2,\ldots, x_n)$. Maintenantla question est que si nous voulonsnotre algorithme quantique pour réussir à chaque entrée avecprobabilité1-εplutôt que l'habituel2/3. Maintenant, en termes deϵquelles seraient les limites supérieure et inférieure appropriées?$\Theta(\sqrt{n})$$1-\epsilon$$2/3$$\epsilon$

Il est immédiat que requêtes suffisent pour cette tâche en répétant l'algorithme Grover. Mais d'après ce dont je me souviens, ce n'est pas du tout optimal car même un algorithme de Grover simple, s'il est exécuté avec soin, c'est-à-dire pour un nombre approprié d'itérations, peut atteindre quelque chose commeϵ=O(1/n)avec justeO($O(\sqrt{n} \log(1/\epsilon))$$\epsilon=O(1/n)$itérations. Et donc en utilisant cela, on peut obtenir une amélioration pour tous lesϵ. Par contre, je ne m'attends pas à ce queΩ($O(\sqrt{n})$$\epsilon$être la bonne réponse pour les très petitsϵ.$\Omega(\sqrt{n})$$\epsilon$

Mais je suis intéressé de voir ce que l'on peut montrer en termes de bornes supérieures et inférieures dépendantes de pour différentes plages de ϵ, en particulier lorsque ϵ est très petit, disons ϵ = exp ( - Ω ( n ) ) ou ϵ = 1 / n k pour gros k .$\epsilon$$\epsilon$$\epsilon$$\epsilon= \exp(-\Omega(n))$$\epsilon=1/n^k$$k$

(Pour donner un peu de contexte, le phénomène général auquel je veux en venir est l'amplification dans le contexte de la complexité des requêtes quantiques.)

Par souci d'exhaustivité, voici une réponse.

$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)})$

Cela découle des limites pour les algorithmes quantiques à petite erreur et à zéro erreur .

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

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

Cela a été montré dans une note sur les algorithmes quantiques et le degré minimal de polynômes d'erreur epsilon pour les fonctions symétriques .