Modelos Computacionais Quânticos

Abstract

A computação quântica vem evoluindo bastante nos últimos anos. O presente trabalho estuda a computação quântica por meio da utilização de máquinas abstratas que utilizam efeitos quânticos: as versões quânticas de autômatos finitos e de pilha. Esse trabalho apresenta alguns dos modelos existentes e suas propriedades conhecidas. Apresenta-se também exemplos de linguagens tratáveis pelo MO-1QFA, um autômato finito quântico com menor poder de reconhecimento, que ainda assim, reconhece algumas linguagens que sua versão clásica não reconhece. Esse trabalho também apresenta um estudo de caso explorando os erros atrelados a execução de um autômato finito quântico em uma plataforma quântica real.