Título:
Um Algoritmo Quântico para Encontrar um Par Mínimo

Palestrante: Nilton Volpato

Sexta-feira, 27 de abril de 2007, sala 01, 16h

Resumo:

Nesta palestra será apresentado um algoritmo quântico para encontrar
um par de elementos que é mínimo sobre uma relação de ordem definida
arbitrariamente. Este algoritmo pode ser usado para resolver inúmeros
problemas em geometria computacional, usando, a menos de fatores
logarítmicos, um número assintoticamente ótimo de consultas a um
oráculo. Este resultado oferece melhorias sobre os anteriores em
vários aspectos, e fecha um problema em aberto proposto por Bahadur,
Dürr et al: apresentar um limitante superior para o problema do par
mais distante.

Obs.: Não é necessário conhecimento prévio de computação quântica
para entender a palestra.