Algoritmo de Busca de Grover

Encontre uma agulha no palheiro em √N passos em vez de N

Exemplo resolvido — Algoritmo de Busca de Grover

Iteração atual	0 (Sobreposição)
Probabilidade alvo	12.50%
Clássico (1/N)	12.50%
Iteração	0 / 2 · Superposição

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Por que √N e não mais rápido? 🖖

O algoritmo de Grover alcança O(√N) consultas, e isso é provavelmente ótimo. Cada iteração gira o estado por θ ≈ 2/√N radianos.

Como a resposta certa é amplificada 🖖

Numa superposição uniforme, cada candidato começa com a mesma amplitude minúscula. Cada rodada faz duas coisas: um oráculo inverte o sinal da amplitude do alvo e, em seguida, uma 'inversão em torno da média' reflete todas as amplitudes ao redor da sua média — a marcada sobe e as demais descem. Repetindo, a probabilidade do alvo se aproxima de 1. Para uma lista de N = 1,000,000, uma busca clássica verifica em média 500,000 entradas; Grover precisa de apenas cerca de 1,000.

Quatro itens, um passo, certeza 🖖

Para N = 4 — uma busca de dois qubits — Grover não é apenas rápido, é exato: uma única iteração acerta o alvo com 100% de probabilidade. O ângulo de rotação satisfaz sin(θ/2) = 1/√N = 1/2, logo θ = 60°, e após um passo o estado girou exatamente (2·1+1)·30° = 90° até o eixo do alvo. É o caso raro em que um algoritmo quântico dá uma resposta garantida, e não apenas provável.

Problema resolvido na íntegra

Duas iterações para encontrar um item marcado entre 8 5 passos
O algoritmo de Grover encontra um item marcado entre 8 em duas iterações. Descubra de onde vem o dois — e o que acontece se executar uma terceira.
1. Antes de qualquer execução, o estado é uma superposição uniforme: cada item é igualmente provável, pelo que o marcado transporta 1/8 da probabilidade. Isto é o mesmo que um palpite aleatório clássico, e o painel mostra ambos para evidenciar o facto.
  
  $N = 8 : uniform superposition gives P = \frac{1}{8} = 12.50%$
2. Cada iteração de Grover é uma rotação por um ângulo fixo num plano bidimensional gerado pelo estado marcado e por todos os outros. O ângulo deriva da amplitude e, para N = 8, é de cerca de 20,7°.
  
  $sin θ = \frac{1}{N} ⟹ θ = 20.7 0^{\circ}; P_{k} = sin^{2} ((2 k + 1) θ)$
3. Assim, a probabilidade não é uma curva que sobe e estabiliza — é um seno ao quadrado, e sobe acentuadamente: 12,5%, depois 78,1%, depois 94,5%.
  
  $k = 1 : 78.12%; k = 2 : 94.53%; k = 3 : 33.01%$
4. O ponto de paragem ótimo é a rotação que fica mais próxima de 90°, que é π/4 vezes a raiz quadrada de N. Para oito itens, esse valor é 2,22 e, como não é possível realizar uma iteração fracionária, o resultado é 2.
  
  $k_{opt} = ⌊ \frac{π}{4} N ⌋ = ⌊ 2.221 ⌋ = 2$
5. Execute uma terceira e a rotação ultrapassa o ponto ótimo. A probabilidade cai para 33,0% — pior do que após uma iteração, regressando em direção ao ponto de partida.
  
  $classical \sim \frac{N}{2} = 4 queries vs O (N) = 2$
Resposta

A ferramenta apresenta 12,50% tanto para a sobreposição inicial como para o caso clássico de 1 em N e interrompe a execução automática em 2, embora os controlos para avançar uma etapa e saltar para o fim permitam chegar a 5. É o excesso de iterações que costuma surpreender: mais iterações pioram o resultado, pois a amplificação de amplitude é uma rotação, e as rotações acabam por dar a volta completa. É também por isso que a aceleração de Grover é apenas quadrática, não exponencial. São necessárias cerca de √N rotações para chegar aos 90°; assim, 8 elementos exigem 2, enquanto um milhão exige 785. É uma vantagem considerável, mas muito diferente da vantagem exponencial que a expressão «pesquisa quântica» pode sugerir.

$P_{k} = sin^{2} ((2 k + 1) θ) ROTATES : past k_{opt} it falls again$

Referências (1)

The algorithm this tool steps through: L. K. Grover, "A fast quantum mechanical algorithm for database search." Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 212–219, 1996.

Pela equipa 42Math · Atualizado 2026-07-29

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Computação →

Problemas de exemplo

N = 4 - N=4 itens — apenas 1 iteração de Grover é necessária para encontrar o alvo
N = 8 - N=8 itens — ~2 iterações são o ideal, tamanho clássico para demonstração
N = 16 - N=16 itens — 3 iterações são o ideal, O(√N) visível
N = 32 - N=32 itens — ~4 iterações, mostra a vantagem quadrática