Otimização do algoritmo de Grover com alta probabilidade de sucesso

É sabido que a complexidade da consulta quântica de erro limitado da função é . Agora, a questão é: se queremos que nosso algoritmo quântico seja bem-sucedido para cada entrada com probabilidade em vez dos usuais . Agora, em termos de quais seriam os limites superior e inferior apropriados?Θ ( $OR(x_1,x_2,\ldots, x_n)$1-ε2/3$\Theta(\sqrt{n})$$1-\epsilon$$2/3$$\epsilon$

É imediato que as consultas suficientes para esta tarefa, repetindo o algoritmo Grover. Mas pelo que me lembro, isso não é de todo ideal, já que o algoritmo Grover simples, se executado com cuidado, ou seja, para um número apropriado de iterações, pode obter algo como com apenas iterações. E, portanto, usá-lo pode obter uma melhoria para todos os 's. Por outro lado, não espero que seja a resposta certa para 's muito pequenos .ϵ=O(1/n)O($O(\sqrt{n} \log(1/\epsilon))$$\epsilon=O(1/n)$ϵΩ($O(\sqrt{n})$$\epsilon$$\Omega(\sqrt{n})$$\epsilon$

Mas estou interessado em ver o que se pode mostrar em termos dos limites superior e inferior dependentes de para diferentes intervalos de especialmente quando é muito pequeno, digamos ou para 's grandes .ϵ ϵ ϵ = exp ( - Ω ( n ) ) ϵ = 1 / n k$\epsilon$$\epsilon$$\epsilon$$\epsilon= \exp(-\Omega(n))$$\epsilon=1/n^k$$k$

(Para dar algum contexto, o fenômeno geral que estou abordando é a amplificação no contexto da complexidade quântica de consultas.)

Por uma questão de integridade, aqui está uma resposta.

Seja a complexidade quântica de consultas error de calcular uma função e seja a função OR em bits, definida como . (Observe que isso é diferente do problema em que você promete que a entrada possui exatamente um 1 e o objetivo é descobrir que 1. Esse problema pode ser resolvido sem nenhum erro nas consultas .)ϵ f O R n n O R n ( x 1 , … , x n ) = ⋁ n i = 1 x i Θ ( $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})$

Então temos para todos ,$\epsilon \in [2^{-n},1/3]$

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

Segue Limites para algoritmos quânticos de erro pequeno e erro zero .

De fato, sabemos algo mais geral. Para todas as funções simétricas , que são funções que dependem apenas do peso de Hamming da entrada, temos isso para todos ,£ ∈ [ 2 - N , 1 / 3 $f$$\epsilon \in [2^{-n},1/3]$

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

Isso foi mostrado em uma nota sobre algoritmos quânticos e o grau mínimo de polinômios de erro épsilon para funções simétricas .