Sumário
203 / 216
Salvando leitura…
Duas reflexões produziram uma rotação de amplitude

A média empurrou a agulha para cima

Deutsch, Grover e Shor sem mitologia

Depois do oráculo, Grover aplicava a difusão D=2|s⟩⟨s|−I. Geometricamente, era reflexão em torno de |s⟩. Com a reflexão do oráculo em torno do subespaço não marcado, o produto virava rotação em direção a |w⟩.

Na linguagem de amplitudes reais do caso simples, D refletia cada amplitude em torno da média. A amplitude negativa do item marcado saltava para acima da média, enquanto as outras diminuíam ligeiramente. Repetir acumulava probabilidade no alvo.

Se senθ=1/√N, após k iterações a amplitude marcada era sen((2k+1)θ). Escolher k próximo de π√N/4 tornava a probabilidade próxima de um para uma solução única.

Lia continuou além do ponto ótimo e viu a probabilidade cair. Amplificação era rotação, não convergência irreversível. Conhecer aproximadamente a fração de soluções ou usar variantes adequadas impedia ultrapassar o alvo.

O ganho em consultas era quadrático: O(√N) contra O(N) para busca clássica não estruturada. Para N=10^12, a raiz ainda era um milhão de iterações coerentes, antes de contabilizar portas do oráculo e correção de erros.

Tomás diferenciou amplificação de amplitude de aumento de energia. Nenhum item ficava fisicamente mais luminoso por mágica; a norma total permanecia um e probabilidade era redistribuída por interferência unitária.

A agulha subiu até dominar a medição. O atalho não examinara caixas em paralelo como trabalhadores clássicos; girara um vetor por duas reflexões cuidadosamente alinhadas.

Fontes desta página

  1. Lov K. Grover (1997). Quantum Mechanics Helps in Searching for a Needle in a Haystack.Physical Review Letters, 79, 325–328. Desenvolve a interpretação por interferência da busca quântica e demonstra o ganho quadrático para encontrar um item em dados não ordenados.
  2. Lov K. Grover (1996). A Fast Quantum Mechanical Algorithm for Database Search.Proceedings of the 28th ACM Symposium on Theory of Computing, 212–219. Introduz o algoritmo de busca quântica não estruturada com ordem √N de consultas por inversões de fase e amplificação de amplitude.
  3. Charles H. Bennett, Ethan Bernstein, Gilles Brassard e Umesh Vazirani (1997). Strengths and Weaknesses of Quantum Computing.SIAM Journal on Computing, 26, 1510–1523. Estabelece limites de consulta para computação quântica, incluindo a ordem √N que mostra a otimalidade assintótica da busca não estruturada de Grover.