Algoritmo de Grover
Busca em um conjunto não ordenado em raiz quadrada do número de passos, em vez de metade deles: um ganho quadrático, não exponencial.
Lov Grover o publicou em 1996. Achar a entrada certa entre um milhão, sem nenhuma estrutura a explorar, leva em média meio milhão de tentativas de forma clássica. O algoritmo de Grover resolve em cerca de mil. O método se chama amplificação de amplitude: a amplitude da resposta correta é empurrada para cima passo a passo enquanto as demais são empurradas para baixo, e depois de umas √N iterações ela domina.
O ganho é real, mas modesto perto do de Shor. A consequência prática para a criptografia é que o tamanho efetivo das chaves simétricas cai pela metade: o AES-128 mantém uma margem equivalente a 64 bits, enquanto o AES-256 continua adequado. Por isso a criptografia simétrica não precisa ser trocada antes da chegada dos computadores quânticos, ao contrário da assimétrica.