O Seminário de Combinatória continua suas atividades de forma online. Agradecemos a oportunidade de receber o Prof. Dr. Leandro Zatesko, da UTFPR.
Emitiremos certificados de participação para Atividade Complementar. Basta colocar seu nome completo, instituição de origem e e-mail no chat ao final do seminário.
Não é necessária inscrição prévia.
Data: 24/06/2026
Horário: 14h (Brasil)
Sala: https://meet.google.com/tgj-mcyg-ogn
Palestrante: Prof. Dr. Leandro Zatesko, UTFPR
Título: Computação Quântica e Problemas NP-Completos
Resumo:
Desde quando o modelo teórico de computação quântica foi proposto, muitos resultados surpreendentes foram obtidos, reforçando a supremacia do modelo quântico sobre o modelo clássico. Dentre os exemplos mais notáveis, está a Transformada Quântica de Fourier, com a qual podemos, em tempo polinomial, encontrar a ordem de grupos abelianos e, portanto, resolver o problema da fatoração inteira.
Por outro lado, computadores quânticos não parecem poderosos o suficiente para resolver problemas NP-completos. Na realidade, não parecem poderosos nem mesmo para vários problemas importantes candidatos a NP-intermediários, como os problemas da classe SZK, que admitem provas de conhecimento zero estatístico.
Nesta palestra será apresentada uma discussão sobre alguns resultados de Complexidade Computacional — especialmente inclusões e separações oraculares — envolvendo as principais classes da computação quântica e suas relações com outras classes importantes.
Contamos com sua presença.
Atenciosamente,
Organização do Seminário de Combinatória