EVENTO
O Problema do Subgrupo Escondido
Tipo de evento: Seminário de Avaliação - Série A
Considere um grupo , um conjunto e uma função tal que exista um subgrupo de , para o qual se, e somente se, quaisquer que sejam . O problema de determinar um conjunto de geradores para a partir de informações obtidas de é chamado o Problema do Subgrupo Escondido (PSE). Atualmente ele é um dos mais importantes e estudados problemas da Computação Quântica e ainda está longe de ser completamente resolvido.Muitos algoritmos quânticos que apresentam ganho exponencial em relação aos seus equivalentes clássicos, como é o caso dos algoritmos de Shor [1] para a fatoração e o cálculo de logaritmo discreto, podem ser vistos como casos particulares de algoritmos quânticos para a solução do PSE; nos exemplos citados, o grupo é abeliano e, neste caso, é conhecido um algoritmo quântico eficiente para a sua solução [4], enquanto nenhum algoritmo clássico eficiente o é. Um outro motivo para o esforço de tentar resolver o PSE reside no fato de que, quando é o grupo simétrico, sua solução implica a solução do problema do isomorfismo de grafos, que possui aplicações nas mais variadas áreas do conhecimento e para o qual não se conhece nenhum algoritmo que o resolva eficientemente. Infelizmente, também não se conhece nenhum algoritmo, nem clássico nem quântico, para a solução do PSE em .Neste seminário apresentaremos o formalismo quântico para o PSE, mostrando as principais ferramentas usadas para o ataque ao problema, os casos onde o PSE está resolvido e também onde a pesquisa recente tem concentrado esforço em sua solução. [1] Inui, Y. and Le Gall, F., An efficient quantum algorithm for the hidden subgroup problem over a class of semi-direct product groups, Los Alamos arXiv, quant-ph/0412033 v2, (2005);[2] Chi, D.P. and Kim, J.S. and Lee, S., Quantum algorithms for the hidden subgroup problem on some semi-direct product groups by reduction to Abelian cases, Physics Letters A, vol. 359(2), pp. 114-116(2006)[3] Shor, P., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing, vol. 26(5), pp. 14841509 (1997);[4] Mosca, M., Quantum Computer Algorithms, PhD thesis, University of Oxford, (1999);[5] Bacon, D. and Childs, A.M. and van Dam,W., From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semi-direct product groups, Proceedings of the 2005 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS05), 0-7695-2468-0/05 $20.00 IEEE (2005);
Data Início: 06/12/2006 Hora: 11:00 Data Fim: 06/12/2006 Hora: 13:00
Local: LNCC - Laboratório Nacional de Computação Ciêntifica - Auditorio A
Aluno: Carlos Magno Martins Cosme - Universidade Federal dos Vales Gequitinhonha - UFVJM
Orientador: Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Participante Banca Examinadora: Guilherme Augusto de La Rocque Leal - IM-UFRJ - UFRJ Paulo César Marques Vieira - Laboratório Nacional de Computação Científica - LNCC Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
