Algoritmo de Grover
algoritmo quântico / De Wikipedia, a enciclopédia encyclopedia
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.[1] O algoritmo quântico Grover permite uma aceleração enorme em algoritmos de busca que afeta a segurança de muitos criptosistemas, incluindo AES.[2] O algoritmo foi inventado por Lov Grover em 1996.[3]
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 é assintoticamente ótimo.[4]
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.[5]
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 um aumento de velocidade quadrático. No entanto, mesmo a aceleração quadrática é considerável quando é grande. O algoritmo de Grover poderia forçar brutalmente uma chave criptográfica simétrica de 128 bits em aproximadamente 2 64 iterações, ou uma chave de 256 bits em aproximadamente 2 128 iterações. Como resultado, às vezes é sugerido[6] que os comprimentos de chave simétrica sejam duplicados para proteger contra futuros ataques quânticos.[carece de fontes?]
Como muitos algoritmos quânticos, o algoritmo de Grover é probabilístico no sentido de dar a resposta correta com uma probabilidade menor que 1. Embora tecnicamente não haja limite superior no número de repetições que podem ser necessárias antes que a resposta correta seja obtida, o número esperado de repetições é um fator constante que não cresce com . O artigo original de Grover descreveu o algoritmo como um algoritmo de busca de banco de dados, e essa descrição ainda é comum. O banco de dados nesta analogia é uma tabela de todas as saídas da função, indexada pela entrada correspondente.[carece de fontes?]