Sobre la optimización del algoritmo de Grover con alta probabilidad de éxito

Es bien sabido que la complejidad de la consulta cuántica de error acotado de la función es Θ ( $OR(x_1,x_2,\ldots, x_n)$. Ahora la pregunta es ¿y si queremos que nuestro algoritmo cuántico tenga éxito para cada entrada con probabilidad1-εen lugar de la habitual2/3. Ahora, en términos deϵ,¿cuáles serían los límites superior e inferior apropiados?$\Theta(\sqrt{n})$$1-\epsilon$$2/3$$\epsilon$

Es inmediato que suficientes para esta tarea repitiendo el algoritmo de Grover. Pero por lo que recuerdo, esto no es del todo óptimo, ya que incluso el algoritmo de Grover simple si se ejecuta con cuidado, es decir, para el número apropiado de iteraciones, puede lograr algo comoϵ=O(1/n)con soloO($O(\sqrt{n} \log(1/\epsilon))$$\epsilon=O(1/n)$iteraciones. Y, por lo tanto, usarlo puede obtener una mejora para todos losϵ. Por otro lado, no espero queΩ($O(\sqrt{n})$$\epsilon$sea ​​la respuesta correcta paraϵmuy pequeños.$\Omega(\sqrt{n})$$\epsilon$

Pero estoy interesado en ver qué se puede mostrar en términos de límites superiores e inferiores dependientes de para diferentes rangos de ϵ especialmente cuando ϵ es muy pequeño, digamos ϵ = exp ( - Ω ( n ) ) o ϵ = 1 / n k para grandes k 's.$\epsilon$$\epsilon$$\epsilon$$\epsilon= \exp(-\Omega(n))$$\epsilon=1/n^k$$k$

(Para dar un poco de contexto, el fenómeno general al que me refiero es la amplificación en el contexto de la complejidad de la consulta cuántica).

En aras de la integridad, aquí hay una respuesta.

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

Esto se desprende de los límites para algoritmos cuánticos de pequeño error y cero error .

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

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

Esto se mostró en una nota sobre algoritmos cuánticos y el grado mínimo de polinomios de error épsilon para funciones simétricas .