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 é improvável que a vantagem quadrática que ela oferece leve, tão cedo, a uma vantagem prática da computação quântica sobre a clássica. 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 da computação quântica sobre a clássica 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 engatinhando em comparação com a computação clássica, não devemos subestimar precipitadamente o potencial dos avanços tecnológicos que poderiam permitir que uma vantagem quadrática da computação quântica sobre a clássica 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.