Complexidade computacional e computação quântica

Resumo

A Computação Quântica ganhou muito destaque quando foi apresentado um algoritmo polinomial no modelo quântico para resolver o problema da fatoração de números inteiros, problema para o qual até hoje só se conhecem algoritmos exponenciais no modelo clássico. Desde então, o tema vem se desenvolvendo e apresentando resultados em várias áreas da Computação. No estudo de Complexidade Computacional o caso não é diferente, e o modelo quântico também vem contribuindo com inúmeros avanços. O objetivo deste projeto de pesquisa é estudar resultados recentes da influência da Computação Quântica na Complexidade Computacional, complementando o estudo realizado durante o período de mestrado regular do candidato. Pretende-se abordar tópicos relacionados com as classes de complexidade introduzidas pelo novo modelo, comparando-as às classes de complexidade dos modelos clássicos. Também está previsto o estudo de resultados obtidos na Teoria de Complexidade clássica utilizando estratégias adquiridas do modelo computacional quântico. (AU)