We present an efficient quantum algorithm for the Hidden Subgroup Problem (HSP) on the semidirect product of the cyclic groups and , where is any odd prime number, and are positives integers and the homomorphism which defines the group is given by the root such that . As a consequence we can solve efficiently de HSP on the semidirect product of the groups by , where has a special prime factorization. / Neste trabalho apresentamos um algoritmo quântico eficiente para o Problema do Subgrupos Oculto (PSO) no produto semidireto dos grupos cíclicos e , onde é qualquer número primo ímpar, e são inteiros positivos e o homomorfismo que define o grupo é dado por uma raiz para a qual . Como conseqüência, podemos resolver eficientemente o PSO também no produto semidireto dos grupos por , onde o inteiro possui uma especial fatoração prima.

O problema do isomorfismo de grafos possui aplicações em diversas áreas da ciência. Tal problema não possui uma solução eficiente para o seu caso geral. No presente trabalho, apresentamos os conceitos básicos em teoria de grupos, teoria dos grafos e mecânica quântica. Apresentamos o problema do subgrupo oculto e uma conhecida redução polinomial do problema do isomorfismo de grafos no seu caso geral para o problema do subgrupo oculto sobre o grupo simétrico. Utilizamos um método que reduz o problema do isomorfismo de grafos para o problema de interseção de grupos. Este método utiliza resultados da computação quântica e da teoria dos grupos solúveis, nos permitindo obter uma solução eficiente através de um algoritmo quântico para o problema do isomorfismo de grafos para uma classe particular de grafos. / The graph isomorphism problem has applications in several areas of science. This problem has not an efficient solution to its general case. In this work, we present the basic concepts of group theory, graph theory and quantum mechanics. We introduce the hidden subgroup problem and a known polynomial reduction of the graph isomorphism problem in its general case to the hidden subgroup problem on the symmetric group. We use a method that reduces the graph isomorphism problem to the group intersection problem. This method combines results from quantum computing and solvable group theory providing a efficient solution through a quantum algorithm to the graph isomorphism problem for the particular class of graphs.

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.

Made available in DSpace on 2015-03-04T18:50:57Z (GMT). No. of bitstreams: 1 Tese-Carlos-Magno1.pdf: 616333 bytes, checksum: 65e51c95902afd18d11a1d7366653fc0 (MD5) Previous issue date: 2008-03-13 / Conselho Nacional de Desenvolvimento Cientifico e Tecnologico / We present an efficient quantum algorithm for the Hidden Subgroup Problem (HSP) on the semidirect product of the cyclic groups and , where is any odd prime number, and are positives integers and the homomorphism which defines the group is given by the root such that . As a consequence we can solve efficiently de HSP on the semidirect product of the groups by , where has a special prime factorization. / Neste trabalho apresentamos um algoritmo quântico eficiente para o Problema do Subgrupos Oculto (PSO) no produto semidireto dos grupos cíclicos e , onde é qualquer número primo ímpar, e são inteiros positivos e o homomorfismo que define o grupo é dado por uma raiz para a qual . Como conseqüência, podemos resolver eficientemente o PSO também no produto semidireto dos grupos por , onde o inteiro possui uma especial fatoração prima.

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.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-08-06T19:17:03Z No. of bitstreams: 1 HERON ARAGÃO MONTEIRO - DISSERTAÇÃO PPGCC 2012..pdf: 15948168 bytes, checksum: e445512265f530700a45c3924f68aa02 (MD5) / Made available in DSpace on 2018-08-06T19:17:03Z (GMT). No. of bitstreams: 1 HERON ARAGÃO MONTEIRO - DISSERTAÇÃO PPGCC 2012..pdf: 15948168 bytes, checksum: e445512265f530700a45c3924f68aa02 (MD5) Previous issue date: 2012-05-31 / Com o avanço da nanotecnologia, a computação quântica tem recebido grande destaque no meio científico. Utilizando os fundamentos da mecânica quântica, têm sido propostos diversos algoritmos quânticos. E, até então, os mesmos têm apresentado ganhos significativos com relação às suas versões clássicas. Na intenção de poder ser verificada a eficiência dos algoritmos quânticos, diversos simuladores vêm sendo desenvolvidos, visto que a confecção de um computador quântico ainda não foi possível. Há duas grandes vertentes de simuladores: os simuladores por software e os simuladores por hardware, chamados de emuladores. Na primeira classe se encontram os programas desenvolvidos em um computador clássico, procurando implementar os fundamentos da mecânica quântica, fazendo uso das linguagens de programação clássicas. Na segunda, são utilizados recursos que não estejam vinculados à plataforma do computador clássico. Dentre os emuladores, particularmente, estudos têm sido realizados fazendo uso de hardware dedicado (mais especificamente, FPGAV). O presente trabalho propõem a verificação da real utilidade da plataforma FPGA, com a intenção de se desenvolver um emulador universal, que permita a emulação de qualquer classe de circuitos, e que os mesmos possam ser implementados com um maior número de q-bits em relação aos circuitos tratados nos trabalhos anteriores. / With the progress of nanotechnology, quantum computing has received great emphasis in scientific circles. Using the basis of quantum mechanics, different quantum algorithms have been proposed. And so far, they have presented significant gains with respect to its classic versions. In order to verify the efficiency of quantum algorithms, several simulators have been developed, since the construction of a quantum computer is not yet possible. There are two major classes of simulators, simulators via software and via hardware. The latter being also called emulators. In the first class, programs are developed in a classical computer, attempting to implement the fundamentais of quantum mechanics, making use of classic programming languages. In the second, resources are used that are not related to the classic computer platform. Among the emulators, in particular, studies have been made using dedicated hardware (more specifically, FPGA's2). The present work proposes the use of the FPGA boards in emulation of quantum circuits aiming a gain scale in relation to the alternatives presented so far. The present work proposes checking the usefulness of the FPGA with the intention of developing an universal emulator that is able to emulate any type of circuit, and that they can be implemented with a larger number of q-bit in respect to the circuits treated in the previous works.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-10-01T16:46:31Z No. of bitstreams: 1 ELLOÁ BARRETO GUEDES DA COSTA - DISSERTAÇÃO PPGCC 2011..pdf: 1433883 bytes, checksum: fb9fa0561b94ab2b495915f5f377c364 (MD5) / Made available in DSpace on 2018-10-01T16:46:31Z (GMT). No. of bitstreams: 1 ELLOÁ BARRETO GUEDES DA COSTA - DISSERTAÇÃO PPGCC 2011..pdf: 1433883 bytes, checksum: fb9fa0561b94ab2b495915f5f377c364 (MD5) Previous issue date: 2011-03-25 / Este trabalho apresenta um ataque quântico de comprometimento permanente ao gerador pseudo-aleatório de Blum-Micali. A segurança deste gerador, classificado como criptograficamente seguro, baseia-se na hipótese de intratabilidade do problema do logaritmo discreto perante a Computação Clássica. O ataque proposto faz uso do algoritmo quântico de busca em conjunto com o algoritmo quântico para o logaritmo discreto para comprometer a imprevisibilidade do gerador, recuperando todas as saídas passadas e futuras do mesmo. O presente trabalho também descreve generalizações deste ataque que o adequam a uma gama mais vasta de geradores, incluindo geradores da Construção de Blum-Micali e geradores com múltiplos predicados difíceis. Tais generalizações também abrangem a realização de ataques em situações adversas, por exemplo, quando o adversário captura bits não consecutivos ou quando há menos bits que o requerido. Comparado à sua contrapartida clássica, o algoritmo quântico proposto nesse trabalho possui um ganho quadrático em relação à recuperação do representante do estado interno do gerador, seguido de um ganho superpolinomial na obtenção dos demais elementos do estado interno. Estes resultados caracterizam ameaças,elaboradas com Computação Quântica, contra a segurança de geradores utilizados em diversas aplicações criptográficas. / This dissertation presents a quantum permanent compromise attack to the Blum-Micali pseudorandom generator. The security of this generator, classified as cryptographically secure, is based on the hypothesis of intractability of the discrete logarithm problem in Classical Computing. The proposed attack is based on the quantum search algorithm jointly with the quantum discrete logarithm procedure and aims to compromise the unpredictability of the referred generator, recovering all of its past and future outputs. This work also describes generalizations that enables attacks to generators from the Blum-Micali construction and also to generators with multiple hard-core predicates. Such generalizations also allow attacks when the adversary intercepts non-consecutive bits or when there are less bits than required. Compared to its classical counterpart, the proposed algorithm has a quadractic speedup regarding the retrieval of the representant of the generator’s internal state followed by a super polynomial speedup regarding the obtention of the entire generator’sinternalstate. These results represent menaces of the Quantum Computing paradigm against the security of pseudorandom generators adopted in many real-world cryptosystems.