• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Master's Dissertation
DOI
https://doi.org/10.11606/D.45.2006.tde-09112020-192503
Document
Author
Full name
Carlos Henrique Cardonha
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2006
Supervisor
Committee
Fernandes, Cristina Gomes (President)
Kohayakawa, Yoshiharu
Moura, Arnaldo Vieira
Title in Portuguese
Sistemas interativos de prova clássicos e quânticos
Keywords in Portuguese
Complexidade computacional
Computação quântica
Teoria da computação
Abstract in Portuguese
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.
Title in English
Classic and quantum interactive proof systems
Keywords in English
Computational complexity
Quantum computing
Theory of computation
Abstract in English
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.
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
MESTRADO_CARDONHA.PDF (656.42 Kbytes)
Publishing Date
2021-06-14
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2021. All rights reserved.