Algoritmo de Grover

Em computação quântica, O algoritmo de Grover ou Algoritmo de Busca O(n½) é um algoritmo quântico que encontra com alta probabilidade a entrada exclusiva para uma função de caixa preta que produz um valor de saída específico, usando apenas avaliações da função , em que N é o tamanho do domínio da função. O algoritmo quântico Grover permite uma aceleração enorme em algoritmos de busca que afeta a segurança de muitos criptosistemas, incluindo AES. O algoritmo foi inventado por Lov Grover em 1996. O problema análogo na computação clássica não pode ser resolvido em menos de avaliações (porque, no pior dos casos, o -th membro do domínio pode ser o membro correto). Aproximadamente na mesma época em que Grover publicou seu algoritmo, Bennett, Bernstein, Brassard e Vazirani provaram que qualquer solução quântica para o problema precisa avaliar a função vezes, o algoritmo de Grover é . Foi demonstrado que um computador quântico de variável oculta não local poderia implementar uma pesquisa sobre um banco de dados com items no máximo passos. Isso é mais rápido que a ordem de passos dados pelo algoritmo de Grover. Porém nenhum dos métodos de busca permitirá que computadores quânticos resolvam problemas NP-Completos em tempo polinomial.