Baseando-se em discussoes relacionadas a simulacao de sistemas quanticos, Feynman sugeriu na decada de 80 a construcao de computadores que pudessem explorar as caracteristicas quanticas da natureza. A consequencia disso foi o inicio do desenvolvimento da teoria de computacao quantica, que consiste num modelo de computacao possivelmente mais poderoso que o modelo classico. O algoritmo de Shor para fatoracao de inteiros reforcou as suspeitas a respeito da superioridade desse modelo. No mesmo periodo, um novo conjunto de ferramentas foi desenvolvido dentro da teoria de complexidade computacional Os sistemas interativos de prova foram introduzidos na decada de 80 e, com eles, muitos resultados importantes foram obtidos, como o teorema PCP. Recentemente, surgiram alguns novos resultados envolvendo sistemas interativos de prova e o modelo qsuantico de computacao. Esta dissertacao apresenta alguns desses resultados com o intuito de evidenciar algumas das potenciais diferencas entre os modelos quanticos e classico de computacao.

Based on discussion related to quantum system simulations, Feynman suggested in the 80s the construction of computers that would explore the quantum features of nature. As a result, it was developed the theory of quantum computing, which consists in a possibly more powerful model of computation than the classical model. Shor's algorithm for integer number factorization enhanced the suspicion about the superiority of this model. In the same period, a new set of tools was developed within the computational complexity theory. The interactive proof systems were introduced in the 80s, and with them many important results were obtained, as the PCP theorem. Recently, some new results involving interactive proof systems and quantum computing were presented. This dissertation shows some of these results to make comparisons between the quantum and the classic model of computation.