Seminário de Teoria da Computação

       
                       O algoritmo de Grover

                      Nilton S. Volpato Filho

                 Sexta-feira, 13 de maio de 2005 

                         Sala 85  14:00hs


Resumo: Iremos mostrar como a computação quântica nos permite realizar
uma busca em um espaço de busca de n elementos não organizados em um
tempo quadraticamente maior que qualquer algoritmo clássico
probabilístico. A analogia clássica utilizada é a da busca por um
telefone em uma lista telefônica de n itens em tempo O(sqrt(n)).

Mostraremos como aplicar esse algoritmo para obter uma aceleração
quadrática na velocidade de resolução dos problemas NP-completos.

No início teremos uma introdução aos conceitos de computação quântica
necessários ao entendimento do algoritmo.