Made available in DSpace on 2015-03-04T18:51:16Z (GMT). No. of bitstreams: 1
Tese Demerson.pdf: 742439 bytes, checksum: 534128a7d9b5cfc57f84985cd77ac16d (MD5)
Previous issue date: 2009-08-28 / 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} \rtimes \Z_{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 \Z_N^m \rtimes \Z_p, where N has a special prime factorization. / 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 \rtimes 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 \rtimes Z_p, com m, N inteiros positivos e N fatorado de forma especial.
| Identifer | oai:union.ndltd.org:IBICT/oai:tede-server.lncc.br:tede/121 |
| Date | 28 August 2009 |
| Creators | Gonçalves, Demerson Nunes |
| Contributors | Portugal, Renato, Giraldi, Gilson Antonio, Leal, Guilherme Augusto de La Roque, Donângelo, Raul José |
| Publisher | Laboratório Nacional de Computação Científica, Programa de Pós-Graduação em Modelagem Computacional, LNCC, BR, Serviço de Análise e Apoio a Formação de Recursos Humanos |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações do LNCC, instname:Laboratório Nacional de Computação Científica, instacron:LNCC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0025 seconds