Sistemas interativos de prova clássicos e quânticos

Autor(es)

Carlos Henrique Cardonha

• Tipo de documento: Dissertação de Mestrado
• Imprenta: São Paulo.
• Instituição: Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI)
• Data de defesa: 2006-09-11

Membros da banca

Cristina Gomes Fernandes; Yoshiharu Kohayakawa; Arnaldo Vieira Moura

• Orientador: Cristina Gomes Fernandes

Resumo

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. (AU)

• Processo FAPESP: 04/11339-0 - Complexidade e computação quântica
• Beneficiário: Carlos Henrique Cardonha
• Modalidade de apoio: Bolsas no Brasil - Mestrado