Algoritmo de Grover

Em computação quântica, o algoritmo de Grover, também conhecido como algoritmo de busca quântica, é um algoritmo quântico para busca não estruturada que encontra com alta probabilidade a única entrada para uma função de caixa preta que produz um determinado valor de saída, usando apenas O ( N ) {\displaystyle O({\sqrt {N}})} avaliações da função, onde N {\displaystyle N} é o tamanho do domínio da função. Ele foi concebido por Lov Grover em 1996. O problema análogo na computação clássica teria uma complexidade de consulta de O ( N ) {\displaystyle O(N)} (isto é, a função teria de ser avaliada O ( N ) {\displaystyle O(N)} vezes: não existe abordagem melhor do que testar todos os valores de entrada um após o outro, o que, em média, leva N / 2 {\displaystyle N/2} passos). Charles H. Bennett, Ethan Bernstein, Gilles Brassard e Umesh Vazirani provaram que qualquer solução quântica para o problema precisa avaliar a função Ω ( N ) {\displaystyle \Omega ({\sqrt {N}})} vezes, logo o algoritmo de Grover é assintoticamente ótimo. Uma vez que os algoritmos clássicos para problemas NP-completos requerem um número exponencial de passos, e o algoritmo de Grover fornece, no máximo, uma aceleração quadrática sobre a solução clássica para a busca não estruturada, isso sugere que o algoritmo de Grover, por si só, não fornecerá soluções em tempo polinomial para problemas NP-completos (já que a raiz quadrada de uma função exponencial continua sendo uma função exponencial, não polinomial). Ao contrário de outros algoritmos quânticos, que podem fornecer aceleração exponencial sobre suas contrapartes clássicas, o algoritmo de Grover fornece apenas uma aceleração quadrática. No entanto, mesmo uma aceleração quadrática é considerável quando N {\displaystyle N} é grande, e o algoritmo de Grover pode ser aplicado para acelerar amplas classes de algoritmos. O algoritmo de Grover poderia...