Banca de DEFESA: PAULO ANDRE VIANA DE ARAUJO

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE: PAULO ANDRE VIANA DE ARAUJO
DATA : 30/01/2025
HORA: 08:30
LOCAL: Virtual
TÍTULO:

A Quantum Genetic Algorithm Framework For The MaxCut Problem

PALAVRAS-CHAVES:

Algoritmo Genético Quântico, MaxCut, Algoritmo de Grover, Computação Quântica, Teoria dos Grafos.

PÁGINAS: 53
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.

MEMBROS DA BANCA:
Presidente - 1351924 - ALUIZIO FAUSTO RIBEIRO ARAUJO
Interno - 1412012 - FERNANDO MACIANO DE PAULA NETO
Externo à Instituição - WILSON ROSA DE OLIVEIRA JUNIOR - UFRPE