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.

Esta dissertação investiga a aplicação dos algoritmos evolucionários inspirados na computação quântica na síntese de circuitos sequenciais. Os sistemas digitais sequenciais representam uma classe de circuitos que é capaz de executar operações em uma determinada sequência. Nos circuitos sequenciais, os valores dos sinais de saída dependem não só dos valores dos sinais de entrada como também do estado atual do sistema. Os requisitos cada vez mais exigentes quanto à funcionalidade e ao desempenho dos sistemas digitais exigem projetos cada vez mais eficientes. O projeto destes circuitos, quando executado de forma manual, se tornou demorado e, com isso, a importância das ferramentas para a síntese automática de circuitos cresceu rapidamente. Estas ferramentas conhecidas como ECAD (Electronic Computer-Aided Design) são programas de computador normalmente baseados em heurísticas. Recentemente, os algoritmos evolucionários também começaram a ser utilizados como base para as ferramentas ECAD. Estas aplicações são referenciadas na literatura como eletrônica evolucionária. Os algoritmos mais comumente utilizados na eletrônica evolucionária são os algoritmos genéticos e a programação genética. Este trabalho apresenta um estudo da aplicação dos algoritmos evolucionários inspirados na computação quântica como uma ferramenta para a síntese automática de circuitos sequenciais. Esta classe de algoritmos utiliza os princípios da computação quântica para melhorar o desempenho dos algoritmos evolucionários. Tradicionalmente, o projeto dos circuitos sequenciais é dividido em cinco etapas principais: (i) Especificação da máquina de estados; (ii) Redução de estados; (iii) Atribuição de estados; (iv) Síntese da lógica de controle e (v) Implementação da máquina de estados. O Algoritmo Evolucionário Inspirado na Computação Quântica (AEICQ) proposto neste trabalho é utilizado na etapa de atribuição de estados. A escolha de uma atribuição de estados ótima é tratada na literatura como um problema ainda sem solução. A atribuição de estados escolhida para uma determinada máquina de estados tem um impacto direto na complexidade da sua lógica de controle. Os resultados mostram que as atribuições de estados obtidas pelo AEICQ de fato conduzem à implementação de circuitos de menor complexidade quando comparados com os circuitos gerados a partir de atribuições obtidas por outros métodos. O AEICQ e utilizado também na etapa de síntese da lógica de controle das máquinas de estados. Os circuitos evoluídos pelo AEICQ são otimizados segundo a área ocupada e o atraso de propagação. Estes circuitos são compatíveis com os circuitos obtidos por outros métodos e em alguns casos até mesmo superior em termos de área e de desempenho, sugerindo que existe um potencial de aplicação desta classe de algoritmos no projeto de circuitos eletrônicos. / This thesis investigates the application of quantum inspired evolutionary algorithms in the synthesis of sequential circuits. Sequential digital systems represent a class of circuit that is able to execute operations in a particular sequence. In sequential circuits, the values of output signals not only depend on the values of input signals but also on the current state of the system. The increasingly high requirements regarding the functionality and performance of digital systems demand more efficient designs. The design of these circuits, when implemented manually, became slow and thus the importance of tools for automatic synthesis of circuits grew rapidly. These tools known as ECAD (Electronic Computer-Aided Design) are computer programs usually based on heuristics. Recently, evolutionary algorithms also began to be used as a basis in ECAD tools developing. These applications are referenced in literature as evolutionary electronics. The algorithms most commonly used in evolutionary electronics are genetic algorithms and genetic programming. This work presents a study of the application of quantum inspired evolutionary algorithms as a tool for automatic synthesis of sequential circuits. This class of algorithms uses the principles of quantum computing to improve the performance of evolutionary algorithms. Traditionally, the design of sequential circuits is divided into five main steps: (i) State machine specification; (ii) Reduction of states; (iii) State assignment; (iv) Control logic synthesis and (v) Implementation of the state machine. The proposed algorithm AEICQ is used in the state assignment design step. The choice of an optimal state assignment is treated in the literature as an issue still unresolved. The state assignment chosen for a particular state machine has a direct impact on the complexity of its control logic. The results show that the state assignment obtained by AEICQ in fact leads to the implementation of circuits of less complexity when compared with the ones generated from assignments obtained by other methods. The AEICQ is also used in the control logic synthesis of the state machine. The circuits evolved by AEICQ are optimized according to the area occupied and the propagation delay. These circuits are compatible with the circuits obtained by other methods and in some cases even higher in terms of area and performance, suggesting that there is a potential for application of this class of algorithms in the design of electronic circuits.

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.

Esta dissertação investiga a aplicação dos algoritmos evolucionários inspirados na computação quântica na síntese de circuitos sequenciais. Os sistemas digitais sequenciais representam uma classe de circuitos que é capaz de executar operações em uma determinada sequência. Nos circuitos sequenciais, os valores dos sinais de saída dependem não só dos valores dos sinais de entrada como também do estado atual do sistema. Os requisitos cada vez mais exigentes quanto à funcionalidade e ao desempenho dos sistemas digitais exigem projetos cada vez mais eficientes. O projeto destes circuitos, quando executado de forma manual, se tornou demorado e, com isso, a importância das ferramentas para a síntese automática de circuitos cresceu rapidamente. Estas ferramentas conhecidas como ECAD (Electronic Computer-Aided Design) são programas de computador normalmente baseados em heurísticas. Recentemente, os algoritmos evolucionários também começaram a ser utilizados como base para as ferramentas ECAD. Estas aplicações são referenciadas na literatura como eletrônica evolucionária. Os algoritmos mais comumente utilizados na eletrônica evolucionária são os algoritmos genéticos e a programação genética. Este trabalho apresenta um estudo da aplicação dos algoritmos evolucionários inspirados na computação quântica como uma ferramenta para a síntese automática de circuitos sequenciais. Esta classe de algoritmos utiliza os princípios da computação quântica para melhorar o desempenho dos algoritmos evolucionários. Tradicionalmente, o projeto dos circuitos sequenciais é dividido em cinco etapas principais: (i) Especificação da máquina de estados; (ii) Redução de estados; (iii) Atribuição de estados; (iv) Síntese da lógica de controle e (v) Implementação da máquina de estados. O Algoritmo Evolucionário Inspirado na Computação Quântica (AEICQ) proposto neste trabalho é utilizado na etapa de atribuição de estados. A escolha de uma atribuição de estados ótima é tratada na literatura como um problema ainda sem solução. A atribuição de estados escolhida para uma determinada máquina de estados tem um impacto direto na complexidade da sua lógica de controle. Os resultados mostram que as atribuições de estados obtidas pelo AEICQ de fato conduzem à implementação de circuitos de menor complexidade quando comparados com os circuitos gerados a partir de atribuições obtidas por outros métodos. O AEICQ e utilizado também na etapa de síntese da lógica de controle das máquinas de estados. Os circuitos evoluídos pelo AEICQ são otimizados segundo a área ocupada e o atraso de propagação. Estes circuitos são compatíveis com os circuitos obtidos por outros métodos e em alguns casos até mesmo superior em termos de área e de desempenho, sugerindo que existe um potencial de aplicação desta classe de algoritmos no projeto de circuitos eletrônicos. / This thesis investigates the application of quantum inspired evolutionary algorithms in the synthesis of sequential circuits. Sequential digital systems represent a class of circuit that is able to execute operations in a particular sequence. In sequential circuits, the values of output signals not only depend on the values of input signals but also on the current state of the system. The increasingly high requirements regarding the functionality and performance of digital systems demand more efficient designs. The design of these circuits, when implemented manually, became slow and thus the importance of tools for automatic synthesis of circuits grew rapidly. These tools known as ECAD (Electronic Computer-Aided Design) are computer programs usually based on heuristics. Recently, evolutionary algorithms also began to be used as a basis in ECAD tools developing. These applications are referenced in literature as evolutionary electronics. The algorithms most commonly used in evolutionary electronics are genetic algorithms and genetic programming. This work presents a study of the application of quantum inspired evolutionary algorithms as a tool for automatic synthesis of sequential circuits. This class of algorithms uses the principles of quantum computing to improve the performance of evolutionary algorithms. Traditionally, the design of sequential circuits is divided into five main steps: (i) State machine specification; (ii) Reduction of states; (iii) State assignment; (iv) Control logic synthesis and (v) Implementation of the state machine. The proposed algorithm AEICQ is used in the state assignment design step. The choice of an optimal state assignment is treated in the literature as an issue still unresolved. The state assignment chosen for a particular state machine has a direct impact on the complexity of its control logic. The results show that the state assignment obtained by AEICQ in fact leads to the implementation of circuits of less complexity when compared with the ones generated from assignments obtained by other methods. The AEICQ is also used in the control logic synthesis of the state machine. The circuits evolved by AEICQ are optimized according to the area occupied and the propagation delay. These circuits are compatible with the circuits obtained by other methods and in some cases even higher in terms of area and performance, suggesting that there is a potential for application of this class of algorithms in the design of electronic circuits.

Made available in DSpace on 2015-05-14T12:14:06Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1577961 bytes, checksum: c71d976d783495df566e0fa6baadf8ca (MD5) Previous issue date: 2009-08-06 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / We start this work studying the appearance of geometric quantum phases as in the relativistic as in the non-relativistic quantum dynamics of a neutral particle with permanent magnetic and electric dipole moment which interacts with external electric and magnetic fields in the presence of linear topological defects. We describe the linear topological defects using the approach proposed by Katanaev and Volovich, where the topological defects in solids are described by line elements which are solutions of the Einstein's equations in the context of general relativity. We also analyze the in uence of non-inertial effects in the quantum dynamics of a neutral particle using two distinct reference frames for the observers: one is the Fermi-Walker reference frame and another is a rotating frame. As a result, we shall see that the difference between these two reference frames is in the presence/absence of dragging effects of the spacetime which makes its in uence on the phase shift of the wave function of the neutral particle. In the following, we shall use our study of geometric quantum phases to make an application on the Holonomic Quantum Computation, where we shall show a new approach to implement the Holonomic Quantum Computation via the interaction between the dipole moments of the neutral particle and external fields and the presence of linear topological defects. Another applications for the Holonomic Quantum Computation is based in the structure of the topological defects in graphene layers. In the presence of topological defects, a graphene layer shows two distinct phase shifts: one comes from the mix of Fermi points while the other phase shift comes from the topology of the defect. To provide a geometric description for each phase shift in the graphene layer, we use the Kaluza-Klein theory where we establish that the extra dimension describes the Fermi points in the graphene layer. Hence, we can implement the Holonomic Quantum Computation through the possibility to build cones and anticones of graphite in such way we can control the quantum uxes in graphene layers. In the last part of this work, we study the Landau quantization for neutral particles as in the relativistic dynamics and non-relativistic dynamics. In the non-relativistic dynamics, we study the Landau quantization in the presence of topological defects as in an inertial as in a non-inertial reference frame. In the relativistic quantum dynamics, we start our study with the Landau quantization in the Minkowisky considering two different gauge fields. At the end, we study the relativistic Landau quantization for neutral particles in the Cosmic Dislocation spacetime. / Neste trabalho estudamos inicialmente o surgimento de fases geometricas nas dinâmicas quânticas relativística e não-relativística de uma partícula neutra que possui momento de dipolo magnético e elétrico permanente interagindo com campos elétricos e magnéticos externos na presença de defeitos topológicos lineares. Para descrevermos defeitos topológicos lineares usamos a aproximação proposta por Katanaev e Volovich, onde defeitos lineares em sólidos são descritos por elementos de linha que são soluções das equações de Einstein no contexto da relatividade geral. Analisamos também a inuência de efeitos não-inerciais na dinâmica quântica de uma partícula neutra em dois tipos distintos de referenciais para os observadores: um é o referencial de Fermi-Walker e outro é um referencial girante. Vemos que a diferença entre dois referenciais está na presença/ausência de efeitos de arrasto do espaço-tempo que irá influenciar diretamente na mudança de fase na funçãao de onda da partícula neutra. Em seguida, usamos nosso estudo de fases geométricas para fazer aplicações na Computação Quântica Holonômica onde mostramos uma nova maneira de implementar a Computação Quântica Holonômica através da interação entre momentos de dipolo e campos externos e pela presença de defeitos topológicos lineares. Outra aplicação para a Computação Quântica Holonômica está baseada na estrutura de defeitos topológicos em um material chamado grafeno. Na presença de defeitos topológicos lineares, esse material apresenta duas fases quânticas de origens distintas: uma da mistura dos pontos de Fermi e outra da topologia do defeito. Para dar uma descrição geométrica para a origem de cada fase no grafeno usamos a Teoria de Kaluza-Klein, onde a dimensão extra sugerida por esta teoria descreve os pontos de Fermi no grafeno. Portanto, a implementação da Computação Quântica Holonômica no grafeno está baseada na possibilidade de construir cones e anticones de grafite de tal maneira que se possa controlar os fluxos quânticos no grafeno. Na última parte deste trabalho estudamos a quantização de Landau para partículas neutras tanto na dinâmica não-relativística quanto na dinâmica relativística. Na dinâmica não-relativítica, estudamos a quantização de Landau na presença de defeitos em um referecial inercial e, em seguida, em um referencial nãoo-inercial. Na dinâmica relativística, estudamos inicialmente a quantização de Landau no espaço-tempo plano em duas configurações de campos diferentes. Por fim, estudamos a quantização de Landau relativística para partículas neutras no espaço-tempo da deslocação cósmica.