Introdução
O algoritmo de Grover é um algoritmo quântico para os chamados problemas de busca não estruturada que oferece uma melhoria quadrática em relação aos algoritmos clássicos. Isso significa que o algoritmo de Grover requer um número de operações da ordem da raiz quadrada do número de operações necessárias para resolver a busca não estruturada de forma clássica — o que equivale a dizer que os algoritmos clássicos para busca não estruturada devem ter um custo pelo menos da ordem do quadrado do custo do algoritmo de Grover.
O algoritmo de Grover, junto com suas extensões e metodologia subjacente, revelam-se amplamente aplicáveis, proporcionando uma vantagem quadrática para muitas tarefas computacionais interessantes que, à primeira vista, podem não parecer problemas de busca não estruturada.
Embora a ampla aplicabilidade da técnica de busca de Grover seja atraente, vale reconhecer logo no início desta lição que a vantagem quadrática que ela oferece parece improvável de gerar uma vantagem prática do quantum sobre a computação clássica tão cedo. O hardware de computação clássica é muito mais avançado do que o hardware de computação quântica — e a vantagem quadrática do quantum sobre o clássico oferecida pelo algoritmo de Grover certamente será eclipsada pelas impressionantes velocidades de clock dos computadores clássicos modernos para qualquer problema de busca não estruturada que possa ser executado de forma viável em breve.
À medida que a tecnologia de computação quântica avança, no entanto, o algoritmo de Grover pode ter potencial. De fato, alguns dos algoritmos clássicos mais importantes e impactantes já descobertos, incluindo a transformada rápida de Fourier e a ordenação rápida (por exemplo, quicksort e merge sort), oferecem uma vantagem ligeiramente inferior à quadrática em relação às abordagens ingênuas dos problemas que resolvem. A diferença fundamental aqui, é claro, é que uma tecnologia completamente nova (ou seja, a computação quântica) é necessária para executar o algoritmo de Grover. Embora essa tecnologia ainda esteja muito em seu estágio inicial em comparação com a computação clássica, não devemos ser tão rápidos em subestimar o potencial dos avanços tecnológicos que poderiam permitir que uma vantagem quadrática do quantum sobre o clássico viesse a oferecer benefícios práticos tangíveis algum dia.
Vídeo da lição
No vídeo a seguir, John Watrous guia você pelo conteúdo desta lição sobre o algoritmo de Grover. Alternativamente, você pode abrir o vídeo do YouTube desta lição em uma janela separada. Baixe os slides desta lição.