Pós-Graduação em Ciência da Computação – UFPE
Defesa de Dissertação de Mestrado Nº 2.184
Aluno: Paulo André Viana de Araujo
Orientador: Prof. Fernando Maciano de Paula Neto
Título: A Quantum Genetic Algorithm Framework For The MaxCut Problem
Data: 30/01/2025
Hora/Local: 8h:30m – Virtual – Interessados em assistir entrar em contato com o aluno
Banca Examinadora:
Prof. Aluizio Fausto Ribeiro Araújo (UFPE / Centro de Informática)
Prof. Wilson Rosa de Oliveira Junior (UFRPE / Departamento de Estatística e Informática)
Prof. Fernando Maciano de Paula Neto (UFPE / Centro de Informática)
RESUMO:
O MaxCut é um problema fundamental na Otimização Combinatória, com implicações significativas em diversos domínios, como logística, design de redes e física estatística. O algoritmo representa abordagens inovadoras que equilibram o rigor teórico com a escalabilidade prática. O método proposto introduz um Algoritmo Genético Quântico usando uma estrutura evolutiva baseada em Grover e princípios de divisão e conquista. Ao particionar grafos em subgrafos gerenciáveis, otimizando cada um de forma independente e aplicando a contração de grafos para unir as soluções, o método explora a simetria binária inerente do MaxCut para garantir eficiência computacional e desempenho robusto em aproximações. A análise teórica estabelece uma base sólida para sua eficiência, enquanto as avaliações empíricas destacam a superioridade do método em grafos densos, onde supera benchmarks clássicos e inspirados em algoritmos quânticos. Este trabalho avança as técnicas computacionais quânticas para análises comparativas com problemas de grande escala, demonstrando o potencial de uma estrutura evolutiva quântica como o QGA. Além disso, este algoritmo demonstra o potencial de computadores quânticos de grande escala, alcançando consistentemente as melhores soluções para instâncias de pequenos grafos.
Palavras-chave: Algoritmo Genético Quântico, MaxCut, Algoritmo de Grover, Computação Quântica, Teoria dos Grafos.
Comentários desativados