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]
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 .[carece de fontes]
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.[carece de fontes]
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.[carece de fontes]
O matemático Gregory Galperin desenvolveu, em seu artigo “Playing Pool with ”, um incrível método para calcular os dígitos do número , com precisão arbitrária, fazendo uso de um sistema elementar da Física em Mecânica Clássica: colisões elásticas em uma dimensão.[8] Inspirado no trabalho de Galperin, Adam Brown demonstrou que existe um isomorfismo entre o sistema físico usado por Galperin e o algoritmo de Grover. O isomorfismo entre esses dois sistemas surge a partir de seus espaços de configuração. Assim, é possível derivar a não tão óbvia relação entre um sistema simples de bilhar clássico, um algoritmo quântico de busca e o número .[9]
Tópicos sobre computação | |
---|---|
História da computação | |
Hardware | |
Software | |
Internet | |
Cientistas | |
Terminologia |