Return to search

Algoritmos Quânticos para Problemas em Teoria de Grupo Computacional / Quantum Algorithms For Problems in Computational Group Theory

Neste trabalho apresentamos um novo algoritmo quântico eficiente para o Problema do Subgrupo Oculto (PSO) sobre uma classe especial de grupos metacíclicos, Z_p
times Z_q^s, com q | (p-1) e p/q= poli(log p), onde p, q são números primos ímpares distintos e s um inteiro positivo qualquer. Em um contexto mais geral, sem impor uma relação entre p e q obtemos um algoritmo quântico com complexidade de tempo 2^{O(sqrt{log p})}. Em qualquer caso, esses resultados são melhores que qualquer algoritmo clássico para o mesmo fim, cuja complexidade é Omega(sqrt{p}). Apresentamos também, algoritmos quânticos para o PSO sobre grupos não abelianos de ordem 2^{n+1} que possuem subgrupos cíclicos de índice 2 e para certos produtos semidiretos de grupos Z_N^m
times Z_p, com m, N inteiros positivos e N fatorado de forma especial. / We present a new polynomial-time quantum algorithm that solves the hidden subgroup problem (HSP) for a special class of metacyclic groups, namely Z_{p}
times _{q^s}, with q mid (p-1) and p/q= up{poly}(log p), where p, q are any odd prime numbers and s is any positive integer. This solution generalizes previous algorithms presented in the literature. In a more general setting, without imposing a relation between p and q, we obtain a quantum algorithm with time and query complexity 2^{O(sqrt{log p})}. In any case, those results improve the classical algorithm, which needs {Omega}(sqrt{p}) queries. We also present quantum algorithms for the HSP over non-abelian groups of order 2^{n+1} which have a cyclic subgroup of index 2 and for some semidirect product _N^m
times _p, where N has a special prime factorization.

Identiferoai:union.ndltd.org:IBICT/oai:agregador.ibict.br.BDTD_LNCC:oai:lncc.br:86
Date28 August 2009
CreatorsDemerson Nunes Gonçalves
ContributorsGilson Antonio Giraldi, Guilherme Augusto de La Roque Leal, Raul José Donângelo, Renato Portugal
PublisherLaboratório Nacional de Computação Científica
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis
Formatapplication/pdf
Sourcereponame:Biblioteca Digital de Teses e Dissertações do LNCC, instname:Laboratório Nacional de Computação Científica, instacron:LNCC
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0022 seconds