Complexidade computacional e computação quântica

• Processo: 12/22478-7
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Mestrado
• Data de Início da vigência: 13 de abril de 2013
• Data de Término da vigência: 12 de outubro de 2013
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Arnaldo Vieira Moura
• Beneficiário: Alex Bredariol Grilo
• Supervisor: Iordanis Kerenidis
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Instituição Anfitriã: Université Paris Diderot - Paris 7, França
• Vinculado à bolsa: 12/06648-0 - Computação Quântica e Teoria da Computação, BP.MS
• Assunto(s): Algoritmos e estruturas de dados Computação quântica
• Palavra(s)-Chave do Pesquisador: Complexidade Computacional | computação quântica | Complexidade Computacional

Resumo

A Computação Quântica ganhou muito destaque quando foi apresentado um algoritmo polinomial no modelo quântico para resolver o problema da fatoração de números inteiros, problema para o qual até hoje só se conhecem algoritmos exponenciais no modelo clássico. Desde então, o tema vem se desenvolvendo e apresentando resultados em várias áreas da Computação. No estudo de Complexidade Computacional o caso não é diferente, e o modelo quântico também vem contribuindo com inúmeros avanços. O objetivo deste projeto de pesquisa é estudar resultados recentes da influência da Computação Quântica na Complexidade Computacional, complementando o estudo realizado durante o período de mestrado regular do candidato. Pretende-se abordar tópicos relacionados com as classes de complexidade introduzidas pelo novo modelo, comparando-as às classes de complexidade dos modelos clássicos. Também está previsto o estudo de resultados obtidos na Teoria de Complexidade clássica utilizando estratégias adquiridas do modelo computacional quântico. (AU)

Publicações científicas

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

GRILO, A. B.; MOURA, A., V. ON FINITE AUTOMATA WITH QUANTUM AND CLASSICAL STATES. SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, v. 10, p. 13-pg., 2013-01-01. (12/22478-7, 12/06648-0)