Hidden subgroup problem in nilpotent groups / Problema do subgrupo oculto em grupos nilpotentes
AUTOR(ES)
Tharso Dominisini Fernandes
DATA DE PUBLICAÇÃO
2008
RESUMO
Computadores quânticos prometem resolver certos problemas assintoticamente mais rápido do que os computadores clássicos. Algoritmos quânticos, como o algoritmo de Shor, podem ser considerados casos particulares do chamado Problema do Subgrupo Oculto(PSO). O PSO consiste em encontrar um subgrupo H de um grupo G por meio de avaliações de uma função f que é constante em classes laterais de H e distinta em classes laterais diferentes. O PSO em grupos abelianos é resolvido eficientemente em um computador quântico, mas será que os computadores quânticos podem resolver o PSO em grupos não abelianos? Esta questão tem sido discutida regularmente pela comunidade científica devido a importantes aplicações, como é o caso do problema de isomorfismo de grafos e do problema do menor vetor em um reticulado. Nesta dissertação é feita uma revisão do trabalho de Ivanyos et al. (2007a), o qual apresenta uma solução para o PSO em grupos nilpotentes de classe 2. Com esta finalidade, é elaborada uma breve revisão sobre a Computação Quântica; são mostradas algumas características dos grupos nilpotentes e dos grupos solúveis, dando uma atenção especial aos grupos nilpotentes de classe 2; é exposto o método padrão de solução do PSO em grupos abelianos; também são exibidas as principais características de sequencias policıclicas e reduçõesde grupos nilpotentes usando as propriedades de sequencias policıclicas
ASSUNTO(S)
problema do subgrupo oculto hidden subgroup problem quantum algorithms quantum computers computadores quânticos computabilidade e modelos de computacao algoritmos quânticos
ACESSO AO ARTIGO
http://www.lncc.br/tdmc/tde_busca/arquivo.php?codArquivo=153Documentos Relacionados
- Quantum Algorithm for the Non Abelian Hidden Subgroup Problem
- O problema do centro-foco para singularidades nilpotentes no plano
- ImersÃes isomÃtricas em grupos de Lie nilpotentes e solÃveis
- An Efficient Quantum Algorithm for the Hidden Subgroup Problem over some Non-Abelian Groups
- Abelian-by-nilpotent of homological type FP IND.3