O algoritmo de Grover: busca quântica
Aula 11 de 23 do curso “Quântica”. Grátis, com animações e teste.
O problema das caixas
Você tem N caixas fechadas e um presente em uma delas. Sem dicas: abre, olha, fecha. Em média vai abrir metade das caixas, no pior caso todas. A versão quântica: temos um “oráculo”, um circuito que diz se a caixa é a certa. Em 1996 Lov Grover, do Bell Labs, mostrou como achar o presente em cerca de √N perguntas. Para um milhão de caixas são umas 800 perguntas em vez de meio milhão.
Como funciona: marcar e refletir
Primeiro, as portas H dão a todas as caixas a mesma amplitude. Passo 1: o oráculo coloca um menos na amplitude da caixa certa, o passo de marcação da nossa receita. Passo 2: “reflexão em torno da média”. A média caiu um pouco por causa do menos, e cada amplitude é virada em torno dela. As caixas comuns ficam um pouco mais baixas, e a negativa salta lá para cima. Repita “marca + reflexo” e a caixa certa cresce a cada vez.
O segredo é parar na hora
Um detalhe nada óbvio: Grover não é “quanto mais, melhor”. A amplitude da caixa certa cresce como uma seta girando. Com 64 caixas, depois de uns 6 passos a chance é quase 100%, e se continuar, a seta passa do ponto e a chance começa a cair. Por isso o número de passos é calculado antes: cerca de π/4 · √N. Se você não sabe quantos presentes há, existem variantes espertas, mas aí já é detalhe.
Grover e a criptografia
Adivinhar uma chave de cifra é exatamente buscar uma caixa entre um número enorme. O AES-128 tem 2 elevado a 128 opções. Grover tira a raiz e sobram 2 elevado a 64 passos, então a segurança de “128 bits” vira “64 bits”. Na prática até isso é muito: os passos de Grover rodam estritamente um após o outro, e não dá para espalhá-los por milhares de máquinas tão fácil quanto a força bruta comum. Mas a cura é simples e já se usa: o AES-256 continua com 128 bits depois de Grover.
O limite de velocidade
E se alguém inventar uma busca ainda mais rápida? Não: em 1997 quatro pesquisadores, Bennett, Bernstein, Brassard e Vazirani, provaram que na busca “às cegas” √N é o limite para qualquer computador quântico. Daí uma conclusão importante. Muitos problemas difíceis, como a rota de entrega ideal, se resumem no fundo a testar opções. Um computador quântico os acelera no máximo até a raiz, não os torna instantâneos. Ninguém achou aceleração exponencial para eles.
Onde Grover é útil de verdade
Parece um “Google quântico”, mas para buscar numa base de dados comum o Grover quase não serve. Para perguntar ao oráculo, primeiro é preciso carregar os dados numa memória quântica, e isso já leva da ordem de N passos e come o ganho. O valor real está onde as “caixas” não são armazenadas, mas calculadas por fórmula: adivinhar chaves, checar soluções, uma sub-rotina dentro de algoritmos mais complexos. E tudo isso vai precisar de grandes computadores com correção de erros.
Teste-se
- Quantos passos de Grover para 10.000 opções?
Resposta certa: Cerca de 80. √10.000 = 100, e π/4 · 100 ≈ 79. Aceleração quadrática, não instantânea. - Um amigo rodou o triplo de passos de Grover “por garantia”. O que acontece?
Resposta certa: A chance cai: a seta passa da resposta. Grover é uma rotação. Depois do ponto ideal, a amplitude da caixa certa volta a diminuir. - É preciso trocar o AES-256 com urgência por causa do Grover?
Resposta certa: Não: depois de Grover ele ainda tem 128 bits de segurança. Grover corta os bits pela metade, e 128 bits são considerados seguros. Por isso o AES-256 é recomendado a longo prazo.
← O mito do “testa tudo de uma vez” O algoritmo de Shor e o RSA →