Introdução

O algoritmo de Grover é um algoritmo quântico para os chamados problemas de pesquisa não estruturada que oferece uma melhoria quadrática em relação aos algoritmos clássicos. Isso significa que o algoritmo de Grover exige 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 a busca não estruturada devem ter um custo pelo menos da ordem do quadrado do custo do algoritmo de Grover.

O algoritmo de Grover, juntamente com suas extensões e a metodologia subjacente, acaba sendo amplamente aplicável, levando a uma vantagem quadrática para muitas tarefas computacionais interessantes que, inicialmente, podem não parecer problemas de pesquisa não estruturada.

Embora a ampla aplicabilidade da técnica de busca de Grover seja convincente, deve-se reconhecer aqui, no início da aula, que a vantagem quadrática que ela oferece parece improvável de levar a uma vantagem prática da computação quântica sobre a clássica em breve. O hardware de computação clássica é muito mais avançado do que o hardware de computação quântica, e a vantagem quântica quadrática sobre a clássica oferecida pelo algoritmo de Grover certamente será eliminada pelas impressionantes velocidades de clock dos computadores clássicos modernos para qualquer problema de pesquisa não estruturada que possa ser executado em breve.

No entanto, com o avanço da tecnologia de computação quântica, 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 classificação rápida (por exemplo, quicksort e merge sort), oferecem um pouco menos do que uma vantagem quadrática em relação às abordagens ingênuas dos problemas que resolvem. A principal diferença aqui, é claro, é que uma tecnologia totalmente nova (ou seja, a computação quântica) é necessária para executar o algoritmo de Grover. Embora essa tecnologia ainda esteja em seus primórdios em comparação com a computação clássica, não devemos subestimar tão rapidamente o potencial dos avanços tecnológicos que poderiam permitir uma vantagem quadrática da computação quântica sobre a clássica para um dia oferecer benefícios práticos tangíveis.

Vídeo da aula

No vídeo a seguir, John Watrous orienta você pelo conteúdo desta lição sobre o algoritmo de Grover. Como alternativa, você pode abrir o vídeo YouTube para esta lição em uma janela separada. Faça o download dos slides para esta lição.