Algoritmo de Grover

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

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.

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.

Aplicações[editar | editar código-fonte]

Embora o propósito do algoritmo de Grover seja usualmente descrito como "pesquisar num banco de dados", pode ser mais preciso descrevê-lo como "inverter uma função". Na verdade, como um oráculo de um banco de dados não estruturado requer pelo menos complexidade linear, o algoritmo não pode ser usado para bancos de dados reais. [7] Grosso modo, se uma função pode ser avaliada por um computador quântico, o algoritmo de Grover calcula quando dado . A inversão de uma função está relacionada à pesquisa de um banco de dados, porque poderíamos criar uma função que produzisse um valor específico de ("verdadeiro", por exemplo) se corresponde a uma entrada desejada no banco e outro valor de ("false") para outros valores de .

O algoritmo de Grover também pode ser usado para estimar a média e a mediana de um conjunto de números e para resolver o problema de colisão. O algoritmo pode ser aperfeiçoado mais se houver mais de uma entrada combinando e o número dos fósforos for sabido de antemão.

O algoritmo de Grover poderia ser usado para fazer engenharia reversa de funções hash criptográficas, permitindo que um invasor encontre a senha da vítima ou gere uma série de blocos falsificados.

Referências[editar | editar código-fonte]

Ícone de esboço Este artigo sobre computação é um esboço. Você pode ajudar a Wikipédia expandindo-o.