Seminário de Teoria da Computação

       
                  Introdução à Computação Quântica

                      Nilton S. Volpato Filho

         Sexta-feira, 18 de março de 2005 

              Sala 85  14:00hs  <-----  Notem mudança de sala e de horário


A tese de Church-Turing diz que um computador digital é um dispositivo
computacional universal; isto é, ele é capaz de simular qualquer
dispositivo fisicamente realizável. Têm-se acreditado que essa
simulação pode ser feita eficientemente, de forma a acarretar no
máximo um aumento polinomial no tempo de computação. Isto pode não ser
verdade se a mecânica quântica for levada em consideração. Um
computador quântico é uma máquina hipotética baseada na mecânica
quântica. A mecânica quântica tem sido uma descrição extremamente
precisa do funcionamento do universo, e apresenta uma série de novas
propriedades que---atualmente ignoradas pelos modelos computacionais
clássicos---podem ser utilizadas na construção de algoritmos mais
eficientes.

Iremos apresentar uma introdução à computação quântica, incluindo os
conceitos principais, a unidade básica de informação (qubit), um
modelo computacional para o computador quântico, os princípios da
mecânica quântica que diferenciam um computador quântico de um
clássico, um circuito para teletransporte e um exemplo de algoritmo
quântico mais eficiente que um algoritmo clássico (o algoritmo de
Deutsch-Jozsa).

Em um seminário posterior daremos continuidade ao assunto,
apresentando o célebre algoritmo de fatoração de inteiros em tempo
polinomial de Shor e o algoritmo de busca de Grover.