← Computação

Algoritmo de Busca de Grover

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

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

  1. 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.

    |s′⟩ |w⟩ θ = 20.70° 2θ k = 0 12.50% k = 1 78.12% k = 2 94.53% k = 3 33.01%

    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=18=12.50%N=8:\quad \text{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⁡θ=1N ⟹ θ=20.70∘;Pk=sin⁡2((2k+1)θ)\sin\theta=\frac{1}{\sqrt N}\ \Longrightarrow\ \theta=20.70^\circ;\quad P_k=\sin^2\left((2k+1)\theta\right)

    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%k=1:\ 78.12\%;\qquad k=2:\ 94.53\%;\qquad 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.

      kopt=⌊π4N⌋=⌊2.221⌋=2k_{\text{opt}}=\left\lfloor\frac{\pi}{4}\sqrt N\right\rfloor=\left\lfloor2.221\right\rfloor=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 ∼N2=4 queriesvsO ⁣(N)=2\text{classical}\ \sim\frac{N}{2}=4\ \text{queries}\quad\text{vs}\quad O\!\left(\sqrt N\right)=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.

    Pk=sin⁡2((2k+1)θ) ROTATES: past kopt it falls againP_k=\sin^2\left((2k+1)\theta\right)\ \text{ROTATES}:\ \text{past}\ k_{\text{opt}}\ \text{it falls again}
Referências (1)

· Verificado com fontes publicadas. Correções bem-vindas.