Data: 26/06/2026

Título:  Computação Quântica e Problemas NP-completos  

Palestrante: Prof. Dr. Leandro Zatesko, UTFPR. 

Data: 26 de Junho de 2026, 14 h (Brasil).

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.

Obs: