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 $O({\sqrt {N}})$ , 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 $O(N)$ avaliações (porque, no pior dos casos, o $N$-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 $\Omega ({\sqrt {N}})$ vezes, o algoritmo de Grover é assintoticamente ótimo.

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 $N$no máximo $O({\sqrt[{3}]{N}})$ passos. Isso é mais rápido que a ordem de $O({\sqrt {N}})$ 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.

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 $N$ é grande. O algoritmo de Grover poderia forçar brutalmente uma chave criptográfica simétrica de 128 bits em aproximadamente 2 ⁶⁴ iterações, ou uma chave de 256 bits em aproximadamente 2 ¹²⁸ iterações. Como resultado, às vezes é sugerido 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 $N$. 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]}

Aplicações

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. Grosso modo, se uma função $y=f(x)$ pode ser avaliada por um computador quântico, o algoritmo de Grover calcula $x$ quando dado $y$. 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 $y$ ("verdadeiro", por exemplo) se $x$ corresponde a uma entrada desejada no banco e outro valor de $y$ ("false") para outros valores de $x$.^{[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 isomorfismo inesperado entre um sistema de bilhar e o algoritmo de Grover

O matemático Gregory Galperin desenvolveu, em seu artigo “Playing Pool with $\pi$”, um incrível método para calcular os dígitos do número $\pi$, 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. 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 $\pi$.

Notas

•  Este artigo incorpora texto de um trabalho de conteúdo livre. Licenciado em CC-BY-4.0 Declaração da licença: Sena, Vitor Lucas O.; Soares-Pinto, Diogo O. (2 de julho de 2021). «O isomorfismo inesperado entre um sistema de bilhar e um algoritmo quântico». Revista Brasileira de Ensino de Física. ISSN 1806-1117. doi:10.1590/1806-9126-RBEF-2021-0088. Consultado em 29 de setembro de 2022 , Para aprender como acrescentar texto de licenças livres a artigos da Wikipédia, veja em agregar textos em licença livre na Wikipédia. Para mais informações sobre como reutilizar texto da Wikipédia, veja as condições de uso.