Tempo de execução do algoritmo de Grover

Qual é a complexidade do tempo (não a complexidade da consulta) do algoritmo de Grover? Parece-me claro que é pois existem iterações e cada iteração requer o uso da operação de reflexão que, por sua vez, leva tempo usando qualquer conjunto padrão de portas universais.Ω($\Omega(\log(N) \sqrt{N})$Ω(log(N)$\Omega(\sqrt{N})$$\Omega(\log(N))$

O problema é que não consigo encontrar nem uma única referência que diga que a complexidade de tempo do algoritmo de Grover é . A Wikipedia e várias outras páginas da Web dizem a complexidade do tempo . O artigo de Grover reivindica "etapas".O($\Omega(\log(N) \sqrt{N})$O($O(\sqrt{N})$$O(\sqrt{N})$

Estou esquecendo de algo? Talvez as pessoas definam a operação de reflexão para levar o tempo da unidade. Mas isso não faz sentido para mim, porque se pudermos jogar o jogo de permitir que os unitários arbitrários levem tempo unitário, não haveria diferença entre a complexidade da consulta e a complexidade do tempo.

Geralmente, a questão é discutida pelo seguinte motivo. O algoritmo de Grover é um algoritmo de busca combinatória para encontrar uma solução para um predicado arbitrário. Enquanto, sim, é a complexidade da porta quântica em cada estágio do algoritmo de caixa preta, o predicado também precisa ser calculado. A complexidade do portão quântico é , porque, caso contrário, não leria toda a entrada e você poderia descartar alguns bits de entrada da pesquisa. Por outro lado, um predicado interessante pode levar muito mais tempo que isso. Portanto, o número de chamadas para o predicado é considerado a moeda padrão, assim como para o análogo clássico do algoritmo de Grover, ou seja, a adivinhação aleatória.Ω ( log N $\Theta(\log N)$$\Omega(\log N)$

Acontece que existe uma maneira de implementar o algoritmo de Grover com menos de portas! É por isso que você não conseguiu encontrar uma referência alegando que as portas são necessárias. Pelo menos no caso em que há um item marcado, é possível fazer melhor.Ω($O(\sqrt{N}\log N)$$\Omega(\sqrt{N}\log N)$

Uma pré-impressão recente de Arunachalam e de Wolf fornece um novo algoritmo para resolver o problema de pesquisa com um item marcado com complexidade de consulta e apenas portões (do portão, defina Toffoli + todos os portões de um qubit).O($O(\sqrt{N})$$O(\sqrt{N}\log(\log^* N))$

Observe que a função cresce tão lentamente que, mesmo que seja o número de átomos no universo, é no máximo 3.N log ( log ∗ N $\log(\log^* N)$$N$$\log(\log^* N)$