EVENTO
Análise, Simulações e Aplicações Algorítmicas de Caminhadas Quânticas
Tipo de evento: Defesa de Tese de Doutorado
A computação quântica é um modelo computacional baseado nas leis da mecânica quântica, que pode ser utilizado para desenvolver algoritmos muito mais eficientes que seus correspondentes clássicos. O desenvolvimento de algoritmos quânticos eficientes, no entanto, é uma tarefa altamente desafiadora. Uma abordagem recente que vem se mostrando bem-sucedida é a utilização de caminhadas quânticas. Neste trabalho, estudamos a caminhada quântica no hipercubo, calculando analiticamente sua distribuição estacionária e analisando propriedades de seu mixing time, tanto na situação ideal como na situação com descoerência gerada por ligações interrompidas. Também estudamos a caminhada na malha bidimensional, calculando sua distribuição estacionária analiticamente e explorando a relação entre o mixing time e a complexidade do algoritmo de busca nesse grafo. Desenvolvemos uma ferramenta computacional para simulação numérica de caminhadas quânticas em malhas uni- e bidimensionais com diversas condições de contorno. Finalmente, estudamos alguns algoritmos de busca em grafos e analisamos numericamente o impacto que a descoerência exerce sobre seus desempenhos.
Data Início: 26/02/2010 Hora: 10:00 Data Fim: 26/02/2010 Hora: 12:30
Local: LNCC - Laboratório Nacional de Computação Ciêntifica - Auditorio A
Aluno: Franklin de Lima Marquezino - Universidade Federal do Rio de Janeiro - UFRJ/COPPE
Orientador: Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Participante Banca Examinadora: Francisco Marcos de Assis - Universidade Federal de Campina Grande - UFCG Gilson Antônio Giraldi - Laboratório Nacional de Computação Científica - LNCC Raul José Donangelo - UFRJ - UFRJ Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
