Algoritmos quânticos para o problema do isomorfismo de grafos / Quantum Algorithms for the Graph Isomorphism Problem
AUTOR(ES)
Edinelço Dalcumune
DATA DE PUBLICAÇÃO
2008
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.
ASSUNTO(S)
computadores quânticos computabilidade e modelos de computacao graph isomorphism quantum algorithms group intersection quantum mechanics isomorfismo de grafos algoritmos quânticos interseção de grupos
