Algoritmos quânticos para o problema do isomorfismo de grafos

Detalhes bibliográficos
Ano de defesa: 2008
Autor(a) principal: Dalcumune, Edinelço
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Laboratório Nacional de Computação Científica
Serviço de Análise e Apoio a Formação de Recursos Humanos
BR
LNCC
Programa de Pós-Graduação em Modelagem Computacional
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://tede.lncc.br/handle/tede/82
Resumo: O problema do isomorfismo de grafos possui aplicações em diversas áreas da ciência. Tal problema não possui uma solução eficiente para o seu caso geral. No presente trabalho, apresentamos os conceitos básicos em teoria de grupos, teoria dos grafos e mecânica quântica. Apresentamos o problema do subgrupo oculto e uma conhecida redução polinomial do problema do isomorfismo de grafos no seu caso geral para o problema do subgrupo oculto sobre o grupo simétrico. Utilizamos um método que reduz o problema do isomorfismo de grafos para o problema de interseção de grupos. Este método utiliza resultados da computação quântica e da teoria dos grupos solúveis, nos permitindo obter uma solução eficiente através de um algoritmo quântico para o problema do isomorfismo de grafos para uma classe particular de grafos.