Algoritmo de Busca de Grover
Encontre uma agulha no palheiro em √N passos em vez de N
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.